Optimisation discrète
===

Notes de cours. Ecole Centrale Supélec. Nov'18-Fev'19.

Evaluation du cours : 2 DM et 1 CF

### Début du TD

http://www-desir.lip6.fr/~durrc/Iut/optim/t/01-42
*Mettre la réponse dans l'URL pour pouvoir avancer à l'exercice suivant.*

Certains codes sont [ici](https://github.com/xtof-durr/simple_constraint_programming)

## Programmation par contraintes

La programmation par contraintes est un outil pour modéliser les problèmes d'optimisation discrète.
L'idée est de trouver une assignation des valeurs aux variables qui valide toutes les contraintes.

### Exemples

#### k-colorabilité d'un graphe
Soit un graphe, peut-on assigner des couleurs ($k$ couleurs au total) aux sommets tels que deux sommets reliés par une arrête n'aient pas la même couleur ?

Soit :
- une variable $X_v$ par sommet dans le domaine $\{1,...,k\}$
- une contrainte par arrête $(u,v)$ : $X_u \neq X_v$

Trouver le nombre minimal de couleurs qui vérifie cette propriété.

#### Mots croisés
Bah un mot croisé quoi. Faut que les mots sur les segments de cases blanches (longueur $\geq 2$) soient dans le dico.

- **Entrée :** dictionnaire (ensemble de mots), et une grille avec cases vides ou noires
- **Sortie :** affectation de lettres aux cases vides, tel que chaque *segment* (voir définition ci-dessous) forme un mot du dictionnaire.

##### Définition
*Segment* = suite consécutive maximale de cases blanches dans une ligne ou une colonne et de longueur $\geq 2$

##### Modélisation 1
Une variable par *case* (domaine : alphabet).
Une contrainte par segment, forçant le mot constitué des lettres dans les cases du segment à être dans le dictionnaire.

##### Modélisation 2
Une variable par *segment* (domaine : mots du dictionnaire de la longueur du segment).
Une contrainte par intersection des segments, demandant que les mots aient la même lettre sur la case d'intersection.

### En général
Pour passer d'un *modèle "primal"* à un *modèle "dual"*, on a :
* variable duale $\equiv$ contrainte primale
* domaine $\equiv$ ensemble de n-uplets validés par la contrainte primale
* contrainte duale $\equiv$ variable primale, elle force les variables duales à avoir la même valeur sur la variable primale

Ce n'est pas toujours pertinent de regarder le modèle dual (par exemple pour la coloration).

### Arbre de résolution
Chaque noeud correspond à une affectation partielle des variables. Une variable de branchement est choisie par noeud qui est encore libre (pas affecté).
Les descendants de ce noeud correspondent chacun à une affectation possible de $x$ **mais** qui soit consistante avec les affectations déjà effectuées, c'est-à-dire les contraintes liant des variables affectées doivent être satisfaites.

### Exemple : n reines

#### Enoncé
Sur un échiquier donné, trouver une situation avec $n$ reines qui ne se mangent pas.

Il s'agit d'un problème scolaire. On connait une description compacte d'une solution qui dépend de $n$, donc normalement on n'a pas besoin d'un solveur pour en trouver une. Mais on l'utilise pour avoir un problème très facilement exprimable, et avec un seul paramêtre qui permet d'influencer sur la difficulté de la résolution.

#### Modélisation

Il y a $n$ variables, une par ligne, qui indiquent dans quelle colonne se trouve la reine dans cette ligne. Cette modélisation a l'avantage d'incorporer déjà la contrainte d'une seule reine par ligne.

Il y a une contrainte pour chaque couple de lignes $(i,j)$ avec $i≠j$, qui demande que les reines ne peuvet pas s'attaquer. Donc les seuls couples de colonnes $(u,v)$ autorisées pour ces reines sont tels que u-v n'est pas $0$, ni $i-j$ ni $j-i$, traduisant le fait que les reines ne sont pas dans la même colonne, ni dans la même diagonale ou anti-diagonale.

Sur un échiquier donné, trouver une situation avec $n$ reines qui ne se mangent pas.

#### Programme pour les n reines

Supposons qu'on aie un module JOE`constraint_programming` qui résolve les problèmes sous contraintes, alors notre code ressemblerait à ça :

import sys
from constraint_programming import constraint_program

n = int(sys.argv[1])
N = range(n)

var = {i: set(N) for i in N} # domaine des variables
# var[i] = ensemble des colonnes possibles pour la reine en ligne i

P = constraint_program(var)
for j in N:
    for i in range(j):
        # les reines sur les lignes i et j sont en conflits
        forbidden = [0,i-j,j-i] # pas la meme ligne ni colonne ni diagonale
        P.add_constraint(i,j,{(u,v) for u in N for v in N if u-v not in forbidden})
        
sol = P.solve()

for i in N:
    for j in N:
        if sol[i] == j:
            print('#', end=' ')
        else:
            print('.', end= ' ')
    print()

Maintenant, codons le module de résolution:

class constraint_program:
    def __init__(self, var):
        self.var = var
        self.assign = {x: None for x in var}
        self.constr = {x: [] for x in var}
        for x in var:
            for y in var:
                if x != y and var[x] is var[y]:
                    raise "two variables must have distinct domain objects"

    def add_constraint(self, x, y, rel):
        self.constr[x].append((y, rel))
        self.constr[y].append((x, rel))

    def choose_var(self):
        x = None
        for y in self.var:
            if self.assign[y] is None and (x is None or (len(self.var[x]) > len(self.var[y]))):
                x = y
        return x

    def backward_check(self, x, u):
        for (y, rel) in self.constr[x]:
            v = self.assign[y]
            if v is not None and (u, v) not in rel:
                return False
        return True

    def solve(self):
        x = self.choose_var()
        if x is None:
            return self.assign
        for u in self.var[x]:
            if not self.backward_check(x, u):
                continue
            self.assign[x] = u
            sol = self.solve()
            if sol is not None:
                return sol
            self.assign[x] = None

>>> python3 nreines.py 10
# . . . . . . . . . 
. . # . . . . . . . 
. . . . . # . . . . 
. . . . . . . # . . 
. . . . . . . . . # 
. . . . # . . . . . 
. . . . . . . . # . 
. # . . . . . . . . 
. . . # . . . . . . 
. . . . . . # . . . 

Par exemple on aura :
$$constr[2] = \{0: \{(0,1), (0,3), (1,0), (1,2), (2,1), (2,3), (3,0), (3,2)\}, ...\}$$
par exemple on n'a pas $(0,2)$ car on ne peut pas mettre la reine de la ligne 2 en colonne 0 et la reine de la ligne 0 en colonne 2 car elles se mangent (diagonale)
La suite de tuples sont les couples de position *possibles*

#### Problème !
L'exécution est très longue, il s'agira donc dans la suite d'optimiser le programme.

#### Vérification en avant
Maintenir les domaines des variables libres $x$ aux valeurs $u$ tel que pour toute contrainte $(x, y)$ avec $y$ affectée (à une valeur $v$) on ait que $(u,v)$ soit une paire de valeurs autorisées pour les variables $x, y$.
Dès qu'on affecte une variable, cela réduit le domaine des variables encore libres liées à la variable qui vient d'être affectée pour que ça reste compatible.
*Cela nécessite un mécanisme pour remettre les domaines des variables comme ils étaient à un moment donné.*

#### Mesures de temps de résolution

|n= | 24 | 32 |
|--- | --- | --- |
|backward_check |9 sec | >> 30min |
|forward_check | 0,2sec | 0,3 sec |

### Arc consistance

Nous introduisons une procédure qui va plus loin que la vérification en avant et qui propage des restrictions de domaines, afin de restreindre d'avantage l'instance et détecter plus rapidement des impossibilités s'il y a.

#### Définitions

Soit une variable $x$ et une valeur $u$ de son domaine. Pour une contrainte binaire $\left( x, y \right)$ on appelle le **support** pour l'affectation $x := u$, l'ensemble des valeurs $v$ du domaine de $y$, tel que l'affectation $x := u, y :=
v$ est acceptée par la contrainte.

On considère un programme par contraintes avec des contraintes binaires. Il défini un graphe, dont les sommets sont les variables et les arêtes correspondent aux contraintes. Une arête peut être vue comme deux arcs orientés opposés pour une version orienté du graphe.

Une instance de CSP est **consistante pour l'arc** $(x, y)$, si toute valeur $u$ du domaine de $x$, a un support dans dans le domaine de $y$.

Une instance est _non_ consistante pour l'arc $(x, y)$ si il existe une valeur $u$ dans le domaine de $x$ qui n'accepte aucun support pour $y$ (_i. e._ pas de valeur possibles pour $y$ si $x$ est affecté à $u$).

Une instance de CSP est **arc-consistante** tout court, si pour toute contrainte binaire $C$, l'instance est consistante pour les arcs $\left( x, y \right)$ et $\left( y, x \right)$ où $x, y$ sont les variables sur lesquelles $C$ porte.

On cherche donc à maintenir l'arc-consistance tout au long de la résolution.

Ce n'est pas très intéressant pour un programme par contrainte avec seulement des contraintes différentes.

Sans perte de généralité, on peut supposer que l'instance initiale est arc-consistante, dans le sens que chaque valeur $u$ du domaine d'une variable $x$ a un support dans toute variable liée. Par exemple pour la contrainte $x=y$ on peut supposer que les domaines de $x$ et de $y$ sont initialement identiques. Toutes les valeurs de la différence symmétrique peuvent être enlevés.

#### Exemple

Considérons le graphe suivant. Les sommets correspondent à des variables, et les arêtes à des contraintes portant sur deux variables. Après avoir affectée la variable $x_3$ (indiquée en jaune) la vérification en avant réduit le domaine des variables libres liées à $x_3$ (en orange) au support pour la valeur affectée.
L'instance a été rendue arc-consistante pour les arêtes indiquées en rouge.

graph {
    node [shape=circle]
    rankdir=LR;
    subgraph cluster_0 {
        label="variables affectées"
        x3 [color=yellow, style=filled]
        x1 -- x2 
        x2 -- x3
        x1 -- x3
    }
    subgraph cluster_1 {
        label="variables libres"        
        x8 -- x9
        x4, x5 [color=orange, style=filled]
        x4 -- x5
        x6 -- x7
        x4 -- x6
        x5 -- x7
    }    
    x1 -- x4
    x1 -- x6
        edge [style=bold,color=red]
    x3 -- x4
    x3 -- x5
}

Pour maintenir l'arc consistance de toute l'instance, ces réductions de domaines pourraient être propagés sur toute la composante connexe des variables libres liées à la variable $x_3$.

graph {
    node [shape=circle]
    rankdir=LR;
    subgraph cluster_0 {
        label="variables affectées"
        x3 [color=yellow, style=filled]
        x1 -- x2 
        x2 -- x3
        x1 -- x3
    }
    subgraph cluster_1 {
        label="variables libres"        
        x8 -- x9
x4, x5, x6, x7 [color=orange, style=filled]
        edge [style=bold,color=red]
        x4 -- x5
        x6 -- x7
        x4 -- x6
        x5 -- x7
    }    
    x1 -- x4
    x1 -- x6
        edge [style=bold,color=red]
    x3 -- x4
    x3 -- x5
}

#### Procédure Revise

L'ingrédient principal pour maintenir l'arc consistance — ou la vérification en avant — est la procédure `revise(x, y)`, qui rend l'arc $\left( x, y \right)$ consistant, et qui retourne vrai si le domaine de $x$ a été réduit. Elle réduit le domaine de $x$ aux valeurs $u$, tel qu'il existe une valeur $v\in D_y$ (le domaine de $y$) avec $(u,v)\in R_{xy}$ (la relation portant sur $x$ et $y$).

PROCEDURE REVISE(x,y):
//Le domaine de y a diminué, faut-il diminuer celui de x ?
Pour toute valeur u du domaine de x:
    Si x:=u n'a pas de support dans y
        Enlever u du domaine de x
Retourner Vrai si le domaine de x a diminué

#### Algorithme AC1

Voici un premier algorithme pour établir l'arc consistance. Il appelle `revise(x, y)` pour toutes les paires de variables $\left( x, y \right)$ liées par une contrainte binaire, et répète cette boucle tant qu'un des appels retourne vrai.
En quelques mots : AC1 applique `revise(x,y)` sur l'ensemble des arcs jusqu'à atteindre un point fixe.

#### Algorithme AC3

Une amélioration possible pour la maintenance de l'arc consistance est d'appeler `revise(x, y)` seulement quand le domaine de $y$ a diminué, en particulier lors d'une affectation de $y$, quand le domaine a été réduit à un singleton. Cet algorithme travaille avec un ensemble de variables dont le domaine a diminué.

`AC3(y)` maintient l'arc consistance après une affectation à $y$. Initialement $Q = \{ y \}$. Puis tant que $Q$ n'est pas vide : $y = Q.dépile()$. Pour toute variable $x$ liée à $y$, appeler `revise(x, y)`. Si l'appel retourne vrai, alors ajouter $x$ à $Q$ s'il n'y est déjà.

Dans ce contexte il peut être une bonne idée de modifier la fonction `forward_check` pour qu'elle fasse appel à `revise` et retourne l'ensemble des variables dont le domaine a été affecté. Ainsi cet ensemble sera le départ pour la procédure AC3.

PROCEDURE AC3(Q):
//Q ensemble de variables dont le domaine a diminué
Tant que Q n'est pas vide:
    y <- Q.pop()
    pour tout x lié à y par une contrainte:
        si Revise(x,y):
            ajouter x à Q

#### Algorithme AC4

Plutôt que de vérifier régulièrement qu'une valeur $v \in D_y$ a encore un support dans $D_x$ à chaque fois que $D_x$ a diminué, on peut travailler avec une structure de données plus subtile, qui stocke pour chaque triplet $( x, u, y )$, le support de $x := u$ dans le domaine de $y$, c'est-à-dire $\{ v : v \in D_y, \left( u, v \right) \in R_{x, y} \}$. Notons `support[x, u, y]` cette donnée.

Cet algorithme travaille alors avec un ensemble $Q$ de couples variable-valeur. Initialement pour établir l'arc consistance $Q$ contient tous les couples $\left( x, u \right)$ tel qu'il existe une variable $y$ avec `support[x, u, y]` $= \emptyset$. Alors que pour maintenir l'arc consistance après une affectation $x := u$, la valeur initiale pour $Q$ sera
\\[
\left\{ \left( x, w \right) : w \in D_x, w \neq u \right\},
\\]
où $D_x$ est le domaine de $x$ avant l'affectation.

Puis tant que Q n'est pas vide, on extrait un couple $\left( x, u \right)$ de $Q$ : Puis on supprime $u$ du domaine de $x$, et pour chaque variable $y$ et valeur $v \in \textrm{support} \left[ x, u, y \right]$, on enlève $u$ de support$[y, v, x]$. Si jamais cet ensemble est devenu vide, alors on ajoute $\left( y, v \right)$ à $Q$.

PROCEDURE AC4(Q):
//Utilise les structures de données 
//support[x,u,y] = ensemble des valeurs v du domaine de y compatibles avec x:=u
//Q = pile de paires (variable, valeur) tq (x,u) dans Q indique que la valeur u doit disparaitre du domaine de x
Tant que Q non vide
    (x,u)<- Q.pop()
    Enlever u du domaine de x
    //mettre a jour le support
    Pour toute variable y liée à x
        Pour tout v dans support[x,u,y]
            Enlever u de support[y,v,x]
            Si support[y,v,x] est vide
                Ajouter (y,v) à Q

> Exercice:
> Soit $t$ le nombre de contraintes, $n$ le nombre de variables, et $m$ une borne supérieur sur la taille des domaines. Analysez la complexité en pire des cas pour les procédures Revise, AC1, AC3 et AC4.

**Complexité**

On note $d$ le degré max, c'est-à-dire le nombre max de variables liées à une variable fixée, $n$ le nombre de variables et $m$ la majoration de la taille des domaines des variables.

* `revise` en $O(m^2)$ sans utiliser la structure de données de AC4 (car vérifier sur $y$ a un support pour $x:=u$ est en $O(m)$).
* `AC3` en $O(ndm^3)$ car on va passer au plus $nm$ fois dans la boucle `while` principale (total des domaines).
* `AC4`en $O(ndm^2)$ car `support`contient $ndm$ variables avec chacune $m$ valeurs possibles qui diminue à chaque fois.

## Programmation linéaire
_1947 par Dantzig, Stigler Diet Problem (21 contraintes, 77 variables) => Simplex Algorithme (fonctionne rapidement en pratique mais exponentiellement dans le pire des cas)_
_1979 par Lenoid Katchian, méthode ellipsoïde_
_1984 par Narendra Karamakar, méthode de point intérieur => en temps polynomial dans le pire des cas_

### Vocabulaire
Si on a un nombre fini de variables continues $x_1,...,x_n$, toutes les contraintes sont de la forme $a_1x_1 + ... +a_nx_n \geq b$.
Objectif : minimiser $c_1x_1+...+c_nx_n$ (ou maximiser en multipliant tous les coefficients par $-1$)

#### Variantes
On peut avoir des contraintes d'égalité $a_1x_1+...+a_nx_n = b$ équivalent à $a_1x_1 + ... +a_nx_n \geq b \land - a_1x_1 - ... - a_nx_n \geq -b$
On ne peut pas avoir de contraintes avec des inégalités strictes.
On pourrait aussi avoir un objectif de maximisation (multiplier les coefficients par -1).

#### Représentation graphique


Chaque contrainte définit un demi plan et l'intersection de ces plans définit l'espace des solutions. Cet espace, convexe, est le **polyèdre** et si le polyèdre est borné dans toutes les directions il est appelé un **polytope**. Ses côtés sont des **faces** (appelées arrêtes si de dimension 1) et ses sommets représentent des solutions extrêmes.
Si le polyèdre est non vide et borné dans la direction de l'objectif (direction à optimiser), alors il existe une solution optimale fini au programme linéaire. Dans ce cas cas **il y existe un sommet du polyèdre qui est une solution optimale**. Comme le polyèdre est un espace convexe, toute combinaison affine de deux solutions est également une solution.

### L'algorithme du Simplex en deux mots

- Le polyèdre décrit un graphe dont les sommets sont les sommets du polyèdre. On appelle **voisinage** un couple de sommets reliés par une arrête.
- L'algorithme choisit un sommet comme point de départ
- et tant que possible va vers un point de son voisinage qui améliore strictement la valeur objectif

#### Comment trouver un sommet du polyèdre ?
En résolvant un autre programme linéaire.

`LP_initial` : $min \sum_{i=1}^{n} c_ix_i$ tq $\forall j=1,..., m: \sum_{i=1}^{n} a_{ij}x_i \geq b_j$

`Nouveau_LP` : $min \sum_{j=1}^{n}\lambda_j$ tq $\forall j=1,..., m, \lambda_j \geq 0, \sum_{i=1}^{n} a_{ij}x_i + \lambda_j \geq b_j$

Solution initiale : $x_i = 0, \lambda_j = b_j$

#### La programmation linéaire en pratique

graph RL
A[Solver, p.ex. Gurobi]
B[API] --> A
C[Fichier .LP ou .MPS] --> A
D[Modeleur, p.ex. AMPL] --> A
E[Fichier .MOD et .DAT] --> D

Implémentation en général de l'algorithme de Simplex:

- GLPK
- SCIP
- lp_solve
- CPLEX
- Gurobi
- or-tools
- GnuMathProg (GMPL)
- AMPL -> Celui qu'on utilisera aujourd'hui

#### Variantes (suite)
forme normale $min \{c^{\top} x|Ax \geq b, x \geq 0\}$

Si vous avez un LP avec une variable $x_i$ sans contrainte de non-négativité, vous pouvez vous rammener le problème à la forme normale en remplacant $x_i$ par 2 variables $X_i^X$ et $X_i^n$ avec
$X_i^n \geq 0, X_i^p \geq 0$
et toute occurence de $X_i$ est remplacée par
$X_i^p - X_i^n$

### Exemples
#### Plus court chemin dans un graphe entre une source et une destination

Soient $G(V,E)$ un graphe, des poids $w: E \to \mathbb{N}$ et $s, t\in V$
On cherche le max $X_t - X_s$ tel que pour chaque arête $(u,v)\in E$, $$X_u - X_v \leq w(u,v)$$ $$X_v - X_u \leq w(u,v)$$

#### Plus court chemin dans un graphe entre une source et toutes les destinations

$$
G(V,E) ; w : E \to \mathbb{N}, s \in V
$$
$$
max \sum_{v \in V, v \not=s} X_v
$$

avec $X_s = 0$ et $(u,v)\in E$
$$X_u - X_v \leq w(u,v)$$ $$X_v - X_u \leq w(u,v)$$

Liens vers l'exercice AMPL: http://www-desir.lip6.fr/~durrc/Iut/optim/ampl/

#### Variante
Si on ajoute des contraintes d'intégrité sur certaines variables, on obtient un **programme linéaire à variables entières (MiP)** dont la résolution est NP-Difficile en pire des cas.
En AMPL :
<pre>
var X binary
^
| Se spécifie avec ce mot clé
</pre>

## Dualité

> cette section est prise du livre [*Approximation Algorithms*](https://doc.lagout.org/science/0_Computer%20Science/2_Algorithms/Approximation%20Algorithms%20%5BVazirani%202010-12-01%5D.pdf) par Vijay Vazirani

Considérons le programme linéaire suivant.

\begin{align*}
\min\: & 7x_1 + x_2+5x_3
\\
s.t.\: & x_1 -x_2+3x_3 \geq 10
\\
& 5x_1 +2x_2 -x_3 \geq 6
\\
&x_1,x_2,x_3 \geq 0
\end{align*}

Notons $\mathbf{z^*}$ la solution optimale. Comment se convaincre que $\mathbf{z^*} \leq 30$ ? Il suffit d'exhiber une solution, par exemple $(x_1,x_2,x_3)=(2,1,3)$ et vérifier qu'elle satisfait bien toutes les contraintes. Comme sa valeur est 30, on a montré que la solution optimale est au plus 30.

Bien, mais comment donner des bornes inférieures sur $\mathbf{z^*}$ ? Par exemple on voit que les coefficients de chaque variable dans la fonction objective dominent les coefficients de la première contrainte. Donc comme les variables sont non-négatives on a
$$
7x_1 + x_2+5x_3 \geq x_1 -x_2+3x_3
$$
et donc $\mathbf{z^*} \geq 10$, la partie de droite de cette contrainte. On arrive a une meilleure borne inférieure si on somme ces deux contraintes~:
\\[
7x_1 + x_2+5x_3 \geq (x_1 -x_2+3x_3) + (5x_1 +2x_2 -x_3) \geq 16.
\\]

Et en général on cherche deux coefficients non-négatifs $y_1,y_2$ pour pondérer ces contraintes, tel que pour chaque variable le coefficient de la fonction objective domine le coefficient de la somme pondérée des contraintes. Trouver le meilleur choix des contraintes revient à résoudre le PL suivant

$$
\begin{align*}
\max\: & 10y_1 + 6y_2
\\
s.t.\: & y_1 +5y \leq 7
\\
& -y_1 + 2y_2\leq 1
\\
& 3y_1 - y_2\leq 5
\\
&y_1,y_2 \geq 0
\end{align*}
$$

En général du dual d'un PL primal $$\min\{ c^T x : Ax \geq b, x\geq 0\}$$ est le PL $$\max\{ b^T y : A^T y \leq c, y\geq 0\}.$$ On a les propriétés suivants.

Le dual du dual est de nouveau le programme linéaire primal.

### Théorème de dualité

Le PL primal est sans solution fini ssi le PL dual n'a pas de solution bornée. Le PL primal a un optimum fini ssi le PL dual a un optimum fini. Dans ce cas
\\[
\min\{ c^T x : Ax \geq b, x\geq
0\} = \max\{ b^T y : A^T y \leq c, y\geq
0\}.
\\]
La version faible du théorème de dualité ne demande que l'inégalité $\min\{\ldots\} \geq \max \{\ldots\}$.

#### Tableau de correspondance

|Primal | Dual|
|--- | --- |
|max | min |
|min | max |
| contrainte | variable |
| variable | contrainte |
| min contrainte $\geq$ | max variable non négative|
| contrainte = | variable sans containte de signe |

#### Exemple : s-t-flot maximal
Entrée :

* $G(V,A)$
* capacités : $c : A \to N$
* source $s\in V$
* puits $t \in V$

##### PL primal
$$\max \sum_{v\in \delta^+(s)} x_{vs} - \sum_{i\in \delta^-(s)} x_{us} \\
\forall v \in V \setminus \{s,t\} : \sum_{u\in \delta^+(s)} x_{uv} - \sum_{i\in \delta^-(v)} x_{uv} = 0 \\
\forall uv \in A 0 \leq x_{uv} \leq c(u,v)$$

Les variables sont les $x_{uv}$. On multiplie la première contrainte par $y_v$ et la deuxième par $z_{uv}$ et on obtient le PL dual

##### PL dual

$$min \sum_{uv \in A} c(u,v)z_{uv} \\
\forall uv \in A, \{u,v\} \cap \{s,t\} = \emptyset : z_{uv} + y_u - y_v \geq 0 \\
\forall sv \in A : z_{sv} \geq 1 \\
\forall vt \in A : z_{vt} \geq -1 \\
\forall uv \in A : z_{uv} \geq 0 \\
\forall v \in V \setminus \{s,t\}, y_v \ \text{est sans contrainte de signe}
$$

On reconnait un problème de coupe.

### Théorème de complementary slackness (complémentarité de marge)

Soient $\textbf{x,y}$ des solutions au PL primal et dual respectifs. Alors ils sont optimaux si et seulement si les conditions suivantes sont satisfaites.

primal complementary slackness condition
: Pour tout $i$, soit la $i$-ème variable dans $\textbf{x}$ est $\textbf{x}_i = 0$, soit la $i$-ème contrainte du PL dual est saturée (c'est-à-dire satisfaite avec égalité).

dual complementary slackness condition
: Pour tout $j$, soit la $j$-ème variable dans $\textbf{y}$ est $\textbf{y}_j = 0$, soit la $j$-ème contrainte du PL primal est saturée.

### Une interprétation physique

> Cette interprétation m'a été enseigné par Nikhil Bansal en 2012

Le dual de $\min\{ c^T x: Ax\geq b\}$ est $\max\{ b^T y: Ay=c, y\geq 0\}$. Considérez l'espace primal, et une particule à une position $x$ dans le polyèdre. On veut minimiser $c^T x$, donc on imagine une force de gravité qui agit sur la particule dans la direction $-c$. Maintenant la physique fait que la particule bouge dans cette direction, peut-être touche le bord du polyèdre, glisse le long du bord, jusqu'à atteindre une position stable où elle ne peut plus tomber plus.


Mais la physique dit que si la particule est stable, alors il y a des forces qui compensent la gravité. D'où viennent ces forces? Chaque contrainte de la forme $a_ i^T x \geq b_i$ (la $i$-ème ligne de $Ax\geq b$) peut agir dans la direction $a_i$ sur la particule en réponse de la gravité exercé sur elle. Donc il existe des coefficients non-négatifs $y_i$ tel que $-c + \sum y_i a_i = 0$, donc tel que les forces agissant sur $x$ s'annulent.

Le point important est que seules les contraintes saturées par $x$ peuvent agir sur $x$, car elle correspondent à des faces du polyèdre touché par $x$. On retrouve ainsi les conditions du *dual complementary slackness*.

### Exemple : plus court chemin, source unique, toute destination

Entrée :

* G(V,A)
* pondération $w: A \to N$
* source $s \in V$

#### PL primal
$$\max \sum_{v \in V \backslash \{s\}} (y_v-y_s)\\
\forall (u,v) \in A : y_v - y_u \leq w(u,v) \\
\forall v \in V y_v \text{ est une variable libre de contrainte de signe.}$$

#### PL Dual
$$\min \sum_{(u,v) \in A} w(u,v)\cdot X_{uv} \\
\forall v \sum_{(u,v) \in A} X_{uv} - \sum_{(v,u) \in A} X_{vu} =
\left\{
\begin{array}{ll}
1 \text{ si } v \neq s\\
- (|v|-1)
\end{array}
\right. \\
\forall (u,v) \in A X_{uv} \geq 0
$$

### Problème de modélisation
Soit un restaurant ouvrant 7j/7. Voici sa demande en personnel
| Lu | Ma | Me | Je | Ve | Sa | Di |
| --- | --- | --- | --- | --- | --- | --- |
| 14 | 13 | 15 | 16 | 19 | 18 | 11 |

Chaque personne travaille 5 jours de suites puis s'arrête pendant 2 jours et ainsi de suite.
But : minimiser le personnel tout en satisfaisant les demandes

On pose $X_j$ le nombre de personnes à embaucher commençant leur période le jour $j$.

$$
X_{Lu} \phantom{+X_{Ma}+X_{Me}} + X_{Je} + X_{Ve} + X_{Sa} + X_{Di} \geq 14 \\
X_{Lu} + X_{Ma} \phantom{+X_{Me}+X_{Je}} + X_{Ve} + X_{Sa} + X_{Di} \geq 13 \\
... \\
\phantom{X_{Lu}+X_{Je}+}X_{Me} + X_{Je} + X_{Ve} + X_{Sa} + X_{Di} \geq 11 \\
X_{Lu}, X_{Ma}, X_{Me}, X_{Je}, X_{Ve}, X_{Sa}, X_{Di} \geq 0
$$

### Exemple couplage biparti
Entrée : $G(U,V,E), E \subseteq U \times V, \omega: E \to R, |U| = |V|$

Sortie : couplage $M \subseteq E$ avec $|M| = |U|$ et $\sum_{e \in M} \omega (e)$ maximal.

#### Programme Linéaire
$$\sum_{e \in E} w(e) x_e$$

tel que

$$\forall u \in U : x(\delta(u))=1\\
\forall v \in V : x(\delta(v)) = 1\\
\forall e \in E : x_e\geq 0\\
\text{avec } x(\delta (u)) = \sum_{v \in V, uv \in E} x_{uv}$$
**Toute solution point extrême est entière.**

$x$ est une solution point extrême si $\nexists y \neq 0 : x + y$ et $x - y$ soient des solutions du programme linéaire, ou encore $\forall y\neq 0: x+y$ et $x-y$ ne sont pas des solutions au programme linéaire.

### Lemme
Soit le polytope $P = \{x: Ax \geq b, x \geq 0\}$ et supposons que $min \{c^\top x |x \in P\}$ existe et soit fini.
Alors pour tout $x\in P$, $\exists x' \in P$ qui est point extrême et tel que $c^\top x' \leq c^\top x$

##### Preuve
Supposons que $x$ est une solution entière qui ne soit pas point extrême.
Alors $\exists y \neq 0$, avec $x + y \in P$ et $x - y \in P$, autrement dit $A(x+y)\geq b, x+y \geq 0$ et $A(x-y)\geq b, x-y \geq 0$.


Comme x est optimal, $c^\top x \leq c^\top (x+y)$ et $c^\top x \leq c^\top (x-y) \Rightarrow c^\top y = 0$.
Comme $y \neq 0, \exists i, y_i > 0$ (sans perte de généralité).
Considérons $x+\lambda y, \text{avec } \lambda \geq 0$, qu'on augmente graduellement jusqu'à ce qu'une des deux choses arrive :

- Une contrainte $A_i(x+\lambda.y) \geq b_i$ devient saturée
- Soit $X_i + \lambda.y \geq 0$ devient saturée

Cela arrive à
$$\lambda^* = min
\left\{
\begin{array}{ll}
min_{i:A_ix>b \text{ et } A_iy < 0} \frac{A_ix-b_i}{-A_iy}\\
min_{j:y_j<0} \frac{x_j}{-y_j}
\end{array}
\right. \\
$$

### Proposition

$X + \lambda^{*}y$ a la même valeur objectif que $X$ et :
- soit a une variable de plus à zéro,
- soit sature une contrainte de plus que $X$.

#### Preuve
Comme $x+y \geq 0$ et $x-y \geq 0$, on a : $x_j = 0$ et $y_j = 0$ également donc en remplaçant successivement $x$ par $x+\lambda^*y$, on doit arriver à une solution point extrême optimale.

### Notation
Soit $A^{=}_X$ la sous-matrice de $A^{=}$ restreinte aux colonnes avec $X_j \neq 0$

### Lemme
$X$ est une solution point extrême $\Leftrightarrow$ $A^{=}_X$ a des colonnes linéairement indépendantes (*fullrank*).

#### Preuve
- $\Leftarrow$
Soit $x$ une solution qui n'est pas point extrême. Alors :
$$
\exists y \neq 0\\
x+y, x-y \in P\\
A^{=}_X = 0
$$
donc $A^{=}$ a des colonnes linéairement dépendantes. Mais comme $x_j = 0 \Rightarrow y_j = 0$, ces colonnes sont dans $A^{=}_x$
- $\Rightarrow$
Supposons que $A^=_x$ a des colonnes linéairement dépendantes. Donc $\exists y \neq 0, A^=_x y = 0$. On complète $y$ avec des zéros pour obtenir un vecteur de même dimension que $x$. Désormais $A^= y = 0$ et $x_j = 0 \Rightarrow y_j = 0$. Pour $\epsilon > 0$ suffisemment petit, $x+\epsilon y \text{ et } x - \epsilon y$ sont également des solutions.

### Lemme du Rang
Soit $x$ une solution point extrême avec $x_j>0, \forall j$. Alors le nombre de contraintes saturées de la forme $A_ix=b_i$ linéairement indépendants est égal au nombre de variables.

#### Preuve
On a $A^=_x = A^=$ par le lemme précédent. $A^=$ a le rang colonne plein. Mais le rang colonne d'une matrice est égal à son rang ligne, et le nombre de colonnes est égal au nombre de variables ici. Donc le nombre maximal de contraintes saturées linéairement indépendantes est égal au nombre de variables.

### Problème de couplage
$G(U,V,E), w: E \to R$

$$\text{max }\sum_{e \in E} w(e) x_e$$

tel que

$$\forall u \in U : x(\delta(u))\leq 1\\
\forall v \in V : x(\delta(v)) \leq 1\\
\forall e \in E : x_e\geq 0$$

Soit $x$ une solution point extrême du programme linéaire et $x_e>0, \forall e \in E$.
Alors $\exists W \in U \cup V$ avec
1. $x(\delta(v)) = 1, \forall v \in W$
2. les vecteurs $\{\chi(\delta(v)): v\in W\}$ sont linérairement indépendants
3. $|W| = |E|$

Voici un algorithme itératif pour construire (et donc prouver l'existence) d'une solution optimale point entière.

F <- ensemble vide
Tant que E non vide
    Trouver une solution point extrême x au programme linéaire
    Enlever toutes les arêtes e avec x_e = 0
    Si il existe e = uv avec x_e = 1 Alors
        Ajouter e à F
        Enlever u, v du graphe
Retourner F

Pour prouver que l'algorithme progresse, on va montrer qu'à tout moment $\exists e$ avec $x_e = 0 \text{ ou } x_e = 1$
Pour une preuve par contradiction, supposons que $\forall e = 0< x_e<1$. D'après le lemme précédent, $\exists W \subseteq U \cup V$ avec $|W| = |E|$ et les contraintes associées à $W$ sont linéairement indépendantes.
Notons $d_E(v)$ le degré de $v$ à ce moment de l'algorithme.

#### Proposition
$d_E(v) = 2$ pour $v\in W$ et $d_E(v) = 0$ pour $v \notin W$

##### Preuve
$$2|W| = 2|E| = \sum_{v\in U \cup V} d_E(v) \geq \sum_{v \in W} d_E(v)$$
Or $\forall v \in W d_E(v) \geq 2$
donc
$$2|W| \geq 2|W|$$
toutes les inégalités sont en fait des égalités.

## La méthode itérative
Permet de prouver par induction qu'un certain programme linéaire est entier.

#### Plus court chemin entre 2 sommets

Entrée : $G(V,A)$ orienté, $\omega : A \rightarrow \mathbb{R}^+$

Problème linéaire: $min \sum_{a \in A} \omega_a * x _{a}$
$$\forall v \in V : \sum_{u : uv \in A} x_{uv} - \sum_{u: uv \in A} x_{vu} = \begin{cases}-1 & \mbox{si } v = s \\ +1, & \mbox{si } v = t \\ 0 &\mbox{sinon} \end{cases} $$
$$\forall a \in A : 0 \leq x_a \leq 1$$

### Algorithme itératif

P = Ø
Tant que il existe au moins deux sommets :
    x := solution optimale point extrème au programme linéaire
    Enlever tout a avec x_a = 0 et les sommets isolés
    Si il existe un arc a avec x_a = 1:
        Ajouter a à P
        Contracter a
Retourner P

Contracter l'arc $a=(u,v)$ signifie réunir les deux sommets $u$ et $v$ en un seul sommet tout en gardant les arcs entrant et sortant de $u$ et $v$. La somme des deux ensembles des arcs qui entrent (sortent) dans $u$ et $v$ est égale à l'ensemble des arcs qui entrent (sortent) dans la contraction $(u, v)$.

### Lemme (Algorithme peut progresser)
Il existe toujours un arc $a$ avec $x_a = 0 \text{ ou } x_a = 1$.

#### Preuve par contradiction
Supposons $0 < x_a < 1$. Par le lemme du rang : $\exists W \subseteq V \text{ avec } |W| = |A|$ et les contraintes associées aux sommets $v\in W$ sont linéairement indépendantes donc $|W| \leq |V|-1$.

Or chaque sommet n'est pas isolé et adjacent à au moins deux arcs, car la partie droite de sa contrainte est entière et la partie gauche somme les valeurs (fractionnelles) sur les arcs adjacents.

Ceci impliquerait $|A| \geq |V|$, ce qui contredit $|A| = |W| \leq |V| - 1$.

Cet algo s'applique aux problèmes suivants :
- Vertex Cover
- Arbre de couverture minimale
- Arbre de couverture minimale avec degrés bornés

### Vertex Cover

$G(V,E)$, $c : V \rightarrow \mathbb{R}^+$.
Choisir $S \subseteq V$ avec $c(S)$ minimal tel que $\forall uv \in E, u \in S \text{ ou } v \in S$
PL : $min \sum_{v \in V} c_v * x_{v}$
tq $\begin{cases}\forall uv \in E: x_u + x_v \geq 1 \\ \forall v \in V : x_v \geq 0 \end{cases}$

#### Théorème [Nemhauser Trotter]
Pour $x$ une solution point extrême à ce PL, on a $\forall v \in V, x_v \in \{0,\frac{1}{2}, 1\}$.

#### Caractérisation des solutions point extrême
Soit $x$ solution point extrême avec $x_v > 0$. Alors par le théorème de rang, il existe $F \subseteq E$, les contraintes associées aux $e \in F$ sont saturées et linéairement indépendantes, et $|F| = |V|$.

#### Algorithme itératif

W = Ø
Soit x solution point extrême optimale
tant que E != Ø
    enlever v du graphe pour tout v avec x_v = 0
    pour tout sommet v avec x_v dans (0.5, 1)
        ajouter v à W
        enlever v du graphe
retourner W

Si l'algo termine alors il produit une solution W dont la valeur est au plus 2 fois la solution optimale.

#### Lemme (Progrès)

L'algorithme peut toujours trouver un sommet $v$ avec $x_v \in \{0, \frac{1}{2}, 1 \}$

##### Preuve

Supposons $\forall v \in V, 0<x_v<1$
Par cette caractérisation $\exists F \subseteq E$ avec les propriétés annoncées.
Supposons que $G$ est connexe (sinon appliquer l'argument sur chaque composante connexe).

Comme $|F| = |V|$, il existe un cycle $C$ de longueur impaire (car sinon en additionant les contraintes associées avec des poids alternant +1 et -1 on obtient 0 et la dépendance des contraintes)

La seule manière de saturer les contraintes associées aux arêtes de $C$ est de mettre la valeur $\frac{1}{2}$ aux sommets de C. Cette valeur se "propage" au reste du graphe.

#### Arbre de couverture minimale
$G(V,E)$, $c : V \rightarrow \mathbb{R}^+$ connexe non orienté.

##### Programme Linéaire à élimination de soustours

$min \sum_{e \in E} c_e * x_{e}$
tq $\forall S \subset V, S \neq \emptyset, x(E(S)) \leq |S| -1$
et $x(E(V)) = |V|-1$
et $\forall e \in E, x_e \geq 0$
notation: $x(E(S)) := \sum_{\substack {u,v \in E \\ u \in S \\ v \in S}} x_{uv}$

On peut résoudre en temps polynomial (en nombre de variables) un programme linéaire, pouvu qu'il existe un oracle de séparation pour le programme linéaire. Un tel oracle prend en entrée une solution potentielle x et il répond en temps polynomial si x satisfait toutes les contraines ou si x viole une contrainte, et dans ce cas l'oracle exhibe cette contrainte.

Plan:
- oracle de séparation
- supermodularité
- la famille $\mathcal{F}$ des contraintes saturges est clos par intersection et réunion
- famille laminaire
- majorer la taillle de la famille laminaire
- algorithme itératif
- Preuve de progression de l'algorithme

###### Oracle de séparation

trouver $S\subseteq V$ avec $|S| -1 - x(E(S)) < 0 \\ \equiv |S| -1 +x(E(V)) - x(E(S)) < |V| - 1$

Pour tout $s,t \in V^2, s \neq t$ on va résoudre un prblème de s-t-coupe minimale. Construire un graphe $G$ orienté sur les mêmes sommets $V$. Toute arête $uv$ génère 2 arcs $u \leftrightarrows v$ de poids $\frac{x_{uv}}{2}$
Tout sommet $v \in V \setminus \{s,t\}$ génère $s \rightarrow v$ de poids $x(\delta(v))/2$ , et $v \rightarrow t$ de poids 1.

Considérons une s-t-coupe S, avec $s \in S, t \notin S$.

- les arêtes sortant de $S$ allant en $t$ contribuent pour $|S| -1$
- sortant de $S$ par $s$ contribuent pour $\sum_{v \notin S} x(\delta(v))/2$
- les aretes sortant de $S$ en dehors de $S$ contribuent pour $x(\delta(S))/2$

Au total
$$|S|-1+\underbrace{\frac{x(\delta(S))}{2}+\sum_{v\notin S}\frac{x(\delta(v))}{2}}_{\text{chaque arrête apparait ici sauf celles}\\ \text{dont les deux extrémités sont dans S}}
\\=|S|-1+x(E(V))-x(E(S))$$

donc si une de ces $\mathcal{O}(n^2)$ coupes a une valeur $< |V| -1$, alors on a identifié une contrainte saturée.

#### Lemme (Supermodularité)
$$\forall x,y \subseteq V:\\
\chi (E(x)) + \chi (E(y)) \leq \chi (E(x \cup y)) + \chi (E(X \cap y))$$
et on a égalité si $E(x \setminus y, y \setminus x) = \emptyset$

##### Notation
$F \subseteq E$
$\chi(F)$ vecteur dans $\mathbb{R}^E$ avec valeur 1 pour tout $e \in F$ et 0 partout ailleurs.

##### Preuve
On a $\chi (E(x)) + \chi (E(y)) = \chi (E(x \cup y)) + \chi (E(X \cap y)) - \chi (E(x \setminus y, y \setminus x)$

*Fixons* $x$ solution point extrème.
*Notons* $\mathcal{F} = \{S: \chi (E(S)) = |S]-1\}$
*Lemme* (preuve omise): $\mathcal{F}$ est clos par union et intersection.
*Notation* span($\mathcal{F}$) l'espace engendré par les vecteurs $\chi(E(S))$ pour tout $S$

$X, Y \subseteq V$ *intersectent* si: $X \cap Y \neq \emptyset, X \setminus Y \neq \emptyset, Y \setminus X \neq \emptyset$

$\mathcal{L} \subseteq \mathcal(F)$ est **laminaire** si $\forall X<Y \in \mathcal{L}, X \neq Y \Rightarrow X \text{ n'intersecte pas } Y$

#### Lemme

si $\mathcal{L} \subseteq \mathcal{F}$ est une famille laminaire et maximal (ie. tout ensemble de $\mathcal{F}\setminus \mathcal{L}$ intersecte un ensemble de $\mathcal{L}$) alors $\text{span}(\mathcal{L}) = \text{span}(\mathcal{F})$

##### Preuve par contradiction:
$\mathcal{L} \subseteq \mathcal{F}$ laminaire maximale mais $\text{span}(\mathcal{L}) \subsetneq \text{span}(\mathcal{F})$.

Pour tout $S \notin \mathcal{L}$ notons intersect$(S,\mathcal{L})$ le nombre de $T \in \mathcal{L}$ avec lesquels $S$ intersecte.

Soit $S \in \mathcal{F}$ avec intersect$(S,\mathcal{L})$ minimal et $\chi(E(S)) \notin$ span($\mathcal{L}$).
- On a intersect$(S,\mathcal{L}) \geq 1$ par maximalité de $\mathcal{L}$ donc $\exists T \in \mathcal{L}$ intersectant $S$.
- On a $S \cup T$ et $S \cap T$ dans $\mathcal{F}$ par clôture de ce dernier.

On va montrer intersect$(S \cup T,\mathcal{L}) <$ intersect$(S,\mathcal{L})$

On a que $T$ n'intersecte ni $S \cup T$ ni $S \cap T$ et donc n'est compté qu'à droite de l'inégalité.

Pour tout $R \neq T$, $R \in \mathcal{L}$, $R$ n'intersecte pas $T$. Si $R$ intersecte $S \cup T$ ou $S \cap T$ alors $R$ et $S$ s'intersectent.

Par le choix de S $S\cap T$ et $S\cup T \in \mathcal{L}$ cependant $\chi(E(S)) + \chi(E(T)) = \chi(E(S\cap T)) + \chi(E(S\cup T))$
tous sauf $\chi(E(S))$ sont dans span$(\mathcal{L})$ donc $\chi(E(S)) \in$ span$(\mathcal{L})$ contredisant le choix de $S$.

#### Lemme

Si $\mathcal{L}$ est une famille laminaire de $\mathcal{F}$ sans singletons alors $|\mathcal{L}| \leq |V| - 1$
*Preuve laissée au lecteur, par induction sur $|V|$*
> \insert{joli schéma avec des notes à l'oral}

#### Algo itératif

F = Ø
tant qu'il existe au moins 2 sommets:
    trouver une solution point extrême optimaleX
    enlever toute arête e avec x_e = 0
    trouver un sommet v avec seulement une arête e adjacente
        ajouter e à F
        enlever v du graphe
retourner F

#### Lemme(Progrès)

pour toute solution point extrème $x$ avec $\forall e, 0 < x_e$, il existe un sommet v de degré 1.

preuve par contradiction: si $\forall v, d(v) \geq 2$ alors $|E| = 1/2 \sum_{v}d(v) \geq |V|$.
Soit $\mathcal{L}$ une famille laminaire maximale d'ensembles $S$ dont la contrainte est saturée. Par le lemme de rang $|\mathcal{L}| =|E|$ ce qui contredit le lemme sur la cardinalité de $\mathcal{L}$

#### Lemme (Correction)

Algo retourne un arbre de couverture minimal.

*preuve*
Pour le pas (\*) on a $x_e=1$ pour l'arête sélectionnée. Le prog linnéaire donne :
$x(E(V \setminus \{v\})) \leq |V| -2$ et $x(E(V) = |V|-1$ donc $x(\delta(v)) \geq 1$ et $x(E(\{u,v\})) \leq 1$ pour $e=uv$
Soit $G'$ le graphe $G$ sans $v$. Par induction l'algo trouve un arbre de couverture minial $T'$ de $G'$. Ajouter $e$ à $T'$ donne un arbre $T$ qui couvre $G$ et la restriction de $x$ sur $E(G')$ est une solution au PL ($x_{res}$) par induction:
$c(T') \leq c(x_{res})$
$c(T) \leq c \cdot x_{res}+c_e = c \cdot x \Rightarrow T$ est optimal

# Ski rental problem (Spyros)

Pour des raisons de performance la suite est [ici](https://hackmd.io/fN65ccc1RB-dQHhEuc_Y6A)

# Blagues & citations (clairement un h1 était nécessaire)

## Hypercube

C'est un couple qui cherche à acheter une maison. Ils se trouvent devant un hypercube et l'un dit à l'autre :
> Tu en penses quoi de la maison que j'ai choisie ?

Ce à quoi le deuxième répond :
> Oui, elle est très bien, mais est-ce que tu penses que l'on a besoin d'autant de dimensions ?

## Psychanalystes
C'est deux pschanalystes qui se rencontrent dans la rue. L'un demande à l'autre :
> «Est-ce que tu sais aller à la gare de l'Est ?»
iew
Le second hésite et répond :
> «Non, je ne sais pas, mais ça fait du bien d'en parler.»

## Citations

> Vous êtes tous sur le DM c'est dommage, j'avais prévu de jolis exercices, si vous les ratez vous ratez la moitié de votre vie