Selected applications of integer programming : a computational study

Abstract

Wij beschouwen het oplossen van wiskundige optimaliseringsproblemen met be- hulp van een computer. Voor elk gegeven probleem omvat dit het opstellen van een wiskundig model voor het probleem in kwestie, het ontwerpen van een op- lossingsmethode die gebaseerd is op dit model, en het implementeren en testen van de ontworpen oplossingsmethode. De volgende problemen komen in dit proefschrift aan de orde: (i) Het plaatsen van zoveel mogelijk plaatsnamen op een kaart onder de voor- waarden dat iedere naam geplaatst wordt bij de plaats waar hij bij hoort en dat namen elkaar niet mogen overlappen. Dit probleem is bekend als het map labelling probleem. (ii) Het bepalen van eciente routes voor een koopman die met een bestel- bus door het land reist en geld verdient door winst te maken met in- en verkoop van goederen. Het probleem is, gegeven de prijzen van de goe- deren in iedere plaats en de kosten van het rijden met de bestelbus, om een optimale dagtrip langs een deelverzameling van de plaatsen uit te re- kenen, samen met de bijbehorende in- en verkoop strategie. Hierbij mag de capaciteit van de bestelbus op geen enkel moment gedurende de trip overschreden worden. Dit probleem heet het merchant subtour probleem, en een oplossing voor dit probleem noemen wij een merchant subtour. (iii) Het routeren van een collectie vrachtwagens, die gestationeerd zijn op ver- schillende depots, en waarin we een verzameling klanten hebben met een vraag naar verschillende soorten goederen. Ieder goed heeft een vaste af- zender en een vaste bestemming en moet in een geheeltallige hoeveelheid vervoerd worden. De afzender en bestemming zijn deel van de klantenver- zameling. Voor het vervoer mogen goederen in geheeltallige hoeveelheden gesplitst worden. Het probleem is, gegeven de kosten van het rijden, om een zodanige routering van de vrachtwagens te vinden plus een laad- en losschema dat aan de vraag wordt voldaan en de totale kosten zo laag mogelijk zijn. Hierbij mag de capaciteit van de vrachtwagens op geen en- kel moment overschreden worden. Omdat dit probleem voorkomt bij Van Gend & Loos bv noemen wij dit het Van Gend & Loos probleem. Ditpro- bleem, alsmede de probleemgegevens die de situatie beschrijven zoals die 153?154 SAMENVATTING bij Van Gend & Loos voorkomt, werden verkregen van Ortec Consultants bv, te Gouda. De hierboven genoemde problemen laten zich modelleren als geheeltallige lineaire programmeringsproblemen. In dit proefschrift beschrijven wij goed ge- denieerde rekenmethoden, ook wel algoritmen genoemd, om met een computer oplossingen voor de genoemde problemen te vinden. De basis voor onze algorit- men wordt gevormd door de zogenaamde lineaire programmering in combinatie met het branch-and-bound algoritme. De combinatie van lineaire programmering en branch-and-bound is bekend als LP-gebaseerde branch-and-bound. Verdere verjningen van LP-gebaseerde branch-and-bound zijn bekend als branch-and- price, branch-and-cut en branch-price-and-cut. In een branch-and-cut algoritme wordt het wiskundige model aangesterkt door zogenaamde geldige ongelijkheden. Wij maken in onze berekeningen ge- bruik van mod-k cuts, een klasse van algemene geldige ongelijkheden die bekend is uit de vakliteratuur [22, 23, 24]. Daarnaast maken wij gebruik van meer probleemspecieke geldige ongelijkheden. Het map labelling probleem laat zich formuleren in termen van een klas- siek optimaliseringsprobleem, namelijk het maximum independent set probleem. Voor het maximum independent set probleem hebben wij een branch-and-cut algoritme ontwikkeld, alsmede verschillende LP-gebaseerde heuristieken die wer- ken door fractionele oplossingen af te ronden. Om een sterke formulering van het probleem te hebben maken wij gebruik van verschillende klassen van geldige ongelijkheden die bekend zijn uit de vakliteratuur. Onze experimenten tonen aan dat op middelgrote problemen van probleemklassen, die in de vakliteratuur gebruikt worden om algoritmiek voor independent set problemen te testen, ons algoritme in staat om binnen redelijke tijd optimale oplossingen te vinden. Interessanter zijn de prestaties van ons branch-and-cut algoritme voor het maximum independent set probleem op independent set problemen die verkre- gen zijn door het herformuleren van map labelling problemen. Map labelling problemen tot 950 steden kunnen wij binnen redelijke tijd optimaal oplossen. Wij zijn er als eerste in geslaagd om map labelling problemen van deze grootte optimaal op te lossen. Daarnaast tonen wij aan dat onze LP-gebaseerde heu- ristieken optimale of bijna optimale oplossingen geven voor independent set problemen die verkregen zijn door het herformuleren van map labelling proble- men. Voor het merchant subtour probleem hebben wij een branch-price-and-cut algoritme ontwikkeld, alsmede een zogenaamde tabu search heuristiek. Ons model voor het merchant subtour probleem is een uitbreiding van het model voor het zogenaamde price-col lecting travel ling salesman probleem [9, 10]. De correctheid van ons model volgt uit het feit dat een speciaal geval van het model beschreven kan worden met een stelsel ongelijkheden dat een mooie wiskundige eigenschap bezit die bekend is als totale unimodulariteit. Wij maken gebruik van verschillende geldige ongelijkheden die afkomstig zijn uit het price-collecting travelling salesman probleem. Ons branch-price-and-cut algoritme is in staat om binnen redelijke tijd problemen tot 22 steden optimaal op te lossen. Op deze?155 klasse problemen vind onze tabu search heuristiek oplossingen die gemiddeld minder dan 3% in waarde afwijken van de optimale oplossingen. Voor het Van Gend & Loos probleem ontwikkelen wij een branch-and-price algoritme, en een hiervan afgeleide afrondheuristiek. Het branch-and-price algo- ritme is gebaseerd op een decompositiemethode die bekend is als Dantzig-Wolfe decompositie. Door deze methode toe te passen op het Van Gend & Loos pro- bleem is het probleem te vertalen naar deelproblemen voor ieder depot die te interpreteren zijn als merchant subtour problemen en een hoofdprobleem die de resultaten van de deelproblemen combineert. Bij dit combineren worden uit de door de deelproblemen berekende merchant subtours diegene gekozen die ge- bruikt gaan worden in de oplossing van het Van Gend & Loos probleem. Wij laten door middel van computationele experimenten zien dat onze afrondheu- ristiek in staat is om op middelgrote problemen oplossingen te vinden die een gemiddelde waarde hebben binnen 60% van onze beste ondergenzen.