NDAK14003U Discrete Optimization

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.