Table des matières
Résumé

v

Abstract

vi

Table des figures

vii

Liste des tableaux

1

1 Introduction
1.1 Problématique . . . . . .
1.2 Contribution . . . . . . .
1.3 Environnement de stage
1.4 Organisation . . . . . . .

.
.
.
.

2
2

4
4
5

.
.
.
.
.
.

6
6
10
11
11
11
12

.
.
.
.

.
.
.
.

.

.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.

.
.
.

.
.
.
.

2 Théorie des graphes et définitions de base
2.1 Théorie des graphes . . . . . . . . . . . . .
2.2 Définitions de base . . . . . . . . . . . . .
2.3 Problèmes d’empaquetage fractionnaire . .
2.4 Problèmes de couverture fractionnaire . . .
2.4.1 Problème de coloration . . . . . . .
2.4.2 Coloration fractionnaire . . . . . .

.
.
.
.

.
.
.
.
.
.

.

.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.

.
.
.
.

3 Algorithmes basés sur les méthodes de fonction
nentielle
3.1 Méthode de fonction potentielle exponentielle . .
3.1.1 Problématique . . . . . . . . . . . . . . . .
3.1.2 Algorithme de base . . . . . . . . . . . . .
3.2 Algorithme de Plotkin et al. . . . . . . . . . . . .
3.2.1 Procédure principale . . . . . . . . . . . .
3.2.2 Analyse . . . . . . . . . . . . . . . . . . .
3.2.3 Problème généralisé . . . . . . . . . . . . .
3.3 Comparaison avec d’autres approches . . . . . . .
3.3.1 Fonctions potentielles alternatives . . . . .
ii

.
.
.
.

.
.
.
.
.
.


.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.

.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.


.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.

.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

potentielle expo.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.

14
14
14
16
17
17
18
20
20
20


iii

Table des matières

3.3.2
3.3.3

Arrondissement inconscient . . . . . . . . . . . . . . . . . . . 20
Algorithmes de Garg-Könemann et de Fleischer . . . . . . . . 21


4 Problème des flots maximum à
4.1 Introduction . . . . . . . . . .
4.2 Algorithme de Fleischer . . .
4.2.1 Algorithme . . . . . .
4.2.2 Analyse . . . . . . . .
4.3 Algorithme de Plotkin et al. .
4.3.1 Algorithme . . . . . .
4.3.2 Analyse . . . . . . . .
4.4 Comparaison . . . . . . . . .
4.4.1 Solution initiale . . . .
4.4.2 Flot de recheminement
4.5 Histoire . . . . . . . . . . . .

plusieurs
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .

commodités
. . . . . . . .
. . . . . . . .
. . . . . . . .

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.
.
.
.

22
22
23
23
24
24
24
25
26
26
26
29

5 Implémentation du problème des flots à plusieurs commodités
31

5.1 Améliorations heuristiques . . . . . . . . . . . . . . . . . . . . . . . . 31
5.2 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.3 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . 33
6 Conclusion et perspectives

37

A Bibliothèque Mascopt
A.1 Architecture . . . . . . . . . . .
A.2 Entreée et sortie des données . .
A.3 Interface graphique d’utilisateur
A.4 Quelques classes de base . . . .

38
38
40
42
43

.
.
.
.

.
.
.
.

.

.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.

.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.

.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.

.
.
.

B Programmation Linéaire

45

C Méthode primale - duale pour des algorithmes d’approximation

48

D Relaxation Lagrangienne

49

E Série de Taylor

52

Bibliographie

53


Remerciements
J’aimerais consacrer cette section pour remercier toutes les personnes qui m’ont supporté tout au long de mon stage :
– Je suis très reconnaissant à mon responsable de stage, Monsieur le professeur
Stéphane Pérennes pour m’avoir donné le sujet très intéressant et m’avoir aidé
à bien mener ce travail par ses conseils, ses remarques et ses suggestions ;

– Je tiens à remercier M. Jean-Claude Bermond, Directeur de Recherche - le
responsable de projet Mascoptte, pour m’avoir accueilli au sein de son équipe
et sa gentillesse.
– Je remercie Monsieur Nelson Morales, doctorant à l’Inria, qui travaille dans
le même bureau avec moi pour sa gentillesse, son aide, et pour les discussions
grâce auxquelles j’ai pu bien mener mon travail ;
– Je tiens à remercier Ephie Deriche pour sa gentillesse et sa efficacité à résoudre
les embarras administratifs ;
– Je voudrais aussi remercier toutes les autres membres du projet Mascotte qui
m’ont supporté tout au long de mon stage ;
– Je tiens à remercier tous mes amis qui m’ont donné beaucoup d’aides et d’encouragements depuis le début de mon stage en France.


Résumé
Les problèmes d’empaquetage et de couverture sont des classes généraux de nombreuse applications en réalité. Un cas spécial du problème d’empaquetage est le problème des flots à plusieurs commodités. Ici, on doit transférer les commodités pour
remplir les demandes sous les contraintes de capacités des arêtes. Les problèmes
de coloration et de découple sont ceux de couverture. Malheureusement, si ces problèmes sont contraints à être entiers alors ils sont NP-Complets. Cependant, on
peut trouver une solution d’approximation pour ces problèmes en se basant sur leurs
versions fractionnaires.
Dans ce rapport, nous présentons une technique de relaxation Lagrangienne pour
la conception des algorithmes d’approximation pour des problèmes ci-dessus. L’idée
principale est simple : partant du problème initial P , certaines contraintes sont
relâchées et remplacées par des pénalités selon le degré de leur violation. En général,
on utilise deux types de fonction potentielle exponentielle et logarithmique pour cette
technique. Dans ce cadre de ce travail, nous nous concentrons seulement sur des
algorithmes qui appliquent la fonction potentielle exponentielle. Nous faisons aussi
des études sur le problème des flots à plusieurs commodités. Après, nous faisons
aussi une comparaison avec des autres méthodes de génération de chemins dans le
cas du flot et de génération de colonnes dans le cas général.
Nous décrivons et examinons notre implémentation du problème des flots à plusieurs commodités basée sur l’algorithme d’approximation de Plotkin et al [20, 17].

Leur algorithme est efficace en théorie, cependant une implémentation directe est
lent en pratique. Nous modifions cet algorithme et démontrons que sa performance
est en pratique garantie comme la prédiction en théorie.

v


Abstract
Packing and covering problems are the class general for several applications. An
important problem, that fits into the packing framework is the multicommodity flow
problem. It involves simultaneously shipping multiple commodities through a single
network so that the total amount of flow on each edge is not more than the capacity of
the edge. Colouring and cut-stock problems are covering. Unfortunately, the integer
version of these problems are NP-Complete. However, we can find approximated
solution for these problems based on theirs fractional versions.
In this thesis, we will present a Lagrangian decomposition method for the design
of the approximation algorithms for problems above. The principal idea is simple: based on the initial problem P , certain constraints are relaxed and replaced by
penalties according to the degree of their violation. In general, we use two types of
potential function for this technique: exponential and logarithmic . In this framework, we focus on the algorithms which apply the exponential potential function for
fractional packing and covering problems. We also study on the multicommodity
flow problem. Afterwards, we will make also a comparison with paths generation
methods in the case of the flow and of columns generation methods in the general
case.
We describe and examine our multicommodity flow implementation based on
the recent combinatorial approximation algorithm of Plotkin et al. [20, 17]. Their
algorithm is effective in theory, however a direct implementation is slow in practice.
We modify this algorithm and show that its performance is guaranteed in practice
like the prediction in theory.

vi



Table des figures
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8

Graphe G1 , V = 1, 2, 3, 4, 5, 6 . . . . . .
Graphe orienté G2 . . . . . . . . . . . .
Matrice adjacente associée au graphe G1
Flot sur un réseau . . . . . . . . . . . . .
Exemple : un réseau N . . . . . . . . . .
Réseau résiduel N (f ) . . . . . . . . . . .
Coupe dans un réseau . . . . . . . . . .
Coloration d’un graphe . . . . . . . . . .

.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

. 6
. 7
. 8
. 8
. 9
. 9
. 10
. 12

4.1
4.2
4.3
4.4

Flot
Flot
Flot
Flot

.
.
.
.


.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.


.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.


.
.
.
.

.
.
.
.

.
.
.
.

27
27
28
28

5.1
5.2
5.3
5.4

Graphe des câbles . . . . . . . . . . . .
Graphe des demandes . . . . . . . . . .
Relation entre le nombre d’itérations et
La solution des flots . . . . . . . . . . .


. . . . . . .
. . . . . . .
la précision
. . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.


.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

34
34
36
36


initiale de Plotkin et al. . .
initiale de Fleisccher . . . .
recheminé de Plotkin et al.
recheminé de Fleischer . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.


A.1 Diagrame de classes de la bibliothèque Mascopt . . . . . . . . . . . . 39
A.2 Réseau avec un chemin . . . . . . . . . . . . . . . . . . . . . . . . . . 43
A.3 Graphe avec des étiquettes montrant des valeurs . . . . . . . . . . . . 44
C.1 Algorithme primal-dual de base . . . . . . . . . . . . . . . . . . . . . 48

vii


Liste des tableaux
4.1
4.2

Comparaison entre Fleischer et PST91 . . . . . . . . . . . . . . . . . 28
Histoire de développement du problème des flots . . . . . . . . . . . . 30

5.1

Quelques fonctions principales pour le problème des flots . . . . . . . 35

1


Chapitre 1
Introduction
1.1

Problématique

Les problèmes d’empaquetage et de couverture fractionnaire sont généraux pour
plusieurs applications en réalité, par exemple : le problème des flots maximum, sac

à dos, coloration,... Dans ce rapport, nous présentons et examinons quelques algorithmes pour ces problèmes. En fait, il existe quelques méthodes pour les résoudre :
la programmation dynamique et des méthodes heuristiques (recherche locale, recherche Taboue, branch-and-bound). La plupart de ces problèmes sont peut-être
formulés comme une programmation linéaire, on peut trouver leur solution optimale
en temps polynomial en utilisant la méthodes ellipsoïde [13, 14]. Karmarmar [12] a
aussi proposé une fonction potentielle logarithmique comme une fonction barrière.
Cette méthode est élargie sous le nom "méthode intérieur point". Elle a prouvé le
caractère polynomiale de la programmation linéaire.
Cependant, ces méthodes pour la programmation linéaire sont très générales,
elles ne tiennent pas compte la structure combinatoire des instances de problèmes
traités. En réalité, la complexité est peut-être polynôme de la taille très grandes de
données d’entrées. L’objectif de ce rapport est alors d’introduire une algorithme d’approximation efficace pour des problèmes d’empaquetage et de couverture fractionnaire. Un algorithme d’approximation nous donne seulement une solution faisable
pour une instance entrée d’un problème d’optimisation avec une précision spécialisée. Cependant, dans plusieurs applications, il est suffisant de traiter les solutions
qui sont près de l’optimum.
L’algorithme que nous introduirons est celui amélioré de Plotkin et al [20, 17, 5]
dans le cas de la génération de chemins pour le problème des flots. Ces améliorations
heuristiques sont basées sur la technique de relaxation Lagrangienne.
En particulier, on va développer des algorithmes pour des problèmes d’empaquetage et de couverture fractionnaire. Un problème d’empaquetage peut être formulé
comme des problèmes de la programmation linéaire :
max
t.q

cT x
Ax ≤ b
x ≥ 0

(1.1)

Où, A est une matrice m×n, b et c sont des vecteurs m et n dimensionnels. Le but



3

1.1. Problématique

dans un problème d’empaquetage est de trouver un choix maximum de bénéfice des
colonnes tels que chaque rangée i est empaquetée par des unités de bi . Intuitivement,
on peut présenter ce problème comme suivant : comment peut-on placer des objets
dans des boîtes tel que ils satisfont des contraintes de capacités de boîtes ? Par
exemple, pour le problème de sac à dos, on doit mettre des objets dans le sac tel
que le total de values d’objets est maximum, le problème des flots est similaire, on
doit maximiser le flot transféré dans un réseau sous des contraintes de capacité des
arêtes.
Un problème de couverture peut être décrit par une instance de programmation
linéaire suivante :
min
t.q

yT b
AT y ≥ c
y ≥ 0

(1.2)

Où, A, c, b sont définis comme dans le cas ci-dessus. Le but de ce problème est
contraire au problème d’empaquetage. On doit trouver un choix minimum de coût
des colonnes tels que chaque rangée i est couverte par des unités de bi . On trouve
que : le dernier problème est le dual de programmation linéaire (1.1).
Lorsque l’on s’autorise à découper les objets en sous parties le problème est
polynomial, il s’exprime en effet sous la forme d’un problème de programmation
linéaire entière. La complexité de la résolution par programmation linéaire standard

n’est cependant pas toujours satisfaisante. L’algorithme de Rao et al. [20] a pour
objet de fournir une méthode plus rapide. Il peut être considéré à la fois comme une
méthode primale - duale et une relaxation Lagrangienne du problème. Son principe
est simple, partant du problème initial P , certaines contraintes sont relâchées et
remplacées par une pénalité exponentielle selon le degré de leur violation (relaxation
Lagrangienne). A chaque étape, l’algorithme effectue une descente de type gradient,
celle-ci nécessite l’optimisation d’un problème plus simple P pour lequel on utilise
une méthode aussi efficace que possible.
Ici, leur objectif est de chercher un point x ∈ P tel que Ax ≥ (1 − )b pour
le problème de couverture (ou bien chercher un point x ∈ P tel que Ax ≤ (1 +
)b pour le problème d’empaquetage). Le nombre d’itérations (le nombre d’appels
la sous-tâche) est O( −2 ρ log(m −1 )) pour le problème d’empaquetage et O(m +
ρ log2 m + −2 ρ log(m −1 )) pour le problème de couverture. Où, ρ la largeur de P ,
ρ = maxi maxx∈P abiix . Dans une autre approche, en utilisant une fonction potentielle
logarithmique modifiée de Karmarkar, J. Villavicencio et M.D. Grigoriadis [24], K.
Jansen et H. Zhang [11] ont présenté un algorithme d’approximation pour des problèmes d’empaquetage. Cet algorithme peut trouver une solution d’approximation
pour n’importe quelle erreur ∈ (0, 1) dans O(M ( −2 ln −1 + ln M )) itérations.
Un problème important traité dans le cadre d’empaquetage est le problème des
flots à plusieurs commodités. Ici, on donne un réseau de flots G = (V, E), une
fonction de capacité sur des arêtes c et k commodités. Chacune de ces commodités
correspond à soit une couple de sommets (source et puits) dans le cas simple à soit
quelques couples de source-puits dans le cas général (dans le cadre de ce travail, on
va traiter seulement le premier). On a un ensemble de couples des sommets T =
(s1 , t1 ), ..., (sk , tk ) et chacune associe avec chaque commodité. Ce qu’on veux chercher


4

Chapitre 1. Introduction


une solution tels que la somme des flots de tous les commodités est maximum,
k
max
i=1 fi cependant, ces flots respectent des contraintes de capacité, c’est-àdire, ki=1 f (e) ≤ c(e) ∀e ∈ E.
Raghavan [22] a proposé un algorithme aléatoire appelé des flots à plusieurs commodités fractionnaire. Un résultat approximatif est aussi donné dans [20, 17], leur
algorithme a utilisé une relaxation Lagrangienne avec des pénalités exponentielles
selon degré de leur violation, à chaque étape, il applique une descente de type gradient. La complexité de leur algorithme est O(kmn log4 n). Ils ont aussi prouvé que
ce problème peut être résolu par O(k log2 n) par rapport à la résolution approximative de celui singe commodité. Cet algorithme est semblable aux ceux de [23]
et [15] qui commencent par un flot satisfaisant les demandes mais non satisfaisant
les contraintes de capacité. Et alors ces algorithmes re-cheminent itérativement des
parties de flot pour produire un nouveau flot qui est plus près d’optimal.
Grag et Könemann [7] ont présenté un cadre de travail pour ce problème et
des autres problèmes d’empaquetage. Ils réalisent à augmenter des flots suivie le
chemin le plus court au lieu de flots minimum coût singe commodité. La complexité
de − approximation est O( −2 km2 ) et ils supposent que le temps de calculs pour
le plus chemin est O(km). Dans [5] Fleischer a basé sur ce cadre et proposé un
algorithme dont sa complexité est indépendante avec le nombre de commodités.
Son idée est simple, au lieu de calculs le chemin le plus court parmi toutes les
commodités, il ne calcule que les plus courts chemins qui sont au plus (1 + )-fois
lmin , où lmin est longueur du chemin le plus court. Récent, D. Coudert et al. [3, 2]
ont amélioré cet algorithme en utilisant l’algorithme de recherche dynamique pour
le problème de chemin le plus court, en outre à partir d’ une idée : la précision ne
demande que à la fin du processus de calcul, leur algorithme pussent rapidement
une grande quantité de flots. Au lieu de graduer des flots selon les capacités d’arcs,
leur algorithme gradue selon la fonction de longueur.

1.2

Contribution


– Introduire généralement des problèmes d’empaquetage et de couverture fractionnaire et des algorithmes développés récemment pour ces problèmes.
– Introduire et analyser la méthode de fonction potentielle exponentielle.
– Faire un état de l’art du problème des flots à plusieurs commodités.
– Modifier et implémenter l’algorithme de Rao et al. [20, 17, 5] pour le problème
des flots à plusieurs commodités.

1.3

Environnement de stage

Mascotte est un projet commun avec le CNRS et l’Université de Nice-Sophia
Antipolis (UNSA) dans le cadre du laboratoire I3S.
Mascotte est équipe associée RESEAUXCOM avec le "Network Modeling Group"
de l’Université Simon Fraser (Vancouver, Canada).
Mascotte a un Contrat de Recherche Collaborative CORSO avec France Telecom
R&D.


1.4. Organisation

5

Mascotte fait partie du pôle ResCom du GdR ASR du CNRS (anciennement axe
TAROT du GdR ARP).
L’objectif du projet Mascotte est de développer des méthodes et outils algorithmiques qui s’appliquent en particulier à la conception de réseaux de télécommunications. La réalisation de cet objectif implique la poursuite de recherches de haut
niveau dans les domaines de l’algorithmique, de la simulation et des mathématiques
discrètes.

1.4


Organisation

Dans le chapitre 2, nous rappelons un peu de la théorie de graphe. Et puis,
nous discutons des algorithmes d’approximation basés sur la méthode de la fonction
potentielle exponentielle pour le problème d’empaquetage et de couverture fractionnaire dans le chapitre 3. Nous examinerons également l’algorithme de Plotkin et al.
dans [20, 17].
Le chapitre 4 aborde le problème des flots à plusieurs commodités. Dans ce
chapitre, nous présentons l’algorithme de Fleischer [5] et celui de Plotkin et al.
[20, 17]. Le premier a utilisé le problème le chemin le plus court comme le problème
dual. Le deuxième a résolu ce problème en se basant sur le problème de flot coûteminimum.
Dans le chapitre 5, nous décrirons notre implémentations pour le problème des
flots à plusieurs commodités. Notre implémentation est basé sur l’algorithme de Rao
et al [20, 17, 5]. Leur algorithme est très efficace en théorie, cependant une implémentation directe est très lent. Nous avons modifié leur algorithme et donné l’implémentation rapide en pratique. Notre implémentation est basé sur la bibliothèque
Mascot [21], une bibliothèque d’optimisation construite par l’équipe Mascotte.
Dans des annexes, nous vous rappelons quelques mots sur la programmation linéaire, la relaxation Lagrangienne, la série de Taylor, ce qui sont des connaissances
de base pour mon rapport. En outre, nous vous présentons quelques mots la bibliothèque Mascot.


Chapitre 2
Théorie des graphes et définitions de
base
2.1

Théorie des graphes

Graphe
Un graphe est constitué d’un ensemble de sommets et d’une famille de liens
(orientés ou non), appelés arêtes ou arcs, entre certains couples de sommets.
Définition 1 (Graphe non orienté) Un graphe G = (V, E) contient un ensemble
fini V de sommets et un ensemble fini E d’arêtes (sans orienté). Le nombre de

sommets |V | est n et le nombre d’arêtes |A| est m.
E ⊆ x, y : x, y ∈ V, x = y

Fig. 2.1 – Graphe G1 , V = 1, 2, 3, 4, 5, 6

Définition 2 (Graphe orienté) Un graphe orienté est un graphe dont les arêtes
sont orientées : on parle alors de l’origine et de l’extrémité d’une arête. Une boucle
est une arête orientée dont l’origine et l’extrémité sont les mêmes.
E ⊆ (x, y) ∈ V × V
Pour chaque arc a = (x, y), des sommets x et y sont appelés des sommets incidents à a.
6


7

2.1. Théorie des graphes

Fig. 2.2 – Graphe orienté G2
Un graphe non-orienté peut-être utilisé pour modéliser des relations de conflits
entre individus ou objets. Un graphe orienté représente typiquement un réseau de
communication, ou encore des relations de domination non-réciproque entre personnes, etc.
Le dégrée du sommet v, deg(v), est le nombre d’arêtes (arcs) incidentes à v.
On considère généralement que le problème des ponts de Königsberg (chercher un
parcours eulérien qui passe exactement une fois par chaque arête), résolu par Euler,
est le premier résultat formel de la théorie des graphes. Et puis, cette théorie s’est
surtout développée depuis la deuxième moitié du 19ème siècle par Hamilton, Heawood, Kempe, Kirchhoff, Petersen, Tait, et depuis les années 30 du 20ème siècle par
König, Hall, Kuratowski, Whitney, Erdös, Tutte, Edmonds, Berge, Lovász, Seymour.
Elle présente des liens évidents avec l’algèbre, la topologie, et d’autres domaines de
combinatoire. On trouve des applications de la théorie des graphes en informatique :
recherche opérationnelle, théorie des jeux et théorie de la décision.

Le nombre de notions que l’on peut définir sur un graphe est très grand, et plusieurs d’entre elles sont à l’origine de problèmes célèbres (le problème des quatre
couleurs par exemple). En fait, un certain nombre de ces notions et des questions
"théoriques" sont issues non pas des mathématiques pures mais de problèmes pratiques. De plus, les théoriciens des graphes s’attachent souvent à trouver des algorithmes efficaces pour résoudre un problème donné.
Les grands problèmes classiques de la théorie des graphes sont suivants : flots,
connectivité, coupe, parcours eulérien, parcours hamiltonien, coloration et ensemble
stable etc,... Certains de ces problèmes (flot maximum, coupe maximum, parcours
eulérien) peuvent être résolus "efficacement", mais la plupart sont très difficiles
("NP-complets").
Chaque graphe peut être associé à une matrice appelée la matrice adjacente. Une
matrice adjacente A = (aij ) du graphe G est définie comme suivante :
aij = {1 si i et j adjacents, 0 sinon}
Un sous-graphe d’un graphe G est un graphe G composé de certains sommets
de G et toutes les arêtes qui relient ces sommets.

Flot
On considère un réseau N = (V, E), chaque arête a une capacité c : E → R+ .


8

Chapitre 2. Théorie des graphes et définitions de base

Fig. 2.3 – Matrice adjacente associée au graphe G1
Un flot f de s à t sur un réseau N est une valeur positive des arcs, c’est à dire
qu’une application de E dans R+ vérifie les deux propriétés suivantes :
– Pour tout arc (u, v) ∈ E, alors 0 ≤ f (u, v) ≤ c(u, v), c’est-à-dire que le total
de flots dans chaque arête n’excède pas leur capacité.
– Pour tous les sommets intermédiaires v ∈ V \{s, t}, alors u f (u, v) = u f (v, u).

Fig. 2.4 – Flot sur un réseau

La somme f − (v) = u f (u, v) est le flot entrant au sommet v.
La somme f+ (v) = u f (v, u) est le flot sortant du sommet v.
La valeur |f | d’un flot f est définie comme la différence entre le flot sortant et
le flot entrant en v : |f | = f + (v) − f − (v).
Définition 3 (Flot Maximum (MaxFlow)) Le problème du Flot Maximum
consiste à trouver un flot fmax de valeur maximale sur le réseau N .

Réseau résiduel
Définition 4 (Réseau résiduel) Le réseau résiduel N (f ) associé à un flot f sur
un réseau N est un réseau comprenant les mêmes sommets que N . Chaque arc (u, v)
de N est associé dans N (f ) selon deux principes suivants :
1. Si f (uv) < c(uv), alors l’arc (u, v) est placé dans E(N (f )) (arc normal)
2. Si f (vu) > 0, alors l’arc (u, v) est placé dans E(N (f )) (arc inverse)
Où, u, v ∈ V .
Définition 5 (Capacité résiduelle) La capacité résiduelle d’un arc sur le réseau
résiduel est définie comme suivant :
1. Si f (uv) < c(uv), u (uv) = c(uv) − f (uv)
2. Si f (vu) > 0, u (uv) = f (uv)


9

2.1. Théorie des graphes

Où, u (uv) est la capacité du arc (u, v) sur le réseau résiduel.
Propriété 1 De ces définitions, on peut additionner tout flot admissible de G(f )
au flot f et obtenir un flot admissible.

Fig. 2.5 – Exemple : un réseau N


Fig. 2.6 – Réseau résiduel N (f )

Coupe
Définition 6 (Coupe) Si s et t sont 2 sommets d’un réseau N = (V, E),
– Une (s, t)-coupe est un ensemble A d’arcs déconnectant s de t : dans le graphe
partiel (V, E\A) il n’existe pas de chemin orienté de s à t.
– Une (s, t)-coupe se définit également par une partition C = S ∪ T des sommets
telle que s ∈ S et t ∈ T . Les arcs de la coupe sont alors les arcs (u, v) ayant
leur origine u dans S et leur destination v dans T .
– La capacité d’une coupe est la somme des capacités ses arcs.
Définition 7 (Coupe Minimum (MinCut)) Le problème de la Coupe Minimum
consiste à trouver une coupe Cmin entre s et t de capacité minimale.
Propriété 2 (MaxFlow MinCut (forme faible)) Si f est un flot sur un réseau
entre s et t, et C est une (s, t)-coupe, alors : |f | ≤ |C|. Cela est équivalent à :
|fmax | ≤ |Cmin |


10

Chapitre 2. Théorie des graphes et définitions de base

Fig. 2.7 – Coupe dans un réseau

2.2

Définitions de base

Définition 8 (L’Optimisation combinatoire) consiste à trouver le meilleur entre
un nombre fini de choix. Autrement dit, à minimiser une fonction avec contraintes
sur un ensemble fini.

Définition 9 (NP-Complet) Un problème est NP-Complet si il est dans N P , et
si n’importe quel problème N P -Complet peut se récrire à l’aide d’un algorithme
polynomial comme un sous ensemble d’instance de ce problème.
Le problème N P -Complet le plus célèbre est le problème satisfaisant. L’ensemble
des problèmes N P -complets ont la propriétés suivante :
– Si on trouve un algorithme efficace pour un problème N P -Complet alors il
existe des algorithmes efficaces pour tous,
Et jusqu’à maintenant :
– Personne n’a jamais trouvé un algorithme efficace pour un problème NPcomplet,
– Personne n’a jamais prouvé qu’il ne peut pas exister d’algorithme efficace pour
un problème NP-complet particulier.
Pour attaquer aux problèmes NP-Complet, on utilise des algorithme d’approximation.
Définition 10 (Algorithme d’approximation) Un algorithme qui donne des solutions presque optimales et s’exécute un temps polynomial au pire des cas est appelé
algorithme d’approximation.
On demande un algorithme d’approximation efficace et ayant la capacité de résoudre
le problème pour toutes les entrées, mais on laisse tomber la demande d’une solution
optimale.
Définition 11 (Facteur d’approximation) Soit OP T (I) est la valeur d’une solution optimale pour l’entrée I, et soit ALG(I) est la valeur de la solution retournée
par l’algorithme A pour l’entrée I. On dit que le facteur d’approximation de
l’algorithme A est A (n) pour tout l’entrée I de taille n si :
max

ALG(I) OP T (I)
,
OP T (I) ALG(I)

≤

A (n)



2.3. Problèmes d’empaquetage fractionnaire

2.3

11

Problèmes d’empaquetage fractionnaire

Définition 12 (Problème d’empaquetage fractionnaire) ∃?x ∈ P tel que Ax ≤
b, où A est une matrice m × n, b > 0 et P est un ensemble convexe dans Rn tel que
Ax ≥ 0 pour chaque x ∈ P .
Pour ce problème, son but est de trouver un choix de bénéfice maximum des
colonnes tels que chaque rangée i est empaquetée par des unités de bi . Intuitivement,
on peut présenter ce problème comme suivant : comment peut-on placer des objets
dans des boîtes tel que ils satisfont aux contraintes de capacités de boîtes ?
Quelques problèmes exemplaires :
– Problème de sac à dos.
– Problème des fichiers sur des CD-Rom (Bin packing).
– Problème de multiflots.
– Problème des sommets dans des ensembles indépendants (coloration, application à des problèmes d’allocation de fréquences).

2.4

Problèmes de couverture fractionnaire

Définition 13 (Problème de couverture fractionnaire) ∃?x ∈ P tel que Ax ≥
b, où A est une matrice m × n, b > 0 et P est un ensemble convexe dans Rn tel que
Ax ≥ 0 pour chaque x ∈ P .
Intuitivement, supposons que on veux assigner des poids sur les colonnes, c.-à-d.

sur le xj tels que i est couvert par au moins bi , où chaque unité de poids sur la
colonne j eme met le poids ai j sur l’élément i. Facilement on trouve que le dernier
problème est la dualité de celui d’empaquetage fractionnaire.

2.4.1

Problème de coloration

On appelle ensemble indépendant d’ un graphe G = (V, E) un sous ensemble de
sommets ayant un sous ensemble d’ arêtes induits vide. Une coloration du graphe
est une partition des sommets en ensembles indépendants, on associe généralement
une couleur à chaque partie à fin de visualiser ou d’aider l´intuition. Le nombre
chromatique du graphe est alors le nombre minimum de parties d´une coloration.

Définition 14 (Coloration) On peut décrire le problème de coloration comme suivant :
Instance : Graphe G = (V, E).
Solution : Une coloration de G, c-à-d, une division de V dans disjoignent des
ensembles V1 , V2 , .., Vk tels que chacun Vi est un ensemble indépendant pour G.
Mesure : La cardinale de la coloration.


12

Chapitre 2. Théorie des graphes et définitions de base

Formulation mathématique : On s’appelle S un ensemble de tous les ensembles
indépendants maximum de G, on doit choisir des ensembles indépendants maximum
dans S pour satisfaire aux contraintes suivantes :
minimiser


xs
s

soumettre a
`

xs ≥ 1

∀i ∈ V

xs ∈ 0, 1

∀s ∈ S

s:i∈S

Où, xs = 1 si l’ensemble s est choisit, au contraire xs = 0. On dit que ce nombre
minimal est le nombre chromatique χ de G.

Fig. 2.8 – Coloration d’un graphe

2.4.2

Coloration fractionnaire

Pour ce problème, on colorie non seulement une couleur mais plusieurs couleurs
pour chaque sommet. Une coloration fractionnaire est une pondération des ensembles
indépendants I telle que pour tous les sommets x, la somme des poids des ensembles
indépendants contenant x soit au moins 1. On appelle aussi une telle pondération
une couverture car chaque sommet est couvert par des ensembles pesant au moins

1.
Supposons que χf est le nombre chromatique fractionnaire de G, on a une lemme
suivante :
Lemme 1

χ(G)
log |V |

≤ χf (G) ≤ χ(G).

Formulation mathématique : T. Matsui dans [19] a proposé un algorithme
2 − approximation pour ce problème sur le graphe d´intersection d´arc circulaires
en résolvant le problème d’ensemble indépendant maximum.
minimiser

xe
e∈∂+(s)

soumettre a
`

xe +
e∈∂+(v)

v∈B(P,p)
x≥0

xf = 0

∀v ∈ A(P )


xe ≥ 1

∀p ∈ P

f ∈∂−(v)

e∈∂+(v)


2.4. Problèmes de couverture fractionnaire

13

Où, A(P ) un graphe auxiliaire est utilisé dans son algorithme d’ensemble indépendant maximum. Il existe en fait une correspondante un-a-un entre l’ensemble de
toutes les ensembles indépendants maximum dans G(P ) et tous les chemins s − t
dans A(P ). Donc, le problème de coloration fractionnaire devient un problème de
flots sur A(P ). Le vecteur x est indexé par des arcs sur A(P ). La solution de ce
problème nous donne la borne inférieure du problème de coloration.
Quelques d’autres problèmes de couverture Couverture minimum de Clique,
Couverture minimum des sommets, Coloration minimum d’arête, Minimum Clique
Partition.


Chapitre 3
Algorithmes basés sur les méthodes
de fonction potentielle exponentielle
Dans ce chapitre, nous faisons revoir quelques résultats fondamentaux de la méthode fonction potentielle exponentielle qui est développée milieu les années 90. Les
fonctions potentielles exponentielles est introduites dans le domaine d’optimisation
par Motzkin (1952) qui a suggéré des méthodes de la descente de type gradient

pour résoudre des systèmes des inégalités linéaires. Shahrokhi et Matula (1990) [23]
ont obtenu un schéma d’approximation totalement en temps polynomial pour le
problème des flots uniforme de concurrencegrâce à cette méthode. Leur borne est
améliorée par Klein et al. [15](1990), et Leighton et al. (1991) [17], et de plus élargie
pour des problèmes d’empaquetage et de couverture fractionnaire par Plotkin et al.
(1991) [20]. Actuellement, les bornes les plus connues est données pour tous les deux
problèmes linéaire et non-linéaire par Grigoriadis et Khachiyan (1994) [9].
D’abord, nous représenterons l’algorithme d’approximation de base pour des problèmes d’empaquetage et de couverture fractionnaire basé sur la méthode de la fonction potentielle exponentielle. Ensuite, nous analyserons l’algorithme de Plotkin et
al. [20, 15, 17]. Dans le reste de ce chapitre, nous faisons une comparaison entre
cette approche avec quelques d’autres approches.

3.1
3.1.1

Méthode de fonction potentielle exponentielle
Problématique

On considère des problèmes qui peuvent être formulés comme la programmation
linéaire suivante :
max
t.q

cT x
Ax ≤ b
x ∈ P

(3.1)

Où, A est une matrice m × n et b et c sont les vecteurs de m et n dimensions
14



3.1. Méthode de fonction potentielle exponentielle

15

respectivement. Ce problème est appelé le problème d’empaquetage fractionnaire.
Le problème de couverture est également considéré similairement.
En donnant une paramètre d’erreur > 0, notre objectif est à chercher un vecteur
x ∈ P tel que Ax ≤ (1 + )b. On appelle que c’est une solution − approximation.
Au contraire, une solution exacte est un vecteur x ∈ P tel que Ax ≤ b.
Largeur de polyèdre
Il est un facteur bien connu parmi les praticiens de la relaxation Lagrangienne
qu’une formulation de programmation linéaire devrait autant que possible utiliser
des bornes supérieures "petites" ou "serrées" sur des variables. Sinon on a des résultats faibles de convergence.
Définition 15 La largeur de polyèdre x ∈ Rn , Ax ≤ b est :
ρ = maxi maxx∈P

ai x − bi
bi

(3.2)

Dans le cas de problème des flots à plusieurs commodités, la largeur est égale la
congestion maximum contractée par n’importe quel flot.
Ce paramètre de largeur est formellement introduit par Plotkin et al. [20]. Leur
algorithme prouve que ou bien (3.1) est infaisable, ou bien on trouve une solution
− approximation x ∈ P . Dans le cas pire, le nombre d’itérations de leur algorithme
de base dépend polynomialement de m et de n, et est également proportionnel au
ρ −3 . Nous allons examiner cet algorithme plus détailléement dans la partie suivante.

Version d’optimisation et solution d’approximation
Dans cette partie, nous représentons la version d’optimisation du problème d’empaquetage fractionnaire. Celle du problème de couverture fractionnaire est pareille.
Soit un paramètre d’erreur > 0, on appelle que une solution − approximation
du problème d’empaquetage fractionnaire, est un vecteur x ∈ P tel que Ax ≤ (1+ )b.
Au contraire, une solution exacte est un vecteur x ∈ P tel que Ax ≤ b. Une procédure
− relachee va nous donner une solution − approximation ou bien nous dire que
aucune solution exacte existe. La version suivante d’optimisation de ce problème est
utilisée pour trouver un tel point :
min
t.q.

λ
Ax ≤ λb
x ∈ P

(3.3)

Supposons que λ∗ est la valeur optimale. Pour chaque x ∈ P il y a une valeur
maximum correspondante λ tel que Ax ≤ λb. On va utiliser une notation (x, λ)
pour dénoter que λ est la valeur maximum correspondant à x. Une solution (x, λ)
est − optimale si x ∈ P et λ ≤ (1 + )λ∗ . Si λ > (1 + σ), on a λ∗ > 1 et alors, il
n’existe pas de solution optimale.
Dans [1], Bienstock a généralement introduit une méthode de la fonction potentielle exponentielle.


16

3.1.2

Chapitre 3. Algorithmes basés sur les méthodes de fonction potentielle

exponentielle

Algorithme de base

Dans cette partie, nous représentons un algorithme − approximation pour des
problèmes ci-dessus.
Paramètres La matrice A a m rangées, n colonnes et un maximum des Q nonzéros par rangée.
L’algorithme peut être vu comme un fonctionnant dans deux étapes. Dans la
première étape, on cherche une borne inférieure λL sur λ∗ , ici on suppose que λ∗
est la solution optimale, et un point x ∈ P tel que λU = λ(x) satisfait λU ≤
O(min{m, Q})λL . Ainsi, on est garanti une erreur multiplicative polynomial dans
l’évaluation initiale de λ∗ . Dans la deuxième étape, on diminue progressivement
l’espace entre les bornes inférieure et supérieure sur λ∗ jusqu’à la précision désirée
soit réalisée.
La première étape
Afin de motiver la stratégie utilisée par l’algorithme dans la première étape,
supposons qu’on a eu une borne supérieure connue lambdaU sur lambda∗ (dans l’algorithme de Plotkin et al [20], cette borne supérieure est égale à λU = maxi ai x/bi ).
Depuis A ≥ 0, alors, on a :
ˆ A ) = x ∈ P : xj ≤ λv
ˆ A
P (λv
j

(3.4)

est non-vide, pour 1 ≤ i ≤ n
vjA = mini a−1
ij .

(3.5)


Réciproquement, si nous avions une valeur γ > 0 tels que P (Γv) est non vide,
alors nous saurions que λ∗ ≤ QΓ. En conclusion, supposez que γ > 0 était tels que
P (2ΓvA) est non vide, mais P (Γv) est vide. Puis γ ≤ λ∗ ≤ 2Qγ.
Ces observations suggèrent un algorithme simple. On commence par un point
x¯ ∈ P , et met initialement γ = λ(¯
x). Alors, P (γv A ) est non vide ; suppose que
on doive réduire à plusieurs γ par un facteur de 2 jusque la première fois qu’à cela
P (γvA) devient vide. Le nombre d’itérations requises pour atteindre ce point est :
O(log(

λ¯
x
λ¯
x
)) = O(log( ∗ ))
γ
λ

En particulier, suppose que le point de départ x¯ est la solution optimale du programme linéaire minx∈P eT Ax. Puis, clairement λ(¯
x) ≤ mλ∗ , et nous concluent que
la première étape demande des O(log m) itérations.
Dans [20], la borne inférieure λL est trouvé en cherchant un point x˜ ∈ P tel que
c˜
x = minx∈P cx, où c = y t A. pour la borne inférieure λL = CP (y)/y t b, ici, on dénote
CP (y) = c˜
x
La deuxième étape
Afin de calculer une -approximation de λ∗ , la deuxième étape réalise une procédure de la recherche binaire. Cette procédure améliore à chaque itération l’espace



3.2. Algorithme de Plotkin et al.

17

entre la borne supérieure et la borne inférieure sur λ∗ par un facteur 2/3, jusqu’à ce
que l’espace soit réduit au plus la précision désirée .
Pas 0 : Supposons que λU , λL sont des bornes supérieure et inférieure sur λ∗
produit par la première étape, et supposons que xˆ0 ∈ P atteint λ(ˆ
x0 ) = λU . Mettre
k = 0.
Pas 1 : Chercher y ∈ P tel que λ(y) ≤ λ∗ + (λU − λL )/3.
Pas 2 : Si λ(y) > λL + 2(λU − λL )/3 alors mettre à jour λL = λL + (λU − λL )/3
Pas 3 : Au contraire, λ(y) ≤ λL + 2(λU − λL )/3 alors on met à jour la borne
supérieure λU = λ(y).
Pas 4 : Si λU ≤ (1 + )λL , arrêter. Autrement, mettre à jour k = k + 1, xˆk = y et
aller au pas 1.
Dans la partie suivante, nous allons examiner l’algorithme de Plotkin et al. [20].

3.2

Algorithme de Plotkin et al.

Dans cette partie, on va introduire des algorithmes dans [20]. Ils ont présenté
un algorithme plus rapide qui peut nous fournir des solutions approximatives pour
la classe générale de problèmes d’empaquetage et de couverture fractionnaire. Leurs
problèmes généralisés sont formulés comme des optimisations convexes.
Leur algorithme peut être considéré à la fois comme une méthode primale &
duale et une relaxation Lagrangienne du problème. Son principe est simple, partant
du problème initial P , certaines contraintes sont relâchées et remplacées par une

pénalité exponentielle selon le degré de leur violation (relaxation Lagrangienne). À
chaque étape, l’algorithme effectue une descente de type gradient, celle-ci nécessite
l’optimisation d’un problème plus simple P pour lequel on utilise une méthode aussi
efficace que possible. De plus, ils ont analysé théoriquement le temps de calculs de
l’algorithme basé une relaxation Lagrangienne.
Après, nous représentons l’algorithme pour le problème d’empaquetage fractionnaire, celui pour le problème de couverture fractionnaire est pareil.

3.2.1

Procédure principale

Entrée : x et , x peut initialiser selon une telle critique. Par exemple, pour le
problème des flots coût-minimum on pousse d’abord des flots autant que possible
selon des demandes malgré la violation des capacités sur des arêtes.
−1
Pas 1. Initialiser. Mettre λ0 ← maxi ai x/bi ; α ← 4λ−1
ln(4m −1 ); σ ←
0
.
4αρ
Pas 2. Mettre à jour la solution duale : Pour chaque i = 1, ..., m : mettre
yi ← b1i e−αai x/bi


Chapitre 3. Algorithmes basés sur les méthodes de fonction potentielle
exponentielle

18

Pas 3. Chercher un point du coût-minimum x ∈ P pour des coûts c = y t A.

Pas 4. Pour une valeur appropriée σ, mettre à jours x ← (1 − σ)x + σx.
Pas 5. Si x des conditions d’arrête, alors s’arrêter.
Pas 6. Au contraire, aller au pas 2.
Les conditions d’arrête dans le pas 5 doit être faites précisément.
1. (P ST 1) (1 − )λy t b ≤ y t Ax
2. (P ST 2) y t Ax − CP (y) ≤ (CP (y) + y t b) .
Dans le pas 3, on suppose qu’in a l’ oracle de génération des colonnes suivant :
m
> 0, l’oracle trouve une colonne x˜ ∈ P , tel que :
Donner y ∈ R+
c˜
x = min(cx : x ∈ P ), ou c = y t A.

(3.6)

Note que si cj = 0 pour quelques j ∈ 1..n, alors sans perte de généralité, on peut
mettre xj = 0, tandis que si bi = 0 pour quelques i ∈ 1..m, alors n’importe quelle
solution faisable a xj = 0 pour tout j ∈ 1..n pour quel Aij > 0.
Théoriquement, la sous-tâche ci-dessus est le problème dual de celui origine.
Dans le chapitre prochaine, nous abordons au problème des flots dans lequel cette
sous-tâche là est le problème minimum coûte dans [17] ou le chemin le plus court
dans [5].

3.2.2

Analyse

On va analyser la convergence de la fonction potentielle exponentielle présentée
par Plotkin et al [20] pour le problème d’empaquetage fractionnaire.
La dualité de la programmation linéaire nous donne une caractéristique de la

solution optimale. Suppose y ≥ 0, y ∈ Rm dénote une solution duale, et suppose
CP (y) dénote la valeur minimum de cT x pour tout x ∈ P , où c = y T A. Suppose
(x, λ) dénote une solution faisable. Nous considérons la chaîne des inégalités :
λy t b ≥ y t Ax ≥ CP (y).

(3.7)

On trouve que toutes les deux y t b et CP (y) sont indépendantes de x et λ. De
plus, pour n’importe quelle solution duale y, la valeur CP (y)/y t b est toujours une
borne inférieure de λ∗ . C’est-à-dire que λ∗ ≥ CP (y)/y t b.
Considérer une paramètre d’erreur > 0, un point x ∈ P satisfaisant Ax ≤ λb
et une solution duale y. On a :
Lemme 2 (Plotkin et al [20]) Si (x, λ) et y sont des solutions primale et duale
faisables qui satisfont des conditions relaxées d’optimalité P ST 1 et P ST 2 et si ≤ 61 ,
alors (x, λ) est 6 − optimal.
Preuve : A partir de P ST 1 et P ST 2. On a
CP (y) ≥ (1 − )(y t Ax − λy t b) ≥ (1 − )2 λy t b − λy t b ≥ (1 − 3 )λy t b.
Alors, λ ≤ (1 − 3 )−1 CP (y)/(y t b) ≤ (1 − 3 )−1 λ∗ ≤ (1 + 6 )λ∗