Efficient algorithms for solving robust variants of network flow problems

Cilj doktorskog rada je proučavanje nekoliko novih robusnih varijanti problema toka u mreži koje razlikujemo po obliku polaznog problema (maksimalni tok ili maksimalni tok minimalne cijene) te po nekim osobinama (načinu izražavanja neizvjesnosti u parametrima, stupnju neodređenosti u parametrima ili načinu mjerenja ponašanja zadanog rješenja za zadani scenarij). Za svaku robusnu varijantu cilj je analiziranje njezinih bitnih svojstava, naprimjer računske složenosti, te implementiranje barem jednog efikasnog algoritma koji je u stanju rješavati relativno velike primjerke problema u razumnom vremenu. U prvom poglavlju formuliramo problem optimizacije pri čemu se i u funkciji cilja i u ograničenjima pojavljuju parametri koje obično ne možemo točno odrediti pa govorimo o neizvjesnosti ili nesigurnosti kod rješavanja problema optimizacije. Promatramo mane stohastičkog pristupa rješavanju problema neizvjesnosti te predlažemo robusni pristup kao alternativu stohastici. U drugom poglavlju formuliramo robusne probleme toka te dokazujemo da su (poopćene) apsolutno i devijantno robusne varijante problema toka minimalne cijene po složenosti NP-teške. Osim problema toka minimalne cijene, u standardnoj literaturi također se proučava problem maksimalnog toka, ali pokazujemo da nema smisla razmatrati njegove robusne varijante jer su trivijalne. U trećem poglavlju definiramo rezidualnu mrežu koju koristimo za traženje maksimalnog toka i maksimalnog toka minimalne cijene u polaznoj mreži, odnosno slojevitu rezidualnu mrežu koju koristimo za traženje maksimalnog toka u polaznoj mreži. Definiramo pojmove poput puta uvećavajućeg toka ili ciklusa smanjujuće cijene. Predstavljamo osnovne operacije s tokovima koje upotrebljavamo kao sastavne metode u (meta)heuristikama te analiziramo njihovu složenost. U četvrtom poglavlju formuliramo (poopćeni) robusni problem toka minimalne cijene kao problem cjelobrojnog linearnog programiranja koji općenito rješavamo egzaktnim algoritmima za cjelobrojno linearno programiranje, pomoću grananja i ograđivanja ili ravnine odsjecanja. U petom poglavlju predstavljamo (meta)heuristke kao skup metoda optimizacije koje pružaju "prihvatljiva" rješenja u "razumnom" vremenu pri rješavanju teških i složenih problema u znanosti i inženjerstvu. Kako su robusne varijante problema toka minimalne cijene NP-teške, to ih ima smisla rješavati (meta)heuristikama, npr. lokalnim traženjem. Opisujemo njihovu implementaciju pa analiziramo njihovu složenost. U zadnjem poglavlju odabiremo reprezentativne i realistične te razmjerno velike primjerke problema pa eksperimentalnom evaluacijom (meta)heuristika za rješavanje robusnih problema toka na takvim primjercima za svaku od razmatranih robusnih varijanti, mjerimo njihovu preciznost i vrijeme izvršenja pa obrađujemo i uspoređujemo rezultate evaluacija te iznosimo prednosti i nedostatke. U prvom dodatku formuliramo srodne robusne probleme linearnog programiranja, najkraćeg puta, minimalnog razapinjućeg stabla i 0/1 naprtnjače te dokazujemo da su po složenosti NP-teški. Kako su robusne varijante navedenih problema polinomijalno reducibilne na odgovarajuće robusne varijante problema toka minimalne cijene, to će bilo koji algoritam koji dovoljno efikasno rješava robusni problem toka minimalne cijene, također dovoljno efikasno rješavati navedene srodne robusne probleme. Naprimjer, prema teoremu 2.6, robusne varijante problema najkraćeg puta su polinomijalno reducibilne na odgovarajuće robusne varijante problema toka minimalne cijene. U drugom dodatku standardne probleme u mreži koji se pojavljuju prilikom rješavanja robusnog problema toka minimalne cijene (meta)heuristikama, npr. lokalnim traženjem ili evolucijom, rješavamo klasičnim algoritmima. Te algoritme koristimo kao pomoćne metode. Stoga je bitno da se izvršavaju što efikasnije, tj. da je njihova složenost polinomijalna. Opisujemo implementaciju klasičnih algoritama za rješavanje problema minimalnog reza, maksimalnog toka, najkraćeg puta, negativnog te jednostavnog ciklusa. U zadnjem dodatku se nalazi programski kod konfiguracije aplikacije i klase (rezidualne) mreže.The aim of thesis is to study several new robust variants of network flow problems that differ in the form of initial problem (maximum flow or minimum cost maximum flow) and by some characteristics (in the way how uncertainty in parameters is expressed - in the way how scenarios are given, in the extent of parameter uncertainty or in the way how behavior of a given solution under a given scenario is measured). For each robust variant the aim is to analyze its important properties, for example computational complexity, and to implement at least one efficient algorithm capable of solving relatively large samples in reasonable time. In the first chapter we formulate optimization problem whose instance is described by values of parameters in its objective function and in its constraints that are usually hard to determine, since they depend on possible scenarios, so it is spoken about uncertainty while solving optimization problem. We observe flaws of stochastic approach toward solving problem with uncertainty and recommend robust approach as alternative to stochastic. In the second chapter we formulate robust flow problems and prove that by complexity (general) absolute and deviant robust variants of minimum cost flow problem are NP-hard. Besides minimum cost flow problem, maximum flow problem is also studied in standard literature, but it is shown that it makes no sense to consider its robust variants because they are trivial. In the third chapter we define residual network which is used for searching maximum flow and minimum cost maximum flow in initial network, that is layered residual network which is used for searching maximum flow in initial network. We define terms such as flow augmenting path or cost reducing cycle. We present basic operations with flows which are used as building blocks in (meta)heuristics and analyze their complexity. In the fourth chapter we formulate (general) robust minimum cost flow problem as an integer linear programming problem which is generally solved with exact algorithms for integer linear programming, via branch-and-bound or cutting-plane. In the fifth chapter we present (meta)heuristics as a set of optimization methods that are providing \acceptable" solutions in \reasonable" time upon solving hard and complex problems in science and engineering. As robust variants of minimum cost flow problem are NP-hard, it makes sense to solve them with (meta)heuristics, e.g. by local search. We describe their implementation and analyze their complexity. In the final chapter we choose representative and realistic, and relatively large samples of problem, and by experimental evaluation of (meta)heuristics for solving robust flow problems on such samples for each of considered robust variants, their precision and execution time is measured, and evaluation results are elaborated and compared, and pros and cons are revealed. In the first appendix we formulate related robust problems of linear programming, shortest path, minimum spanning tree and 0/1 knapsack, and prove that by complexity they are NP-hard. As robust variants of mentioned problems are polynomial-time reducible to corresponding robust variants of minimum cost flow problem, any algorithm that efficiently solves robust minimum cost flow problem will also sufficiently efficient solve mentioned related robust problems. For example, according to theorem 2.6, robust variants of shortest path problem are polynomial-time reducible to corresponding robust variants of minimum cost flow problem. In the second appendix standard network problems that appear when solving robust minimum cost flow problem with (meta)heuristics, e.g. by local search or evolution, are solved with classical algorithms. Those algorithms are used as building blocks. Therefore it is important that they are executed as efficiently as possible, i.e. that their complexity is polynomial-time. We describe implementation of classical algorithms for solving problems of minimal cut, maximal flow, shortest path, negative and simple cycle. In the final appendix there is a programming code of application’s configuration and (residual) network class