NDAK14003U Discrete Optimisation (DO)
Discrete Optimisation is concerned with solving optimisation
problems with discrete variables. Such variables may represent
indivisible commodities or yes/no decisions to buy, invest, hire,
build, etc. Discrete optimisation problems arise in countless
scenarios, e.g. when developing time tables for aeroplanes, trains
or buses, in scheduling problems, in facility location problems and
in network design problems.
Many discrete optimisation problems can be formulated as integer linear programming (ILP) problems with integer variables, a linear objective function and linear constraints. The advances of ILP have been remarkable over the last 25 years. Many difficult practical ILP problems can today be solved to near-optimality not because of faster computers but because of new theoretical results.
The purpose of this course is to familiarised participants with state-of-the-art ILP techniques. The course will cover such topics as lower bound techniques (e.g. linear and Lagrangian relaxations) and their importance in branch-and-bound algorithms. Cutting planes, column generation and branch-and-cut algorithms will also be covered. Since linear programming (with continuous variables) plays a key role in solving ILP problems, this topic will be covered and the SIMPLEX algorithm will be explained in detail.
Not all ILP problems can be solved within reasonable time limits. The course will therefore also cover approximation algorithms and heuristic methods where the optimality requirement is abandoned but where it is possible to either bound the deviation from the optimum or where reasonable solutions can be produced very fast but without any error guarantees.
- Comprehensive knowledge of discrete optimisation problems (linear and integer programming in particular).
- Familiarity with algorithms and heuristics that can solve discrete optimisation problems.
- Formulation of (simple) real-life problems as (integer) linear programming problems.
- Selection of appropriate algorithms suitable to solve a particular discrete optimisation problem.
- Application of software packages or self-implemented software to solve such problems.
- Recognition of real-life problems solvable by methods introduced in this course.
- Identification of suitable algorithms to solve such problems.
- Design of new algorithms and heuristics for existing and new problems.
Academic qualifications equivalent to a BSc degree is recommended.
As an exchange, guest and credit student - click here!
Continuing Education - click here!
PhD’s can register for MSc-course by following the same procedure as credit-students, see link above.
- 7,5 ECTS
- Type of assessment
- Oral examination, 30 minutes
- Type of assessment details
- The oral examination is without preparation.
The oral examination will consist of two parts:
1. Questions related to the scientific paper presented during the course
2. Questions covering the syllabus of the course
- Exam registration requirements
Students will have to get approved lecture notes on 3 selected topics covered in the course (individually). These will be reviewed by other students and by the lecturer.
Students will have to present a scientific paper (in groups of 2 -3).
- All aids allowed
- Marking scale
- 7-point grading scale
- Censorship form
- No external censorship
Several internal examiners.
Same as the ordinary exam.
If a student has not qualified for the ordinary exam he/she can qualify by submitting 3 lecture notes and a written summary of selected paper no later than two weeks before the re-exam (if this was not done during the course).
Criteria for exam assesment
See Learning Outcome.
- Course code
- 7,5 ECTS
- Full Degree Master
- 1 block
- Block 1
- Course capacity
- No limit
- Study Board of Mathematics and Computer Science
- Department of Computer Science
- Faculty of Science
- Pawel Winter (5-807187757c5074793e7b853e747b)