[PDF] Optimisation en nombres entiers de fonctions quadratiques non

View - Download Optimisation en nombres entiers de fonctions quadratiques non

Previous PDF

Next PDF

MASTER 2 Recherche

INTELLIGENCE ARTIFICIELLE ET D´ECISION

Universit´e Pierre et Marie Curie (Paris VI)

Rapport de Stage

Optimisation en nombres entiers de

fonctions quadratiques non convexessoumises `a des contraintes lin´eaires

Am´elie Lambert

Directeurs de Stage

M. Alain Billionnet, professeur des universit´es Mme Sourour Elloumi, maˆıtre de Conf´erences Laboratoire CEDRIC du Conservatoire National des Arts et M´etiers

Soutenu le 11 Septembre 2006 devant le jury

M Patrice Perny, professeur des universit´es

M Michel Minoux, professeur des universit´es

M. Alain Billionnet, professeur des universit´es M Philippe Chr´etienne, professeur des universit´es Mme Safia Kedad-Sidhoum, maˆıtre de Conf´erences

Laboratoire LIP6 de l"Universit´e Paris VI

R´esum´e

Cette ´etude traite de programmes math´ematiques quadratiques non con- vexes `a variables enti`eres et dont la fonction objectif est soumise `a des contraintes lin´eaires. Cette cat´egorie de probl`emes, qui fait partie des probl`e- mes difficiles, ne peut ˆetre r´esolue par un solveur standard sans transforma- tion pr´ealable. En effet, ces solveurs ne peuvent r´esoudre que des programmes o`u la fonction objectif est soit lin´eaire, soit quadratique et convexe. Nous aborderons donc diff´erentes m´ethodes de r´esolution de cette cat´egorie de probl`emes, tout d"abord grˆace `a des reformulations convexes, puis en com- parant la qualit´e des diff´erentes r´esolutions avec celle d"une lin´earisation. Enfin, nous essayerons d"introduire une nouvelle id´ee de convexification, ins- pir´ee d"un m´elange de ces derni`eres, qui serait plus performante. Pour ´evaluer la qualit´e de ces reformulations, nous avons r´ealis´e un logiciel nomm´e Resolutionqui est capable `a la fois de g´en´erer et de lire des instances, mais aussi de les r´esoudre par la m´ethode souhait´ee grˆace `a ses diff´erentes options. 1

Remerciements

Je tiens tout d"abord `a remercier Sourour Elloumi et Alain Billionnet, qui m"ont encadr´e et guid´e tout au long de mon stage. Leur attention et leurs conseils m"ont permis d"avancer dans mon travail et m"ont donn´e envie de poursuivre mon cursus en th`ese avec eux. Je remercie ´egalement Marie-Christine Costa et Christophe Picouleau pour leur accueil au sein du CEDRIC, ainsi qu"Agn`es Plateau pour avoir partag´e son bureau avec moi. Enfin, je voudrais remercier les doctorants du CEDRIC, Nicolas Derhy, Marie-Christine Plateau, C´edric Bentz et Aur´elie Le Maˆıtre, que j"ai cˆotoy´e au cours de mon stage, pour leur disponibilit´e. 2

Table des mati`eres1 Introduction5

2 R´esolution d"un programme quadratique en nombres entiers

par transformation en un programme quadratique en va- riables 0-17

2.1 Reformulation du probl`eme en variables 0-1 . . . . . . . . . . 7

2.2 Convexification par la m´ethode de la plus petite valeur propre 10

2.3 Convexification par la m´ethode qui maximise la borne de la

relaxation continue (QCR) . . . . . . . . . . . . . . . . . . . . 11

3 Une nouvelle m´ethode de convexification directe des pro-

grammes quadratiques en nombres entiers : m´ethode "semi

0-1"14

4 Une nouvelle m´ethode de lin´earisation des programmes qua-

dratiques en nombres entiers 17

5 R´esultats exp´erimentaux et ´etude comparative des diff´erentes

m´ethodes20

5.1 R´esultats des test des instances IQKP(1) . . . . . . . . . . . . 22

5.2 R´esultats des test des instances IQKP(2) . . . . . . . . . . . . 23

5.3 R´esultats des test des instances UIQP(1) . . . . . . . . . . . . 25

6 Conclusion27

R´ef´erences28

7 Annexes29

A Suivi d"un exemple d´etaill´e29

A.1 Reformulation du probl`eme en variables 0-1 . . . . . . . . . . 29 A.2 R´esolution par la m´ethode de la plus petite valeur propre : . . 33 A.3 R´esolution par la m´ethode QCR : . . . . . . . . . . . . . . . . 35 A.4 R´esolution par la m´ethode "semi 0-1" : . . . . . . . . . . . . . 37 A.5 R´esolution par la lin´earisation : . . . . . . . . . . . . . . . . . 38 3

B D´etails des r´esultats39

B.1 R´esolution des instances IQKP(1) . . . . . . . . . . . . . . . . 39 B.2 R´esolution des instances IQKP(2) . . . . . . . . . . . . . . . . 43 B.3 R´esolution des instances UIQP(1) . . . . . . . . . . . . . . . . 47

C R´ealisation Pratique51

C.1 D´etails de l"impl´ementation . . . . . . . . . . . . . . . . . . . 51 C.2 Manuel deResolution. . . . . . . . . . . . . . . . . . . . . . 54 C.2.1 Compilation . . . . . . . . . . . . . . . . . . . . . . . . 54 C.2.2 Utilisation . . . . . . . . . . . . . . . . . . . . . . . . . 54 C.2.3 Format de lecture de fichier . . . . . . . . . . . . . . . 56 C.3 D´etail du code . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4

1 Introduction

De nombreux probl`emes de recherche op´erationnelle peuvent se mod´eliser sous la forme d"un programme math´ematique `a valeurs enti`eres dont la fonc- tion objectif est quadratique, non convexe et est soumise `a des contraintes lin´eaires . Sans perte de g´en´eralit´e, un probl`eme de ce type peut s"´ecrire sous la forme :

Dx=e(2)

x i?N(4) O`u les matrices et vecteurs sont d´efinis comme suit : - La matriceQest sym´etrique et de dimensionn?n - Le vecteurcest de dimensionn - la matriceAest de dimensionn?m - le vecteurbest de dimensionm - la matriceDest de dimensionn?p - le vecteureest de dimensionp - le vecteuru, chaqueuicorrespondant `a la borne sup´erieure de la valeur autoris´ee `a la variablexiet de dimensionn. Ce probl`eme entre dans la classe des probl`emes difficiles, car il doit traiter `a la fois une fonction objectif non lin´eaire et trouver une solution `a valeurs enti`eres. Nous allons donc proposer une s´erie de transformations de ce probl`eme (P) en un probl`eme (P?) ´equivalent, dont la fonction ´economique est quadratique et convexe, et que nous pourrons donc r´esoudre grˆace `a un solveur comme

XPress.

Pour ´evaluer la qualit´e de la transformation apport´ee, nous ´evaluerons la valeur de la relaxation continue de (P?), qui nous fournit une borne inf´erieure de l"optimum entier recherch´e. La valeur de cette borne doit ˆetre la plus proche possible de l"optimum en question pour d´emarrer une proc´edure de Branch and Bound, mise en oeuvre lors de la r´esolution d"un programme math´ematique en nombres entiers. Les m´ethodes de convexification connues sont en g´en´eral des convexifi- 5 cations lorsque le probl`eme est a valeurs dans{0,1}, car le fait de forcer le vecteur solution `a ne prendre qu"une de ces deux valeurs nous donne une propri´et´e qui facilite la convexification : sit? {0,1}, alorst2-t= 0 L"int´erˆet de cette propri´et´et2-t= 0 est qu"elle nous permet d"additionner un certain nombreλde fois cette diff´erence `a notre fonction quadratique non convexef(t), jusqu"`a ce que son hessien soit semi d´efini positif, et donc que f(t) soit convexe sans en modifier la valeur en{0,1}. Avec la propri´et´e vue pr´ec´edemment, on a : sit? {0,1}, alorsf(t) =f(t) +n? i=1λ i(t2i-ti). Une fa¸con de faire consiste `a transformer notre probl`eme `a solutions enti`eres en un probl`eme `a solutions `a valeurs dans{0,1}afin de lui ap- pliquer ces m´ethodes. Parmi les m´ethodes de convexification connues, nous allons en utiliser deux la premi`ere qui est la m´ethode de la plus petite valeur propre [1] [2]. La deuxi`eme est la m´ethode des coefficients par la program- mation semi-d´efinie : m´ethode dite QCR [3]. Elles ont ´et´e ´etudi´ees pour des programmes quadratiques `a variables dans{0,1}du type : S.c

ˆD?t=e(2)

t i? {0,1}(3) Nous introduirons ´egalement une nouvelle convexification qui ne n´ecessite pas de transformation pr´ealable des variables en{0,1}. Cette m´ethode convexi- fief(x) en utilisant le principe de la plus petite valeur propre deQ[1]. Enfin, nous comparerons l"efficacit´e de ces diff´erentes m´ethodes de convexification avec une lin´earisation. Ces deux reformulations s"appliquent directement `a des probl`emes de type (P). Dans la suite de cette ´etude nous expliquerons le principe de chacune de ces m´ethodes et tenterons de les appliquer `a notre probl`eme afin d"´evaluer si une m´ethode de r´esolution existante est efficace ou s"il est n´ecessaired"en trouver une nouvelle. Commen¸cons d"abord par expliquer la transformation du probl`eme en nombres entiers en un probl`eme en variables 0-1. 6

2 R´esolution d"un programme quadratique en

nombres entiers par transformation en un programme quadratique en variables 0-1

2.1 Reformulation du probl`eme en variables 0-1

Pour r´esoudre le probl`eme (P) en nombres entiers, on peut donc transfor- mer notre programme quadratique en un programme quadratique ´equivalent qui ne contient que des variables prenant les valeurs 0 ou 1. Apr`es avoir ef- fectu´e cette op´eration, il est possible de convexifier la fonction objectif par des m´ethodes connues, notamment celles qui utilisent la plus petite valeur propre deQ, ou bien un vecteurλplus appropri´e qui maximiserait la borne n´ecessaire au branch and bound. Nous nous int´eresserons donc dans cette section `a la fa¸con de mod´eliser notre programme quadratique (P) d´efini pr´ec´edemment en un programme ´equivalent ayant des solutions de valeur 0 ou 1. La fa¸con la plus logique pour effectuer ce changement est de transformer notre vecteur solutionx= (x1,...,xi,...,xn) en d´ecomposant lesxien puissances de 2 et donc de la fa¸con suivante : x i=?log(ui)?? k=02k?tiko`utik? {0,1}

On obtient ainsi un nouveau vecteur solution :

t= (t10,...,t1?log(u1)?,t20,...,t2?log(u2)?,...,tn0,...tn?log(un)?)

Notre programme quadratique devient donc :

S.c.

ˆD?t=e(2)

t ik? {0,1}, i= 1,...,n, k= 0,...,?log(ui)?(3)

Si on poseN=n?

i=1(?log(ui)?+1), les matrices et vecteursˆQ,ˆA,ˆDet ˆcsont d´efinis de la mani`ere suivante :

-ˆQest la matriceQde dimensionn?ntransform´ee. La nouvelle matriceˆQa comme dimensionN?Net est compos´ee des coefficients suivants :

7 O`u le coefficient ˆqikjl=qij?2k?2lest celui du produit des variablestik ettjl, en effet on a : q ij?xi?xj=qij?(?log(ui)?? k=02k?tik)?(?log(uj)?? l=02l?tjl) q ij?xi?xj=?log(ui)?? k=0?log(uj)?? l=0(qij?2k?2l?tik?tjl) q ij?xi?xj=?log(ui)?? k=0?log(uj)?? l=0(ˆqikjl?tik?tjl)

Donc ˆqikjl=qij?2k?2l

- ˆcest le vecteurcde dimensionntransform´e, ce nouveau vecteur a comme dimensionNet est compos´e des coefficients suivants : ˆc= (ˆc10,...,ˆc1?log(u1)?,ˆci0,...,ˆci?log(ui)?,ˆcn0,...,ˆcn?log(un)?) O`u le coefficient ˆcik=ci?2kest celui de la variabletik, en effet, on a : c i?xi=ci?(?log(ui)?? k=02k?tik) c i?xi=?log(ui)?? k=0(ci?2k?tik) c i?xi=?log(ui)?? k=0(ˆcik?tik)

Donc ˆcik=ci?2k

8

-ˆAest la matriceAde dimensionn?mtransform´ee. La nouvelle matriceˆAa comme dimensionN?met est compos´ee des coefficients suivants :

O`u le coefficient ˆaijl=aij?2lest celui de la variabletjldans la contrainte i. aij?xj=aij?(?log(uj)?? l=02l?tjl) a ij?xj=?log(uj)?? l=0(aij?2l?tjl) a ij?xj=?log(uj)?? l=0(ˆaijl?tjl)

Donc ˆaijl=aij?2l

ˆDest la matriceDde dimensionn?ptransform´ee. La nouvelle matriceˆDa comme dimensionN?pet est compos´ee des coefficients suivants :

O`u le coefficient

ˆdijl=dij?2lest celui de la variabletjldans la

contrainte i. d ij?xj=dij?(?log(uj)?? l=02l?tjl) d ij?xj=?log(uj)?? l=0(dij?2l?tjl) 9 dij?xj=?log(uj)?? l=0(ˆdijl?tjl) Donc

ˆdijl=dij?2l

- Les vecteursbetesont les mˆemes que dans (P). La complexit´e totale de cette transformation est polynomiale, il est int´eressant d"´etudier les m´ethodes de convexifications existantes sur les programmes qua- dratiques en variables 0-1 apr`es avoir effectu´e cette transformation sur notre programme quadratique (P) de d´epart.

2.2 Convexification par la m´ethode de la plus petite

valeur propre Cette m´ethode a ´et´e ´etudi´ee pour le probl`eme quadratique en variables

0-1, obtenu `a la fin du paragraphe pr´ec´edent suivant :

S.c

ˆD?t=e(2)

t ik? {0,1}, i= 1,...,n, k= 0,...,?log(ui)?(3) Comme nous travaillons sur un espace de solution qui est{0,1}, nous avons donc la propri´et´e que : sitik? {0,1}, alorst2ik-tik= 0.

De plus,

ˆQest sym´etrique car la reformulation d´ecrite pr´ec´edemment, d"une matrice sym´etrique donne une matrice sym´etrique. Ensuite, notonsdiag(λ) la matrice diagonale de dimensionN?Nobtenue depuis le vecteurλde dimensionNd´efinit comme suit : λ= (λ10,...,λ1?log(u1)?,λi0,...,λi?log(ui)?,λn0,...,λn?log(un)?) f

λ(t) =tT?(ˆQ-diag(λ))?t+ (ˆc+λ)T?t

f

λ(t) =f(t) +n?

i=1?log(ui)?? k=0λ ik(tik-t2ik) 10 Il est ´evident que :fλ(t) =f(t)?λ, sitik? {0,1}n Notre programme quadratique (P?) peut donc s"´ecrire en un programme quadratique (Pλ) ´equivalent :

λ(t) =tT?ˆQ?t+ ˆcT?t+n

i=1?log(ui)?? k=0λ ik(tik-t2ik) S.c

ˆD?t=e(2)

t ik? {0,1}, i= 1,...,n, k= 0,...,?log(ui)?(3)

Pour quefλ(t) soit convexe, il faut trouver un vecteurλtel que la matriceˆQ-diag(λ) soit semi-d´efinie positive.

Propri´et´e 2.1Soitλminla plus petite valeur propre deˆQ, on a la propri´et´e

Posonsλ=λmin?eavecele vecteur identit´e,

etfλmin?e=tT?(ˆQ-diag(λmin?e))?t+ (ˆc+λmin?e)T?t Propri´et´e 2.2(P?)´equivalent `a(Pλ), avec la matrice(ˆQ-diag(λmin?e)) qui est semi-d´efinie positive et doncfλmin?equi est convexe .

2.3 Convexification par la m´ethode qui maximise la

borne de la relaxation continue (QCR) Cette m´ethode est une am´elioration de la m´ethode´enonc´ee pr´ec´edemment, en effet, l"id´ee est de trouver une valeur meilleure pour le vecteurλqui rend quand mˆeme convexe la fonction objectiffλ. Cette m´ethode int`egre´egalement 11 les contraintes d"´egalit´e `a la fonction objectif afin de la convexifier aumieux. Soit S.c

ˆD?t=e(2)

t ik? {0,1}, i= 1,...,n, k= 0,...,?log(ui)?(3)

Soitα?Rm?Netλ?RNet

α,λ(t)

S.c

ˆD?t=e(2)

t ik? {0,1}, i= 1,...,n, k= 0,...,?log(ui)?(3) avecfα,λ(t) =f(t) +m? v=1Nquotesdbs_dbs1.pdfusesText_1

[PDF] fonction racine carrée exercices corrigés

[PDF] fonction ressources humaines dans l'entreprise

[PDF] fonction ressources humaines définition

[PDF] fonction ressources humaines pdf

[PDF] fonction statistique excel

[PDF] fonction variable complexe exercices corrigés

[PDF] fonction varoma thermomix tm5

[PDF] fonction word 2010

[PDF] fonctionnement boite de vitesse automatique pdf

[PDF] fonctionnement clé token

[PDF] fonctionnement d internet schéma

[PDF] fonctionnement d'un groupe electrogene pdf

[PDF] fonctionnement d'un hacheur

[PDF] fonctionnement d'un sprinkler

[PDF] fonctionnement d'une banque pdf