Chapter 1 Présentation des problèmes d'optimisation combinatoire

1.1 Modèle général

1.1.1 Programmation linéaire

Un problème d'optimisation exprimé sous la forme d'un programme linéaire en variables continues (Linear Program) [dW90, Teghem96] peut s'écrire sous la forme générale suivante (1.1) :

(1.1)

avec `Opt' pouvant signifier Minimiser ou Maximiser selon le problème traité.

Notons que les contraintes peuvent aussi être exprimées sous forme matricielle. Dans ce cas å_j=1ⁿ T_ij X_j D_i d_i, " i devient TX D d où T représente la matrice des contraintes. Dans la suite, les deux notations seront utilisées indifféremment.

Les variables utilisées dans ce problème prennent des valeurs réelles (quantité de produit ou temps par exemple). Le système de contraintes définissant un domaine éventuellement vide de solutions admissibles, l'objectif est d'obtenir la ou les solution(s) optimale(s) (quand il en existe) vis à vis de la fonction objectif. Des résultats d'algèbre linéaire ont montré que le domaine des solutions admissibles est convexe (sauf s'il est vide) et que la solution optimale est un sommet du domaine (ou une face s'il y a plusieurs solutions optimales).

1.1.2 Problèmes en variables entières

Cependant, dans de nombreuses situations réelles, des variables peuvent être astreintes au domaine des valeurs discrètes (nombre de pièces à produire par exemple). Ces problèmes sont dits en variables mixtes (Mixed Integer Linear Problem). Lorsque toutes les variables du problème sont entières, on parle d'un problème en variables entières (Integer Linear Program) [Teghem96] qui se présente sous la forme suivante (1.2):

é
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ë

`Opt' z =

j=1

C_j X_j

j=1

T_ij X_j D_i d_i

, " i

l_j £ X_j £ u_j

, " j

X_j entier

, " j

D_i Î {£ ; = ; ³}

, " i

ù
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
û

(1.2)

Contrairement aux problèmes en variables continues, la résolution de ces problèmes n'est généralement pas aisée pour deux raisons :

ce sont des problèmes NP difficiles
la propriété de convexité du domaine des solutions n'est plus valable.

1.1.3 Problèmes en variables binaires

Enfin, certains problèmes comportent uniquement des variables de type booléen (pour des décisions par exemple). La formulation algébrique de ces problèmes appelés 0-1ILP est la suivante (1.3) :

é
ê
ê
ê
ê
ê
ê
ê
ê
ê
ë

`Opt' z =

j=1

C_j X_j

j=1

T_ij X_j D_i d_i

, " i

X_j = (0 ;1)

, " j

D_i Î {£ ; = ; ³}

, " i

ù
ú
ú
ú
ú
ú
ú
ú
ú
ú
û

(1.3)

Même si une variable binaire peut-être considérée comme une variable aux valeurs restreintes à l'intervalle discret , les problèmes n'utilisant que des variables booléennes sont nombreux (par exemple des problèmes d'affectation, de transport, de transbordement) et font partie d'un domaine particulier appelé optimisation combinatoire [Sakarovitch84].

En plus des difficultés liées aux problèmes en variables entières ou mixtes, la principale difficulté de ces problèmes réside dans le grand nombre de variables nécessaires pour modéliser des situations réelles. Cependant certains problèmes présentent des structures particulières qui permettent de simplifier leur résolution.

1.2 Méthodes de résolution

1.2.1 Méthodes exactes

Les méthodes de résolution exactes sont nombreuses et se caractérisent par le fait qu'elles permettent d'obtenir une ou plusieurs solutions dont l'optimalité est garantie.

Parmi ces méthodes, on peut remarquer l'algorithme du simplexe qui permet d'obtenir la solution optimale d'un problème en parcourant la fermeture convexe de l'ensemble de recherche (ensemble des solutions admissibles) et ce en passant de sommet en sommet. Malgré une complexité mathématique dans le pire des cas non polynomiale, il permet de résoudre la plupart des problèmes rapidement. Cependant il ne peut s'appliquer qu'aux problèmes ayant la propriété de convexité c'est-à-dire aux problèmes en variables continues ou à des problèmes en variables entières ayant une matrice des contraintes T unimodulaire (car dans ce cas, tous les sommets de l'ensemble de recherche sont entiers) comme les problèmes de transport ou d'affectation.

Pour les autres problèmes (ILP, MILP, 0-1ILP), il existe plusieurs méthodes :

la programmation dynamique consistant à placer le problème dans une famille de problèmes de même nature mais de difficulté différente puis à trouver une relation de récurrence liant les solutions optimales de ces problèmes.
le Branch & Bound consistant à faire une énumération implicite en séparant le problème en sous-problèmes et en évaluant ceux-ci à l'aide d'une relaxation (continue ou lagrangienne principalement) jusqu'à ne plus avoir que des problèmes faciles à résoudre ou dont on sait avec certitude qu'ils ne peuvent pas contenir de solution optimale.
les méthodes polyédrales consistant à ajouter progressivement des contraintes supplémentaires afin de ramener le domaine des solutions admissibles à un domaine convexe (sans en enlever la ou les solutions optimales bien évidemment).

Ces méthodes sont générales et demande souvent une particularisation vis-à-vis d'un problème spécifique. Il existe aussi des applications génériques (AMPL, CPLEX, LINDO, MPL, OMP, XPRESS...) permettant de résoudre l'ensemble des problèmes pouvant s'écrire sous la forme algébrique d'un problème en variables binaires, entières ou mixtes.

Il faut aussi noter que la méthode consistant à effectuer une énumération explicite de toutes les solutions (c'est-à-dire de les tester une à une, méthode envisageable pour tous les problèmes à variables à valeurs bornées) montre très vite ses limites dès que le nombre de variables augmente puisque sa complexité est en kn où k représente le nombre de valeurs que peut prendre une variable et n le nombre de variables du problème.

1.2.2 Méthodes approchées

Dans certaines situations, il est nécessaire de disposer d'une solution de bonne qualité (c'est-à-dire assez proche de l'optimale) dans un contexte de ressources (temps de calcul et/ou mémoire) limitées. Dans ce cas l'optimalité de la solution ne sera pas garantie, ni même l'écart avec la valeur optimale. Cependant, le temps nécessaire pour obtenir cette solution sera beaucoup plus faible et pourra même être fixé (bien évidemment dans ce cas la qualité de la solution obtenue dépendra fortement du temps laissé à l'algorithme pour l'obtenir).

Typiquement ce type de méthodes, dites heuristiques¹ est particulièrement utile pour les problèmes nécessitant une solution en temps réel (ou très court) ou pour résoudre des problèmes difficiles sur des instances numériques de grande taille. Elles peuvent aussi être utilisées afin d'initialiser une méthode exacte (Branch & Bound par exemple).

Parmi ces méthodes, il faut distinguer les heuristiques ciblées sur un problème particulier et les métaheuristiques plus puissantes et adaptables pour résoudre un grand nombre de problèmes. Cependant une métaheuristique, pour être suffisamment performante sur un problème donné nécessitera une adaptation plus ou moins fine.

Ces méthodes approchées peuvent se classer en différentes catégories [Freville00]:

Constructives (algorithmes glouton, méthode Pilote, GRASP)
Recherche locale (algorithmes de descente, multi-départs, recuit simulé, algorithme à seuil, recherche Tabou, méthode de bruitage)
Évolutionnistes (algorithmes génétiques, algorithmes d'évolution, recherche dispersée, méthode des chemins, systèmes de fourmis)
Réseaux de neurones (Modèle de Hopfield-Tank, machine de Boltzmann, réseau auto-adaptatif, réseau élastique)
Heuristiques Bayésiennes (optimisation globale, optimisation discrète)
Superposition (perturbation des données, perturbation des paramètres d'une heuristique).

1.3 Quelques problèmes classiques de l'optimisation combinatoire

1.3.1 Set Covering Problem

Ce problème est aussi appelé problème de couverture [Teghem96, Sakarovitch84] ou encore problème de couverture d'ensemble pondéré (Weighted Set Covering Problem). En effet, si l'on suppose un ensemble I={1,...,m} et un ensemble de parties de I P={P₁,...,P_n} où P_j Í I pour j Î J={1,...,n}, un sous-ensemble J^* Í J définit une couverture de I si et seulement si È_{j Î J^*} P_j = I. Un coût positif étant associé à chaque j Î J, l'objectif de ce problème est de déterminer une couverture de coût minimum. Un exemple d'application classique est celui de l'ouverture d'un nombre minimum de magasins dans une région pour couvrir l'ensemble de la zone.

Sa formulation algébrique (1.4) peut être obtenue en considérant des variables binaires qui définissent les parties retenues dans la couverture (la matrice des contraintes indique alors les différents éléments de couverts par chacune des variables) :

é
ê
ê
ê
ê
ê
ê
ê
ê
ë

Min z =

j=1

C_j X_j

j=1

T_ij X_j ³ 1

, " i

X_j = (0 ;1)

, " j

ù
ú
ú
ú
ú
ú
ú
ú
ú
û

(1.4)

Dans ce problème, ainsi que dans ceux que nous traiterons par la suite, les valeurs des termes de la matrice sont donc restreints à l'intervalle discret [0 ;1].

1.3.2 Set Packing Problem

Ce problème est aussi appelé problème d'emballage [Teghem96] ou encore couplage généralisé [Sakarovitch84]. En effet, l'objectif de ce problème est de déterminer un couplage (ensemble d'éléments indépendants) de valeur maximale. Un exemple d'application classique est celui de la mise en oeuvre d'une production de valeur maximale dans un contexte de ressources limitées. Sa formulation algébrique est la suivante (1.5) :

é
ê
ê
ê
ê
ê
ê
ê
ê
ë

Max z =

j=1

C_j X_j

j=1

T_ij X_j £ 1

, " i

X_j = (0 ;1)

, " j

ù
ú
ú
ú
ú
ú
ú
ú
ú
û

(1.5)

1.3.3 Node Packing Problem

Ce problème est connu sous différents noms. On peut citer parmi eux les termes de Vertex Packing, Maximum Stable Set, Maximum Clique, Anti-Covering Problem et surtout Maximum Independant Set [Gondran et al.95, Murray et al.97].

L'objectif de ce problème est de déterminer un nombre maximum de sommets non adjacents dans un graphe G=(V,E) où V représente l'ensemble des sommets et E l'ensemble des arcs. Par définition, deux sommets sont adjacents si et seulement si ils sont reliés par un arc. Sa formulation algébrique est la suivante (1.6) :

é
ê
ê
ê
ê
ê
ë

Max z =

j=1

C_j X_j

X_j + X_k £ 1

, " (j,k) Î E

X_j = (0 ;1)

, " j

ù
ú
ú
ú
ú
ú
û

(1.6)

La formulation de ce problème est très proche de celle du Set Packing. D'ailleurs, il peut être exprimé comme tel. Dans ce cas la matrice des contraintes T possède certaines particularités. Ainsi, la formulation algébrique de ce problème peut aussi être la suivante (1.7) :

é
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ë

Max z =

j=1

C_j X_j

j=1

T_ij X_j £ 1

, " i

X_j = (0 ;1)

, " j

avec

j=1

T_ij = 2

, " i

ù
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
û

(1.7)

Malgré tout, il ne faut pas confondre ces deux problèmes. En effet, la nuance peut sembler minime mais la propriété particulière dont hérite la matrice T est très importante pour la raison suivante :

Posons le changement de variable X'_j = 1 - X_j , " j. Dans ce cas, le problème peut se formuler de la manière suivante (1.8) :

é
ê
ê
ê
ê
ê
ê
ê
ê
ë

Max z =

j=1

C_j (1 - X'_j)

j=1

T_ij (1 - X'_j) £ 1

, " i

X'_j = (0 ;1)

, " j

ù
ú
ú
ú
ú
ú
ú
ú
ú
û

(1.8)

qui est de manière évidente équivalent au problème suivant (1.9) :

é
ê
ê
ê
ê
ê
ê
ê
ê
ë

Max z =

j=1

- C_j X'_j

j=1

T_ij -

j=1

T_ij X'_j £ 1

, " i

X'_j = (0 ;1)

, " j

ù
ú
ú
ú
ú
ú
ú
ú
ú
û

(1.9)

Et comme å_j=1ⁿ T_ij=2, ce problème peut aussi se formuler de la manière suivante (1.10) :

é
ê
ê
ê
ê
ê
ê
ê
ê
ë

Min z =

j=1

C_j X'_j

j=1

T_ij X'_j ³ 1

, " i

X'_j = (0 ;1)

, " j

ù
ú
ú
ú
ú
ú
ú
ú
ú
û

(1.10)

C'est-à-dire comme un Set Covering Problem. Ce problème est donc en fait un cas particulier des Set Packing et Set Covering Problem.

1: du grec heuriskein = trouver