Newer
Older
# Sheet 04: (Mixed) Integer (Linear) Programming
The oldest and most common technique for solving NP-hard optimization problems in practice is [(Mixed) Integer (Linear) Programming](https://en.wikipedia.org/wiki/Integer_programming).
It allows modeling problems using linear constraints and objective functions on fractional and integral variables.
Most combinatorial problems are easily expressible by Mixed Integer Programming, and most practical optimization problems can be sufficiently approximated.
The probably most famous success story of this technique is its usage by the [TSP-solver Concorde](https://en.wikipedia.org/wiki/Concorde_TSP_Solver), which was able to solve a (non-trivial) instance with over 85000 vertices to optimality.
The solvers are usually based on [Branch&Bound](https://en.wikipedia.org/wiki/Branch_and_bound), [Linear Relaxation](https://en.wikipedia.org/wiki/Linear_programming_relaxation), and [Cutting Planes](https://en.wikipedia.org/wiki/Cutting-plane_method), of which especially the last two have a serious mathematical foundation.
Mixed Integer Programming is one of the prime examples for the importance of theoretical research for practical progress.
However, you don't have to worry about any mathematical details, as modern solvers will do most of the complicated stuff for you.
This [primer](https://www.gurobi.com/resources/mixed-integer-programming-mip-a-primer-on-the-basics/) gives you some further details on how it is working.
We will focus here on just modeling the problems and using such a solver as a black box.
Modern MIP-solvers like Gurobi have a very expressive API that allows a declarative usage, similar to CP-SAT that we used in a [previous sheet](../02_cpsat).
The main differences are that MIP-solvers are usually limited to linear expressions (everything non-linear is usually done by inefficient tricks) but can deal much better with fractional values.
An advanced concept are also lazy constraints, that allow to efficiently add further constraints via callbacks.
In the [previous sheet](../03_card_sat), we already used iterative model building to only add constraints if necessary, with MIP-solvers this is more interactive.
Linear expressions are algebraic formulas of the first degree, i.e., variables are not multiplied or divided by each other (or themselves).
As comparisons, only $\leq, =, \geq$ are allowed, but not true inequalities, making them essentially half-planes or spaces in a high-dimensional spaces (and the solution space linear).
An example for a linear constraint is $4\cdot x_1-3 \cdot x_2+0.5\cdot x_3 \geq 7.3$.
$x_1^2 \leq 3$ would *not* be linear as $x_1$ is multiplied by itself.
Advanced functions such as $\sin x$ are of course completely forbidden (though, there are tricks to approximate them).
1. Variables, which can be fractional, boolean, or integral. Fractional and integral variables can additional have a lower and upper bound.
2. A linear objective function that can be minimized or maximized.
3. A set of linear constraints on the variables that have to be satisfied by every solution.
4. Optionally, a lazy constraints-function that gets a solution and returns nothing if the solution is feasible or constraints that are violated and should be added to the set. This allows to have a theoretically huge number of constraints in the model, but not in the computer memory.
You can also check out these [video lectures](https://www.gurobi.com/resource/tutorial-mixed-integer-linear-programming/).
We again provide an [example for the Degree Constrained Bottleneck Spanning Tree](./dbst_mip).
## Installation
We will use [Gurobi](https://www.gurobi.com/). In case you haven't already installed it, you can do so using Anaconda
```bash
conda config --add channels http://conda.anaconda.org/gurobi
conda install gurobi
```
You can also install it via `pip` but this may not install the license tool `grbgetkey`, which is required for activating a full academic license.
Without such a license, only very small models and only a subset of the API can be used.
For getting such an academic license, you have to [register](https://www.gurobi.com/academia/academic-program-and-licenses/).
In the past, this page has been buggy from time to time (e.g., it forgot your student status).
Once you got a license from the webpage, you can run
```bash
grbgetkey XXXXXXXX-YOUR-KEY-XXXXXXXXXX
```
to activate it.
You may have to be within the university's network (or use VPN) for this.
* Model the BTSP as a Mixed Integer Program on paper.
* Implement the model with Gurobi.
* How does the solver performs compared to the CP-SAT-solver and the SAT-solver? What is the smallest instance you can no longer solve, and what is the largest instance you still can solve in 5 minutes.
* You can provide Gurobi with initial solutions. How does this influence the performance?