Velkommen til Københavns Universitets kursuskatalog
NDAK14003U Discrete Optimization
Volume
2014/2015  Language  English   Credit  7,5 ECTS   Level  Full Degree Master   Duration  1 block   Placement  Block 1  Schedule  A (Tues 812 + Thurs 817)   Course capacity  No limits   Study board  Study Board of Mathematics and Computer
Science   Contracting department   Department of Computer Science
  Course responsible   Pawel Winter (574657b697044686d326f7932686f)
  Saved on the
27022015 
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 nearoptimality not because of
faster computers but because of new theoretical results.
The purpose of this course is to familarized participants with the
stateoftheart ILP techniques. The course will cover such topics
as lower bound techniques (e.g., linear and Lagrangian relaxations)
and their importance in branchandbound algorithms. Cutting
planes, column generation and branchand 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:
 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) reallife problems as (integer) linear
programming problems.
 Selection of appropriate algorithms suitable to solve a
particular discrete optimization problem.
 Application of software packages or selfimplemented software
to solve such problems.
Competences:
 Recognition of reallife 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 
Sign up  Self Service at KUnet

Exam  Credit  7,5 ECTS   Type of assessment  Written assignment Oral 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  7point grading scale   Censorship form  No external censorship
Several internal examiners.    Criteria for exam assesment  See learning
outcome. 

Workload  Category  Hours  Lectures  28  Exercises  14  Preparation  89  Exam  75  Total  206 

Saved on the
27022015

