Optimalisering en complexiteit

De hoofdmoot van het vak wordt gevormd door lineaire programmering. Verder wordt nog behandeld hoe je geheeltallige lineaire programmeringsproblemen op kunt lossen en er wordt kort behandeld hoe de techniek van `local search' werkt. In vergelijking met vorig jaar is het onderdeel `complexiteitstheorie' vervangen door `geheeltallige lineaire programmering' (dit is uitgewisseld met het vak Algoritmiek). In grote lijnen zal het college er als volgt uit gaan zien

• Behandeling van de techniek van local search met een overzicht van hoe local search kan worden gebruikt om het `vehicle routing problem' op te lossen (wat werkt er wel in de praktijk, en wat werkt er niet). Bij het vehicle routing probleem heb je een aantal klanten die uit een depot beleverd moeten worden. Hiervoor heb je een aantal vrachtwagens beschikbaar met een gegeven capaciteit. Het doel is het vinden van een toegelaten oplossing (je neemt niet meer mee dan in de vrachtauto past, de chauffeurs hoeven niet te lang te werken, enz.) met minimale kosten (meestal gemeten in aantal gereden kilometers). Een voorbeeld hiervan is het `pizza-bezorg probleem', waarbij je dan ook nog de extra beperking hebt dat de klanten ongeduldig zijn. Een van de twee opdrachten die jullie krijgen (dit is de grootste van de twee) betreft het vinden van een zo goed mogelijke oplossing voor een instantie van een vehicle routing probleem met een paar zijvoorwaarden dat uit de praktijk komt; `match your skills with the masters'.
• Inleiding Lineaire Algebra (vooral het rekenen met matrices). Hierna is een ieder die geen Lineaire Algebra heeft gehad voldoende voorbereid op hetgeen er gaat komen; het is dus niet nodig om Lineaire Algebra dan wel Graphics nieuwe stijl gevolgd te hebben.
• Formuleren van een probleem als een (geheeltallig) lineair programmeringsprobleem, zodat je het door een solver (zoals CPLEX) op kunt laten lossen. Hier krijgen jullie een opdracht over.
• Behandeling van een simpele versie van het Simplex algoritme, dat wordt gebruikt om lineaire programmeringsproblemen op te lossen.
• Dualiteit en gevoeligheidsanalyse. Hierbij gaat het erom dat je een indruk krijgt hoe de oplossing van een probleem gaat veranderen wanneer je het probleem enigszins verandert, zonder natuurlijk het aangepaste probleem weer van `scratch' op te hoeven lossen.
• Twee efficientere implementaties van de simplex methode en de methode van kolomgeneratie.
• Het oplossen van geheeltallige lineaire programmeringsproblemen met behulp van branch-and-bound.
• Twee praktijktoepassingen: het `gate-assignment' probleem en het `seriegrootte' probleem. Het eerste probleem speelt op Schiphol: de binnenkomende en vertrekkende vliegtuigen hebben een gate nodig; de vraag is natuurlijk welke. Een probleem hierbij is dat de werkelijke aankomst- en vertrektijden van vliegtuigen vaak een beetje van de planning afwijken, en je wilt dan natuurlijk zo min mogelijk aan je huidige oplossing veranderen. Het tweede probleem komt van Grolsch, en het gaat hier om de vraag hoeveel je van een bepaald product moet produceren en wanneer, zodat je uit voorraad kunt leveren zonder dat de voorraden uit het magazijn puilen.

Dit is hetzelfde boek als vorig jaar. Het wordt hoofdzakelijk als naslagwerk gebruikt. Het is daarom niet verplicht om het aan te schaffen, hoewel het door de vele voorbeelden erin wel een nuttig boek is. Indien gewenst kun je het vak volgen zonder boek (zie ook de evaluatie-enquetes). Aangezien het boek de afgelopen tijd schandalig in prijs verhoogd is raad ik aan het boek van iemand te lenen/kopen/... (de stippeltjes staan voor een illegale optie die ik niet letterlijk wil noemen). Wie het toch nieuw wil kopen raad ik aan om even op het web rond te kijken.

Het bezoek aan het werkcollege is niet verplicht; ik ga uit van de eigen verantwoordelijkheid van de studenten; de studenten die er de voorkeur aan geven om de opgaven niet eerst zelf te maken maar gelijk de uitwerkingen erbij pakken zie ik meestal het jaar erna terug (tenzij ze de moed op hebben gegeven). Trots kan ik vermelden dat volgens de evaluatie-enquetes Optimalisering het eerste vak is waarvan terecht door de docent wordt gezegd dat het bezoek aan het werkcollege noodzakelijk is om het tentamen te halen (voor de doorsnee student).
Tot slot kan ik nog vermelden dat we erin zijn geslaagd om Chaim en Eelko, die vorig jaar ook hebben geassisteerd en waarover zoveel lof werd uitgestrooid in de evaluatie-enquetes, opnieuw te contracteren voor het werkcollege; zij worden hierbij geassisteerd door de onvolprezen nieuwe kracht Niels Reijngoud.

De vakken Algoritmiek en Optimalisering vormen beide een vervolg op het vak Datastructuren. Het verschil zit in de algoritmen die bij deze beide vakken worden behandeld. Beide vakken kunnen onafhankelijk van elkaar worden gevolgd. Zie ook de website van het vak Algoritmiek.