< Terug naar vorige pagina

Project

Combinatorische optimalisatie problemen met conflicten of vectoren

In deze thesis getiteld, combinatorial optimization problem with conflicts or vectors, introduceren we drie combinatorische optimalisatie problemen en onderzoeken we voor ieder probleem of er efficiënte algoritmes bestaan om het probleem (sub-)optimaal op te lossen.

Als eerste probleem beschouwen[SF1] [AF2]  we Balanced Optimization with vector costs, vertaald: gebalanceerde optimalisatie met vector kosten. Een instantie van zo’n probleem bestaat uit een basis verzameling X, een kost vector voor iedere element uit X en een verzameling toegestane deelverzamelingen van X. Het doel is om een toegestane deelverzameling te vinden die het maximale verschil over de vector-coördinaten minimaliseert. Gebalanceerde optimalisatie met vector kosten is equivalent met robuuste gebalanceerde optimalisatie problemen. We beschouwen deze problemen als een familie van problemen; een specifiek lid van de familie is het bekende gebalanceerde toewijzingsprobleem[SF3]  met vector kosten. We introduceren twee algoritmes die toepasbaar zijn op ieder robuuste gebalanceerde[SF4] [SF5]  optimalisatie probleem. En we identificeren een grote familie van problemen waarvoor er een 2-approximatie algoritme bestaat en tonen aan dat dit het best mogelijk is (tenzij P=NP).

Ten tweede bekijken we het Transport Probleem met conflicten. Het klassieke Transport Probleem is een fundamenteel probleem in Operationeel Onderzoek, waarin items vervoerd moeten worden van een depot (met een gegeven aanbod) naar een locatie (met een gegeven vraag) op de goedkoopste manier. Wij zijn geïnteresseerd in een generalisatie van het Transport Probleem waarbij ieder depot een (mogelijk lege) conflict verzameling heeft bestaande uit conflicterende tweetallen van locaties, en iedere locatie een (mogelijk lege) conflict verzameling heeft bestaande uit conflicterende tweetallen van depots. Ieder depot mag items sturen naar slechts een van de twee locaties die in conflict zijn met elkaar. Insgelijks mag een locatie items ontvangen van slechts een van de twee depots dit in conflict zijn. Het resulterende probleem noemen we het Transport Probleem met Conflicten (TPC). We tonen aan dat de complexiteit van TPC afhangt van de structuur van een zogeheten conflict graaf die bepaald wordt door de conflicterende tweetallen. Concreter, we tonen aan dat voor veel graaf klassen het bijbehorende TPC NP-moeilijk blijft, en voor enkele speciale gevallen beschrijven we een approximatie algoritme met een constante factor.

Als laatste bekijken we het partitioneren van vectoren in zogeheten quads. In dit probleem zijn 4n vectoren gegeven die gepartitioneerd moeten worden in groepen van vier. Een groep van vier vectoren noemen we een quad, en de kosten van een quad is gelijk aan de som van de maxima over de componenten van de vier vectoren in de quad. Het probleem is om de gegeven 4n vectoren te partitioneren in n quads van minimale totale kosten. We presenteren een 3/2-approximatie algoritme voor dit probleem en analyseren de resultaten van de algoritme voor enkele speciale gevallen[SF6] . In het meest speciale geval, beschouwen we unieke binaire vectoren die precies twee enen bevatten zijn en dat de graaf opgesteld uit die vectoren een verbonden graaf is. Voor dit speciale geval bewijzen we dat het een NP-moeilijk probleem is en dat het algoritme een 5/4-approximatie algoritme is.

Datum:1 okt 2013 →  13 jun 2018
Trefwoorden:Combinatorial Optimization
Disciplines:Toegepaste economie, Economische geschiedenis, Macro-economie en monetaire economie, Micro-economie, Toerisme
Project type:PhD project