Imperatieve programmeertalen beschrijven imperatief hoe iets moet worden uitgevoerd. Ze worden gekenmerkt door een opeenvolging van opdrachten. Voorbeelden zijn PHP, JavaScript, C#, …
Declaratief programmeren
Declaratieve programmeren beschrijven eerder wat moet opgelost worden of uitgevoerd worden, niet HOE dat moet worden gedaan. Een simpel voorbeeld is XHTML: deze beschrijft hoe de site is opgebouwd, maar het is de browser zelf die beslist op basis van deze beschrijving hoe de site zal getoond worden. Voor Chrome zal de WebKit engine hierover beslissen.
Constraint programming, AMPL, OPL, … het valt allemaal onder de declaratieve programmeertalen.
Om de kracht van constraint programming aan te duiden, volgt hieronder een simpel voorbeeld van een sudoku solver.
Sudoku
Een sudoku oplossen kan imperatief gedaan worden via een backtracking algoritme. Het vereist relatief veel code voor een relatief makkelijk probleem, maar de execution zal wel snel verlopen, omdat de code specifiek is aangepast voor dit probleem.
Declaratief kunnen we in heel weinig code ook snel een oplossing bekomen. Aangezien OPL (de taal gebruikt binnen CPLEX) een declaratieve taal is, hoeven we enkel de regels uit te leggen, waarna de engine zelf de oplossing zal proberen bepalen. De CP Optimizer zal het brand-and-bound algoritme gebruiken om een oplossing te vinden.
Regels:
Horizontaal moet elke regel 9 verschillende cijfers bevatten [1,9]
Verticaal moet elke regel 9 verschillende cijfers bevatten [1,9]
Elke vierkantje van 3 op 3 moet 9 verschillende cijfers bevatten [1,9]
// Code gemaakt door Arya Ghodsi
using CP; // gebruik de CP-engine
dvar int x[1..9][1..9] in 1..9; // vertical|horizontal
// Volgende code bevat onze eigenlijke constraints:
forall (idx in 1..9)
allDifferent(all (i in 1..9) x[idx][i]) && // horizontaal allDifferent(all (i in 1..9) x[i][idx]) && // verticaal allDifferent(all (i in 1..3, j in 1..3) x[((idx-1) div 3)*3 + i][((idx-1) % 3)*3 + j]); // vierkant
};
De “dvar” noemen we een decision variable. Het matrix van 9 op 9 kan getallen bevatten tussen 1 en 9. We weten de waarden nog niet van de velden hiervan… vandaar de naam “decision”.
De allDifferent-functie specifieert dat elk getal binnen de opgegeven array verschillend moet zijn. Eerst doen we dit horizontaal, dan verticaal, dan voor het vierkant.
Een paar milliseconden na de execution krijgen we een oplossing :) Toch wel een krachtige programmeertaal, vind ik dan!
Dergelijke voorbeelden kunnen hopelijk meer mensen warm maken voor OPL!
Binnen ILOG CPLEX is het mogelijk om twee verschillende engines te gebruiken.
CPLEX-engine: bestemd voor mathematisch programmeren (MP)
CP-engine: bestemd voor constraint programming (CP)
Mathematisch programmeren
Een populair probleem is het Kleuren van grafen. We willen het aantal kleuren minimaliseren die moeten gebruikt worden zodat geen enkele aangrenzende edge dezelfde kleur heeft (#kantkleuring).
Puur mathematisch kunnen we dit als volgt uitdrukken:
Constraint programming
Hetzelfde probleem, via constraint programming:
De 3e regel stelt: voor elke combinatie van edges, zorg ervoor dat hun kleur verschilt. Simpel en logisch. Hetzelfde uitdrukken als MP-probleem is niet bepaald straightforward.
Engines
De CPLEX-engine kan gebruikt worden voor mathematical programming (LP-problemen). De CP Optimizer werkt met dezelfde concepten als mathematical programming (MP): het is evenwel mogelijk om decision variables, objectives, en constraints te specifiëren in beide. Toch zijn er wat verschillen tussen CP models en MP models.
De CP Optimizer is toegespitst op grafentheorie en algoritmische problemen. De CPLEX engine laat toe om mathematische problemen op te lossen. Elke engine gebruikt verschillende methodes om de problemen op te lossen.
Voor ons VRP ben ik ondertussen overgeschakeld op de CP-engine. We hebben enkele constraints die niet langer lineair zijn en de CP-engine vereisen. (Kortelings ben ik begonnen met ons grotendeels mathematisch model om te zetten in een CP model… de tijdswinst is gigantisch.) Binnen CP models kan je veel verder gaan: je kan intervallen gebruiken, uitdrukken dat die intervallen niet mogen overlappen, een aaneenschakeling van intervallen uitdrukken als een sequence. Dit laat toe op een makkelijke manier time scheduling problemen op te lossen (optimale lessenroosters berekenen, busregelingen optimaliseren, …).
In de voorbije weken heb ik heel wat nieuwe dingen geleerd. Vooral veel nieuwe wiskunde dan. Het algoritme waarmee we geconfronteerd worden is geen gemakkelijk.
Een Vehicle Routing Problem
Voor een buitenstaander kan een VRP er makkelijk uitzien: het is een kwestie van gewoon alle combinaties uit te proberen en te zoeken naar het kortste/snelste/goedkoopste pad.
Veronderstel dat we één camion hebben die goederen moet leveren in locatie A,B, en C. We hebben dan 6 oplossingen: ABC,ACB,BAC,BCA,CAB,CBA.
Voor meer locaties stijgt het aantal mogelijke combinaties echter zeer snel:
There are more combinations for our VRP than the number of atoms in the universe— Myself
Of in Maple (dit zal waarschijnlijk een tijdje duren): n -> n!; [seq(n!,n={1 .. 1000})]
Bij ons spelen er echter meer parameters mee: we hebben meerdere camions, we hebben het tijdsschema waarbinnen de levering moet gebeuren, we hebben clients die meerdere keren kunnen bezocht worden… Die condities mag je als extra factor zien die het rekenwerk nog eens gaan bemoeilijken.
Lineair programmeren
Lineair programmeren is een methode voor het oplossen van zogenaamde lineaire programmeringsproblemen (kortweg LP-problemen).
Ziehier een voorbeeld van een LP-probleem (thanks Wikipedia):
Een landbouwer heeft een stuk landbouwgrond, zeg A vierkante kilometer groot. Hij kan er tarwe, gerst of een combinatie van beide op verbouwen. Tarwe brengt per oppervlakte-eenheid een bedrag
op en gerst een bedrag
. Het lijkt lucratief om alleen het gewas met de hoogste opbrengst te gaan verbouwen, maar er zijn beperkingen aan de verbouw vanwege de benodigde kunstmest en insecticide. De benodigde hoeveelheden daarvan per oppervlakte-eenheid zijn voor de beide gewassen verschillend, en wel voor tarwe (
) en voor gerst (
). De landbouwer heeft een beperkte toelaatbare hoeveelheid
F meststof en P insecticide die kunnen worden gebruikt. Als we de oppervlakten die met tarwe en gerst worden beplant aanduiden met respectievelijk en , dan kan de optimale verdeling van het beschikbare oppervlak aan landbouwgrond over de beide gewassen als lineair programmeringsprobleem worden uitgedrukt:
Merk op dat in dit voorbeeld
en . Vanuit kunnen we dus berekenen. Hoe groot is kunnen we een beslissingsvariabele noemen: het is het algoritme die ons gaat vertellen hoe groot zal zijn opdat de winst optimaal is.
Kortweg hebben we:
Eén of meerdere objectieven: maximaliseren van de winst, of minimaliseren van de transportkosten in ons geval.
Eén of meerdere decision variables: variabelen waarvan we de waarde nog niet kennen, en door het algoritme moeten bepaald worden.
Constraints: beperkingen of voorwaarden waar het objectief aan moet voldoen.
Er bestaan verschillende soorten LP-problemen:
ILP of integer linear programming: waarin de decision variables integers zijn.
MILP of mixed-integer linear programming: nite alle dvar’s moeten integers zijn.
Zo bestaan er binnen de optimalisatie ook QP-problemen en andere exotische varianten, maar dat valt buiten de scope van dit bericht.
Dergelijke lineaire problemen kunnen opgelost worden met de simplexmethode (indien ze oplosbaar zijn). Solvers zoals CPLEX zullen brand-and-cut gebruiken voor MILP-problemen.
Ins ons geval kunnen we zeggen dat onze VRP een NP-hard probleem is. NP-hard/NP-complete'ness is eventueel voor de volgende keer. Laten we zeggen dat een heuristiek noodzakelijk is om ons probleem te gaan oplossen.
Solvers
Voor onze simulaties te kunnen uitvoeren, gingen we op zoek naar de juiste software daarvoor (handmatig dit doen is nogal problematisch):
GLPK: GLPK gebruikt MathProg als modellerings-taal. Er is geen GUI voorzien. Er zijn bindings voorzien naar vele andere programmeertalen, maar als analist moet je toch zelf nog eerst op zoek gaan om de puzzelstukjes in elkaar te passen en de simulatie werkende te krijgen. Pluspunt: gratis, open-source. Nadeel: weinig documentatie.
LINGO: Minder courant. Aan de GUI te zien is het duidelijk dat het programma is blijven steken in het Windows 95-tijdperk en sindsdien niet veel aandacht meer heeft gekregen. Betalend, maar trialversie is beschikbaar. Skip.
Xpress-MP: Twee weken na de aanvraag van de academische licentie nog geen antwoord gekregen. Skip.
CPLEX: Wordt onderhouden door IBM en heeft academische licenties beschikbaar. CPLEX gebruikt zijn eigen programmeertaal “OPL”, maar je kan evengoed MathProg scripts hebben en CPLEX gebruiken als solver. CPLEX heeft ook een volwaardige GUI (overduidelijk gebaseerd op Eclipse) en een profiler. Voorkeur.
Gurobi: Een tool die een volwaardig alternatief lijkt voor CPLEX. Vele benchmarks doen uitschijnen dat Gurobi sneller is voor veel LP/MIP/MIQP-problemen. Gurobi biedt ook acadamische licenties aan. Voorkeur.
We hebben besloten voor CPLEX te gaan aangezien er iemand was binnen de afdeling die er al een goede ervaring mee had gehad. Na enkele problemen gehad te hebben met de licentieaanvraag voor IBM ILOG CPLEX (en meerdere emails met mevrouw Torres van het IBM team), zijn we dan uiteindelijk toch aan een gevalideerde academische licentie geraakt.
Modeling Language
CPLEX heeft haar eigen propriëtair taaltje om lineaire problemen te gaan utdrukken: OPL. Ik heb er toch een dikke week over gedaan om dit onder de knie te krijgen: hoe gegevens inladen, deze manipuleren, constraints uitdrukken, etc…
De taal is krachtig: een tuple is zoals een klasse met verschillende attributen. 3 puntjes volstaan om data in te laden uit een ander bestand. Een “:” is voldoende om je data te gaan filteren.
Hierboven zie je dan weer ons (op dit moment veel te eenvoudig) objectief, dat onderworpen wordt aan constraints.
Up next
Volgende keer een nieuwe post, maar dan over de soorten VRP’s, met SDVRP in het bijzonder, eliminatie van subroutes daarvan, en (meta-)heuristieken die daarmee gepaard gaan.
Deze week hebben we verder gezocht naar constraints, en deze constraints dan ook omgezet in hun wiskundige notatie (dat moet helaas ook gebeuren ت). Om uit te drukken dat onze camion alle klanten moet bezoeken, kunnen we dit vertalen naar de volgende wiskundige constraint:
Dit komt erop neer dat elke klant in verbinding moet staan met exact twee andere klanten op eender welk moment. Of anders gezegd: een camion volgt een bepaalde route, en kan niet naar meer dan één klant tegelijk rijden. (Qua notatie schort er misschien wel wat aan deze vergelijking, maar het onderliggende idee is het belangrijkste.)
Donderdag hebben we onze huidige manuele simulatie voorgetoond aan de andere onderzoekers binnen de afdeling, die weinig opmerkingen hadden (good!). Vrijdag volgde dan een videoconferentie met de professor in Bordeaux die aan het hoofd staat van het onderzoek. Samen met hem overlegden we de verdere stappen die we moeten nemen. De conclusie was dat we vanaf nu aan aan de simulatie kunnen beginnen.
De dagen dat we samenkomen met onze begeleider zijn lange dagen: we beginnen telkens met onze bevindingen te presenteren, waarna we aanpassingen aanbrengen in gezamenlijk overleg. Een bijeenkomst die vaak uitloopt tot acht uur ’s avonds of later. (De conciërge komt dan onze snoep opeten en mee een babbel slaan :).)
Volgende week gaan we op zoek naar optimalisatiesoftware om onze simulaties met uit te voeren! We hebben al enkele tips gekregen (met name CPLEX, GLPK en Xpress-MP). Die ga ik dit weekend al eens installeren of licenties voor aanvragen. We zien dan komende week wel met wat we verder gaan.
We hebben min of meer een consensus bereikt over de werking van het algoritme. Sommige onderdelen zijn echter nog moeilijk om in te schatten.
Ik weet niet hoeveel dergelijke bovenstaande schema’s we deze week hebben gemaakt, maar het wordt tijd om over te gaan op de simulatie… Dit handmatig doen is eerlijk gezegd apenwerk! (The above is actually an animation.)
Weinig nieuws, maar vooral veel verder gewerkt aan de modellen die we reeds hadden. Deze week onderzochten we onder andere hoe een probleem meerdere herconfiguraties gaat triggeren. In principe zouden we moeten starten van een reeds geoptimaliseerde route waarop zich een probleem voordoet, en enkel dan kunnen we betrouwbare resultaten verkrijgen. Dit zal dan hopelijk ook duidelijk worden tijdens de simulatie.
We kwamen deze week ook samen met andere mensen van de onderzoeksafdeling om verdere stappen te overleggen over het eten. Ik ontmoette daarbij ook Esther, die werkt binnen logistics (maar dan weer met heel andere dingen bezig is dan VRP’s).
Volgende week kunnen we hopelijk de analyse afwerken, om de week daarop aan de simulatie te beginnen. Best-case scenario θ(7d) en worst-case binnen θ(14d).
Zoals aangekondigd kwamen we dinsdag opnieuw samen met onze begeleider. Mohamed en ik maakten een presentatie zodat we onze graaf beter konden visualiseren. Donderdag hebben we onze bevindingen ook gepresenteerd voor de directeur van de afdeling. De analyse is nog niet volledig, maar we boeken snel vooruitgang.
Binnenkort mogen we naar Bordeaux om ons algoritme daar te gaan voorstellen aan de universiteit. Het is een transportbedrijf uit Bordeaux dat hen inhuurt, waarop Bordeaux het EIGSI heeft ingehuurd. We zullen dan ook te zien krijgen voor wie we dit onderzoek uiteindelijk leveren ت!
Recap
We willen ervoor zorgen dat wanneer een probleem zich voordoet voor een vrachtwagen, diens vracht (of een deel van de vracht) dynamisch kan geherrouteerd worden opdat ze toch tijdig bij de klant aankomt. De herroutering gebeurt door vrachtwagens met een gelijkaardige route aan te spreken en te kijken of zij nog voldoende capaciteit hebben.
Cas classique - Hoe wordt een probleem op de klassieke manier aangepakt?
Cas dynamique - Hoe we een probleem zouden aanpakken wanneer we gebruik maken van ons dynamisch VRP-algoritme.
We moeten nu gaan bepalen wat de mogelijke scenario’s zijn waarin ons dynamisch VRP-algoritme kan aangewend worden, en wat de kosten en baten zijn tegenover de traditionele aanpak.
Cas classique
Hoe wordt er standaard gereageerd wanneer we te maken krijgen met een probleem? Dit hangt af van de grootte van het probleem: een lekke band kan misschien binnen het vereiste tijdsvenster worden opgelost. Indien er een probleem is met de motor, kan de herstelling misschien meerdere uren duren.
In het klassiek geval treedt er een vertraging op, en moet eventueel een nieuwe vrachtwagen, die vertrekt vanuit het depot, de vracht overnemen.
Een node op deze graaf kan zowel een klant als een laadplatform voorstellen (of een klant waarmee een samenwerkingscontract bestaat).
Cas dynamique
De probleem-ondervindende camion op de rode route is er in geslaagd zijn paletten tot een laadplatform te brengen. In het dynamische geval gaan we gelijkaardige routes analyseren. We zien dat er een zwarte, oranje, en groene route beschikbaar is. Op basis van meerdere parameters kan dan een route uitverkozen worden:
Positie van de camion op de andere route
Tijdschema waar de camion zich aan moet houden
De kost van het pad, van het overladen, …
Dit brengt heel wat denkwerk met zich mee:
Kan een optimalisatie op de ene plaats een probleem doen optreden ergens anders? Laten we dit toe, of leggen we constraints op?
Kunnen we meerdere paden optimaliseren om de globale kost van de graaf te verlagen?
Hoe brengen we deze kosten in kaart, en voeren we “penalties” in voor vertragingen?
Wat gebeurt er wanneer een probleem zich voordoet en de vrachtwagen niet tijdig naar een naburig laadplatform getakeld kan worden: worden er fictieve nodes geïntroduceerd?
Volgende week zitten we opnieuw samen op dinsdag om de bevindingen van onze laatste briefing terug voor te stellen, en de opmerkingen van anderen aan te kaarten.
Deze week kwam ik toe op het EIGSI waar ik mijn stage zal doen bij één van de onderzoeksafdelingen. (EIGSI staat voor École d'Ingénieurs, maar niemand blijkt nog te weten waar de andere letters voor staan.)
Ik ontmoette Mohamed Guedria waar ik samen het project met ga maken. Hij is een 26-jarige Tunesiër die zijn PFE komt maken in La Rochelle (projet de fin d'études). Tezamen trokken we naar Samir Amrioui, de begeleider van ons project. Samir gaf ons een rondleiding doorheen het EIGSI, dat de vorm van een boot blijkt te hebben (…? judge for yourself). Alvast een aangename ontmoeting, die eindigde in een tas capuccino.
Actief intelligent product
Daarna was het business: Samir legde ons uit dat hij bezig was aan een project dat toeliet om een product van capaciteiten te voorzien om te communiceren, beslissingen te nemen, en te reageren op gebeurtenissen van buitenaf om zich op die manier aan te passen aan bepaalde omstandigheden. In de praktijk komt dit neer op het volgende:
Gegeven een transportbedrijf dat meerdere vrachtwagens op de weg heeft. Deze vrachtwagens vervoeren telkens paletten die niet noodzakelijk voor dezelfde klanten bestemd zijn. Wat dient er te gebeuren wanneer een vrachtwagen onderweg een probleem tegenkomt? Stel dat de vrachtwagen door omstandigheden niet meer kan verder rijden, zal de lading te laat bij de klant aankomen. Wij zullen onderzoeken hoe de lading (op niveau van de palet) zo efficiënt mogelijk kan geherrouteerd worden, opdat de paletten binnen het gegeven tijdsvenster bij hun bestemming aankomen. Dit wil zeggen dat vrachtwagens die een gelijkaardige route hebben, een omweg kunnen nemen om bepaalde paletten over te nemen van de vrachtwagen in panne.
Om dit te realiseren zullen we stapsgewijs te werk gaan:
Simulatie, verdere optimalisatie via GPLK / Xpress-MP.
Implementatie, het maken van een mobiele applicatie op Android / iPhone / WP. (I’m kinda looking forward to this step ت)
Ons product wordt gekenmerkt door enkele eigenschappen:
Ex-ante: proactief: mogelijkheid om situaties te berekenen voor ze zich voordoen afhankelijk van de noden van het product.
Realtime: vanaf het moment een probleemsituatie zich voordoet, past het product zich hier aan aan, en worden de omstandigheden geoptimaliseerd.
Ex-post: een eerdere beslissing die tot succes of mislukking leidde, kan worden aangewend om een volgende beslissing te nemen.
(De?)centralisatie
Als eerste stap willen we een eerste niveau van intelligentie bereiken, waarin het product kan communiceren via RFID met bijvoorbeeld de boordcomputer van de vrachtwagen. Indien een probleem zich voordoet, kan de boordcomputer dan communiceren met een centrale server op het depot, waarna het product kan geherrouteerd worden. We spreken van een gecentraliseerde omgeving.
Als tweede stap willen we onderzoeken of het mogelijk is om een tweede niveau van intelligentie te bereiken, zijnde een gedecentraliseerde omgeving, waarin de vrachtwagens onderling communiceren over de herconfiguratie van producten onderling.
Deze week kwamen we twee keer samen met de begeleider om onze bedenkingen en opmerkingen te overleggen. We kregen enkele boeken mee over VRP-problemen (die alvast mijn wiskundeniveau ruimschoots overschrijden), die ik in de komende weken ga doornemen.
Next up: dinsdag zullen Mohamed en ik een presentatie geven over onze bedenkingen en opmerkingen tot nu toe. Ondertussen gaan we tezamen alvast op verkenning door La Rochelle.
