Projet de m moire pour lobtention du titre de
Docteur en Syst mes Informatiques et
Automatiques
de lEcole 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 lart ................................................................................................................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 larchitecture 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 doptimisations...............................................................................................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 Suvre 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 lart ................................................................................................................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 Suvre 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 lart ..............................................................................................................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 dun probl me .....................................................12
III.1 D roulement de lalgorithme 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 dune 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 dacc 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 nSuds par la grille de threads sur GPU....................................85
V.4
Etape d lagage : Proc dure de substitution sur GPU dun nSud non prometteur l
apr s affectation sur CPU de ladresse j du nSud 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 lalgorithme 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 dex cution de lalgorithme 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 darticles.........................................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 lalgorithme 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 doptimisation 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 davions ou de bateaux, l conomie
comme la gestion de portefeuille ou dans lindustrie 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 douvrages qui lui sont consacr s
est important, on peut notamment citer les ouvrages de r f rence et ,
Publicité
mais aussi les diff rents travaux proposant diverses m thodes pour r soudre ce probl me (cf
, , , , , , , et
).
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 , Hanafi et al. et Boyer et al. .
Le probl me du partage quitable (KSP) : on notera les travaux de Hifi et al.
Belgacem et Hifi , Boyer et al. .
Le probl me du sac dos multiple (MKP) : on notera les travaux de Hung et Fisk
, Martello et Toth .
2
Chapitre I. Introduction g n rale
Le probl me du sac dos disjonctif (DCKP) : on notera les travaux de Yamada et
Kataoka , Hifi et Michrafy .
Le probl me de bin packing: on notera les travaux de Bekrar et al. et Hifi et
al. .
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 loptimalit 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 sur une m thode
coop rative pour le probl me du sac dos. On note aussi le travail de Boyer et al.
sur une m thode coop rative pour le probl me du sac dos multidimensionnel. Les tests
num riques pr sent s montrent lefficacit des m thodes coop ratives par rapport aux
m thodes classiques.
Le parall lisme constitue une autre approche afin dacc l rer la r solution de probl mes
doptimisation combinatoire. Lapparition 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. , .
On sest int ress dans ce m moire la r solution dune 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
sagit de choisir certains conteneurs, dans un ensemble de n conteneurs charger dans m
navires de diff rentes capacit s de chargement (cf ), le chargement de n r servoirs
par m liquides qui ne peuvent pas tre m lang s (cf ); laffectation 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 lutilisation des GPUs pour la mise en
Suvre parall le de m thodes doptimisation 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
Suvre parall le de la m thode de programmation dynamique sur GPU, cf. Boyer et al. et . Notre travail, sest concentr sur la mise en Suvre 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 dabord par un tat de lart du MKP et d taillons en
particulier une heuristique qui t propos e pour le probl me du sac dos multiple, savoir
lheuristique MTHM de Martello et Toth . Nous pr sentons en d tail notre
contribution savoir lheuristique 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
lapproche bas e sur la programmation dynamique propos e par Elkihel tandis que
le dernier noyau est r solu en utilisant la programmation dynamique classique.
Le chapitre IV est consacr au GPU. Nous commen ons dabord par donner un tat de lart
du calcul sur GPU. Puis, nous nous int resserons larchitecture CUDA (Compute Unied
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 lapproche que nous avons suivie pour la mise en Suvre
parall le de lalgorithme de Branch and Bound sur GPU. Nous donnons un bref tat de lart
relatant les diff rentes impl mentations parall les existantes pour lalgorithme de Branch and
Bound, quelles soient sur des machines multi-cSurs, grilles de calculs ou sur architecture
GPU. Nous expliquons les diff rents choix que nous avons faits pour aboutir la mise en
Suvre propos e. Ceux-ci concernent tout aussi bien la strat gie de s paration des nSuds, les
donn es sauvegard s pour chaque nSuds, 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 dacc s en
m moire. Pour finir, nous pr sentons nos r sultats et les analysons.
Enfin, nous pr sentons au chapitre VI, lapproche que nous avons suivie pour la mise en
Suvre parall le de la m thode du Simplexe sur GPU et sur un syst me Multi-GPU. Nous
commen ons dabord par pr senter un bref tat de lart. Nous expliquons ensuite les diff rents
choix que nous avons faits pour aboutir la mise en Suvre propos e. Ceux-ci concernent
aussi bien lidentification des t ches de cet lalgorithme qui peuvent se parall liser de mani re
performante, que le choix des m moires utilis es et le moyen utilis pour r duire leffet de
chemins divergents induits par des instructions conditionnelles. Nous proposons, ensuite, une
mise en Suvre multi-GPU de lalgorithme 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 Suvre s quentielle, sur GPU et
la mise en Suvre 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 dun 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 dun probl me, afin de r duire sa cardinalit . Enfin nous
pr senterons quelques solveurs utilis s dans le domaine de loptimisation.
II.2 Le probl me du sac dos (KP)
De mani re g n rale, un probl me doptimisation peut tre formul de la fa on suivante :
(
P
)
max
)(
xf
..
Xxcs
(II.1)
o :
-
f
(.)
est une fonction dutilit 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
)
e
(
xf
),
Xx
Publicité
.
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 sint 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 doptimisation combinatoire appartenant
la classe des probl mes NP-complets . 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 dobjets 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
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 lobjet 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 en 1957. Lint r t
port au sac dos est d au fait quil 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 doptimisation 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 dapplication, on r sout souvent
un probl me KP afin dobtenir 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 01, 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 darticles charger o chaque article dindice j est
caract ris par un profit
jp et un poids
jw . Nous consid rons m sacs dos o chaque sac
dindice 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 dindice i ne d passe pas la capacit
ic .
Nous notons par xij la variable binaire de d cision qui prend la valeur 1 si larticle dindice j
est affect au sac dos dindice 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
K
,
m
}
,
cs
..
n
Publicité
1
j
=
m
x
ij
i
1
=
}
,1,0
i
,1
{
,1
j
K
,
,
{
K
,1
}
jm
,
,
}
n
{
,1
K
,
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 dinstances 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 .
Nous faisons lhypoth se que les n articles sont tri s par ratio profit sur poids d croissant, on
dit aussi efficacit d croissante, comme illustr par lin galit (II.6).
p
1
w
1
p
2
w
2
...
p
n
w
n
.
(II.6)
Nous d signons par s lindice de rupture ou de base du probl me (KP) qui est donn par
lin 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
,
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
L
nd
.
(II.9)
Le noyau ou core, en anglais, correspond au sous-ensemble darticles avoisinant larticle de
base, dindice s.
Balas et Zemel 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
Publicité
*
j
*
j
Lensemble 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 dinstances, 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)
lensemble 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 larticle de base.
Plusieurs propositions ont t faites quant la taille C du noyau. Balas et Zemel
ont propos de prendre une valeur constante C = 50 ; Martello et Toth ont
propos une valeur
C =
n
, puis
C 2=
n
. 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
et Martello et Toth . Pisinger a propos un algorithme bas sur la
m thode du Quick-sort modifi e (cf. Hoare ), qui d termine lindice de la variable
de rupture s et trie les C articles autour de s (voir aussi r f rence ).
Plusieurs exp rimentations ont t men es par Pisinger 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 darticles (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 lon 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 dalgorithmes :
-
les algorithmes noyau fixe (cf Balas et Zemel , Fayard et Plateau , Martello et Toth ).
11
Chapitre II. G n ralit s sur le sac dos.
-
les algorithmes noyau extensible, comme lalgorithme Expknap pr sent par
Pisinger 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 dalgorithmes 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) est lune des m thodes les plus connues
pour la r solution de probl mes doptimisation combinatoire NP...