Linköping University

Number of credits: 9 hp

Examiner: Torbjörn Larsson

Aim: The course gives a broad orientation of the field of discrete optimization, including basic modeling, theory and solution methods, as well as examples of solution with commercial software and selected real-life applications. It is intended for students in scientific disciplines where discrete optimization can serve as tool in research and development, such as management science, logistics management, engineering design, computer science, and electrical engineering. It is also intended as a first course in discrete optimization for students in mathematical sciences.

Course literature: Applied Integer Programming: Modeling and Solution, D.-S.Chen, R.G. Batson and Y. Dang, Wiley, 2010. Complementary articles about applications.

Course contents: Modeling and models: assumptions, modeling process, examples of discrete optimization models. Transformations using 0-1 variables. Better formulation by preprocessing. Modeling combinatorial optimization problems: set covering, set partitioning, matching, cutting stock, and traveling salesman problems. Review of linear programming: fundamentals, geometric concepts, solution methods. Review of network optimization problems and solutions methods. Classical solution approaches: branch-and-bound, cutting planes, group theoretic approach. Branch-and-cut: valid inequalities, cut generating techniques, cuts for special applications and structures. Branch-and-price: Dantzig-Wolfe decomposition, application to generalized assignment. Solution via primal heuristics, Lagrangian relaxation, and Benders partitioning. Solution with commercial software. Selected real-life applications.

Organisation: Seminars where the participants present the course topics, solutions to selected exercises from the book, and applications from the literature.

Examination: Active participation with presentations of course topics, solutions to exercises and applications.

Prerequisites: Undergraduate courses in mathematics, optimization and computer science.

The course is eligible also on advanced level, that is, for master's students, see TA1014  Discrete Optimization/Diskret optimering.