Seminarium Advanced Heuristic Search Techniques
Het seminarium Advanced Heuristic Search Techniques
wordt in het studiejaar 1998/1999 verzorgd door
Elena Marchiori.
Het doel van het seminarium is het leren van de meest gebruikte
zoek-technieken voor het vinden van goede benaderingen
van oplossingen voor moeilijke,
combinatorische optimaliserings-problemen.
Op deze manier kunnen vele problemen uit de alledaagse praktijk
worden behandeld met goede heuristische algoritmen.
De te behandelen onderwerpen zullen in overleg met de studenten
worden bepaald. Hieronder volgen (in het Engels)
enkele onderwerpen die mogelijk aan bod zullen komen:
- NP-hard combinatorial optimization problems;
- Heuristics algorithms;
- Simulated Annealing;
- Tabu Search;
- Reactive Local Search;
- The GRASP algorithm;
- Various
Case Study Problems, such as:
Graph Coloring, Maximum Clique, Setcovering,
Traveling Salesman, Scheduling, Vehicle Routing.
Gebruik zal worden gemaakt van de boeken:
- Modern Heuristic Search Methods, eds. V.J. Rayward-Smith et al,
Wiley, 1996, ISBN 0471 96280 5;
- Local Search in Combinatorial Optimization, eds. E. Aarts, J.K. Lenstra,
Wiley, 1997, ISBN 0471948225,
en van verschillende artikelen op het gebied van de gegeven problemen.
Ieder van de deelnemers zal enkele malen een voordracht houden (in het Nederlands of in het Engels)
over een nader te bepalen onderwerp: in groepjes van twee personen
zal gewerkt worden aan een bepaald combinatorisch optimaliserings-probleem
(bijvoorbeeld uit de bovenstaande lijst van `case studies'). Voor dit probleem
zullen de groepsleden een heuristisch algoritme
ontwikkelen, implementeren (in C of C++) en testen.
Hieronder volgt de lijst van onderwerpen van deelnemende studenten aan het seminarium.
Interessante informatie op WWW:
Benchmark instances voor SAT:
Vragen of opmerkingen kunnen worden gestuurd naar:
kosters@liacs.nl.
http://www.liacs.nl/home/kosters/semheu.html