All programmes > Combinatorial Optimization and Local Search Techniques

Combinatorial Optimization and Local Search Techniques (B-KUL-D0M60B)

6 ECTSEnglish39 First termCannot be taken as part of an examination contract
Demeulemeester Erik
OC Handelsingenieur en Handelsingenieur in de beleidsinformatica FEB Campus Leuven

Aims

Upon completion of this course, the student is able to:

  • Design algorithms for various combinatorial problems
  • Program these algorithms efficiently in Microsoft Visual C (++)
  • Have good knowledge of branch-and-bound algorithms
  • Have good knowledge of various metaheuristics

Previous knowledge

The admission criteria for the programme can be found in the programme catalogue.

If you want to follow this course, it is advisable to have completed the following courses first:

D0H28A - Operationaal Onderzoek (HIR) (or a similar course on linear programming and/or operations research);

At the beginning of this course students should:

  • be able to formulate linear programming (LP) problems and mixed integer programming (MIP) problems;
  • preferably be able to develop basic programs in some programming language (C++, Pascal, Delphi, Java, etc.) or at least be able to develop advanced programming skills in a limited time.

Is included in these courses of study

Activities

6 ects. Combinatorial Optimization and Local Search Techniques (B-KUL-D0M60a)

6 ECTSEnglishFormat: Lecture39 First term
Demeulemeester Erik
OC Handelsingenieur en Handelsingenieur in de beleidsinformatica FEB Campus Leuven

Content

Basic C programming concepts:

  • Variables, functions, arrays, loops, conditional statements
  • Memory management and program execution: stack and heap
  • Recursion

Advanced C programming concepts:

  • Exception handling
  • Threads
  • Bitwise programming
  • C++ programming concepts:
  • Classes and objects
  • Data members, construction, destruction, mutators, inspectors, access modifiers and access rules, …

Combinatorial optimization:

  • Mixed Integer Programming
  • Branch-and-Bound

Metaheuristics:

  • Simulated Annealing
  • Tabu Search
  • Genetic Algorithms

Course material

Before each session, the students are provided with slides through Toledo.
Additional advised literature:

  • Standish, T., 1995, Data structures, algorithms & software principles in C, Addison-Wesley.
  • Sedgewick, R., 1998, Algorithms in C++, Parts 1-4, Addison-Wesley.
  • Sedgewick, R., 1998, Algorithms in C++, Part 5, Addison-Wesley.
  • Michalewicz, Z. & Fogel, D.B., 2000, How to solve it: Modern heuristics, Springer-Verlag.

Format: more information

The course consists of ten sessions of three hours. During these sessions the topic of the session is explained and a homework is provided that tests whether the students have grasped the material. In the next session some selected students have to present their homework after which an 'ideal' solution is presented.

Evaluation

Evaluation: Combinatorial Optimization and Local Search Techniques (B-KUL-D2M60b)

Type : Continuous assessment without exam during the examination period
Description of evaluation : Paper/Project
Type of questions : Open questions
Learning material : Course material, Computer

Explanation


Features of the evaluation

* During this course nine homeworks have to be made, from which the last five are graded. As most of the students have little background on programming in C, the first four homeworks are rather meant to bring the students to a level that allows them to make the more involved last five homeworks.
* The deadline of the homeworks will be determined by the lecturer and communicated via Toledo.

Determination of final grades
 

*The grades are determined by the lecturer as communicated via Toledo and stated in the examination schedule. The result is calculated and communicated as a integer number on a scale of 20
*The average of the grades obtained for  the last five homeworks  constitutes the score of the course.
* If the set deadline of one of the last five homeworks was not respected, the student obtains an score of 0 for this homework.
* If the student does not participate in one of the last five homeworks, he/she wil obtain a score of 0 for this homework.

Second examination opportunity

* The features of the evaluation and/or the determination of grades differ between the first and second examination opportunity

* At the second examination opportunity the homeworks of the first examination period are no longer part of the evaluation. The grade is entirely based on a final exam. This final exam is a take-home exam (with an agreed upon deadline) after which the student has to explain the resulting algorithm and code to the professor.


 

Information about retaking exams

* See 'Explanation' for further information regarding the second examination opportunity.