Department of Information and Computing Sciences

Departement Informatica Onderwijs
Bachelor Informatica Informatiekunde Kunstmatige intelligentie Master Computing Science Game&Media Technology Artifical Intelligence Business Informatics

Onderwijs Informatica en Informatiekunde

Vak-informatie Informatica en Informatiekunde

Optimalisering en complexiteit

Website:website met extra informatie
Vakcode:INFOOPT
Studiepunten:7.5 ECTS
Periode:periode 2 (week 46 t/m 5, d.w.z. 14-11-2016 t/m 3-2-2017; herkansing week 16)
Timeslot:B
Deelnemers:tot nu toe 111 inschrijvingen
Rooster:De officiële roosters staan ook in Osiris
Docenten:Dit is een oud rooster!
vormgroeptijdweekzaaldocent
college   di 11.00-12.4546-50 KBG-PANGEA Han Hoogeveen
 
2 KBG-PANGEA
3-4 KBG-PANGEA
do 15.15-17.0046-50 KBG-PANGEA
2 KBG-PANGEA
3-4 KBG-PANGEA
werkcollege groep 1 di 9.00-10.4547-50 BBG-083 Bas Brouwer
 
2-4 BBG-083
do 13.15-15.0046-50 BBG-083
2-4 BBG-083
groep 2 di 9.00-10.4548-50 BBG-169 Roel Brouwer
 
2 BBG-169
do 13.15-15.0046-50 BBG-169
2 BBG-169
groep 3        Ivo Gabe de Wolff
 
Tentamen:
week: 51di 19-12-201711.00-13.00 uurzaal: EDUC-GAMMA
week: 5do 1-2-201813.30-16.30 uurzaal: EDUC-ALFA
week: 16do 19-4-201813.30-16.30 uurzaal: -aanvullende toets
Inhoud: Kijk vooral op de website http://www.cs.uu.nl/docs/vakken/opt/ voor de actuele informatie.

Voorkennis enz.

  • Een belangrijk onderdeel van het vak is de `Grote opdracht', waarbij het vuilnis-ophaal probleem moet worden aangepakt met local search (zie ook onder). Hiervoor moeten jullie in groepjes van maximaal 3 personen een computerprogramma schrijven. Omdat er zich veel wiskunde studenten (met minder programmeerervaring dan de gemiddelde informatica student) hebben ingeschreven, is het de bedoeling dat er gemengde groepjes (informatica studenten samen met wiskunde studenten) worden gevormd.
  • Het zou mooi zijn als je enige kennis van lineaire algebra bezit, maar wanneer dat niet het geval is, geen nood: ik herhaal de voor het vak benodigde lineaire algebra (hoofdzakelijk matrixrekening) bij het college.

Algemeen 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 het ophalen van afval. Uiteraard kent iedereen de grote vuilnisauto's waarmee van AVR-Van Gansewinkel het afval ophaalt. Slechts weinigen zullen zich hebben gerealiseerd dat er heel wat planning aan te pas komt om dit efficient te doen: hoe verdeel je een regio in gebieden die ieder kunnen worden `bediend' door een vuilnisauto, en welke route moet die vuilnisauto dan rijden? AVR-Van Gansewinkel heeft het consultancy bedrijf CQM hiervoor een pakket laten ontwikkelen. Daarna heeft CQM deze case gebruikt voor de jaarlijkse wedstrijd `De Nacht van Eindhoven', en nu kunnen jullie proberen om een zo goed mogelijke oplossing te vinden `match your skills with the masters' (in 2008, 2014, en in 2016 is de wedstrijd gewonnen door een team uit Utrecht). Op dinsdag 22 november komt onze oud-student Kevin van Blokland, die nu werkzaam is bij CQM, het probleem uitleggen. Daarna gaat Roel van den Broek een presentatie geven over zijn afstudeerwerk bij NedTrain, waar hij local search heeft gebruikt om een probleem op te lossen waarbij zoveel mogelijk treinen moeten worden onderhouden/ge├»nspecteerd (waarbij je steeds moet rangeren om de treinen op de goede plaats te krijgen).
  • 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. Er is geen opkomstplicht, er is weinig ruimte in de zaal (het college vindt plaats tijdens het werkcollege in een werkcollegezaal) en het begint om 9.00 uur 's ochtends: allemaal goede redenen om alleen te gaan indien het nodig is om je kennis van lineaire algebra bij te spijkeren (kijk ook eerst even naar de slides).
  • 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. Tom van der Zanden heeft een solver ontdekt bij Microsoft, en hij wil jullie ervan overtuigen om die te gaan gebruiken. Meer informatie op de site.
  • 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.
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 een naslagwerk. Het is dus niet verplicht om het aan te schaffen! Vanwege de te hoge prijs wordt het boek niet meer aangeschaft door Aeskwadraat (misschien nog wel door Sticky). Het boek is ook in de voorgaande jaren gebruikt; misschien dat je het op een accoordje kunt gooien met een student die het vak vorig jaar heeft gevolgd. 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. Het schijnt dat je daar het boek ook kunt vinden.

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. Ik heb ook voorbeelduitwerkingen op het web staan. Het is natuurlijk de bedoeling dat je de opgaven eerst zelf probeert.

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 de onderstaande quote vermelden van een eerdere evaluatie:

SUPERBELANGRIJK, GA ER ALTIJD HEEN. Of maak in ieder geval alle opgaven thuis, maar vaak was het beter om de opgaven samen met anderen te maken, anders duurde het twee keer zo lang en je leerde het wel allemaal.


Bas Brouwer, Roel Brouwer, en Ivo-Gabe de Wolff gaan samen met mij het werkcollege begeleiden.

Toetsvorm:Deeltentamen, Eindtentamen plus practicumopgave. Op basis van het deeltentamen en eindtentamen krijg je een tentamencijfer dat voor 60% meetelt; het local search practicum voor 40%. Op het modelleer practicum moet je een voldoende halen; op het local search practicum moet minstens een 5.0 worden gescoord; het tentamencijfer moet minstens een 4.5 zijn. Indien het cijfer voor het eindtentamen hoger is dan het cijfer voor het deeltentamen (tussentoets), dan wordt het cijfer voor het deeltentamen vervangen door het cijfer voor het eindtentamen. Eerder behaalde deelresultaten zijn nog steeds geldig (maar de houdbaarheid kan na dit jaar wel eens minder worden, dus rond het vak deze keer wel af).
Inspanningsverplichting voor aanvullende toets:Wie bij het deeltentamen en bij het tentamen werk heeft ingeleverd ter beoordeling en in beide gevallen minder dan een 4 heeft gescoord mag niet deelnemen aan de herkansing.
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?