Projet de mémoire pour l’obtention du titre de
Docteur en Systèmes Informatiques et Automatiques
de l’Ecole Doctorale EDSYS
Université Toulouse 3 Paul Sabatier
Présenté par :
Mohamed Esseghir LALAMI
Titre :
Contribution à la résolution de problèmes d'optimisation
combinatoire: méthodes heuristiques et parallèles
Table des matières
I.
Introduction générale ................................................................................................1
II.
Généralités sur le sac à dos........................................................................................5
II.1
II.2
Introduction .................................................................................................................5
Le problème du sac à dos (KP).....................................................................................6
II.2.1 Le problème du sac à dos multiple .............................................................................7
II.2.2 Le noyau du sac à dos................................................................................................8
II.3 Méthodes de résolution exactes..................................................................................11
II.3.1 La méthode de Branch and Bound ...........................................................................11
II.3.2 La Programmation Dynamique ................................................................................14
II.4 Calcul de bornes et méthode de réduction de variables ...............................................19
II.4.1 Bornes supérieures pour le problème KP .................................................................19
II.4.2 Bornes inferieures pour le problème KP...................................................................21
II.4.3 Réduction de variables.............................................................................................21
II.5
Les solveurs existants ................................................................................................23
II.6 Conclusion.................................................................................................................25
III. Le problème du sac à dos multiple ..........................................................................27
III.1 Introduction ...............................................................................................................27
III.2 Le problème du sac à dos multiple MKP ....................................................................28
III.3 Etat de l’art ................................................................................................................29
III.3.1 Différentes relaxations du problème MKP ..............................................................29
a. La relaxation surrogate ...........................................................................................30
b. La relaxation continue ............................................................................................31
c. La relaxation Lagrangienne ....................................................................................31
III.3.2 Algorithmes pour le problème du MKP ..................................................................33
ii
Table des matières
III.4 Une Nouvelle heuristique RCH pour le problème MKP .............................................36
III.4.1 Remplissage classique : algorithme Glouton .......................................................38
III.4.2 Remplissage efficace : utilisation du noyau.........................................................39
III.5 Résultats expérimentaux ............................................................................................44
III.6 Conclusions et perspectives .......................................................................................48
IV.
Introduction à CUDA et à l’architecture GPU .......................................................49
IV.1 Introduction ...............................................................................................................50
IV.2 Algorithmes et applications........................................................................................52
IV.3 Architecture GPU ......................................................................................................55
IV.3.1 Les threads.............................................................................................................57
IV.3.2 Les mémoires.........................................................................................................58
IV.3.3 Host et Device........................................................................................................59
IV.4 Règles d’optimisations...............................................................................................63
IV.4.1 Instructions de base ................................................................................................63
IV.4.2 Instructions de contrôle ..........................................................................................63
IV.4.3 Instruction de gestion mémoire...............................................................................64
a. Mémoire globale ....................................................................................................64
b. Mémoire locale ......................................................................................................66
c. Mémoire constante .................................................................................................66
d. Registres et mémoire partagée ................................................................................66
e. Nombre de threads par bloc ....................................................................................69
f.
Transferts de données CPU ↔ GPU .......................................................................70
IV.5 Conclusion.................................................................................................................70
V. Mise en œuvre CPU-GPU de la méthode du Branch and Bound...........................71
V.1
Introduction ...............................................................................................................71
V.2 Branch and Bound pour le sac à dos...........................................................................72
V.2.1 Formulation du problème ........................................................................................72
V.2.2 La méthode de Branch and Bound ...........................................................................73
iii
Table des matières
V.3
Etat de l’art ................................................................................................................77
V.4 Calcul hybride ...........................................................................................................80
V.4.1
Initialisation et algorithme général ......................................................................80
V.4.2 Algorithme parallèle ...........................................................................................81
V.4.3
Calculs sur GPU .................................................................................................83
V.4.4
Calculs sur CPU..................................................................................................91
V.5 Résultats expérimentaux ............................................................................................91
V.6 Conclusions et perspectives .......................................................................................94
VI. Mises en œuvre CPU-GPU et Multi-GPU de la méthode du Simplexe ..................96
VI.1 Introduction ...............................................................................................................97
VI.2 Rappel mathématique sur la méthode du Simplexe.....................................................98
VI.3 Etat de l’art ..............................................................................................................104
VI.4 Simplexe sur un système CPU-GPU ........................................................................107
VI.4.1 Initialisation et algorithme général .......................................................................107
VI.4.2 Calcul de la variable entrante et la variable sortante .............................................108
VI.4.3 Mise à jour de la base...........................................................................................111
VI.5 Simplexe sur un système Multi-GPU .......................................................................117
VI.5.1 Initialisation .........................................................................................................118
VI.5.2 Les threads CPU ..................................................................................................118
VI.5.3 Calcul de la variable entrante et la variable sortante .............................................120
VI.6 Résultats expérimentaux ..........................................................................................121
VI.7 Conclusions et perspectives .....................................................................................124
VII. Conclusions et Perspectives ...................................................................................127
Annexe A...........................................................................................................................131
Liste des publications .......................................................................................................133
Références bibliographiques ............................................................................................135
iv
Table des matières
Table des figures
II.1 Arbre engendré par décomposition d’un problème .....................................................12
III.1 Déroulement de l’algorithme associant la réduction de variables à la méthode de
programmation dynamique. .......................................................................................43
IV.1 Evolution des performances de calcul des CPUs et GPUs ..........................................50
IV.2 Architecture CPU et architecture GPU. ......................................................................51
IV.3 Architecture des applications CUDA..........................................................................55
IV.4 Illustration d’une grille de threads..............................................................................58
IV.5 Déroulement du programme sur CPU faisant intervenir le GPU. ................................60
IV.6 Multiprocesseur SIMT avec mémoire partagée embarquée.........................................62
IV.7 Exemples d’accès à la mémoire globale .....................................................................65
IV.8 Adressages à la mémoire partagée avec et sans conflit de bancs.................................68
IV.9 Adressages à la mémoire partagée avec diffusion.......................................................69
V.1 Arbre de décision.......................................................................................................76
V.2 Algorithme de Branch and Bound sur CPU-GPU ......................................................82
V.3 Création de nouveaux nœuds par la grille de threads sur GPU....................................85
V.4
Etape d’élagage : Procédure de substitution sur GPU d’un nœud non prometteur l
après affectation sur CPU de l’adresse j du nœud qui va le remplacer ........................90
VI.1 Représentation géométrique du polytope pour un exemple.........................................99
VI.2 Déclaration et allocation mémoire du tableau Simplexe............................................108
VI.3 Architecture globale de l’algorithme du Simplexe sur un système CPU-GPU...........109
VI.4 Operations matricielles, gestion de mémoire dans le kernel 3’..................................114
VI.5 Décomposition du TableauSimplexe et accès mémoire des threads CPU ..................118
vi
Table des figures
VI.6 Temps d’exécution de l’algorithme du Simplexe sur un CPU et différents
systèmes avec un GPU et deux GPUs (Nvidia Tesla C2050) ....................................122
Liste des tableaux
II.1
Taille minimale du noyau C suivant le nombre d’articles.........................................10
II.2
Listes de la programmation dynamique .....................................................................17
III.1 Temps de calcul et gaps pour des problèmes non corrélés ..........................................46
III.2 Temps de calcul et gaps pour les problèmes faiblement corrélés ................................46
III.3 Temps de calcul et gaps pour des problèmes fortement corrélés .................................47
V.1 Comparaison des temps moyens de calcul de l’algorithme B&B séquentiel et
parallèle .....................................................................................................................92
V.2
Speedup de l’étape de calcul de borne ........................................................................93
VI.1 Tableau du Simplexe................................................................................................101
VI.2 Accélérations moyennes...........................................................................................123
viii
Liste des tableaux
Chapitre I Introduction générale
Le problème du sac à dos fait partie des problèmes d’optimisation combinatoire les plus
étudiés ces cinquante dernières années, en raison de ces nombreuses applications dans le
monde réel. En effet, ce problème intervient souvent comme sous-problème à résoudre dans
plusieurs domaines : la logistique comme le chargement d’avions ou de bateaux, l’économie
comme la gestion de portefeuille ou dans l’industrie comme la découpe de matériaux.
Ce problème en variables 0-1, dont l’énoncé est assez simple, fait partie des problèmes
mathématiques NP-complets. Cela explique que le nombre d’ouvrages qui lui sont consacrés
est important, on peut notamment citer les ouvrages de référence [KEL 04] et [MAR 90],
mais aussi les différents travaux proposant diverses méthodes pour résoudre ce problème (cf
[BEL 57], [GIL 65], [KOL 67], [BAL 80], [PLA 85] , [ELK 02] , [MEL 05] , [HIF 08] et
[BEL 08a]).
De nos jours le problème du sac à dos se résout de manière assez efficace. Les travaux actuels
portent sur différentes variantes du problème du sac à dos qui sont beaucoup plus difficiles à
résoudre. On peut en citer :
– Le problème du sac à dos multidimensionnel (MKP) : on notera les travaux de Freville
et Plateau [FRE 94], Hanafi et al. [HAN 96] et Boyer et al.[BOY 10].
– Le problème du partage équitable (KSP) : on notera les travaux de Hifi et al. [HIF 05]
Belgacem et Hifi [BEL 08b], Boyer et al. [BOY 11].
– Le problème du sac à dos multiple (MKP) : on notera les travaux de Hung et Fisk
[HUN 78], Martello et Toth [MAR 80].
2
Chapitre I. Introduction générale
– Le problème du sac à dos disjonctif (DCKP) : on notera les travaux de Yamada et
Publicité
Kataoka [YAM 01], Hifi et Michrafy [HIF 07].
– Le problème de bin packing: on notera les travaux de Bekrar et al.[BEK 10] et Hifi et
al. [HIF 10].
Les approches proposées dans la littérature, pour résoudre les problèmes de la famille du sac à
dos sont des méthodes exactes capables de résoudre un problème à l’optimalité ou des
heuristiques qui fournissent une solution approchée de bonne qualité dans des temps de
résolution très raisonnables.
Les méthodes classiques telles que la programmation dynamique et le Branch and Bound
peuvent être combinées de manière efficace afin de donner naissance à des méthodes
coopératives ou hybrides. On note par exemple le travail de Viader [VIA 98] sur une méthode
coopérative pour le problème du sac à dos. On note aussi le travail de Boyer et al. [BOY 10]
sur une méthode coopérative pour le problème du sac à dos multidimensionnel. Les tests
numériques présentés montrent l’efficacité des méthodes coopératives par rapport aux
méthodes classiques.
Le parallélisme constitue une autre approche afin d’accélérer la résolution de problèmes
d’optimisation combinatoire. L’apparition de nouvelles architectures comme les Graphics
Processing Units ou GPUs semble particulièrement intéressante afin de diminuer les temps de
résolution de manière économique. cf. [LUO 10], [BOY 11].
On s’est intéressé dans ce mémoire à la résolution d’une variante du problème du sac à dos à
savoir le problème du sac à dos multiple (MKP). Ce problème compte plusieurs applications
industrielles dont on peut citer quelques exemples : le chargement de fret sur les navires, où il
s’agit de choisir certains conteneurs, dans un ensemble de n conteneurs à charger dans m
navires de différentes capacités de chargement (cf [EIL 71]), le chargement de n réservoirs
par m liquides qui ne peuvent pas être mélangés (cf [MAR 80]); l’affectation de tâches. Le
problème MKP est NP-complet et la nécessité de trouver des algorithmes donnant une bonne
solution heuristique se justifie par la complexité de ce type de problème.
La deuxième partie de notre contribution porte sur l’utilisation des GPUs pour la mise en
œuvre parallèle de méthodes d’optimisation combinatoire en variables 0-1. Ces travaux font
suite à une série d’études effectuées dans l’équipe CDA du LAAS-CNRS sur la mise en
3
Chapitre I. Introduction générale
œuvre parallèle de la méthode de programmation dynamique sur GPU, cf. Boyer et al. [BOY
11] et [BOY 10]. Notre travail, s’est concentré sur la mise en œuvre parallèle sur GPU de la
méthode de Branch and Bound ainsi que de la méthode du Simplexe.
Organisation de la thèse
Dans le chapitre II, nous commençons par présenter le problème du sac à dos ainsi que
certaines de ces variantes comme le problème du sac à dos multiple. Nous nous intéressons en
particulier à des méthodes de résolution classiques, comme la programmation dynamique et le
Branch and Bound.
Nous proposons au chapitre III une méthode heuristique pour résoudre le problème du sac à
dos multiple. Nous commençons d’abord par un état de l’art du MKP et détaillons en
particulier une heuristique qui à été proposée pour le problème du sac à dos multiple, à savoir
l’heuristique MTHM de Martello et Toth [MAR 81]. Nous présentons en détail notre
contribution à savoir l’heuristique RCH pour Recursive Core Heuristic. Dans cette dernière
méthode, nous considérons le problème du sac à dos multiple comme une succession de
problème de sac à dos à résoudre. Nous définissons alors pour chaque problème KP un noyau.
Nous résolvons alors pour chaque noyau excepté le dernier, un problème de subset sum par
l’approche basée sur la programmation dynamique proposée par Elkihel [ELK 84] tandis que
le dernier noyau est résolu en utilisant la programmation dynamique classique.
Le chapitre IV est consacré au GPU. Nous commençons d’abord par donner un état de l’art
du calcul sur GPU. Puis, nous nous intéresserons à l’architecture CUDA (Compute Unified
Device Architecture) proposée par NVIDIA. Les performances de cette architecture reposent
sur deux éléments fondamentaux : la mémoire et la décomposition du travail en tâches.
Au chapitre V, nous présentons l’approche que nous avons suivie pour la mise en œuvre
parallèle de l’algorithme de Branch and Bound sur GPU. Nous donnons un bref état de l’art
relatant les différentes implémentations parallèles existantes pour l’algorithme de Branch and
Bound, qu’elles soient sur des machines multi-cœurs, grilles de calculs ou sur architecture
GPU. Nous expliquons les différents choix que nous avons faits pour aboutir à la mise en
œuvre proposée. Ceux-ci concernent tout aussi bien la stratégie de séparation des nœuds, les
données sauvegardés pour chaque nœuds, les mémoires utilisées mais aussi les différentes
4
Chapitre I. Introduction générale
techniques et synchronisations utilisées pour diminuer les temps de latence d’accès en
mémoire. Pour finir, nous présentons nos résultats et les analysons.
Enfin, nous présentons au chapitre VI, l’approche que nous avons suivie pour la mise en
œuvre parallèle de la méthode du Simplexe sur GPU et sur un système Multi-GPU. Nous
commençons d’abord par présenter un bref état de l’art. Nous expliquons ensuite les différents
choix que nous avons faits pour aboutir à la mise en œuvre proposée. Ceux-ci concernent
aussi bien l’identification des tâches de cet l’algorithme qui peuvent se paralléliser de manière
performante, que le choix des mémoires utilisées et le moyen utilisé pour réduire l’effet de
chemins divergents induits par des instructions conditionnelles. Nous proposons, ensuite, une
mise en œuvre multi-GPU de l’algorithme du Simplexe mettant à contribution plusieurs cartes
GPUs disponibles dans un seul système pour résoudre un problème de programmation
linéaire. Nous expliquons comment partager le tableau du Simplexe entres les différents
GPUs et comment diminuer ainsi les échanges entre les GPUs et le CPU. Enfin, nous
présentons et analysons les résultats obtenues pour la mise en œuvre séquentielle, sur GPU et
la mise en œuvre parallèle sur un système multi-GPU.
Nous terminons ce mémoire en présentant nos conclusions générales et les perspectives de
recherche.
5
Chapitre I. Introduction générale
Chapitre II Généralités sur le sac à dos
Sommaire
II.1
II.2
Introduction ............................................................................................................................... 5
Le problème du sac à dos (KP)................................................................................................. 6
II.2.1 Le problème du sac à dos multiple ............................................................................................ 7
II.2.2 Le noyau du sac à dos ................................................................................................................ 8
II.3 Méthodes de résolution exactes .............................................................................................. 11
II.3.1 La méthode de Branch and Bound........................................................................................... 11
II.3.2 La Programmation Dynamique................................................................................................ 14
II.4
Calcul de bornes et méthode de réduction de variables....................................................... 19
II.4.1 Bornes supérieures pour le problème KP ................................................................................ 19
II.4.2 Bornes inferieures pour le problème KP.................................................................................. 21
II.4.3 Réduction de variables............................................................................................................. 21
II.5
II.6
Les solveurs existants .............................................................................................................. 23
Conclusion................................................................................................................................ 25
II.1 Introduction
Dans le présent chapitre, nous présentons le contexte dans lequel vont s'inscrire nos travaux
de recherche. Ces travaux s'articulent autour de la résolution de problèmes d'optimisation.
Dans la sous-section II.2, Nous définirons le problème du sac à dos ainsi que le problème du
sac à dos multiple (MKP). Nous définirons aussi la notion de noyau d’un problème de sac à
dos.
6
Chapitre II. Généralités sur le sac à dos.
Dans la sous-section II.3, Nous présenterons les deux méthodes exactes utilisées pour la
résolution de problème de type sac à dos : le Branch and Bound et la programmation
dynamique. Nous parlerons aussi de la manière de calculer les bornes supérieures et
inferieures pour le problème du sac à dos et présenterons la méthode de réduction de variables
qui est une étape de prétraitement d’un problème, afin de réduire sa cardinalité. Enfin nous
présenterons quelques solveurs utilisés dans le domaine de l’optimisation.
II.2 Le problème du sac à dos (KP)
De manière générale, un problème d’optimisation peut être formulé de la façon suivante :
P
max )( xf .. Xxcs
(II.1)
où:
-
f
(.)
est une fonction d’utilité à maximiser (ou minimiser en remplaçant max par min),
- X est un ensemble fini, défini par un ensemble de contraintes sur les variables.
On recherche alors une solution optimale
x ∈*
X
telle que
( *xf
)
≥
( xf
∈∀),
Xx
.
Plusieurs problèmes théoriques ou réels peuvent être écrits suivant (II.1), avec une fonction
objectif et un ensemble de contraintes et de variables bien déterminés. Ces dernières peuvent
être linéaires, entières ou mixtes.
On s’intéresse ici aux problèmes à variables entières 0-1 à savoir des problèmes de la famille
du sac à dos.
Le problème du sac à dos est un problème classique d’optimisation combinatoire appartenant
à la classe des problèmes NP-complets [FRE 04]. L’énoncé de ce problème est simple : étant
donné un ensemble de n objets, où chaque objet i est caractérisé par un poids
iw et un profit
ip on cherche le sous-ensemble d’objets à charger dans un sac de capacité c afin de maximiser
la somme des profits. Ainsi, le problème du sac à dos se présente sous la forme mathématique
suivante :
7
Chapitre II. Généralités sur le sac à dos.
max
n
i
1
n
. xw i 1 i ,1,0
i
(
KP
)
x
i
. xp i
i
,
,
c
,..,1
Publicité
i
n
(II.2)
Les poids wi et les profits pi ainsi que la capacité c sont des entiers positifs
i
1
,...,
n
.
La variable xi est la variable de décision ; elle prend la valeur 1 si l’objet i est chargé dans le
sac, sinon elle prend la valeur 0.
Résoudre ainsi le problème du sac à dos revient à trouver le vecteur solution
x
*
(
* x 1
,...,
* nx
T
)
qui optimise (maximise dans ce cas) la fonction objectif définie en (II.2).
Le problème du sac à dos, Knapsack Problem (KP) en anglais, et ces différentes variantes ont
été longuement étudiés depuis le travail pionnier de Dantzig [DAN 57] en 1957. L’intérêt
porté au sac à dos est dû au fait qu’il permet de modéliser de très nombreux problèmes
comme les problèmes de gestion de capital, de chargement de cargaison, de rotation
d’équipage, de tournées et de livraison ; par ailleurs, ce problème apparaît comme un sous-
problème de nombreux problèmes d’optimisation combinatoire.
Les problèmes de type sac à dos apparaissent aussi fréquemment comme une relaxation de
problèmes de programmation en nombre entier. Dans ce type d’application, on résout souvent
un problème KP afin d’obtenir une borne supérieure. On présente dans ce qui suit le problème
du sac à dos multiple que nous serons amenés à étudier au chapitre III. Nous définirons aussi
une notion importante qui est le « noyau » du sac à dos.
II.2.1 Le problème du sac à dos multiple
Le problème du sac à dos multiple (MKP) est une généralisation du problème standard du sac
à dos en variable 0–1, où on essaie de remplir m sacs à dos de différentes capacités au lieu de
considérer un seul sac à dos.
Soit N = {1, ..., n} l'ensemble des indices d’articles à charger où chaque article d’indice j est
caractérisé par un profit
jp et un poids
jw . Nous considérons m sacs à dos où chaque sac
d’indice i, i
{1, ..., m} est de capacité de chargement
ic . Alors le problème du sac à dos
∈
8
Chapitre II. Généralités sur le sac à dos.
multiple consiste à remplir tous les sacs à dos de façon à maximiser le profit total et de sorte
que la somme des poids dans chaque sac à dos d’indice i ne dépasse pas la capacité
ic .
Nous notons par xij la variable binaire de décision qui prend la valeur 1 si l’article d’indice j
est affecté au sac à dos d’indice i et 0 dans le cas contraire. Le problème du sac à dos multiple
(MKP) peut être formulé de la manière suivante :
(
MKP
)
max
m
n
i
1
j
1
xp j
ij
,
xw j
ij
ic , i
,1
,
m
,
cs ..
n
1
j m
x
ij
i 1 ,1,0
i
,1
,1
j
,
,
,1 jm ,
,
n
,1
,
n
;
x
ij
(II.3)
(II.4)
(II.5)
où jp ,
ic et
jw sont des entiers positifs et les contraintes (II.4) et (II.5), assurent respectivement,
que le remplissage du sac à dos i ne dépasse pas sa capacité correspondante ic et que chaque
article sélectionné est attribué, au plus, à un seul sac à dos.
II.2.2 Le noyau du sac à dos
De nombreux tests expérimentaux sur une large variété d’instances de problèmes de sac à dos
ont montré que seul un sous-ensemble contenant un nombre relativement faible d'articles est
crucial pour la détermination de la solution optimale, ceci est particulièrement vrai si le
nombre d'articles est très grand [PIS 97].
Nous faisons l’hypothèse que les n articles sont triés par ratio profit sur poids décroissant, on
dit aussi efficacité décroissante, comme illustré par l’inégalité (II.6).
p 1 w 1
p 2 w 2
...
p n w n
.
(II.6)
Nous désignons par s l’indice de rupture ou de base du problème (KP) qui est donné par
l’inégalité suivante :
9
Chapitre II. Généralités sur le sac à dos.
s
1
j
1
w
j
c
s
j
1
w
.
j
(II.7)
Nous introduisons la notion de coût réduit pour un article j comme suit :
d
j
p
j
p
s
.
w
j
w s
Publicité
,
j
,...,1
. n
(II.8)
Les articles les plus attractifs sont ceux qui on le coût réduit le plus grand en valeur absolue
d 1
d
2
nd
.
(II.9)
Le noyau ou core, en anglais, correspond au sous-ensemble d’articles avoisinant l’article de
base, d’indice s.
Balas et Zemel [BAL 80] ont donné une définition précise du noyau d'un problème de sac à
dos, cette définition présentée ci-dessous est basée sur la connaissance d'une solution optimale
du problème LKP.
Définition II.1: Supposons que les éléments sont triés suivant un ratio profit sur poids décroissant et notons par x* le vecteur solution optimale du problème KP. Posons ,0
max
min
(II.10)
xj
.1
xj
:
:
b
a
* j
* j
L’ensemble C = {a, ..., b} représente le noyau du problème (KP). De plus, si on pose
~ p
a
1
j
1
~et w
p
j
a
1
j
1
w
j
le problème du knapsack sur le noyau est formulé ainsi :
max
xp j
j
,~ p
Cj xw j
(
KPC
)
s.c.
Cj x
j
.1,0
,~ wc
j
(II.11)
Pour de nombreuses classes d’instances, la taille du noyau est petite par rapport à n. Par
conséquent, si les valeurs a et b sont connues a priori, le problème initial peut facilement être
résolu en posant
= 1 pour j = 1, ..., a 1 et
= 0 pour j = b +1,..., n et en résolvant tout
∗ simplement le knapsack sur le noyau par la méthode de Branch and Bound ou la (cid:1876)(cid:3037) programmation dynamique. Nous rappelons que la notation C correspond au cardinal de
∗ (cid:1876)(cid:3037)
l’ensemble C.
10
Chapitre II. Généralités sur le sac à dos.
En pratique, les valeurs de a et b ne sont pas connues a priori, la plupart des algorithmes
utilisant la notion de noyau reposent sur le choix de C articles autour de l’article de base.
Plusieurs propositions ont été faites quant à la taille C du noyau. Balas et Zemel [BAL 80]
ont proposé de prendre une valeur constante C = 50 ; Martello et Toth [MAR 88] ont
proposé une valeur
C
n
, puis
C 2
n
[MAR 97]. Ces différentes valeurs de C se
rapportent à des interprétations différentes du problème.
Des algorithmes de recherche de la taille du noyau ont aussi été proposés par Balas et Zemel
[BAL 80] et Martello et Toth [MAR 88]. Pisinger a proposé un algorithme basé sur la
méthode du Quick-sort modifiée (cf. Hoare [HOA 62]), qui détermine l’indice de la variable
de rupture s et trie les C articles autour de s (voir aussi référence [PIS 95]).
Plusieurs expérimentations ont été menées par Pisinger [PIS 97] sur différents types de
problèmes (KP) pour déterminer la taille minimale du noyau. Celles-ci sont présentées dans le
tableau ci-après :
N
Problèmes faiblement corrélés 12 17 17 21 25 TABLEAU II.1 Taille minimale du noyau C suivant le nombre d’articles (moyenne sur
Problèmes Non corrélés 5 8 11 14 17
Problèmes Fortement Corrélés 13 25 36 79 104
100 500 1000 5000 10000
14 13 13 13 13
Subset sum
100 instances).
La taille du noyau en pratique doit être plus grande que les valeurs présentées dans le tableau
ci-contre, si l’on veut prouver l'optimalité de la solution obtenue.
De cette étude sur le noyau, plusieurs algorithmes exacts de résolution de problèmes (KP),
appelés algorithmes noyau, ont été proposés. On dénombre deux types d’algorithmes :
-
les algorithmes à noyau fixe (cf Balas et Zemel [BAL 80], Fayard et Plateau [FAY
82], Martello et Toth [MAR 88] [MAR 97]).
11
Chapitre II. Généralités sur le sac à dos.
-
les algorithmes à noyau extensible, comme l’algorithme Expknap présenté par
Pisinger [PIS 95] qui utilise la méthode de Branch and Bound. Dans cette méthode, le
noyau contient initialement la variable de base, mais cet ensemble est étendu à chaque
fois que la méthode de Branch and Bound atteint les bords du noyau ou la solution du
problème initiale.
Ces algorithmes utilisent généralement la méthode de Branch and Bound pour l’énumération.
II.3 Méthodes de résolution exactes
Nous présentons dans cette sous-section deux méthodes sur lesquelles se basent un grand
nombre d’algorithmes pour la résolution des problèmes de type sac à dos : la méthode de
séparation et d’évaluation (Branch and Bound) et la méthode de programmation dynamique.
II.3.1 La méthode de Branch and Bound
La méthode de Branch and Bound (B&B) [LAN 60] est l’une des méthodes les plus connues
pour la résolution de problèmes d’optimisation combinatoire NP-difficiles. Cette méthode est
basée sur une recherche arborescente d’une solution optimale par séparation et évaluation.
Ainsi la résolution d’un problème combinatoire formulé par (II.1) consiste à trouver la
solution optimale
x *
X
telle que
( * xf
)
maximiser.
( xf
),
Xx
, où f est la fonction
objectif à
Il est à noter que l’énumération de l’ensemble des éléments de X est très souvent peu réaliste
en raison de l’importance de son cardinal. La méthode de Branch and Bound tente d’explorer
intelligemment l’ensemble des solutions admissibles en éliminant de l’espace de recherche les
sous-ensembles de solutions qui ne peuvent pas fournir une solution optimale.
Présentation de l’algorithme
La recherche par décomposition de l’ensemble des solutions peut être représentée
graphiquement par un arbre (voir la Figure II.1). C’est de cette représentation que vient le
nom de “méthode de recherche arborescente”.
- Chaque sous-problème créé au cours de l’exploration est symbolisé par un nœud
de l’arbre (ou sommet), le nœud racine représentant le problème initial.
12
Chapitre II. Généralités sur le sac à dos.
- Les branches de l’arbre symbolisent le processus de séparation. Elles représentent
la relation entre les nœuds.
- Lors de la séparation, un nœud «père» crée un ensemble de nœuds «fils».
Nœud Initial
x1 = 1
Nœud père x1 = 0
x2 = 1