Optimalisering en complexiteit

Website:website met extra informatie
Vakcode:INFOOPT
Studiepunten:7.5 ECTS
Periode:periode 3 (week 6 t/m 16, dwz 4-2-2008 t/m 18-4-2008; herkansing week 22)
Timeslot:A
Deelnemers:tot nu toe 22 inschrijvingen
Rooster:Dit is een oud rooster!
vormgroeptijdweekzaaldocent
college   ma 09-116-11.14,15 BBL-416 Han Hoogeveen
 
wo 09-116-11,13-15 BBL-416
practicum          Rooij
Bart Jansen
   
werkcollege   ma 11-136-11.14,15 BBL-416 Han Hoogeveen
Bart Jansen
  
wo 11-136-11.13-15 BBL-416
Inhoud:Na het inleidende college over local search op maandagochtend is er van 11.00 - 12.45 geen werkcollege, maar een gewoon hoorcollege. Hierbij wordt de grote opdracht uitgelegd. De colleges in de week van 10-15 februari vallen uit.

Bij dit vak draait het om modelleren en optimaliseren. In allerlei (productie)situaties spelen optimaliseringsproblemen een rol, waarbij niet alleen een oplossing moet worden gevonden, maar bij voorkeur zelfs de beste. Voorbeelden hiervan zijn dieetproblemen, mengproblemen, maar ook het zogenaamde glassnijprobleem, waarbij uit zo min mogelijk glasplaten van standaard formaat (6.00 x 3.21) de bestelde ruiten (van willekeurige afmetingen) moeten worden gesneden.

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 grote lijnen zal het college er als volgt uit gaan zien

  • Behandeling van de techniek van local search. 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 het bepalen van een zo goed mogelijk cyclisch dienstroosters voor de chauffeurs van Connexxion. Gegeven zijn een aantal (zeg n) chauffeurs, die met z'n allen een gegeven verzameling diensten moeten verzorgen. Jullie moeten een schema opstellen dat bestaat uit n weekroosters, met een ordening erbij. De weekroosters rouleren onder de chauffeurs; na afloop van de week krijgt een chauffeur het volgende weekrooster op de lijst. Het doel is zoveel mogelijk de wensen van de chauffeurs te honoreren, waarbij je natuurlijk moet voldoen aan de CAO-eisen (en iedere dienst moet worden bezet). Voor deze opdracht wordt een echte praktijkinstantie gebruikt: `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. Dit wordt geillustreerd met een praktijktoepassing: afstudeeronderzoek `Online capacity planning of repairs'.
  • 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.
Literatuur:M.S. Bazaraa, J.J. Jarvis, H.D. Sherali (1990). Linear programming and network flows. Wiley, New York. ISBN: 0-471-48599-3, of 0-471-51284-2 of 0-471-63681-9.

Dit is hetzelfde boek als vorig jaar (er is nu een nieuwe editie van verschenen; ik weet niet wat er allemaal is veranderd). 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); het hangt dus van je manier van studeren af of het verstandig is om het boek aan te schaffen. 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.

Werkvorm:Hoorcollege en Werkcollege. Voorafgaand aan het college wordt een samenvatting op het web gezet; deze kun je afdrukken en van te voren doorlezen. De opgaven voor het werkcollege komen voor aanvang op het web te staan; die moeten jullie zelf uitdraaien. Tijdens het werkcollege worden enkele uitwerkingen uitgedeeld zodat je je antwoorden kunt checken. Na afloop komen de uitwerkingen op het web te staan.

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).
De student-assistenten voor het werkcollege zijn nog niet bekend.

Toetsvorm:Tentamen plus practicumopgave. Tentamen telt voor 60%; de modelleeropgave telt voor 10%; het local search practicum voor 30%. Op beide opdrachten moet minstens een 6.0 worden gescoord; op het tentamen moet minstens een 5.0 worden gescoord. In verband met de BaMa wordt de houdbaarheid van de deelresultaten beperkt; wie al een onderdeel heeft gehaald wordt verzocht dit jaar toch vooral de resterende onderdelen van het vak te gaan halen. Voorlopig wordt er nog redelijk soepel omgegaan met de houdbaarheid van deelresultaten.
Tussentijds worden er twee maal huiswerkopgaven opgegeven, waarbij je kunt nagaan hoe je er voorstaat (al spreekt de mate waarin je zelf de werkcollege-opgaven kunt maken natuurlijk boekdelen). Deze opgaven kun je (hoeft niet) inleveren, waarna ze worden nagekeken. Er zijn geen consequenties verbonden aan het niet inleveren/niet voldoende maken.
Inspanningsverplichting voor aanvullende toets:Om aan de aanvullende toets te mogen meedoen moet de oorspronkelijke uitslag minstens 4 zijn indien je het tentamenwerk hebt ingeleverd. Wie ten tijde van het tentamen ziek/zwak/misselijk is (of denkt dat hij nodig op vakantie moet) of vanwege het zich ziek/zwak/misselijk voelen tijdens het tentamen niet in staat is om het werk in te leveren mag ook aan de herkansing deelnemen.
Beschrijving:Dit is een vak uit de `algoritmiek' hoek, waarbij het er niet omgaat om een algoritme zo snel mogelijk te maken (al kun je je daar wel op uitleven bij de practicumopdracht); de nadruk ligt hier op het bedenken van een goed algoritme. Om een concreet voorbeeld te nemen: stel dat je een rij getallen moet sorteren op grootte. Een simpel algoritme (uit de steentijd) zou zijn het omwisselen van twee naast elkaar staande getallen die niet in de goede volgorde staan. Dit duurt lang, maar met een beetje handigheid in software engineering kun je het enorm versnellen, zodat je in het tijdperk van de Flintstones komt: het leven is comfortabel, maar het blijft de steentijd. De volgende stap voorwaarts is het vinden van een goed algoritme, zoals Quicksort; je kunt stellen dat je met een beetje normale implementatie dan al in de 20ste eeuw bent beland. Tot slot kun je natuurlijk nog het algoritme versnellen door een goede implementatie te kiezen, zodat je uiteindelijk in de 21ste eeuw terecht bent gekomen. Uiteraard kun je erover twisten wat nu belangrijker is: implementatie of algoritme, maar de top wordt geleverd door van beide het beste te kiezen.

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.

wijzigen?