Integer Programming Methods (2023/2024)
The vast majority of problems in combinatorial optimization can be formulated as an integer linear program (ILP): Maximize or minimize a linear objective function subject to linear constraints and the additional restriction that the decision variables can take only integer values (typically only 0/1). This makes ILPs a perfect tool for formulating problems in combinatorial optimization; many software packages are available for this. The drawback is that solving ILPs is generally a computationally demanding task; it is NP-hard. Nevertheless, in practice, also these problems have to be solved. In this part of the course we focus on techniques for solving ILPs.