README.md

# 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 modelling problems using linear constraints and objective functions on fractional and integral variables.
Most combinatorial problems are easily expressable by Mixed Integer Programming, and most practical optimization problems can be sufficiently approximated.
The probably most famous sucess 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 modelling the problems and using such a solver as a black box.

## Modelling

TBD: Give some basics on modelling.

Ein *lineares Programm* (LP) besteht, ähnlich wie ein Constraint Program, aus Variablen $x_1,\ldots,x_n$ sowie einer Zielfunktion und Nebenbedingungen über diesen Variablen.
Allerdings ist man bei einem LP auf eine lineare Zielfunktion sowie lineare Nebenbedingungen beschränkt.
Die Zielfunktion hat im Allgemeinen die Form $\sum_{i=1}^{n} c_ix_i$ für frei bestimmbare, aber feste Koeffizienten $c_i \in \mathbb{R}$, und kann entweder minimiert oder maximiert werden.
Es ist insbesondere nicht möglich, Variablen miteinander zu multiplizieren oder ihren Absolutwert zu bestimmen, oder ähnliche nicht-lineare Elemente in die Zielfunktion einzubauen.

Genau wie die Zielfunktion müssen auch die Nebenbedingungen linear sein.
Die $j$-te Nebenbedingung hat im Allgemeinen die Form $\sum_{i=1}^n a_{ij}x_i \leq b_j$, wobei $a_{ij}$ und $b_j$ wieder frei bestimmbare, aber feste Koeffizienten aus $\mathbb{R}$ sind.
Es darf statt $\leq$ auch $\geq$ oder $=$ genutzt werden.
Auch hier ist es also nicht möglich, Variablen miteinander zu multiplizieren oder andere nicht-lineare Nebenbedingungen einzuführen.

Üblicherweise haben die Variablen Schranken, also Nebenbedingungen der Form $\ell_i \leq x_i \leq u_i$, die ihren Wertebereich einschränken.
Diese kann man gesondert behandeln, aber auch einfach als zusätzliche Nebenbedingungen betrachten.


Nun brauchen wir zur Modellierung eines NP-schweren Problems natürlich zwingend ein NP-schweres Problem, es sei denn, uns ist der Beweis für $P = NP$ geglückt.
Hier kommt die Erweiterung der linearen Programmierung zur ganzzahligen linearen Programmierung (IP) ins Spiel.
Sie erlaubt es uns, alle Variablen (oder auch nur einen Teil der Variablen\footnote{Man spricht technisch gesehen von einem Mixed Integer Program (MIP), wenn es sowohl ganzzahlige als auch kontinuierliche Variablen gibt.}) auf ganzzahlige Werte zu beschränken.
Dadurch wird es zum einen möglich, unter anderem Entscheidungsvariablen als $\{0,1\}$-Variablen zu implementieren, und das Problem wird NP-schwer.
Zum anderen erlaubt uns Integer Programming, auf Umwegen auch einige nicht-lineare Nebenbedingungen zu modellieren.

Anders als die bisher verwendeten CP- und SAT-Solver bieten IP-Solver oft die Möglichkeit, während einer laufenden Suche neue Bedingungen hinzuzufügen.
Solche Nebenbedingungen werden auch  *Lazy Constraints* genannt.
Dies geschieht in der Regel durch sogenannte \emph{Callbacks}: Während der Suche ruft der IP-Solver an bestimmten Punkten den zuvor registrierten Code des Benutzers auf.
Dabei erhält der Benutzer-Code Zugriff auf eine aktuelle (ganzzahlige oder auch nicht-ganzzahlige) Lösung und erhält die Möglichkeit, neue Bedingungen einzufügen, die diese Lösung verbieten.
Dies wird beim TSP zum Beispiel verwendet, um während der Lösung auftretende Subtouren zu verbieten, ähnlich wie wir das bei SAT gemacht haben, allerdings ohne den Solver immer wieder neu zu starten.

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. 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 as subset of the API can be used.
For getting such an acemdic license, you have to [register](https://www.gurobi.com/academia/academic-program-and-licenses/).

Once you got a license from the webpage, you can run
```bash
grbgetkey XXXXXXXX-YOUR-KEY-XXXXXXXXXX
```
to activate  it.

## Tasks

* Modelliert statt des DBST das BTSP als Integer Program und implementiert einen Solver auf dieser Basis. Ihr könnt Euch dabei wieder an dem DBST-Beispiel orientieren; achtet allerdings darauf, dass die von Euch generierten Lazy Constraints so scharf wie möglich sind.
* Modelliert auch die Variante des BTSP, bei der die kürzeste Tour gesucht wird, deren Bottleneck minimal ist, und implementiert einen Solver für diese Problemvariante.
* Wie groß sind die Instanzen, die Ihr in der Regel noch in einer Minute bzw.\ in einer Viertelstunde lösen könnt? Wie schnell ist der IP-basierte Solver im Vergleich zum SAT-basierten und zum CP-basierten Solver? Wie viel länger dauert es, die Problemvariante zu lösen, bei der nach einer kürzesten Tour mit minimalem Bottleneck gesucht wird? Überlegt Euch, wie Ihr diese Fragen experimentell beantworten könnt, und wie Ihr die Ergebnisse Eurer Experimente graphisch (mithilfe von Plots) darstellen könnt.
* Im Codebeispiel seht Ihr, dass Ihr nicht nur ganzzahlige Zwischenlösungen bekommen könnt, sondern im Callback auch Zugang zu den nicht-ganzzahligen (fraktionalen) Zwischenlösungen bekommt. Baut eine Option in Eure Solver ein, mit der Ihr die entstehenden fraktionalen Zwischenlösungen visualisieren könnt. Ihr könnt dazu beispielsweise jede Zwischenlösung in ein Bild exportieren. Stellt dabei am besten nur diejenigen Kanten dar, deren Entscheidungsvariablen größer als ein gewisser Minimalwert (z.\,B. $10^{-4}$) sind. Ihr könnt neben Labels an den Kanten dabei mit Transparenz oder Farben arbeiten, um den Wert der zugehörigen Variablen darzustellen.
* Untersucht für ein paar kleine Beispiele die entstehenden Zwischenlösungen. Könnt ihr Bedingungen identifizieren, die sich als lineare Nebenbedingungen darstellen lassen, welche von allen zulässigen ganzzahligen Lösungen erfüllt werden, aber von vielen Eurer Zwischenlösungen nicht? Achtet dabei insbesondere darauf, dass der Solver nicht alle Constraints kennt und diese daher in vielen Zwischenlösungen nicht berücksichtigt werden können, bevor Ihr sie dem Solver gebt.
* Falls Ihr solche Nebenbedingungen finden könnt, implementiert Routinen, die diese Nebenbedingungen finden und dem Solver zur Verfügung stellen. Diese Routinen sollten mit Optionen abschaltbar sein. Führt Experimente durch und untersucht, ob die Performance Eures Solvers sich mit diesen Nebenbedingungen verbessert. Versucht auch herauszufinden, mit welchen Optionen der Solver am besten funktioniert.