Eﬃcient Algorithms for Graph Optimization Problems

Kovács, Péter

Eﬃcient Algorithms for Graph Optimization Problems

Subject: Műszaki tudományok/Informatikai tudományok
graph
network
algorithm
optimization
efficient algorithms
optimization problems
combinatorial optimization
heuristics
implementation
minimum-cost flow
network flow
network simplex
maximum common subgraph
cheminformatics
molecular graph
Informatika D. I./Az informatika alapjai és módszerei.
gráf
hálózat
algoritmus
optimalizálás
hatékony algoritmusok
optimalizálási feladatok
kombinatorikus optimalizálás
heurisztikák
implementáció
minimális költségű folyam
hálózati folyam
hálózati szimplex
legnagyobb közös részgráf
kémiai informatika
molekulagráf

URI: http://hdl.handle.net/10831/44497

Link to Library Catalogue: http://opac.elte.hu/F?func=direct&doc_number=984179

MTMT: 30938140

DOI: 10.15476/ELTE.2019.029

Abstract:

A doktori értekezés hatékony algoritmusokat mutat be gráfokon értelmezett nehéz kombinatorikus optimalizálási feladatok megoldására. A kutatás legfontosabb eredményét különböző megoldási módszerekhez kidolgozott javítások jelentik, amelyek magukban foglalnak új heurisztikákat, valamint gráfok és fák speciális reprezentációit is. Az elvégzett elemzések igazolták, hogy a szerző által adott leghatékonyabb algoritmusok az esetek többségében gyorsabbak, illetve jobb eredményeket adnak, mint más elérhető implementációk. A dolgozat első fele hét különböző algoritmust és számos hasznos javítást mutat be a minimális költségű folyam feladatra, amely a legtöbbet vizsgált és alkalmazott gráfoptimalizálási problémák egyike. Az implementációinkat egy átfogó tapasztalati elemzés keretében összehasonlítottuk nyolc másik megoldóprogrammal, köztük a leggyakrabban használt és legelismertebb implementációkkal. A hálózati szimplex algoritmusunk lényegesen hatékonyabbnak és robusztusabbnak bizonyult, mint a módszer más implementációi, továbbá a legtöbb tesztadaton ez az algoritmus a leggyorsabb. A bemutatott költségskálázó algoritmus szintén rendkívül hatékony; nagy méretű ritka gráfokon felülmúlja a hálózati szimplex implementációkat. Az értekezésben tárgyalt másik optimalizálási feladat a legnagyobb közös részgráf probléma. Ezt a feladatot kémiai alkalmazások szempontjából vizsgáltuk. Hatékony heurisztikákat dolgoztunk ki, amelyek jelentősen javítják két megoldási módszer pontosságát és sebességét, valamint kémiailag relevánsabb módon rendelik egymáshoz molekulagráfok atomjait és kötéseit. Az algoritmusainkat összehasonlítottuk két ismert megoldóprogrammal, amelyeknél lényegesen jobb eredményeket sikerült elérnünk. A kifejlesztett implementációk bekerültek a ChemAxon Kft. több szoftvertermékébe, melyek vezető nemzetközi gyógyszercégek használatában állnak. Ezen kívül az értekezés röviden bemutatja a LEMON nevű nyílt forrású C++ gráfoptimalizációs programkönyvtárat, amely magában foglalja a minimális költségű folyam feladatra adott algoritmusokat. Ezek az implementációk nagy mértékben hozzájárultak a programcsomag népszerűségének növekedéséhez.

Abstract:

This thesis presents efficient algorithms for solving complex combinatorial optimization problems related to graphs. The main contribution of this work is the development of various improvements for different solution methods, including novel heuristics and special representations of graph and tree structures. Extensive experimental studies have verified that the most efficient algorithms of the author are usually faster or yield better results than other available implementations. The first part of the thesis presents seven different algorithms and several practical improvements for solving the minimum-cost flow problem, which is a fundamental graph optimization task with diverse applications in various fields. A comprehensive computational study was carried out to compare these algorithms with eight other solvers, including the most widely used and acknowledged ones. The network simplex code of the author turned out to be significantly more efficient and robust than the other implementations of this method. Furthermore, it is the fastest algorithm on the majority of the problem instances. The presented cost-scaling implementation is also highly efficient; it outperforms the network simplex methods on large sparse networks. The other problem of primary focus in the thesis is the maximum common subgraph problem, which we study in the context of cheminformatics. We developed several heuristics for improving the accuracy and efficiency of two solution methods, as well as for achieving chemically more relevant mapping of the atoms and bonds of the input molecular graphs. The presented algorithms were compared with two other solvers, to which they turned out to be superior. The developed methods have been integrated into multiple software products of ChemAxon, which are used by leading international companies in the pharmaceutical industry. Furthermore, the thesis briefly introduces the open-source C++ graph optimization library called LEMON, which includes the presented minimum-cost flow algorithms. These implementations have played an important role in the increasing popularity of the library.

Show full item record