Optimalisering en complexiteit

Website:

website met extra informatie

Vakcode:

INFOOPT

Studiepunten:

7.5 ECTS (=5.25 oude studiepunten)

Periode:

periode 3 (week 6 t/m 16, dwz 2-2-2004 t/m 16-4-2004; herkansing week 21)

Deelnemers:

tot nu toe 103 inschrijvingen

Rooster:

Dit is een oud rooster!

vorm	groep	tijd	week	zaal	docent
college		wo 11-13	6-8,10-15	MIN-208	Han Hoogeveen
college		vr 13-15	6-8,10-12,14	MIN-208	Han Hoogeveen
werkcollege	groep 1	ma 13-15	7-8,10-15	BBL-505	Peter Lennartz
	groep 1	do 11-13	6-8,10-15	BBL-505	Peter Lennartz
	groep 2	di 13-15	7-8,10-15	BBL-505
	groep 2	do 13-15	6-8,10-15	BBL-505
	groep 9	ma 11-13	7-8,10-15	BBL-430	Marjan van den Akker
	groep 9	do 11-13	6-8,10-15	BBL-430	Marjan van den Akker

Inhoud:

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.

Een belangrijk deel van het vak wordt gevormd door lineaire programmering; andere onderdelen zijn `local search' algoritmen en complexiteitstheorie. In grote lijnen zal het college er als volgt uit gaan zien

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 (dit is een verandering ten opzichte van vorig jaar).
Behandeling van een simpele versie van het Simplex algoritme, dat wordt gebruikt om lineaire programmeringsproblemen op te lossen.
Intermezzo: `local search' algoritmen. Locale zoekalgoritmen worden met veel succes ingezet om beroerde praktijkproblemen op te lossen. Bij dit soort algoritmen ga je uit van een huidige oplossing waarop je een kleine verandering toepast. Wanneer dit een betere oplossing oplevert, dan reken je daar mee verder; wanneer de oplossing er slechter van wordt, dan kun je eventueel toch met die oplossing verder werken. Jullie krijgen hier een opdracht over, waarbij jullie waarschijnlijk de NS mogen helpen door een van hun praktijkproblemen 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.
Complexiteitstheorie. De complexiteitstheorie biedt een verklaring waarom het ene probleem (bijv. een kortste pad probleem) wel snel oplosbaar is en het andere probleem (bijv. het handelsreizigersprobleem) niet.
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-51284-2 of 0-471-63681-9.

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.

Werkvorm:

Hoorcollege en Werkcollege. Na afloop van het college wordt een samenvatting op het web gezet. 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, maar 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). Ik ga er hierbij vanuit dat BaMa niet betekent dat ik met presentielijsten hoef te werken.

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 het volledige vak te gaan halen. Tussentijds worden er twee maal huiswerkopgaven opgegeven. Zoals de naam al zegt moet je die thuis uitwerken en inleveren. Het resultaat hierop is voldoende/onvoldoende, en het telt niet mee voor het eindresultaat. Wie beide keren onvoldoende haalt mag niet meedoen aan de herkansing. Wie in het verleden al het tentamen dan wel de opdracht heeft gehaald kan gebruik maken van een overgangsregeling. Je hoeft dan alleen het resterende onderdeel te halen (en dus niet de modelleeropgave. Dit levert echter dan maar 6 studiepunten op en geen 7.5. Deze regeling geldt alleen voor dit jaar en alleen voor mensen die in het verleden al een deel hebben gehaald.

Inspanningsverplichting voor aanvullende toets:

Om aan de aanvullende toets te mogen meedoen is ontbreken van ten hoogte 1 toetsactiviteit toegestaan.

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?