Prerequisites

Indispensible: Solid knowledge in linear/integer optimization from the courses "quantitative methods" and "operations research 1" (BWL) or "efficient algorithms" (CS) or "integer linear optimization" (maths), i.e., in particular you master duality, branch-and-bound, and modeling with integer programs.

Contents

State of the art in models and algorithms to solve extremely large-scale and complex optimization problems, in particular column generation and branch-and-price: structued integer programs, Dantzig-Wolfe reformulation, Lagrange relaxation, cutting planes in connection with column generation, branching rules, stabilization technqiues, implementation tricks, practical applications

Learning Goals

The students aquire basic and advanced skills in modelling very large-scale and practical optimization problems, as well as the algorithmic thinking to solve such models using decomposition approaches. By working on practical implementation exercises, these algorithms shall be actually applied and the basic implementation of a column generation approach will be learned. Students will be enabled to read scientific publications at the current level of scientific knowledge and transfer this knowledge to practical modeling situations.

Prerequisites

Basic knowledge in linear optimization and graph algorithms, in particular modeling with networks (minimum cost flows, shortest paths) and linear programs. If missing, this background must be acquired before or simultaneously to the course.

Contents

1. Modeling with integer linear programs: assignment problems, knapsack problem, faclity location, machine scheduling, traveling salesperson problem, vehicle routing, set partitioning, bin packing, cutting stock, logical constraints; 2. algorithms for solving integer programs: branch-and-bound, cutting planes, branch-and-cut, dynamic programming; 3. basics of heuristics and meta heuristics (construction and improvement heuristics, greedy algorithm, local search, simulated annealing, tabu search, evolutionary and genetic algorithms); 4. particular modeling situations like soft constraints, non-linearities, heuristic modeling; introduction to computational complexity theory

Learnig Goals

Students learn modeling techniques and methods of integer optimization, in particular their use cases and limitations. Students aquire the ability to identify the mathematical core of a practical optmization task and to exploit problem structure when selecting/developing a model or selecting an algorithm. The theoretical knowledge is deepened using practical exercises with standard software (currently Gurobi/Python). We generally sharpen abstraction capabilities.

Videos from winter term WS17/18 are here.

Prerequisites

Indispensible: Solid knowledge in linear/integer optimization from the courses "quantitative methods" and "operations research 1" (BWL) or "efficient algorithms" (CS) or "integer linear optimization" (maths), i.e., in particular you master duality, branch-and-bound, and modeling with integer programs.

Contents

State of the art in models and algorithms to solve extremely large-scale and complex optimization problems, in particular column generation and branch-and-price: structued integer programs, Dantzig-Wolfe reformulation, Lagrange relaxation, cutting planes in connection with column generation, branching rules, stabilization technqiues, implementation tricks, practical applications

Learning Goals

The students aquire basic and advanced skills in modelling very large-scale and practical optimization problems, as well as the algorithmic thinking to solve such models using decomposition approaches. By working on practical implementation exercises, these algorithms shall be actually applied and the basic implementation of a column generation approach will be learned. Students will be enabled to read scientific publications at the current level of scientific knowledge and transfer this knowledge to practical modeling situations.

Prerequisites

Basic knowledge in linear optimization and graph algorithms, in particular modeling with networks (minimum cost flows, shortest paths) and linear programs. If missing, this background must be acquired before or simultaneously to the course.

Contents

1. Modeling with integer linear programs: assignment problems, knapsack problem, faclity location, machine scheduling, traveling salesperson problem, vehicle routing, set partitioning, bin packing, cutting stock, logical constraints; 2. algorithms for solving integer programs: branch-and-bound, cutting planes, branch-and-cut, dynamic programming; 3. basics of heuristics and meta heuristics (construction and improvement heuristics, greedy algorithm, local search, simulated annealing, tabu search, evolutionary and genetic algorithms); 4. particular modeling situations like soft constraints, non-linearities, heuristic modeling; introduction to computational complexity theory

Learnig Goals

Students learn modeling techniques and methods of integer optimization, in particular their use cases and limitations. Students aquire the ability to identify the mathematical core of a practical optmization task and to exploit problem structure when selecting/developing a model or selecting an algorithm. The theoretical knowledge is deepened using practical exercises with standard software (currently Gurobi/Python). We generally sharpen abstraction capabilities.

Videos from winter term WS17/18 are here.

This course is no longer offered. Please participate in the courses offered by the computer science department, like basics in programming ("for everyone") and algorithms and data structures.