Robusna diskretna optimizacija

master's thesis

• Title (english): Robust discrete optimization
• Author: Dario Bogović
• Mentor: Robert Manger (mentor)
• Committee member: Robert Manger (predsjednik povjerenstva)
• Committee member: Marko Radulović (član povjerenstva)
• Committee member: Marko Horvat (član povjerenstva)
• Committee member: Vedran Krčadinac (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2023-03-03, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom radu opisane su vremenske složenosti nekih robusnih diskretnih problema optimizacije. Nakon navođenja osnovnih pojmova, problema i definicija ispituju se robusne varijante problema najkraćeg puta, najmanjeg razapinjućeg stabla i pakiranja naprtnjače. Uvode se pojmovi klasa P i NP te P-teških i NP-teških problema. Proučavaju se navedeni problemi s određenim ograničenjima u usporedbi sa svojim konvencionalnim varijantama. Definira se slojevita mreža i pokazuje se da su apsolutni i devijacijski robusni problemi najkraćeg puta slabo NP-teški čak i u slojevitim mrežama širine dva i sa samo dva scenarija. Nakon dokazivanja tih tvrdnji dani su i algoritmi koji rješavaju probleme na slojevitim mrežama u pseudo-polinomnom vremenu. Problemi su jako NP-teški kada broj scenarija nije ograničen. Nakon što su te tvrdnje dokazane, u slijede ćem poglavlju se uvodi pojam rešetkastog grafa. Dokazuje se je apsolutni problem najmanjeg razapinjućeg stabla slabo NP-težak na poprilično restringiranom rešetkastom grafu sa samo dva scenarija. Dan je algoritam koji rješava problem na rešetkastom grafu u pseudo-polinomnom vremenu. Zatim se dokazuje da je apsolutni problem najmanjeg razapinju ćeg stabla jako NP-težak kada je broj scenarija neograničen. Nadalje, dokazuje se da je apsolutni robusni problem naprtnjače jako NP-težak na neograničenom broju scenarija i dan je pripadajući algoritam. Zadnje poglavlje sadrži konkretnu implementaciju algoritma koji rješava apsolutni robusni problem najkraćeg puta u jeziku Ruby s pripadajućim primjerima.

Abstract (english)

In this paper, the time complexities of some robust discrete optimization problems are described. After stating the basic concepts, problems and definitions, robust variants of the shortest path, smallest spanning tree and knapsack packing problems are examined. The concepts of classes P and NP as well as P-hard and NP-hard problems are introduced. The aforementioned problems are studied with certain limitations compared to their conventional variants. A layered network is defined and it is shown that the absolute robust and robust deviation shortest path problems are weakly NP-hard even in layered networks of width two and with only two scenarios. After proving these statements, algorithms for the layered network problem for each are given. These problems are strongly NP-hard when the number of scenarios is not limited. After these claims have been proven, the next chapter introduces the concept of a grid graph. The absolute minimum spanning tree problem is proven to be weakly NP-hard on a fairly restricted grid graph with only two scenarios. An algorithm is given that solves the problem in pseudo-polynomial time for a grid graph and a bounded number of scenarios. Then it is proven that the absolute minimum spanning tree problem is strongly NP-hard when the number of scenarios is unbounded. The second to last chapter proves that the absolute robust knapsack problem is strongly NP-hard on an unlimited number of scenarios and the corresponding algorithm is given. The last chapter contains a concrete implementation of an algorithm that solves the absolute robust shortest path problem in the Ruby programming language with associated examples.

• Keywords: problem najkraćeg puta; najmanje razapinjuće stablo; pakiranje naprtnjače; slojevita mreža; pseudo-polinomno vrijeme
• Keywords (english): shortest path; smallest spanning tree; knapsack packing problems; layered network; pseudo-polynomial time
• Language: croatian
• URN:NBN: urn:nbn:hr:217:775562
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2023-03-23 12:43:44