مسابقة دكتوراه 2017 — Université Abderrahmane Mira

التمرين 1

Exercice 1 — Voyageur de commerce et relaxation par 1-arbres

#traveling-salesman#integer-programming#one-tree

Soit $G=(V,E)$ un graphe simple non orienté muni de coûts $c_e$ .

Formuler le STSP comme un programme linéaire en nombres entiers.
Soit $v_1\in V$ . Un $1$ -arbre est un arbre sur $V\setminus\{v_1\}$ complété par deux arêtes incidentes à $v_1$ . a. Montrer que le $1$ -arbre minimum est une relaxation du STSP. b. Formuler cette relaxation.
Montrer que, pour $n\ge4$ , un $1$ -arbre qui n’est pas une tournée possède un sommet de degré au moins $3$ .
Résoudre par branch-and-bound l’instance

C=\begin{pmatrix}-&3&10&5\\-&-&9&2\\-&-&-&1\\-&-&-&- \end{pmatrix}.

◀الحل

\min\sum_{e\in E}c_ex_e

sous

\sum_{e\in\delta(v)}x_e=2, \qquad \sum_{e\in\delta(S)}x_e\ge2, \qquad x_e\in\{0,1\}.

Toute tournée est un $1$ -arbre, donc le minimum sur les $1$ -arbres est une borne inférieure.

La somme des degrés d’un $1$ -arbre vaut $2n$ . Si tous les degrés sont au plus $2$ , ils valent tous $2$ et le graphe est une tournée.

\boxed{1-2-4-3-1}

\boxed{z^*=16}