Mathématiques et modélisation en optimisation industrielle

1. Introduction

Le but de cet arti­cle est de mon­tr­er, en nous appuyant sur dif­férents exem­ples tirés de pro­jets indus­triels con­crets, quel peut être l’im­pact de résul­tats math­é­ma­tiques, même très abstraits et théoriques, dans le con­texte de la mod­éli­sa­tion et de la réso­lu­tion effec­tive de prob­lèmes d’op­ti­mi­sa­tion industrielle.

L’ex­péri­ence mon­tre que dans une pro­por­tion de cas très impor­tante (au moins 50 %), les prob­lèmes qui se posent en opti­mi­sa­tion indus­trielle sont com­bi­na­toires en ce sens qu’ils con­sis­tent à déter­min­er une solu­tion (une com­bi­nai­son) opti­male par­mi un ensem­ble de solu­tions (de com­bi­naisons) fini, mais de car­di­nal­ité telle­ment élevée qu’il n’est pas pos­si­ble de procéder par énuméra­tion com­plète de toutes les combinaisons.

Les mod­èles math­é­ma­tiques per­ti­nents pour mod­élis­er ce type de prob­lèmes ne relèvent pas exclu­sive­ment de dis­ci­plines math­é­ma­tiques ” tra­di­tion­nelles ” telles que l’analyse, l’analyse fonc­tion­nelle ou la topolo­gie, mais aus­si de ce qu’il est con­venu d’ap­pel­er les math­é­ma­tiques dis­crètes.

Nous met­trons l’ac­cent, dans la suite de cet arti­cle, sur quelques-uns des prin­ci­paux out­ils math­é­ma­tiques inter­venant, de façon essen­tielle, dans la mod­éli­sa­tion et la réso­lu­tion effi­cace de prob­lèmes com­bi­na­toires tels qu’on peut en ren­con­tr­er en opti­mi­sa­tion indus­trielle, en par­ti­c­uli­er : la pro­gram­ma­tion linéaire (cf. para­graphe 4) ; la com­bi­na­toire polyé­drique qui four­nit les out­ils théoriques per­me­t­tant de con­stru­ire des algo­rithmes de réso­lu­tion exacte pra­tique­ment effi­caces pour beau­coup de prob­lèmes com­bi­na­toires dif­fi­ciles (cf. para­graphe 5).

Plusieurs exem­ples, tirés de pro­jets indus­triels divers, seront présen­tés et per­me­t­tront d’il­lus­tr­er la façon dont ces out­ils théoriques peu­vent inter­venir, d’abord au niveau de la mod­éli­sa­tion (en vue du choix de la meilleure représen­ta­tion pos­si­ble du prob­lème), puis au niveau de la con­cep­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­ci­aux généraux per­for­mants pour mod­élis­er et résoudre beau­coup de prob­lèmes d’op­ti­mi­sa­tion indus­trielle (par exem­ple le logi­ciel CPLEX de la société Ilog, le logi­ciel XPress de la société Dash), la capac­ité de ces out­ils à résoudre effec­tive­ment les prob­lè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 prob­lèmes sont décrits (for­mulés) préal­able­ment à leur traite­ment en machine.

Une bonne con­nais­sance et une bonne maîtrise des out­ils math­é­ma­tiques présen­tés ici appa­rais­sent alors indis­pens­ables en vue d’une util­i­sa­tion rationnelle et effi­cace des logi­ciels com­mer­ci­aux, quels qu’ils soient.

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

Ce type de prob­lème appa­raît chaque fois que l’on doit effectuer une sélec­tion de k objets par­mi n objets don­nés, tout en respec­tant un ensem­ble de con­traintes binaires d’incompatibilité.

Il peut être décrit de la façon suiv­ante. Étant don­nées n tâch­es à réalis­er et une liste L de cou­ples (i, j), représen­tant des incom­pat­i­bil­ités entre paires de tâch­es, on veut savoir s’il est pos­si­ble d’exé­cuter simul­tané­ment k tâch­es (k entier > 0 don­né) tout en véri­fi­ant l’ensem­ble des con­traintes d’in­com­pat­i­bil­ité : pour tout (i, j) dans L, les tâch­es i et j ne peu­vent être exé­cutées simultanément.

Dans le lan­gage de la théorie des graphes, ce prob­lème est con­nu sous le nom de prob­lème de ” l’ensem­ble stable “.

Le graphe de la fig­ure 2 cor­re­spond à un exem­ple où on a n = 6 tâch­es représen­tées par les som­mets numérotés de 1 à 6, et où les arêtes mod­élisent des rela­tions d’in­com­pat­i­bil­ité entre paires de tâch­es : l’arête (1, 2) exprime le fait que les tâch­es 1 et 2 ne peu­vent être exé­cutées simultanément.

De même, l’arête (1, 4) exprime l’in­com­pat­i­bil­ité entre les tâch­es 1 et 4, etc. Un sous-ensem­ble de som­mets sat­is­faisant les con­traintes d’in­com­pat­i­bil­ité est encore appelé un ensem­ble sta­ble du graphe.

On le voit sur cet exem­ple, il existe une solu­tion pour k = 3 (on peut exé­cuter trois tâch­es simul­tané­ment, par exem­ple les tâch­es 2, 4 et 6), par con­tre si k = 4, il n’y a pas de solution.

Fig­ure 2

Le graphe des con­traintes d’incompatibilité pour l’exemple du prob­lème de sélec­tion de tâches. L’ensemble (2, 4, 6) est une solu­tion de car­di­nal­ité max­i­male k = 3.

Il est facile de voir que le nom­bre de solu­tions d’un tel prob­lème est fini, et majoré par 2ⁿ (le nom­bre de sous-ensem­bles de tâches).

Le prob­lème de la déter­mi­na­tion du sous-ensem­ble de tâch­es com­pat­i­bles de car­di­nal­ité don­née paraît donc, a pri­ori, bien sim­ple à résoudre : ne suf­fit-il pas d’ex­am­in­er une à une toutes les com­bi­naisons (tous les sous-ensem­bles de tâch­es) jusqu’à en trou­ver une sat­is­faisant les con­traintes du prob­lème posé ?

Néan­moins, la ques­tion se com­plique quelque peu si l’on se préoc­cupe de la pos­si­bil­ité effec­tive (physique) de résoudre le prob­lème pour des valeurs assez grandes de n (n = 100 ou n = 200 pour fix­er les idées). Voyons les chiffres. Pour n = 50, le nom­bre de com­bi­naisons à tester est supérieur à 10⁶ mil­liards ; pour n = 100 il est supérieur à 10³⁰ et pour n = 200 il est supérieur à 10 élevé à la puis­sance 60, un nom­bre beau­coup plus grand (au dire des spé­cial­istes) que le nom­bre d’atomes dans l’univers !

En rai­son du nom­bre extrême­ment élevé de com­bi­naisons à envis­ager pour le résoudre, le prob­lème d’af­fec­ta­tion présen­té ci-dessus est qual­i­fié de ” combinatoire “.

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

Si on sup­pose que des ordi­na­teurs sont capa­bles, indi­vidu­elle­ment, d’énumér­er et de véri­fi­er mille mil­liards de com­bi­naisons par sec­onde (10¹²), ce qui est déjà très au-delà des pos­si­bil­ités actuelles de la tech­nolo­gie, et que l’on puisse en faire tra­vailler un mil­lion en par­al­lèle, il faudrait alors plusieurs années pour résoudre un prob­lème de taille n = 90 (90 tâch­es) ; plusieurs mil­lions d’an­nées pour résoudre un prob­lème de taille n = 110 ; et un mil­lion de fois plus de temps encore pour un prob­lème de taille n = 130… !

Cette aug­men­ta­tion expo­nen­tielle­ment rapi­de du nom­bre de com­bi­naisons a pri­ori, en fonc­tion de la taille du prob­lème (définie ici par le paramètre n), est le phénomène bien con­nu des prati­ciens sous le nom ” d’ex­plo­sion com­bi­na­toire “. Il mon­tre que si, pour un prob­lème don­né (par exem­ple le prob­lème d’af­fec­ta­tion), on ne dis­pose que de l’ap­proche par énuméra­tion, alors, même des pro­grès con­sid­érables dans la tech­nolo­gie des cal­cu­la­teurs ne peu­vent reculer que de très peu les tailles lim­ites des prob­lèmes pou­vant être effec­tive­ment résolus.

Dans l’ex­em­ple ci-dessus, un accroisse­ment de per­for­mances des ordi­na­teurs dans un rap­port de un mil­lion ne reculerait la taille lim­ite que de n = 90 à n = 110 env­i­ron. Le prob­lème de sélec­tion des tâch­es présen­té dans le para­graphe 2 fait par­tie d’une classe de prob­lèmes dif­fi­ciles pour lesquels on ne con­naît pas d’al­go­rithme de réso­lu­tion exacte effi­cace au sens de la théorie de la com­plex­ité (cf. référence [2]).

Par­mi les exem­ples les plus con­nus de cette classe de prob­lèmes (dits ” NP-dif­fi­ciles ”), on peut citer : le fameux prob­lème de Hamil­ton (sou­vent appelé prob­lème du ” voyageur de com­merce ”) qui a de très nom­breuses appli­ca­tions dans les trans­ports, en logis­tique, etc. ; le prob­lème dit du ” Sac à dos ” (cf. encadré 2) qui appa­raît dans de très nom­breux mod­èles d’op­ti­mi­sa­tion et dont nous repar­lerons plus loin.

Pour la réso­lu­tion effec­tive de nom­breux prob­lè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­rais­sent essen­tielle­ment comme le résul­tat d’analy­ses math­é­ma­tiques et algo­rith­miques appro­fondies, le pro­grès des cal­cu­la­teurs élec­tron­iques n’y inter­venant que fort peu.

Les para­graphes qui suiv­ent 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 out­ils dont on dis­pose actuelle­ment pour résoudre de grands prob­lèmes d’optimisation.

Un prob­lème de pro­gram­ma­tion linéaire con­siste en la recherche du min­i­mum (ou du max­i­mum) d’une fonc­tion objec­tif linéaire de n vari­ables réelles x₁…, x_n, le min­i­mum étant pris sur un sous-ensem­ble X de Rⁿ (polyè­dre) défi­ni par un sys­tème linéaire d’é­gal­ités ou d’iné­gal­ités (cf. encadré 1). Dans ce type de prob­lème, les vari­ables sont autorisées à pren­dre des valeurs réelles quel­con­ques dans X, on par­le de pro­grammes linéaires con­ti­nus.

De nom­breux prob­lèmes indus­triels peu­vent se for­muler et se résoudre comme des pro­grammes linéaires continus.

Aujour­d’hui, il existe des logi­ciels com­mer­ci­aux extrême­ment per­for­mants tels que CPLEX ou XPress, qui per­me­t­tent de résoudre de tels prob­lèmes jusqu’à des tailles très importantes.

Des pro­grammes linéaires à quelques mil­liers de vari­ables et de con­traintes sont réso­lus typ­ique­ment en quelques min­utes sur un ordi­na­teur type PC ordi­naire. Et même la réso­lu­tion de pro­grammes linéaires à plusieurs cen­taines de mil­liers de vari­ables et plusieurs dizaines de mil­liers de con­traintes est dev­enue par­faite­ment pos­si­ble en des temps de cal­cul raisonnables (typ­ique­ment de l’or­dre de une à quelques heures).

Cepen­dant cette effi­cac­ité remar­quable cesse d’être au ren­dez-vous dès que les prob­lèmes à résoudre com­por­tent — ce qui est mal­heureuse­ment très fréquent — des restric­tions des valeurs pos­si­bles des vari­ables à des domaines de valeurs entières. On obtient alors ce que l’on appelle des pro­grammes linéaires en nom­bres entiers. C’est le cas, dans l’ex­em­ple du prob­lème ℗ de l’en­cadré 1, si on impose, en plus, à la solu­tion cher­chée d’avoir ses com­posantes x₁ et x₂ entières.

La plu­part des prob­lèmes com­bi­na­toires dif­fi­ciles évo­qués dans le para­graphe 3 peu­vent être aisé­ment for­mulés comme des pro­grammes linéaires en nom­bres entiers, ceci explique pourquoi il est a pri­ori beau­coup plus dif­fi­cile de résoudre un pro­gramme linéaire en nom­bres entiers qu’un pro­gramme linéaire continu.

Peut-on néan­moins songer à exploiter la puis­sance des out­ils de pro­gram­ma­tion linéaire con­tin­ue pour aider la réso­lu­tion de pro­grammes linéaires en nom­bres entiers ? L’ensem­ble des recherch­es, 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 appliquées, la com­bi­na­toire polyé­drique, et a per­mis d’ap­porter une réponse pos­i­tive à cette question.

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

L’idée de départ de la com­bi­na­toire polyé­drique con­siste à essay­er de ramen­er la réso­lu­tion d’un prob­lème linéaire en nom­bres entiers à celle d’un sim­ple pro­gramme linéaire con­tinu, celui obtenu en sub­sti­tu­ant à l’ensem­ble des con­traintes décrivant ini­tiale­ment le prob­lème, l’ensem­ble des con­traintes définis­sant le plus petit polyè­dre X con­tenant toutes les solu­tions entières (en hachures sur la fig­ure 1 de l’en­cadré 1).

Mal­heureuse­ment, on peut mon­tr­er que même pour des prob­lèmes en nom­bres entiers de taille rel­a­tive­ment réduite (à par­tir de quelques dizaines de vari­ables) l’ob­ten­tion de la liste com­plète des iné­gal­ités per­me­t­tant de décrire le plus petit polyè­dre con­tenant les solu­tions entières est impos­si­ble en pra­tique (à cause du nom­bre extra­or­di­naire­ment élevé d’iné­gal­ités nécessaires).

Pour con­tourn­er cette dif­fi­culté, on doit donc se con­tenter de tra­vailler avec une descrip­tion incom­plète du polyè­dre X, c’est-à-dire avec une approx­i­ma­tion con­stru­ite en n’u­til­isant que des sous-ensem­bles par­ti­c­uliers d’iné­gal­ités. Encore cela néces­site-t-il une étude appro­fondie de la struc­ture des polyè­dres con­sid­érés, afin de car­ac­téris­er les familles d’iné­gal­ités les plus intéres­santes (celles con­duisant aux meilleures approx­i­ma­tions possibles).

En par­ti­c­uli­er, on s’ef­force, chaque fois que pos­si­ble, de faire en sorte que ces iné­gal­ités soient des facettes du polyè­dre . Il s’ag­it là de prob­lèmes ardus, dont la réso­lu­tion a demandé le développe­ment d’outils théoriques sophistiqués.

Ce type d’ap­proche a jusqu’i­ci été util­isé avec suc­cès sur des prob­lèmes com­bi­na­toires types réputés dif­fi­ciles comme le prob­lème du ” voyageur de com­merce “. De nom­breuses class­es de facettes du polyè­dre asso­cié ont pu être mis­es en évi­dence, per­me­t­tant d’obtenir des approx­i­ma­tions très pré­cis­es de ce polyèdre.

Grâce à de tels résul­tats, il devient alors pos­si­ble (avec des tech­niques d’énuméra­tion par­tielle, de type recherche arbores­cente par exem­ple) d’obtenir des solu­tions opti­males exactes (et d’ap­porter la preuve de leur opti­mal­ité) en n’ex­plo­rant seule­ment qu’une infime frac­tion de l’ensem­ble des com­bi­naisons a pri­ori pos­si­bles.

On mesur­era bien les pro­grès théoriques et algo­rith­miques accom­plis en obser­vant pour le prob­lème ” voyageur de com­merce ” l’évo­lu­tion, dans le temps, des records mon­di­aux des plus grands prob­lèmes réso­lus, de façon exacte (avec preuve d’op­ti­mal­ité exacte).

Au début des années soix­ante-dix, à la suite des travaux de Held et Karp on par­ve­nait à résoudre de façon exacte des prob­lèmes jusqu’à une taille de l’or­dre de n = 100 (n = nom­bre de villes = nom­bre de som­mets du graphe).

En 1980, Crow­der et Pad­berg, util­isant la pro­gram­ma­tion linéaire et la com­bi­na­toire polyé­drique, trou­vent pour la pre­mière fois la solu­tion exacte d’un prob­lè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 derniers records se situent main­tenant au-dessus de n = 10 000 (!).

On peut donc con­sid­ér­er que la dis­ci­pline a atteint aujour­d’hui une matu­rité cer­taine, qui lui per­met d’en­vis­ager la réso­lu­tion de prob­lèmes d’op­ti­mi­sa­tion indus­trielle cor­re­spon­dant à des mod­èles plus com­plex­es, car plus proches de la réalité.

Nous décrivons ci-dessous quelques exem­ples représen­tat­ifs de cette évo­lu­tion récente vers le traite­ment d’ap­pli­ca­tions indus­trielles ” en vraie grandeur “.

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

Pour réalis­er son pro­gramme de vols sur une péri­ode de temps don­née (une semaine, deux semaines, un mois), une com­pag­nie aéri­enne doit déter­min­er une affec­ta­tion des per­son­nels nav­i­gants tech­niques (PNT) disponibles (pilotes, copi­lotes) aux dif­férents vols de façon à min­imiser le coût total de l’af­fec­ta­tion, tout en respec­tant un cer­tain nom­bre de contraintes.

La fonc­tion de coût inclut typ­ique­ment le total des heures sup­plé­men­taires dues (au-delà du temps de vol statu­taire, heb­do­madaire ou men­su­el, un PNT perçoit des heures sup­plé­men­taires) et le coût total des ” mis­es en place ” (une ” mise en place ” est néces­saire chaque fois qu’un PNT doit assur­er un vol dont l’aéro­port de départ ou d’ar­rivée ne coïn­cide pas avec sa base de rat­tache­ment habituelle).

Divers types de con­traintes sont à pren­dre en compte, en particulier :

— type 1 : des con­traintes ” d’af­fec­ta­tion ” : à chaque vol doivent être affec­tés exacte­ment un pilote et un copilote ;
— type 2 : des con­traintes de temps de vol max­i­mum : pour une péri­ode de temps don­née (une semaine, un mois), un PNT ne doit pas effectuer un nom­bre d’heures de vol supérieur à une lim­ite fixée, sup­posée donnée ;
— type 3 : des con­traintes ” d’in­com­pat­i­bil­ité ” : un même PNT ne peut être affec­té à deux vols devant avoir lieu simul­tané­ment (on tient aus­si compte, dans l’ex­pres­sion de ces con­traintes, de la néces­sité, pour un même PNT, de dis­pos­er d’un temps min­i­mum entre deux vols suc­ces­sifs aux­quels il est affecté).

Si on prend comme vari­ables de déci­sion dans ce prob­lème des vari­ables 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­si­ble de for­muler le prob­lème avec un ensem­ble de con­traintes com­bi­nant des con­traintes d’af­fec­ta­tion, des con­traintes de ” sac à dos ” mul­ti­ples (cf. encadré 2) et des con­traintes de type ” ensem­ble sta­ble ” 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 obtenus avec cette for­mu­la­tion 1 sur une série de douze prob­lèmes réels met­tant en jeu jusqu’à 8 000 vari­ables et plus de 100 000 con­traintes. Ils con­cer­nent la com­pag­nie Tuni­sair (cf. [9]). Comme le mon­tre le tableau 1, la for­mu­la­tion 1 per­met la réso­lu­tion exacte de 9 prob­lè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­posée per­met d’i­den­ti­fi­er cer­taines struc­tures math­é­ma­tiques du prob­lème que l’on peut ensuite chercher à mieux exploiter, par exem­ple en met­tant en œuvre des méth­odes de réso­lu­tion effi­caces bien adap­tées à ces structures.

Encadré 1

Pro­grammes linéaires con­ti­nus et en nom­bres entiers La fig­ure 1 représente l’ensemble X des solu­tions du pro­gramme linéaire à deux vari­ables x1 et x2 et 4 con­traintes linéaires d’inégalité ℗ ci-dessous : Max­imiser 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 con­tinu, les vari­ables pou­vant pren­dre des valeurs réelles quel­con­ques com­pat­i­bles avec les con­traintes. Par exem­ple x1 = 2.35 et x2 = 1.62 con­stitue une solu­tion pos­si­ble de ce problème.)

Ensem­ble 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 con­tenant ces trois points est indiqué en grisé et noté .

L’ensemble X est con­sti­tué du poly­gone délim­ité par les 4 points et son intérieur. Il s’agit d’un ensem­ble con­vexe appelé polyè­dre, dont A B C D sont appelé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 prob­lème ℗ cor­re­spon­dent aux trois points E, F et G et la solu­tion opti­male entière cor­re­spond à F. On remar­que aisé­ment qu’elle peut être obtenue par max­imi­sa­tion de la fonc­tion objec­tif z sur le polyè­dre (en grisé sur la fig­ure) qui est le plus petit polyè­dre con­tenant 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 prob­lème con­siste à utilis­er des iné­gal­ités dites de cliques, clas­siques pour le prob­lème de sta­ble (cf. para­graphe 2) pour refor­muler le prob­lème en rem­plaçant un grand nom­bre des con­traintes binaires d’ex­clu­sion par de telles iné­gal­ités. Cette refor­mu­la­tion aboutit, ici, à réduire très sen­si­ble­ment la taille des prob­lèmes ain­si que l’é­cart entre la relax­ation con­tin­ue et le prob­lème en nom­bres entiers à résoudre (on dit que l’on a ” ren­for­cé ” la for­mu­la­tion), ce qui se traduit par une amélio­ra­tion très sig­ni­fica­tive de l’ef­fi­cac­ité de la réso­lu­tion (cf. tableau 1, for­mu­la­tion 2). Comme le mon­tre la derniè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 peu­vent attein­dre 20 ou 30 !

7. Autres problèmes, structures analogues

Il se trou­ve que les prin­ci­pales struc­tures présentes dans le prob­lème d’af­fec­ta­tion d’équipages présen­té plus haut (con­traintes d’af­fec­ta­tion, de sta­ble et de ” sac à dos ” mul­ti­ple) appa­rais­sent très sou­vent dans la mod­éli­sa­tion de prob­lèmes d’op­ti­mi­sa­tion indus­trielle. Nous nous con­tenterons d’évo­quer suc­cincte­ment ici deux exem­ples emprun­tés à des domaines très dif­férents : un prob­lème de plan­i­fi­ca­tion des tâch­es (opti­mi­sa­tion de plan­nings de main­te­nance par exem­ple) ; un prob­lè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’ag­it d’un prob­lème de plan­i­fi­ca­tion sous con­traintes de ressources qui appa­raît, par exem­ple dans le cadre de l’op­ti­mi­sa­tion de plan­nings de main­te­nance à EDF [5]. Ce prob­lème admet, bien sûr, de nom­breuses vari­antes qui peu­vent se ren­con­tr­er dans des domaines d’ap­pli­ca­tion très divers (travaux publics, pro­duc­tique, logis­tique, etc.). Sur une péri­ode de temps don­née, découpée en P unités de temps (selon l’ap­pli­ca­tion, l’u­nité de temps peut être l’heure, la minute, la semaine…), on doit réalis­er un ensem­ble de n tâch­es T1, T2…, Tn en respec­tant des con­traintes divers­es, essen­tielle­ment des con­traintes de précé­dence et des con­traintes de ressources.

Les vari­ables de déci­sion du prob­lème cor­re­spon­dent typ­ique­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­posée con­nue (dans des vari­antes plus com­plex­es du prob­lème, cette durée peut elle-même dépen­dre des vari­ables de décision).

Une con­trainte de précé­dence entre deux tâch­es T_i et T_j exprime le fait que le début de la tâche T_j doit être posté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 con­traintes de ressources con­cer­nent un ou plusieurs types de ressources néces­sitées par l’exé­cu­tion des tâch­es, et peu­vent cor­re­spon­dre, par exem­ple, à des effec­tifs humains, à des nom­bres de machines, à des vol­umes de matières pre­mières, etc. Pour une tâche don­née T_i, la quan­tité de ressource de type k util­isée au cours d’une péri­ode de temps unité pen­dant l’exé­cu­tion de la tâche T_i est sup­posée con­nue et donnée.

Une con­trainte sur la ressource n° k s’ex­prime alors en imposant qu’à chaque péri­ode de temps la somme des quan­tités de la ressource k, util­isées pour toutes les tâch­es en cours d’exé­cu­tion, soit inférieure ou égale à la quan­tité totale de ressource disponible (sup­posée connue).

On peut montrer :

• que les con­traintes de précé­dence peu­vent s’ex­primer par un ensem­ble de con­traintes binaires d’in­com­pat­i­bil­ité (du même type que celles inter­venant dans le prob­lème de l’ensem­ble sta­ble d’un graphe, cf. para­graphe 2) ;
• que les con­traintes de ressources peu­vent s’ex­primer par un ensem­ble de con­traintes du type de celles inter­venant dans le prob­lème de ” sac à dos ” (cf. encadré 2).

À titre d’ex­em­ple, le prob­lème de main­te­nance posé par EDF [5] pour un exem­ple de plan­i­fi­ca­tion sur trois ans, l’u­nité de temps étant la semaine, avec un nom­bre de tâch­es de l’or­dre de 150, con­duit typ­ique­ment à un nom­bre de vari­ables binaires de l’or­dre de 3 000 à 5 000 et à un nom­bre de con­traintes de l’or­dre de 15 000 à 20 000.

Compte tenu de la taille de ces prob­lèmes, un tra­vail impor­tant de mod­éli­sa­tion s’est révélé être néces­saire avant d’aboutir à une effi­cac­ité de réso­lu­tion suff­isante. Ain­si, une refor­mu­la­tion des con­traintes binaires d’in­com­pat­i­bil­ité a per­mis de résoudre effec­tive­ment de tels prob­lè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 prob­lème évo­qué ici appa­raît, sous des formes divers­es, dans de nom­breux con­textes, 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­pris­es. Il con­siste à déter­min­er com­ment con­stru­ire, au moin­dre coût, un réseau de télé­com­mu­ni­ca­tions capa­ble de sat­is­faire la demande en traf­ic, sup­posée con­nue des usagers ou des clients.

La dif­fi­culté du prob­lème tient, d’une part à sa taille (le nom­bre de flux de traf­ic à écouler croît comme le car­ré du nom­bre 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éth­ode de réso­lu­tion exacte ont été pro­posés dans [7] qui ont per­mis, pour la pre­mière fois, la réso­lu­tion exacte d’un ensem­ble de prob­lèmes-tests par­ti­c­ulière­ment dif­fi­ciles. La mod­éli­sa­tion util­isée fait inter­venir des struc­tures que nous avons déjà ren­con­trées, puisqu’elle utilise une refor­mu­la­tion du prob­lème com­bi­nant des con­traintes de type ” affec­ta­tion “, avec des con­traintes de type ” sac à dos ” mul­ti­ple (cf. encadré 2).

8. Conclusions

Comme les dif­férents exem­ples men­tion­nés dans cet arti­cle l’ont fait appa­raître, la façon dont on mod­élise un grand prob­lème d’op­ti­mi­sa­tion indus­trielle de struc­ture com­plexe est déter­mi­nante pour l’ef­fi­cac­ité des tech­niques de réso­lu­tion qui peu­vent lui être appliquées.

Dans les années récentes, divers­es approches regroupées sous le voca­ble de ” pro­gram­ma­tion par con­traintes ” ont ten­té d’abor­der ce prob­lème dif­fi­cile de l’in­ter­ac­tion entre for­mu­la­tion et réso­lu­tion sous l’an­gle 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 prob­lèmes com­bi­na­toires ont ain­si été dévelop­pés, dont cer­tains sont disponibles com­mer­ciale­ment (par exem­ple : Chip de la société Cosytec, Ilog Solver de la société Ilog).

Néan­moins, dans ces sys­tèmes, les algo­rithmes de réso­lu­tion pro­posés (de type ” énuméra­tion implicite ”) ne sont générale­ment pas en mesure de résoudre de façon exacte des prob­lèmes dif­fi­ciles de grandes dimen­sions tels que ceux présen­tés dans les para­graphes 6 et 7.

Des recherch­es actuelle­ment en cours visent pré­cisé­ment à amélior­er leur effi­cac­ité 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 Banque et mathématiques Prob­a­bil­ité de ruine ou val­ue at risk… et vol Paris-Nice Le radar : la théorie, la tech­nique et la technologie Math­é­ma­tiques en biomédecine Doit-on mod­élis­er les effets tox­iques des sub­stances chim­iques dans l’environnement avec des out­ils mathématiques ?