Prüfungsstoff für die Veranstaltung
"Mixed-Integer Programming"

Linear programming

• Standard LP formulations
• Duality
• Polyhedra and basic solutions
• Primal and dual simplex algorithm
• Postoptimal analysis and reoptimization

• Decisions, logical conditions, products of binary variables
• Disjunctions, general integers, semi-continuous variables
• Partial integers, fixed costs, products of binary and real variables
• Special ordered sets, piecewise linear functions
• Incremental price breaks, all items discount
• Min-max objective functions, ratio objective functions

• Combinatorial problems
• Combinatorial problems and integer programming

• Branch-and-bound
• Cutting plane algorithms
• Branch-and-cut
• Dynamic programming

• Combinatorial polytopes and linear programs
• Polyhedral theory
• Separation and optimization

• Enumeration
• Projection
• Computation techniques

• Combinatorial relaxation
• Linear programming relaxation
• Lagrangian relaxation

• Separation
• Pricing
• Fixing and setting of variables
• Branching
• Addition of variables
• Parallelization

• Row and column analysis
• Coefficient reduction
• Clique constraints
• Aggregation and disaggregation
• Probing
• Model improvement

• Lifting of inequalities
• Chvatal-Gomory cuts
• Knapsack cuts
• Disjunctive cuts
• Flow cover inequalities
• Maximally violated mod-k cuts
• Target cuts
• Small facet separation
• Separation for large problems

• Cutting stock problem
• Dantzig-Wolfe decomposition
• Benders decomposition