مسابقة دكتوراه 2016 — Université des Sciences et de la Technologie Houari Boumediène (USTHB)

التمرين 1

Exercice 1 — Programme linéaire bi-objectif et solutions efficaces

#multiobjective-optimization#linear-programming#efficient-solutions#weighted-sum#pareto-front

On considère le programme linéaire bi-objectif suivant :

(P) \begin{cases} \min \{-2x_1 + x_2\} \\\\ \min \{-4x_1 - 3x_2\} \\\\ \text{s.c. } x_1 + 2x_2 \leq 10, \; x_1 \leq 5, \; x_1,x_2 \geq 0. \end{cases}

Écrire le programme linéaire paramétrique associé au problème $P$ , noté $LP(\lambda)$ .
Calculer l'ensemble des bases efficientes, l'ensemble des points extrêmes efficients, l'ensemble des arêtes efficientes $Eff_{P_\lambda}$ , l'ensemble de toutes les solutions efficientes $X_{eff}$ et l'ensemble de tous les vecteurs critères non dominés $Y_N$ .
Donner les équations des courbes paramétriques relatives aux valeurs critiques de $\lambda$ et retrouver graphiquement les résultats obtenus ci-dessus.
En utilisant le cône polaire semi positif, retrouver graphiquement les ensembles $X_{eff}$ et $Y_N$ dans l'espace des décisions et dans l'espace des critères.

◀الحل

1.

Le problème pondéré est :

LP(\lambda): \min \lambda(-2x_1+x_2) + (1-\lambda)(-4x_1-3x_2), \quad 0 \leq \lambda \leq 1

sous les mêmes contraintes.

2.

On détermine les sommets du polyèdre admissible : $(0,0)$ , $(5,0)$ , $(5,2.5)$ , $(0,5)$ . On calcule les images bi-objectif et on compare la dominance. Les points extrêmes efficients sont ceux non dominés. Les arêtes efficientes sont les segments joignant ces points où une combinaison convexe reste efficace.

3.

Les valeurs critiques de $\lambda$ sont celles où deux sommets donnent la même valeur pondérée. On les obtient en résolvant les égalités d'objectifs pondérés.

4.

Le cône polaire semi positif permet de caractériser les directions d'amélioration. Graphiquement, on retrouve le front de Pareto et l'ensemble efficace.

التمرين 2

Exercice 2 — Arbre de poids maximum et formulation en 0-1

#graph-theory#maximum-spanning-tree#0-1-linear-programming#greedy-algorithm

Soit $G=(V,E)$ un graphe simple et connexe et soit $p:E \to \mathbb{R}$ une application poids. On note $|V|=n$ et $E=\{e_1,e_2,\ldots,e_m\}$ et on suppose que $\forall i, p(e_i) \le p(e_{i+1})$ . Rappelons qu'un arbre est un graphe connexe et sans cycles et une forêt est un graphe sans cycles.

Donner au moins trois caractérisations différentes des arbres et montrer leur équivalence.
Montrer que dans un graphe connexe, si $T$ et $T'$ sont deux graphes partiels distincts qui sont des arbres, alors $T$ contient une arête dont le rajout à $T'$ crée un unique cycle.
Soit la famille $T_i$ définie par : $T_0=E$ , $T_i=T_{i-1}\setminus\{e_i\}$ si $i>0$ et le graphe $(V, T_{i-1}\setminus\{e_i\})$ est connexe, et $T_i=T_{i-1}$ sinon. Montrer que $T_m$ est un arbre de poids maximum dans $G$ .
Donner la complexité de l'algorithme pour déterminer $T_m$ .
Comment modifier cet algorithme pour déterminer une forêt de poids maximum de $G$ ?
Dans le graphe donné, donner un arbre et une forêt de poids maximums.
Prouver que si $\forall e,e'\in E, p(e) \ne p(e')$ , alors l'arbre de poids maximum est unique.
Montrer que si $G$ possède un cycle ayant une arête de poids inférieur à celui de toute autre arête de ce cycle, alors cette arête n'appartient à aucun arbre de poids maximum de $G$ .
On considère les deux programmes linéaires en nombres entiers $(F_1)$ et $(F_2)$ du sujet. Montrer qu'ils formulent le problème de l'arbre de poids minimum dans $G$ et que la formulation $(F_2)$ est meilleure.

◀الحل

1.

Caractérisations équivalentes d'un arbre $T$ :

$T$ est connexe et sans cycle.
$T$ est connexe et possède $n-1$ arêtes.
$T$ est sans cycle et possède $n-1$ arêtes.
Entre deux sommets quelconques de $T$ , il existe une unique chaîne.

Les équivalences sont classiques.

2.

Dans un graphe connexe, si $T \neq T'$ sont deux arbres, il existe une arête $e \in T \setminus T'$ . Comme $T'$ est connexe, ajouter $e$ à $T'$ crée exactement un cycle unique.

3.

L'algorithme supprime successivement les arêtes de plus faible poids quand leur suppression ne déconnecte pas le graphe. C'est la version inverse de Kruskal. À la fin, on obtient un sous-graphe connexe sans cycle, donc un arbre. Le raisonnement par échange montre qu'il est de poids maximum.

4.

Si on teste la connexité à chaque suppression par DFS/BFS, la complexité est $O(m(n+m))$ .

5.

Pour obtenir une forêt de poids maximum, on supprime la contrainte de connexité globale : on garde simplement l'absence de cycle. Cela revient à appliquer Kruskal décroissant sans imposer une seule composante.

6.

On sélectionne les arêtes de poids les plus élevés sans former de cycle.

7.

Si tous les poids sont distincts, l'algorithme glouton choisit de manière déterministe. Donc l'arbre de poids maximum est unique.

8.

Une arête strictement plus légère que toutes les autres d'un cycle ne peut appartenir à aucun arbre de poids maximum, sinon on pourrait l'échanger avec une arête plus lourde du cycle et augmenter le poids total.

9.

$(F_1)$ et $(F_2)$ sont des formulations 0-1 classiques du problème de l'arbre de poids minimum. $(F_2)$ est plus forte car ses contraintes de coupures donnent une relaxation linéaire plus serrée.

التمرين 2

Exercice 2 — Efficacité au sens multiobjectif et séparation par pondération

#multiobjective-optimization#efficiency#weighted-sum#scalarization

Soit $x^0$ une solution réalisable de l'ensemble $X = \{x \in \mathbb{R}^n : Ax=b, x \geq 0\}$ et $(P)$ le problème multi-objectif défini par $\min\{Cx : x \in X\}$ où $C \in \mathbb{R}^{r \times n}$ . Montrer que :

x^0 \text{ est une solution efficiente si et seulement si il existe } \lambda \in \mathbb{R}_+^r \setminus \{0\} \text{ tel que } \lambda^T Cx^0 \leq \lambda^T Cx, \; \forall x \in X.

◀الحل

C'est la caractérisation classique des solutions efficaces supportées.

$\Rightarrow$ : si $x^0$ est efficace et $X$ est polyédral convexe, alors l'image $CX$ est convexe. Le cône d'amélioration $-\mathbb{R}_+^r$ ne coupe pas $Cx^0 - CX$ sauf en 0. Par théorème de séparation, il existe un hyperplan défini par $\lambda \in \mathbb{R}_+^r \setminus \{0\}$ tel que $\lambda^T Cx^0 \leq \lambda^T Cx$ pour tout $x \in X$ .

$\Leftarrow$ : si une telle pondération existe, aucun $x$ ne peut strictement améliorer toutes les composantes, sinon on aurait $\lambda^T Cx \lt \lambda^T Cx^0$ , contradiction.

\boxed{x^0 \text{ efficace} \iff \exists \lambda \ge 0, \lambda \ne 0, \; \lambda^T Cx^0 \le \lambda^T Cx, \forall x \in X}\n$$

التمرين 3

Exercice 3 — Ordonnancement en binômes et coloriage de graphe

#graph-theory#scheduling#coloring#optimization

Exercice 3. Dans une entreprise, l'ensemble des ouvriers $O$ doivent exécuter un certain nombre de tâches pour achever un projet. L'ensemble de toutes les tâches possibles étant $T$ . On désire que tous les ouvriers qui doivent exécuter la tâche $t$ le fassent simultanément. Chaque ouvrier ne pouvant se présenter qu'à une tâche au plus chaque semaine. Le problème consiste à chercher le nombre minimum de semaines nécessaires pour terminer toutes les tâches (i.e. le projet). Présenter une modélisation mathématique de ce problème sous forme d'un outil de la théorie des graphes.

◀الحل

On construit un graphe de conflits $G = (T,E)$ dont les sommets sont les tâches. Deux tâches $t_1, t_2$ sont reliées par une arête si elles nécessitent au moins un même ouvrier, donc ne peuvent pas être exécutées la même semaine.

Chercher le nombre minimal de semaines revient à colorier les sommets de $G$ avec un nombre minimal de couleurs, chaque couleur représentant une semaine.

\boxed{\text{Nombre minimal de semaines} = \chi(G)}

التمرين 4

Exercice 4 — Planarité, triangulation, nombre chromatique et graphe parfait

#graph-theory#planar-graphs#chromatic-number#perfect-graphs#clique-number

Soit $G=(V,E)$ un graphe simple, connexe et non orienté. On note $\chi(G)$ le nombre chromatique, $\omega(G)$ la cardinalité d'une clique maximum, $\alpha(G)$ la cardinalité du plus grand stable, et $\theta(G)$ la cardinalité d'une partition minimum en cliques.

Montrer que $\omega(G) \leq \chi(G)$ et en déduire que $\alpha(G) \leq \theta(G)$ .
Montrer que $\chi(G) \alpha(G) \geq |V(G)|$ .
Montrer que $\chi(G) \leq \Delta(G)+1$ .
a) Montrer que tout graphe planaire admet une triangulation. b) En supposant que tout graphe planaire admet au moins un sommet de degré \leq 5, montrer que si $G$ est planaire alors $\chi \leq 5$ .
a) Montrer que $K_5$ n'est pas planaire. b) Montrer que si $G$ est planaire et parfait alors $\chi(G) \leq 4$ et $\alpha(G) \leq 4$ .
Si $G$ est planaire non nécessairement parfait, a-t-on $\alpha(G) \leq 4$ ?

◀الحل

1.

Une clique de taille $k$ nécessite $k$ couleurs différentes, donc $\omega(G) \leq \chi(G)$ . Par passage au graphe complémentaire, $\alpha(G) = \omega(\bar G)$ et $\theta(G) = \chi(\bar G)$ , donc $\alpha(G) \leq \theta(G)$ .

2.

Une coloration en $\chi(G)$ classes de couleurs donne une partition en $\chi(G)$ stables, chacun de taille au plus $\alpha(G)$ . Donc $|V| \leq \chi(G)\alpha(G)$ .

3.

Par coloration gloutonne : chaque sommet a au plus $\Delta(G)$ voisins déjà colorés, donc $\Delta(G)+1$ couleurs suffisent.

4.a

En ajoutant des arêtes entre sommets non adjacents de chaque face de taille > 3, on triangule sans changer l'ensemble des sommets.

4.b

Par récurrence sur $|V|$ . En retirant un sommet de degré \leq 5, on colore le graphe restant avec 6 couleurs puis on recolore le sommet retiré. On obtient $\chi(G) \leq 6$ (et même 5 avec raffinement, mais le résultat standard donné ici suit du théorème des cinq couleurs).

5.a

$K_5$ n'est pas planaire par Euler : un graphe planaire simple vérifie $m \leq 3n-6$ . Or pour $K_5$ , $m=10 > 9$ .

5.b

Si $G$ est parfait, $\chi(G)=\omega(G)$ . Un graphe planaire ne contient pas $K_5$ , donc $\omega(G) \leq 4$ , d'où $\chi(G) \leq 4$ . Par complémentarité dans les graphes parfaits, on obtient aussi $\alpha(G) \leq 4$ sous l'hypothèse correspondante.

6.

Non. On peut avoir un graphe planaire avec grand stable, donc il n'y a pas de borne universelle $\alpha(G) \leq 4$ .

\boxed{\text{Non, } \alpha(G) \leq 4 \text{ n'est pas vrai en général}}