Optimisation combinatoire 4 : problèmes paradigmatiques (Traité IC2 série informatique et systèmes d information)
234 pages
Français

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Optimisation combinatoire 4 : problèmes paradigmatiques (Traité IC2 série informatique et systèmes d'information) , livre ebook

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
234 pages
Français
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Cet ouvrage est le quatrième de la série "Optimisation combinatoire". Il traite des problèmes phares de l'optimisation combinatoire ainsi que des problématiques récentes ou émergentes. L'ouvrage est divisé en deux parties. La première partie est consacrée aux problèmes paradigmatiques (ordonnancements, voyageur du commerce, coloration, etc.) dont les études et les concepts ont façonné l'optimisation combinatoire en lui donnant le visage que l'on lui connaît aujourd'hui. La deuxième partie présente des sujets émergents en optimisation combinatoire tels que la théorie des jeux combinatoires, l'optimisation combinatoire multicritère, la robustesse ou encore les algorithmes exacts avec complexité non-triviale au pire des cas pour des problèmes NP-difficiles.
Avant-propos -V. Th. PASCHOS. Chapitre 1. Le problème de coupe maximum -W. BEN-AMEUR, A. R. MAHJOUB, J. NETO. Chapitre 2. Ordonnancements - Ph. CHRÉTIENNE, Ch. PICOULEAU. Chapitre 3. Localisation de ressources -A. GIANNAKOS. Chapitre 4. Algorithmes MiniMax et jeux -M. KOSKAS. Chapitre 5. Le problème de bin packing à deux dimensions -A. LODI, S. MARTELLO, D. VIGO. Chapitre 6. Le problème du sac à dos 0-1-G. PLATEAU, A. NAGIH. Chapitre 7. Les problèmes de sac à dos quadratiques entiers -D. QUADRI, E. SOUTIF, P. TOLLA. Index.

Sujets

Informations

Publié par
Date de parution 02 mars 2007
Nombre de lectures 85
EAN13 9782746228290
Langue Français

Informations légales : prix de location à la page 0,0698€. Cette information est donnée uniquement à titre indicatif conformément à la législation en vigueur.

Extrait

Chapitre 1
Le problème de coupe maximum
1.1. Introduction
Unecoupedans un grapheG= (V, E), correspondant à un ensemble de som-metsWV, est l’ensemble d’arêtes ayant une extrémité dansWet l’autre dans V\W.Le problème de coupe maximum(COUPE-MAX) est un des problèmes fonda-mentaux en optimisation combinatoire. Ce problème peut être présenté de la manière suivante : étant donnés un grapheG= (V, E)et des poids(ω(e)R, eE)sur les arêtes, trouver une coupeδ(W),WV, telle queω(e)est maximum. eδ(W) Ce problème était, durant ces vingt dernières années, l’objet de recherches intensives [DEZ 97]. Il est l’un des premiers problèmes démontrés NP-complets [GAR 79]. Il a des applications dans plusieurs domaines comme par exemple la physique statistique, les circuits VLSI et lesots dans les réseaux. Il a été étudié à l’aide de différentes ap-proches comme par exemple l’approche polyédrale, qui est basée sur le polyèdre des solutions du problème, la programmation semi-dénie et les algorithmes approchés avec et sans garantie. Le problème COUPE-MAX était ainsi un des sujets les plus motivants et les plus étudiés en optimisation combinatoire. Dans ce chapitre, nous discutons de ce problème en mettant l’accent sur les aspects algorithmiques.
Le problème COUPE-MAX est étroitement lié au problème du sous-graphe biparti maximum. Un grapheG= (V, E)est ditbipartisiVpeut être partitionné en deux sous-ensembles V1etV2de telle manière que toutes les arêtes soient entreV1etV. Si 2 G= (V, E)est un graphe muni de poids sur les arêtes,le problème du sous-graphe biparti maximumdansGconsiste à trouver un sous-graphe biparti deGdont le poids total des arêtes est maximum. SiBEest un sous-ensemble d’arêtes induisant un
Chapitre rédigé par Walid BE N-AM E U R, Ali Ridha MA H JO U Bet José NE TO.
18
Optimisation
combinatoire
sous-graphe biparti deG, alors il est clair queBest contenu dans une coupe deG. Si les poids sont positifs, le problème du sous-graphe biparti maximum et le problème COUPE-MAX sont équivalents. Le problème du sous-graphe biparti a également été l’objet de plusieurs études dans la littérature [BAR 85, GUE 01, SCH 03].
Ce chapitre est organisé comme suit. Dans la section suivante, nous discutons de la complexité du problème COUPE-MAX et de certains cas où le problème peut être résolu en temps polynomial. Dans la section 7.3, nous présentons certaines applica-tions du problème COUPE-MAX. Dans la section 7.4, nous discutons du polytope des coupes. Nous présentons en particulier certaines classes de facettes de ce poly-èdre et étudions leurs problèmes de séparation. Nous décrivons également des appli-cations de ces contraintes dans le cadre d’un algorithme de coupes et branchements pour résoudre le problème COUPE-MAX. La section 7.5 sera consacrée à l’étude du problème COUPE-MAX en utilisant la programmation semi-dénie. Dans la section 7.6, nous présentons certaines applications du cône des coupes. Certaines méthodes approchées, avec et sans garantie, pour le problème COUPE-MAX sont présentées dans la section 7.7. Dans la section 7.8, nous discutons de certains problèmes liés au problème COUPE-MAX, et de leurs polyèdres associés.
Le reste de cette section est consacré à quelques dénitions et notations. Nous considérons des graphes non orientés. Un graphe sera noté parG= (V, E)Vest l’ensemble dessommetsetEest celui desarêtes. Sieest une arête entre deux sommets uetv, alors nous écrivonse=uv. Une chaîne entre deux sommetsuetvdansGest d’arêtes une séquence de sommets et(v0, v, e 1 1, e2, v2, . . . , vl1, el, vl)u=v0, v=vletei=vi1vipouri= 1, . . . , letv0, . . . , vsont des sommets distincts de l V. Les sommetsuetvsont appelés lesextrémitésde la chaîne. Une chaîne sera notée par son ensemble d’arêtes(e1, . . . , el). Uncycleest une chaîne dont les extrémités coïncident. SiFE, alorsV(F)désignera l’ensemble des sommets des arêtes deF. SiSV, on notera parE(S)l’ensemble des arêtes ayant leurs deux extrémités dans S.
E SoitE={e1, . . . , en}un ensembleni. SiFEetx= (x(e), eE)R, E alors nous notons parx(F)la sommex(e). Siaetxsont des vecteurs deR,   eF nous désignons paraxla sommea(e)x(e). Ainsi, l’inégalitéa(e)x(e)eE eE αs’écritaxα.
Unpolyèdreest l’ensemble de solutions d’un systèmeni d’inégalités linéaires. Un polyèdre borné est appelépolytope. La dimension d’un polyèdrePest le nombre maximum de points afnement indépendants dansPmoins 1. Etant donné un poly-èdreP, une inégalitéaxαest ditevalidepourPsiaxαest vériée par toute solution deP. UnefacedeP, associée à une inégalité valideaxα, est le polyèdre donné par{xP:ax=α}. UnefacettedePest une face de dimension maxi-mum (c’est-à-dire de dimensiond1dest la dimension deP). Pour des notions
Le problème de coupe maximum
19
complémentaires sur les graphes et les polyèdres combinatoires, on peut consulter respectivement [BER 83] et [MAH 05].
1.2. Complexité et cas polynomiaux
Comme il a été mentionné ci-dessus, le problème COUPE-MAX est NP-complet en général. Karp [KAR 72] a montré que le problème du transversal de cardinalité minimum, qui est NP-complet, peut se ramener à ce problème. (Un transversal est un sous-ensemble de sommets qui couvre toutes les arêtes du graphe.) Yannakakis [YAN 78] a montré que le problème de coupe maximum reste NP-complet dans les graphes dont le degré maximum ne dépasse pas 3. Barahona [BAR 83] a montré que le problème COUPE-MAX est NP-complet dans les graphes presque planaires, c’est-à-dire les graphesGayant un sommetvtel queGvest planaire.
Toutefois ce problème peut être résolu en temps polynomial sur des instances avec une fonction coût et/ou une topologie particulière(s) du graphe.
Si les poids sont tous négatifs, le problème COUPE-MAX se ramène au problème de coupe minimum avec des poids positifs, et peut donc être résolu en temps po-lynomial en utilisant lesots. McCormicket al.étudient la complexité[MCC 03] + du problème dépendamment des signes des coefcients de la fonction coût. SoitE l’ensemble des arêtes du grapheG= (V, E)associées à un coût positif strictement, + etc(V, E)la cardinalité minimale d’un sous-ensemble de sommetsXVtel que + toute arête deEpossède une extrémité dansX. Les auteurs démontrent que le pro-blème COUPE-MAX peut être résolu en temps polynomial sur des instances pour +k lesquellesc(V, E) =O(log(n)), pourkxé,k >0. En revanche, ce problème est 1 + NP-complet pour des instances telles quec(V, E) = Ω(n), pour une constantek k xée.
Le problème COUPE-MAX peut être également résolu en temps polynomial dans certaines classes de graphes. Orlova et Dorfman [ORL 72] et Hadlock [HAD 75] ont indépendamment montré que le problème COUPE-MAX peut être résolu en temps po-lynomial si le graphe est planaire. Leur approche est basée sur la dualité des graphes planaires et consiste à ramener le calcul d’une coupe maximum à la recherche d’un couplage de poids maximum. Barahona [BAR 83] a étendu ce résultat en montrant que le problème COUPE-MAX reste polynomial dans les graphes qui ne sont pas contrac-s à tibleK5. (Un grapheGestcontractibleà un grapheHsiHpeut être obtenu à partir deGpar une séquence de suppressions et de contractions d’arêtes. Le grapheH est alors ditmineurdeG.) Barahona [BAR 81a] a également montré que le problème COUPE-MAX peut être résolu en temps polynomial si le graphe peut être plongé dans un tore et les poids sont égaux à±1. Grötschel et Pulleyblanck [GRÖ 81b] ont introduit la classe des graphes ditsfaiblement bipartis, et ont montré que le problème COUPE-MAX peut être résolu en temps polynomial dans cette classe de graphes, en
20
Optimisation
combinatoire
utilisant la méthode des ellipsoïdes. La classe des graphes faiblement bipartis contient comme sous-classe les graphes non contractibles àK5[FON 92]. Une caractérisation de cette classe de graphes a été donnée récemment par Guenin [GUE 01]. Dans le cas de coûts positifs portés sur les arêtes, Grötschel et Nemhauser [GRÖ 84] ont montré que, pour tout entierkxé, il existe un algorithme polynomial pour résoudre le pro-blème COUPE-MAX sur les graphes dont la longueur des cycles impairs n’excède pas 2k+ 1. Aussi, dépendamment de la fonction coût et de la topologie du graphe étudié, Gallucioet al.[GAL 01] ont démontré que sous les hypothèses suivantes, le problème COUPE-MAX peut être résolu en temps polynomial : – les poids portés sur les arêtes sont des entiers, dont la valeur est bornée supérieu-rement par un polynôme en|V|; – le graphe considéré a une valeur degenusgxée.
(La procédure de résolution proposée a une complexité qui croît de façon exponen-tielle avecg.)
1.3. Applications
Le problème COUPE-MAX a de nombreuses applications dans plusieurs domaines. Dans cette section, nous présentons certaines applications de ce problème aux modèles de verres de spins en physique statistique, à la programmation quadratique en01 sans contraintes et à la conception des circuits VLSI.
1.3.1.Modèles de verres de spins
Unverre de spinsest un système obtenu par une faible dilution (1%) d’un maté-riau magnétique (Fer) dans un matériau non magnétique (Or). L’intérêt des physiciens pour ce matériau vient de l’observation d’un pic dans la courbe de ce qu’on appelle lasusceptibilitémagnétique en fonction de la température. Un tel pic est générale-ment l’indice d’une transition de phase, d’un changement d’état du système. D’où la recherche de modèles susceptibles d’expliquer ce phénomène.
Dans un verre de spins, les atomes magnétiques sont disposés aléatoirement dans l’espace. Entre deux atomesi, j, il existe une énergie d’interaction :
Hij=J(R)SiSj,
t le moment magnétique (spin) de l’ato Si(Sj) es mei(j), etJ(R)est une fonction qui dépend de la distanceRentre les deux atomes. Pour modéliser ces systèmes, les physiciens ont construit un modèle simplié : ils supposent que les spins sont situés aux nœuds d’un maillage régulier (au lieu d’être répartis aléatoirement) et sont dénis par des vecteurs unidimensionnels (au lieu d’être tridimensionnels)Sprenant les i
Le problème de coupe maximum
21
valeurs+1et1. Ces maillages sont généralement carrés ou cubiques. Ils supposent en plus que les interactions entre les spins n’ont lieu qu’entre les plus proches voisins, et que leurs énergies (J) sont des variables aléatoires pouvant prendre des valeurs ij positives ou négatives. Les interactions correspondent alors aux liaisons du maillage.
A une congurationSdes spins (c’est-à-dire, une affectation+1et1aux spins) correspond une énergie du système donnée par :
H(S) =JijSiSj, ijL
[1.1]
Lest l’ensemble des liaisons etJijl’interaction entre les spinsietj. Le problème que posent les physiciens est de déterminer une congurationSqui minimise l’énergie [1.1] du système. Une telle conguration est ditel’état fondamental du systèmeet le problème est appeléproblème de l’état fondamental. Les physiciens utilisent tradition-nellement des heuristiques de type Monte-Carlo pour déterminer des solutions appro-chées pour ce problème même dans le cas où le maillage est carré (planaire). Comme il est montré dans la suite, ce problème peut se ramener au problème COUPE-MAX.
A un système de verre de spins, on peut associer un grapheG= (V, E)où les sommets correspondent aux spins, et deux sommets sont liés par une arête s’il existe une liaison entre les spins correspondant aux sommets. On associe à chaque liaisonij le poids ωij=Jij. Le problème de l’état fondamental est par conséquent équivalent au programme :
minH(S) =ωijSiSj ijE
:Si∈ {−1,1},
iV
[1.2]
Ainsi le problème est de déterminer une affectation de+1et1aux sommets du graphe de telle manière que ffectation de ωijSiSjsoit minimum. SoitSune a ijE +1et1aux sommets deV. SoitV+={iV:Si= +1}etV={iV:Si= 1}. Alors :
H(S)
  =ωijSiSj=ωij+ωij ijE i,jV+i,jVωij iV+,jV  =ωij2ωij. ijE ijδ(V+)
Puisqueωijest une constante, minimiserH(S)est, par conséquent, équivalent ijE à maximiserwij, le poids de la coupe induite parV+. Ainsi, le problème ijδ(V+) de l’état fondamental se ramène au problème COUPE-MAX dansG.
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents