Mathématiques et modélisation en optimisation industrielle

1. Introduction

Le but de cet article est de mon­trer, en nous appuyant sur dif­fé­rents exemples tirés de pro­jets indus­triels concrets, quel peut être l’im­pact de résul­tats mathé­ma­tiques, même très abs­traits et théo­riques, dans le contexte de la modé­li­sa­tion et de la réso­lu­tion effec­tive de pro­blèmes d’op­ti­mi­sa­tion industrielle.

L’ex­pé­rience montre que dans une pro­por­tion de cas très impor­tante (au moins 50 %), les pro­blèmes qui se posent en opti­mi­sa­tion indus­trielle sont com­bi­na­toires en ce sens qu’ils consistent à déter­mi­ner une solu­tion (une com­bi­nai­son) opti­male par­mi un ensemble de solu­tions (de com­bi­nai­sons) fini, mais de car­di­na­li­té tel­le­ment éle­vée qu’il n’est pas pos­sible de pro­cé­der par énu­mé­ra­tion com­plète de toutes les combinaisons.

Les modèles mathé­ma­tiques per­ti­nents pour modé­li­ser ce type de pro­blèmes ne relèvent pas exclu­si­ve­ment de dis­ci­plines mathé­ma­tiques » tra­di­tion­nelles » telles que l’a­na­lyse, l’a­na­lyse fonc­tion­nelle ou la topo­lo­gie, mais aus­si de ce qu’il est conve­nu d’ap­pe­ler les mathé­ma­tiques dis­crètes.

Nous met­trons l’ac­cent, dans la suite de cet article, sur quelques-uns des prin­ci­paux outils mathé­ma­tiques inter­ve­nant, de façon essen­tielle, dans la modé­li­sa­tion et la réso­lu­tion effi­cace de pro­blèmes com­bi­na­toires tels qu’on peut en ren­con­trer en opti­mi­sa­tion indus­trielle, en par­ti­cu­lier : la pro­gram­ma­tion linéaire (cf. para­graphe 4) ; la com­bi­na­toire poly­édrique qui four­nit les outils théo­riques per­met­tant de construire des algo­rithmes de réso­lu­tion exacte pra­ti­que­ment effi­caces pour beau­coup de pro­blèmes com­bi­na­toires dif­fi­ciles (cf. para­graphe 5).

Plu­sieurs exemples, tirés de pro­jets indus­triels divers, seront pré­sen­tés et per­met­tront d’illus­trer la façon dont ces outils théo­riques peuvent inter­ve­nir, d’a­bord au niveau de la modé­li­sa­tion (en vue du choix de la meilleure repré­sen­ta­tion pos­sible du pro­blème), puis au niveau de la concep­tion d’al­go­rithmes de réso­lu­tion efficaces.

S’il est vrai que l’on dis­pose, depuis quelques années, de logi­ciels com­mer­ciaux géné­raux per­for­mants pour modé­li­ser et résoudre beau­coup de pro­blèmes d’op­ti­mi­sa­tion indus­trielle (par exemple le logi­ciel CPLEX de la socié­té Ilog, le logi­ciel XPress de la socié­té Dash), la capa­ci­té de ces outils à résoudre effec­ti­ve­ment les pro­blèmes les plus dif­fi­ciles (du fait de leur taille ou de leur struc­ture) dépend beau­coup de la façon dont les pro­blèmes sont décrits (for­mu­lés) préa­la­ble­ment à leur trai­te­ment en machine.

Une bonne connais­sance et une bonne maî­trise des outils mathé­ma­tiques pré­sen­tés ici appa­raissent alors indis­pen­sables en vue d’une uti­li­sa­tion ration­nelle et effi­cace des logi­ciels com­mer­ciaux, quels qu’ils soient.

2. Un problème d’optimisation combinatoire en productique

Ce type de pro­blème appa­raît chaque fois que l’on doit effec­tuer une sélec­tion de k objets par­mi n objets don­nés, tout en res­pec­tant un ensemble de contraintes binaires d’incompatibilité.

Il peut être décrit de la façon sui­vante. Étant don­nées n tâches à réa­li­ser et une liste L de couples (i, j), repré­sen­tant des incom­pa­ti­bi­li­tés entre paires de tâches, on veut savoir s’il est pos­sible d’exé­cu­ter simul­ta­né­ment k tâches (k entier > 0 don­né) tout en véri­fiant l’en­semble des contraintes d’in­com­pa­ti­bi­li­té : pour tout (i, j) dans L, les tâches i et j ne peuvent être exé­cu­tées simultanément.

Dans le lan­gage de la théo­rie des graphes, ce pro­blème est connu sous le nom de pro­blème de » l’en­semble stable « .

Le graphe de la figure 2 cor­res­pond à un exemple où on a n = 6 tâches repré­sen­tées par les som­mets numé­ro­tés de 1 à 6, et où les arêtes modé­lisent des rela­tions d’in­com­pa­ti­bi­li­té entre paires de tâches : l’a­rête (1, 2) exprime le fait que les tâches 1 et 2 ne peuvent être exé­cu­tées simultanément.

De même, l’a­rête (1, 4) exprime l’in­com­pa­ti­bi­li­té entre les tâches 1 et 4, etc. Un sous-ensemble de som­mets satis­fai­sant les contraintes d’in­com­pa­ti­bi­li­té est encore appe­lé un ensemble stable du graphe.

On le voit sur cet exemple, il existe une solu­tion pour k = 3 (on peut exé­cu­ter trois tâches simul­ta­né­ment, par exemple les tâches 2, 4 et 6), par contre si k = 4, il n’y a pas de solution.

Figure 2

Le graphe des contraintes d’incompatibilité pour l’exemple du pro­blème de sélec­tion de tâches. L’ensemble (2, 4, 6) est une solu­tion de car­di­na­li­té maxi­male k = 3.

Il est facile de voir que le nombre de solu­tions d’un tel pro­blème est fini, et majo­ré par 2ⁿ (le nombre de sous-ensembles de tâches).

Le pro­blème de la déter­mi­na­tion du sous-ensemble de tâches com­pa­tibles de car­di­na­li­té don­née paraît donc, a prio­ri, bien simple à résoudre : ne suf­fit-il pas d’exa­mi­ner une à une toutes les com­bi­nai­sons (tous les sous-ensembles de tâches) jus­qu’à en trou­ver une satis­fai­sant les contraintes du pro­blème posé ?

Néan­moins, la ques­tion se com­plique quelque peu si l’on se pré­oc­cupe de la pos­si­bi­li­té effec­tive (phy­sique) de résoudre le pro­blème pour des valeurs assez grandes de n (n = 100 ou n = 200 pour fixer les idées). Voyons les chiffres. Pour n = 50, le nombre de com­bi­nai­sons à tes­ter est supé­rieur à 10⁶ mil­liards ; pour n = 100 il est supé­rieur à 10³⁰ et pour n = 200 il est supé­rieur à 10 éle­vé à la puis­sance 60, un nombre beau­coup plus grand (au dire des spé­cia­listes) que le nombre d’a­tomes dans l’univers !

En rai­son du nombre extrê­me­ment éle­vé de com­bi­nai­sons à envi­sa­ger pour le résoudre, le pro­blème d’af­fec­ta­tion pré­sen­té ci-des­sus est qua­li­fié de » combinatoire « .

3. Complexité des problèmes combinatoires : les limites de la technologie

Si on sup­pose que des ordi­na­teurs sont capables, indi­vi­duel­le­ment, d’é­nu­mé­rer et de véri­fier mille mil­liards de com­bi­nai­sons par seconde (10¹²), ce qui est déjà très au-delà des pos­si­bi­li­tés actuelles de la tech­no­lo­gie, et que l’on puisse en faire tra­vailler un mil­lion en paral­lèle, il fau­drait alors plu­sieurs années pour résoudre un pro­blème de taille n = 90 (90 tâches) ; plu­sieurs mil­lions d’an­nées pour résoudre un pro­blème de taille n = 110 ; et un mil­lion de fois plus de temps encore pour un pro­blème de taille n = 130… !

Cette aug­men­ta­tion expo­nen­tiel­le­ment rapide du nombre de com­bi­nai­sons a prio­ri, en fonc­tion de la taille du pro­blème (défi­nie ici par le para­mètre n), est le phé­no­mène bien connu des pra­ti­ciens sous le nom » d’ex­plo­sion com­bi­na­toire « . Il montre que si, pour un pro­blème don­né (par exemple le pro­blème d’af­fec­ta­tion), on ne dis­pose que de l’ap­proche par énu­mé­ra­tion, alors, même des pro­grès consi­dé­rables dans la tech­no­lo­gie des cal­cu­la­teurs ne peuvent recu­ler que de très peu les tailles limites des pro­blèmes pou­vant être effec­ti­ve­ment résolus.

Dans l’exemple ci-des­sus, un accrois­se­ment de per­for­mances des ordi­na­teurs dans un rap­port de un mil­lion ne recu­le­rait la taille limite que de n = 90 à n = 110 envi­ron. Le pro­blème de sélec­tion des tâches pré­sen­té dans le para­graphe 2 fait par­tie d’une classe de pro­blèmes dif­fi­ciles pour les­quels on ne connaît pas d’al­go­rithme de réso­lu­tion exacte effi­cace au sens de la théo­rie de la com­plexi­té (cf. réfé­rence [2]).

Par­mi les exemples les plus connus de cette classe de pro­blèmes (dits » NP-dif­fi­ciles »), on peut citer : le fameux pro­blème de Hamil­ton (sou­vent appe­lé pro­blème du » voya­geur de com­merce ») qui a de très nom­breuses appli­ca­tions dans les trans­ports, en logis­tique, etc. ; le pro­blème dit du » Sac à dos » (cf. enca­dré 2) qui appa­raît dans de très nom­breux modèles d’op­ti­mi­sa­tion et dont nous repar­le­rons plus loin.

Pour la réso­lu­tion effec­tive de nom­breux pro­blèmes dif­fi­ciles de ce type, les pro­grès impor­tants qui ont été accom­plis depuis une ving­taine d’an­nées appa­raissent essen­tiel­le­ment comme le résul­tat d’a­na­lyses mathé­ma­tiques et algo­rith­miques appro­fon­dies, le pro­grès des cal­cu­la­teurs élec­tro­niques n’y inter­ve­nant que fort peu.

Les para­graphes qui suivent vont don­ner un aper­çu des tech­niques ayant per­mis ces progrès.

4. Modèles de programmation linéaire : difficulté des problèmes en nombres entiers

La pro­gram­ma­tion linéaire est un des prin­ci­paux outils dont on dis­pose actuel­le­ment pour résoudre de grands pro­blèmes d’optimisation.

Un pro­blème de pro­gram­ma­tion linéaire consiste en la recherche du mini­mum (ou du maxi­mum) d’une fonc­tion objec­tif linéaire de n variables réelles x₁…, x_n, le mini­mum étant pris sur un sous-ensemble X de Rⁿ (poly­èdre) défi­ni par un sys­tème linéaire d’é­ga­li­tés ou d’i­né­ga­li­tés (cf. enca­dré 1). Dans ce type de pro­blème, les variables sont auto­ri­sées à prendre des valeurs réelles quel­conques dans X, on parle de pro­grammes linéaires conti­nus.

De nom­breux pro­blèmes indus­triels peuvent se for­mu­ler et se résoudre comme des pro­grammes linéaires continus.

Aujourd’­hui, il existe des logi­ciels com­mer­ciaux extrê­me­ment per­for­mants tels que CPLEX ou XPress, qui per­mettent de résoudre de tels pro­blèmes jus­qu’à des tailles très importantes.

Des pro­grammes linéaires à quelques mil­liers de variables et de contraintes sont réso­lus typi­que­ment en quelques minutes sur un ordi­na­teur type PC ordi­naire. Et même la réso­lu­tion de pro­grammes linéaires à plu­sieurs cen­taines de mil­liers de variables et plu­sieurs dizaines de mil­liers de contraintes est deve­nue par­fai­te­ment pos­sible en des temps de cal­cul rai­son­nables (typi­que­ment de l’ordre de une à quelques heures).

Cepen­dant cette effi­ca­ci­té remar­quable cesse d’être au ren­dez-vous dès que les pro­blèmes à résoudre com­portent – ce qui est mal­heu­reu­se­ment très fré­quent – des res­tric­tions des valeurs pos­sibles des variables à des domaines de valeurs entières. On obtient alors ce que l’on appelle des pro­grammes linéaires en nombres entiers. C’est le cas, dans l’exemple du pro­blème ℗ de l’en­ca­dré 1, si on impose, en plus, à la solu­tion cher­chée d’a­voir ses com­po­santes x₁ et x₂ entières.

La plu­part des pro­blèmes com­bi­na­toires dif­fi­ciles évo­qués dans le para­graphe 3 peuvent être aisé­ment for­mu­lés comme des pro­grammes linéaires en nombres entiers, ceci explique pour­quoi il est a prio­ri beau­coup plus dif­fi­cile de résoudre un pro­gramme linéaire en nombres entiers qu’un pro­gramme linéaire continu.

Peut-on néan­moins son­ger à exploi­ter la puis­sance des outils de pro­gram­ma­tion linéaire conti­nue pour aider la réso­lu­tion de pro­grammes linéaires en nombres entiers ? L’en­semble des recherches, très actives, menées depuis une bonne ving­taine d’an­nées dans cette direc­tion, a don­né nais­sance à une branche nou­velle des mathé­ma­tiques appli­quées, la com­bi­na­toire poly­édrique, et a per­mis d’ap­por­ter une réponse posi­tive à cette question.

5. Une théorie de l’approximation des polyèdres

L’i­dée de départ de la com­bi­na­toire poly­édrique consiste à essayer de rame­ner la réso­lu­tion d’un pro­blème linéaire en nombres entiers à celle d’un simple pro­gramme linéaire conti­nu, celui obte­nu en sub­sti­tuant à l’en­semble des contraintes décri­vant ini­tia­le­ment le pro­blème, l’en­semble des contraintes défi­nis­sant le plus petit poly­èdre X conte­nant toutes les solu­tions entières (en hachures sur la figure 1 de l’en­ca­dré 1).

Mal­heu­reu­se­ment, on peut mon­trer que même pour des pro­blèmes en nombres entiers de taille rela­ti­ve­ment réduite (à par­tir de quelques dizaines de variables) l’ob­ten­tion de la liste com­plète des inéga­li­tés per­met­tant de décrire le plus petit poly­èdre conte­nant les solu­tions entières est impos­sible en pra­tique (à cause du nombre extra­or­di­nai­re­ment éle­vé d’i­né­ga­li­tés nécessaires).

Pour contour­ner cette dif­fi­cul­té, on doit donc se conten­ter de tra­vailler avec une des­crip­tion incom­plète du poly­èdre X, c’est-à-dire avec une approxi­ma­tion construite en n’u­ti­li­sant que des sous-ensembles par­ti­cu­liers d’i­né­ga­li­tés. Encore cela néces­site-t-il une étude appro­fon­die de la struc­ture des poly­èdres consi­dé­rés, afin de carac­té­ri­ser les familles d’i­né­ga­li­tés les plus inté­res­santes (celles condui­sant aux meilleures approxi­ma­tions possibles).

En par­ti­cu­lier, on s’ef­force, chaque fois que pos­sible, de faire en sorte que ces inéga­li­tés soient des facettes du poly­èdre . Il s’a­git là de pro­blèmes ardus, dont la réso­lu­tion a deman­dé le déve­lop­pe­ment d’ou­tils théo­riques sophistiqués.

Ce type d’ap­proche a jus­qu’i­ci été uti­li­sé avec suc­cès sur des pro­blèmes com­bi­na­toires types répu­tés dif­fi­ciles comme le pro­blème du » voya­geur de com­merce « . De nom­breuses classes de facettes du poly­èdre asso­cié ont pu être mises en évi­dence, per­met­tant d’ob­te­nir des approxi­ma­tions très pré­cises de ce polyèdre.

Grâce à de tels résul­tats, il devient alors pos­sible (avec des tech­niques d’é­nu­mé­ra­tion par­tielle, de type recherche arbo­res­cente par exemple) d’ob­te­nir des solu­tions opti­males exactes (et d’ap­por­ter la preuve de leur opti­ma­li­té) en n’ex­plo­rant seule­ment qu’une infime frac­tion de l’en­semble des com­bi­nai­sons a prio­ri pos­sibles.

On mesu­re­ra bien les pro­grès théo­riques et algo­rith­miques accom­plis en obser­vant pour le pro­blème » voya­geur de com­merce » l’é­vo­lu­tion, dans le temps, des records mon­diaux des plus grands pro­blèmes réso­lus, de façon exacte (avec preuve d’op­ti­ma­li­té exacte).

Au début des années soixante-dix, à la suite des tra­vaux de Held et Karp on par­ve­nait à résoudre de façon exacte des pro­blèmes jus­qu’à une taille de l’ordre de n = 100 (n = nombre de villes = nombre de som­mets du graphe).

En 1980, Crow­der et Pad­berg, uti­li­sant la pro­gram­ma­tion linéaire et la com­bi­na­toire poly­édrique, trouvent pour la pre­mière fois la solu­tion exacte d’un pro­blème de taille n = 318.

En 1987, Pad­berg et Rinal­di, per­fec­tion­nant les mêmes tech­niques, atteignent la taille n = 532. Les der­niers records se situent main­te­nant au-des­sus de n = 10 000 (!).

On peut donc consi­dé­rer que la dis­ci­pline a atteint aujourd’­hui une matu­ri­té cer­taine, qui lui per­met d’en­vi­sa­ger la réso­lu­tion de pro­blèmes d’op­ti­mi­sa­tion indus­trielle cor­res­pon­dant à des modèles plus com­plexes, car plus proches de la réalité.

Nous décri­vons ci-des­sous quelques exemples repré­sen­ta­tifs de cette évo­lu­tion récente vers le trai­te­ment d’ap­pli­ca­tions indus­trielles » en vraie grandeur « .

6. Un problème d’optimisation en transports aériens

Pour réa­li­ser son pro­gramme de vols sur une période de temps don­née (une semaine, deux semaines, un mois), une com­pa­gnie aérienne doit déter­mi­ner une affec­ta­tion des per­son­nels navi­gants tech­niques (PNT) dis­po­nibles (pilotes, copi­lotes) aux dif­fé­rents vols de façon à mini­mi­ser le coût total de l’af­fec­ta­tion, tout en res­pec­tant un cer­tain nombre de contraintes.

La fonc­tion de coût inclut typi­que­ment le total des heures sup­plé­men­taires dues (au-delà du temps de vol sta­tu­taire, heb­do­ma­daire ou men­suel, un PNT per­çoit des heures sup­plé­men­taires) et le coût total des » mises en place » (une » mise en place » est néces­saire chaque fois qu’un PNT doit assu­rer un vol dont l’aé­ro­port de départ ou d’ar­ri­vée ne coïn­cide pas avec sa base de rat­ta­che­ment habituelle).

Divers types de contraintes sont à prendre en compte, en particulier :

– type 1 : des contraintes » d’af­fec­ta­tion » : à chaque vol doivent être affec­tés exac­te­ment un pilote et un copilote ;
– type 2 : des contraintes de temps de vol maxi­mum : pour une période de temps don­née (une semaine, un mois), un PNT ne doit pas effec­tuer un nombre d’heures de vol supé­rieur à une limite fixée, sup­po­sée donnée ;
– type 3 : des contraintes » d’in­com­pa­ti­bi­li­té » : un même PNT ne peut être affec­té à deux vols devant avoir lieu simul­ta­né­ment (on tient aus­si compte, dans l’ex­pres­sion de ces contraintes, de la néces­si­té, pour un même PNT, de dis­po­ser d’un temps mini­mum entre deux vols suc­ces­sifs aux­quels il est affecté).

Si on prend comme variables de déci­sion dans ce pro­blème des variables binaires x_ij = 0 ou 1 (x_ij = 1, si et seule­ment si le PNT i est affec­té au vol j, x_ij = 0 sinon), il est pos­sible de for­mu­ler le pro­blème avec un ensemble de contraintes com­bi­nant des contraintes d’af­fec­ta­tion, des contraintes de » sac à dos » mul­tiples (cf. enca­dré 2) et des contraintes de type » ensemble stable » d’un graphe (cf. para­graphe 2 ci-dessus).

La pre­mière par­tie du tableau 1 résume les résul­tats de réso­lu­tion exacte obte­nus avec cette for­mu­la­tion 1 sur une série de douze pro­blèmes réels met­tant en jeu jus­qu’à 8 000 variables et plus de 100 000 contraintes. Ils concernent la com­pa­gnie Tuni­sair (cf. [9]). Comme le montre le tableau 1, la for­mu­la­tion 1 per­met la réso­lu­tion exacte de 9 pro­blèmes sur 12 dans un temps de cal­cul infé­rieur à huit heures avec le logi­ciel com­mer­cial CPLEX (ver­sion 6.0.2).

On voit cepen­dant que la modé­li­sa­tion pro­po­sée per­met d’i­den­ti­fier cer­taines struc­tures mathé­ma­tiques du pro­blème que l’on peut ensuite cher­cher à mieux exploi­ter, par exemple en met­tant en œuvre des méthodes de réso­lu­tion effi­caces bien adap­tées à ces structures.

Enca­dré 1

Pro­grammes linéaires conti­nus et en nombres entiers La figure 1 repré­sente l’ensemble X des solu­tions du pro­gramme linéaire à deux variables x1 et x2 et 4 contraintes linéaires d’inégalité ℗ ci-dessous : Maxi­mi­ser x = x1 + x2 sous des conditions  2 x1 + 2 x2 ≥ 3 – 6 x1 + 4 x2 ≤ 1  6 x1 – 8 x2 ≤ 9  2 x1 + 4 x2 ≤ 13 (Un tel pro­gramme linéaire est dit conti­nu, les variables pou­vant prendre des valeurs réelles quel­conques com­pa­tibles avec les contraintes. Par exemple x1 = 2.35 et x2 = 1.62 consti­tue une solu­tion pos­sible de ce problème.)

Ensemble X des solu­tions du pro­gramme linéaire ℗. Les points EFG sont les points de X à coor­don­nées entières. Le plus petit poly­èdre conte­nant ces trois points est indi­qué en gri­sé et noté .

L’ensemble X est consti­tué du poly­gone déli­mi­té par les 4 points et son inté­rieur. Il s’agit d’un ensemble convexe appe­lé poly­èdre, dont A B C D sont appe­lés les points extrêmes (ou encore : les som­mets). Il est facile de voir que, par­mi tous les points de X, c’est le point D, de coor­don­nées x1 = 3,5, x2 = 1,5 pour lequel la plus grande valeur de la fonc­tion objec­tif z est atteinte (z = 5 pour le point D). Les solu­tions entières du pro­blème ℗ cor­res­pondent aux trois points E, F et G et la solu­tion opti­male entière cor­res­pond à F. On remarque aisé­ment qu’elle peut être obte­nue par maxi­mi­sa­tion de la fonc­tion objec­tif z sur le poly­èdre (en gri­sé sur la figure) qui est le plus petit poly­èdre conte­nant l’ensemble des solu­tions entières de ℗.

Ain­si, une des idées qui a été mise en œuvre avec suc­cès sur ce pro­blème consiste à uti­li­ser des inéga­li­tés dites de cliques, clas­siques pour le pro­blème de stable (cf. para­graphe 2) pour refor­mu­ler le pro­blème en rem­pla­çant un grand nombre des contraintes binaires d’ex­clu­sion par de telles inéga­li­tés. Cette refor­mu­la­tion abou­tit, ici, à réduire très sen­si­ble­ment la taille des pro­blèmes ain­si que l’é­cart entre la relaxa­tion conti­nue et le pro­blème en nombres entiers à résoudre (on dit que l’on a » ren­for­cé » la for­mu­la­tion), ce qui se tra­duit par une amé­lio­ra­tion très signi­fi­ca­tive de l’ef­fi­ca­ci­té de la réso­lu­tion (cf. tableau 1, for­mu­la­tion 2). Comme le montre la der­nière colonne du tableau 1, les fac­teurs de gain entre la for­mu­la­tion 1 et la for­mu­la­tion 2 sont sou­vent supé­rieurs à 2 et peuvent atteindre 20 ou 30 !

7. Autres problèmes, structures analogues

Il se trouve que les prin­ci­pales struc­tures pré­sentes dans le pro­blème d’af­fec­ta­tion d’é­qui­pages pré­sen­té plus haut (contraintes d’af­fec­ta­tion, de stable et de » sac à dos » mul­tiple) appa­raissent très sou­vent dans la modé­li­sa­tion de pro­blèmes d’op­ti­mi­sa­tion indus­trielle. Nous nous conten­te­rons d’é­vo­quer suc­cinc­te­ment ici deux exemples emprun­tés à des domaines très dif­fé­rents : un pro­blème de pla­ni­fi­ca­tion des tâches (opti­mi­sa­tion de plan­nings de main­te­nance par exemple) ; un pro­blème d’op­ti­mi­sa­tion de réseaux de télécommunications.

7.1. Un problème de planification de tâches

Il s’a­git d’un pro­blème de pla­ni­fi­ca­tion sous contraintes de res­sources qui appa­raît, par exemple dans le cadre de l’op­ti­mi­sa­tion de plan­nings de main­te­nance à EDF [5]. Ce pro­blème admet, bien sûr, de nom­breuses variantes qui peuvent se ren­con­trer dans des domaines d’ap­pli­ca­tion très divers (tra­vaux publics, pro­duc­tique, logis­tique, etc.). Sur une période de temps don­née, décou­pée en P uni­tés de temps (selon l’ap­pli­ca­tion, l’u­ni­té de temps peut être l’heure, la minute, la semaine…), on doit réa­li­ser un ensemble de n tâches T1, T2…, Tn en res­pec­tant des contraintes diverses, essen­tiel­le­ment des contraintes de pré­cé­dence et des contraintes de res­sources.

Les variables de déci­sion du pro­blème cor­res­pondent typi­que­ment au choix pour chaque tâche, d’une date de début. La durée d’exé­cu­tion de chaque tâche est sup­po­sée connue (dans des variantes plus com­plexes du pro­blème, cette durée peut elle-même dépendre des variables de décision).

Une contrainte de pré­cé­dence entre deux tâches T_i et T_j exprime le fait que le début de la tâche T_j doit être pos­té­rieur au début de la tâche T_i et que l’in­ter­valle de temps entre le début de la tâche T_j et le début de la tâche T_i doit avoir une durée com­prise entre deux valeurs extrêmes données.

Les contraintes de res­sources concernent un ou plu­sieurs types de res­sources néces­si­tées par l’exé­cu­tion des tâches, et peuvent cor­res­pondre, par exemple, à des effec­tifs humains, à des nombres de machines, à des volumes de matières pre­mières, etc. Pour une tâche don­née T_i, la quan­ti­té de res­source de type k uti­li­sée au cours d’une période de temps uni­té pen­dant l’exé­cu­tion de la tâche T_i est sup­po­sée connue et donnée.

Une contrainte sur la res­source n° k s’ex­prime alors en impo­sant qu’à chaque période de temps la somme des quan­ti­tés de la res­source k, uti­li­sées pour toutes les tâches en cours d’exé­cu­tion, soit infé­rieure ou égale à la quan­ti­té totale de res­source dis­po­nible (sup­po­sée connue).

On peut montrer :

• que les contraintes de pré­cé­dence peuvent s’ex­pri­mer par un ensemble de contraintes binaires d’in­com­pa­ti­bi­li­té (du même type que celles inter­ve­nant dans le pro­blème de l’en­semble stable d’un graphe, cf. para­graphe 2) ;
• que les contraintes de res­sources peuvent s’ex­pri­mer par un ensemble de contraintes du type de celles inter­ve­nant dans le pro­blème de » sac à dos » (cf. enca­dré 2).

À titre d’exemple, le pro­blème de main­te­nance posé par EDF [5] pour un exemple de pla­ni­fi­ca­tion sur trois ans, l’u­ni­té de temps étant la semaine, avec un nombre de tâches de l’ordre de 150, conduit typi­que­ment à un nombre de variables binaires de l’ordre de 3 000 à 5 000 et à un nombre de contraintes de l’ordre de 15 000 à 20 000.

Compte tenu de la taille de ces pro­blèmes, un tra­vail impor­tant de modé­li­sa­tion s’est révé­lé être néces­saire avant d’a­bou­tir à une effi­ca­ci­té de réso­lu­tion suf­fi­sante. Ain­si, une refor­mu­la­tion des contraintes binaires d’in­com­pa­ti­bi­li­té a per­mis de résoudre effec­ti­ve­ment de tels pro­blèmes en des temps de cal­cul infé­rieurs à deux heures, et avec une pré­ci­sion meilleure que 1 % sur la valeur de l’optimum.

7.2. Un problème de réseaux de télécommunications

Le pro­blème évo­qué ici appa­raît, sous des formes diverses, dans de nom­breux contextes, que ce soit au niveau des grands opé­ra­teurs de Télé­com, ou au niveau des réseaux de com­mu­ni­ca­tion d’en­tre­prises. Il consiste à déter­mi­ner com­ment construire, au moindre coût, un réseau de télé­com­mu­ni­ca­tions capable de satis­faire la demande en tra­fic, sup­po­sée connue des usa­gers ou des clients.

La dif­fi­cul­té du pro­blème tient, d’une part à sa taille (le nombre de flux de tra­fic à écou­ler croît comme le car­ré du nombre de nœuds du réseau), d’autre part à la struc­ture des fonc­tions de coût (qui sont discontinues).

Un modèle et une méthode de réso­lu­tion exacte ont été pro­po­sés dans [7] qui ont per­mis, pour la pre­mière fois, la réso­lu­tion exacte d’un ensemble de pro­blèmes-tests par­ti­cu­liè­re­ment dif­fi­ciles. La modé­li­sa­tion uti­li­sée fait inter­ve­nir des struc­tures que nous avons déjà ren­con­trées, puis­qu’elle uti­lise une refor­mu­la­tion du pro­blème com­bi­nant des contraintes de type » affec­ta­tion « , avec des contraintes de type » sac à dos » mul­tiple (cf. enca­dré 2).

8. Conclusions

Comme les dif­fé­rents exemples men­tion­nés dans cet article l’ont fait appa­raître, la façon dont on modé­lise un grand pro­blème d’op­ti­mi­sa­tion indus­trielle de struc­ture com­plexe est déter­mi­nante pour l’ef­fi­ca­ci­té des tech­niques de réso­lu­tion qui peuvent lui être appliquées.

Dans les années récentes, diverses approches regrou­pées sous le vocable de » pro­gram­ma­tion par contraintes » ont ten­té d’a­bor­der ce pro­blème dif­fi­cile de l’in­te­rac­tion entre for­mu­la­tion et réso­lu­tion sous l’angle de la pro­gram­ma­tion logique et de l’in­tel­li­gence arti­fi­cielle (cf. [3]). De nom­breux logi­ciels de réso­lu­tion de pro­blèmes com­bi­na­toires ont ain­si été déve­lop­pés, dont cer­tains sont dis­po­nibles com­mer­cia­le­ment (par exemple : Chip de la socié­té Cosy­tec, Ilog Sol­ver de la socié­té Ilog).

Néan­moins, dans ces sys­tèmes, les algo­rithmes de réso­lu­tion pro­po­sés (de type » énu­mé­ra­tion impli­cite ») ne sont géné­ra­le­ment pas en mesure de résoudre de façon exacte des pro­blèmes dif­fi­ciles de grandes dimen­sions tels que ceux pré­sen­tés dans les para­graphes 6 et 7.

Des recherches actuel­le­ment en cours visent pré­ci­sé­ment à amé­lio­rer leur effi­ca­ci­té par une inté­gra­tion des tech­niques de pro­gram­ma­tion linéaire et de com­bi­na­toire poly­édrique évo­quées plus haut. 

---

Articles similaires :

Les mathé­ma­tiques du réel Quelles sta­tis­tiques sont utiles aux entreprises ? Le radar : la théo­rie, la tech­nique et la technologie Mathé­ma­tiques en biomédecine Doit-on modé­li­ser les effets toxiques des sub­stances chi­miques dans l’environnement avec des outils mathématiques ?