NDAK14003U Discrete Optimization
Volume 2014/2015
Content
Discrete Optimization is
concerned with solving optimization problems with discrete
variables. Such variables may represent indivisible commodities or
yes/no decisions to buy, invest, hire, build, etc. Discrete
optimization problems arise in countless scenarios, e.g., when
developing time tables for airplanes, trains or buses, in
scheduling problems, in facility location problems and in network
design problems.
Many discrete optimization 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 familarized participants with the 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 also 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 abondoned 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.
Many discrete optimization 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 familarized participants with the 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 also 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 abondoned 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.
Learning Outcome
Knowledge:
Skills:
Competences:
- Comprehensive knowledge of discrete optimization problems (linear and integer programming in particular).
- Familarity with algorithms and heuristics that can solve discrete optimization problems.
Skills:
- Formulation of (simple) real-life problems as (integer) linear programming problems.
- Selection of appropriate algorithms suitable to solve a particular discrete optimization problem.
- Application of software packages or self-implemented software to solve such problems.
Competences:
- 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.
Teaching and learning methods
Lectures and
tutorials
Workload
- Category
- Hours
- Exam
- 75
- Exercises
- 14
- Lectures
- 28
- Preparation
- 89
- Total
- 206
Sign up
Self Service at KUnet
As an exchange, guest and credit student - click
here!
Continuing Education - click here!
Continuing Education - click here!
Exam
- Credit
- 7,5 ECTS
- Type of assessment
- Written assignmentOral examination, 30 min.1. Students will have to write lecture notes on a selected topic covered in the course.
2. Students will have to implement and document two related assignments.
3. Students will have to take an oral exam, 30 min. without preparation. The exam will consist of two parts: questions related to the assignments mentioned in (2) and questions covering the syllabus of the course. (1) and (2) has to be handed in, in order to participate in the oral exam.
The grade will be based on the overall evaluation of (1), (2) and (3). - Aid
- Only certain aids allowed
Lecture notes (see 1.) and assignments (see 2.)
- Marking scale
- 7-point grading scale
- Censorship form
- No external censorship
Several internal examiners.
Criteria for exam assesment
See learning outcome.
Course information
- Language
- English
- Course code
- NDAK14003U
- Credit
- 7,5 ECTS
- Level
- Full Degree Master
- Duration
- 1 block
- Placement
- Block 1
- Schedule
- A (Tues 8-12 + Thurs 8-17)
- Course capacity
- No limits
- Study board
- Study Board of Mathematics and Computer Science
Contracting department
- Department of Computer Science
Course responsibles
- Pawel Winter (5-74657b697044686d326f7932686f)
Saved on the
27-02-2015