SluitenHelpPrint
Switch to English
Cursus: INFOOPT
INFOOPT
Optimalisering en complexiteit
Cursus informatie
CursuscodeINFOOPT
Studiepunten (EC)7,5
Cursusdoelen

Cursusdoelen

Bij dit vak gelden de volgende leerdoelen:
  • Kunnen formuleren van een probleem als een LP of ILP
  • Kunnen oplossen van een LP of ILP met een solver
  • Kunnen implementeren van een local search voor een praktisch probleem
  • Kennis van de basis van simplex en dit kunnen toepassen
  • Kennis van de meer geavanceerde vormen van simplex en deze toe kunnen passen
  • Dualiteit + gevoeligheidsanalyse en deze theorie toe kunnen passen
  • Oplossen van ILPs met branch-and-bound en dit kunnen toepassen

Inhoud
Eerst een potentieel misverstand voorkomen: Dit vak gaat NIET over het optimaliseren van code (al kun je je bij de zogenaamde Grote Opdracht wel uitleven op dat gebied). Bij dit vak draait het vooral om het vinden van een zo goed mogelijke oplossing voor logistieke problemen. Hiervoor komen twee technieken aan bod: Local Search (en dan vooral Simulated Annealing) en Lineaire Programmering (en deze techniek heeft niets met het programmeren van een computer te maken ...). Simulated Annealing leer je vooral door het toe te passen: hiervoor is de Grote Opdracht bestemd. Bij de Grote Opdracht moet je een computer programma schrijven dat voor een praktijkprobleem van het ophalen van afval bij zo'n 1100 bedrijven een zo goed mogelijke oplossing vindt. Hier kun je je uitleven met geschikte datastructuren en handig programmeren; er komt ook een college (van gastdocent Ivor van der Hoog) over het versnellen van de code, waarbij Ivor handige tips en trucs geeft over het gebruik van datastructuren. Bij de overige hoor- en werkcolleges staat de theorie van Lineaire Programmering centraal. Zie ook de website (van vorig jaar); deze kun je vinden op https://www.cs.uu.nl/docs/vakken/opt/

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: de kleine opdracht
  • Behandeling van de techniek van local search. Dit kun je vervolgens gebruiken om de Grote Opdracht (volgens sommigen de MEGA opdracht) tot een goed einde te brengen. De Grote Opdracht betreft het vinden van een zo goed mogelijke oplossing voor het ophalen van afval. Dit is gebaseerd op een praktijkprobleem dat is opgelost door het consultancy bedrijf CQM; CQM heeft deze case gebruikt voor de jaarlijkse wedstrijd `De Nacht van Eindhoven'. Je kunt bonuspunten verdienen door een zo goed mogelijke oplossing te vinden.
  • Behandeling van een simpele versie van het Simplex algoritme, dat wordt gebruikt om lineaire programmeringsproblemen op te lossen.
  • Twee efficientere implementaties van de simplex methode en de methode van kolomgeneratie.
  • 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. 
  • Het oplossen van geheeltallige lineaire programmeringsproblemen met behulp van branch-and-bound.
  • Een praktijktoepassing: het `seriegrootte' probleem. Dit 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.
     
Toetsing
De toetsing bestaat uit een aantal verschillende onderdelen, namelijk
  • De kleine opdracht: deze moet voldoende zijn.
  • De grote opdracht: deze telt mee voor 40%
  • De minitoetsen: deze tellen mee voor 15%, maar je mag dit vervangen door 10% van het tentamencijfer
  • Het schriftelijk eindtentamen: dit telt mee voor 50%
  • Eventuele bonus (wordt bij het eindcijfer opgeteld, mits voldoende). Hier is maximaal 1,4 punt te verdienen + eeuwige roem als je het (zeer scherpe) record weet te verbeteren
Voor uitgebreide informatie: zie website

Competenties
-
Ingangseisen
Enige basisvaardigheden op het gebied van programmeren; het is een pre als je het vak Datastructuren hebt gevolgd. Kennis van Lineaire Algebra is niet vereist.
 

 
Inhoud
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.

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
  • Het oplossen van geheeltallige lineaire programmeringsproblemen met behulp van branch-and-bound.
  • Twee efficientere implementaties van de simplex methode en de methode van kolomgeneratie.
  • 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. 
  • Behandeling van een simpele versie van het Simplex algoritme, dat wordt gebruikt om lineaire programmeringsproblemen op te lossen.
  • 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. Vorig jaar kon Excel gebruikt worden, maar 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.
  • 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.
  • 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' (zie hier), en nu kunnen jullie proberen om een zo goed mogelijke oplossing te vinden `match your skills with the masters' (in 2008 en in 2014 is de wedstrijd gewonnen door een team uit Utrecht).
  • 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.
     
SluitenHelpPrint
Switch to English