Introduction to Integer Linear Programming (ILP) – Mansini (1 hour): Combinatorial optimization and ILP problems. Alternative equivalent mathematical formulations. The Convex Hull and the ideal formulation of an ILP problem. Exact algorithms (basics) and the use of relaxations.
Linear Programming (LP) versus Integer Linear Programming – Mansini (1 hour): The concept of relaxation. Relaxation optimization problem. The continuous relaxation (LP relaxation). The surrogate relaxation (basics). Dual problem and duality in LP. The duality gap in ILP.
The Lagrangian Relaxation – Mansini (3 hours): Lagrangian’s formulation of a generic constrained optimization problem. Basic construction. Lagrangian relaxation of inequality and equality constraints. Meaning of the Lagrangian multipliers. Family of relaxations. Lagrangian dual formulation. Main properties. Relation between LP relaxation and Lagrangian relaxation. Integrality property. The optimal solution of the Lagrangian dual problem. Some examples.
The subgradient and the multiplier adjustment methods: theoretical aspects – Zanotti (3 hours): Multipliers’ initialization. Parameters setting. The methods by steps. Convergence results. Main properties. Examples.
The subgradient method: applications – Zanotti (3 hours): Application of the method to known combinatorial problems. Examples in different application domains (logistics, computer science, telecommunications, … ).
Lagrangian decomposition – Zanotti (3 hours): Decomposition of complex combinatorial optimization problems through the lagrangian relaxation. Comparison with standard Lagrangian relaxation. Examples in different application domains.
Lagrangian Heuristics - Zanotti (3 hours): Lagrangian Heuristics for the identification of feasible solutions. Lagrangian Cost Fixing. Enhancing heuristic frameworks with the use of Lagrangian relaxations.