Relaxation

j'en parlais dans un post récent, en ce moment, c'est relachement, par manque de courage un peu, par épuisement surtout....

Mais la relaxation, c'est aussi un thème majeur du mémoire que je suis en train de finir. Son titre sera quelque chose comme "Hybridation de schémas de sous gradient par des métaheuristiques pour la résolution approchée de problèmes de sac à dos". Bon ok, ça fait Hype (qu'est ce que je deteste ce mot !!), mais surtout bien vrai.

Explications.

un problème de sac à dos, c'est quoi ? Imaginez vous en train de cambrioler le Louvre. Vous avez, seul, la nuit, en face de vous, une table avec 1000 objets. Chaque objet a une valeur (2 €, 17 €, 5€ ...), mais chaque objet a aussi un poids et un volume. Or, votre sac à dos possède deux contraintes : vous ne pouvez pas emmener ni plus de 40 kg, ni plus de 1 m3. LA question qui se pose à vous est alors la suivante : quels sont les objets que je vais prendre, de telle façon que mon sac à dos ait la plus grande valeur sachant que ce sac à dos devra respecter les deux contraintes précitées. LA question conséquente est alors : quel algorithme vais je utiliser ?

A la base, il faut savoir que ce type de problème est très compliqué à résoudre. Je ne vais pas faire ici un cours de NP-complétude, mais en gros, imaginez vous qu'aujourd'hui, pour ce type de problème, on a pas mieux que l'énumération complète (ou presque) pour avoir la meilleure solution. L'énumération complète, ça veut dire quoi ? ça veut dire que je regarde toutes les solutions possibles, c'est à dire : {x1} puis {x2} puis {x1, x2} puis {x3} puis {x1, x3} puis ... Si vous avez n objets, vous avez donc à essayer toutes les combinaisons de 1 objets parmi les n, puis toutes les combinaisons de 2 objets parmi les n, ... toutes les combinaisons de p objets parmi les n etc... c'est à dire la somme, pour p allant de 1 à n, des combinaisons de p objets parmi n, c'est à dire 2 puissance n. petite application numérique : si vous avez 1000 objets, il faut donc essayer 2^1000 soient environs 10^300 solutions... même en faisant plusieurs milliards de .... miliards de milliards d'essais par seconde, l'énumération complète vous prendra plusieurs milliard de ... de milliards de fois l'age de l'univers. Oui, ça prendrait du temps.

Du coup, pour résoudre exactement ce problème, on utilise des "branch and bound". C'est à dire que vous construisez l'arbre des solutions à partir de l'énumération complète, et de temps en temps, vous pouvez élaguer une branche de l'arbre. Par exemple, vous montrez qu'en prenant les objets 7 et 8 vous obtenez un sac à dos de 50€. mais vous ne pouvez plus mettre aucun objet. Or, en prenant les objets 5, 11 et 22, vous avez un sac à dos de 51€. Vous pouvez donc en conclure que tous les sac à dos contenant les objets 7 et 8 ne sont plus à essayer car vous savez que quoi qu'il arrive, il ne seront pas les meilleurs. Inutile donc d'essayer les sac à dos avec les objest {7,8,9} ou {7,8,10} ou {7,8,11} ... {7,8,1000} mais aussi {7,8,9,10}, {7,8,9,11} etc... Cette technique permet donc de réaliser une pseudo-énumération, mais peut s'avérer longue en temps quand même, sachant qu'aussi, l'arbre construit en mémoire peut être gigantesque...

Une autre approche s'appelle la résolution approchée. Ici, le but du jeu n'est pas d'avoir la solution exacte, mais d'avoir une très bonne solution, très rapidement. Dans le monde industriel, ces solutions sont très prisées. Imaginons que la valeur optimale du sac à dos soit de 31415 €. une entreprise préférera imaginer un sac à dos de 31410€ en 25 secondes que 31415 en 871 jours de calculs. Il est clair que notre voleur du louvre a aussi sa contrainte : un tien vaut mieux que deux tu l'auras : satisfaisons nous d'un très bon sac à dos en terme de valeur que je pourrai emporter avant l'ouverture du louvre que de passer ma nuit à trouver le meilleur, sachant qu'une nuit ne suffira pas...

Mais la résolution approchée n'est pas simple non plus. Sans considération trop technique, sachez qu'on ne peut pas approximer aussi bien qu'on le veut ce genre de problème dans des temps raisonnables... C'est à dire que si on pose à Z* la valeur optimale et e un pourcentage à 100, ai je à ma disposition un algorithme qui puisse me garantir que d'une part, quand il s'arrêtera, je serai à moins de e% de Z*, et que d'autre part, cet algorithme ne sera pas trop long ie il fait autre chose que de l'énumération ? Eh bien non : il n'y pas de garantie de performance pour des algo dont le temps de déroulement soit acceptable.

Les algorithmes que l'on va donc utiliser, quand il s'arrêterons, n'aurons pas de garantie de performance. Ce critère d'arrêt sera donc souvent le temps.

Voila pour le sac à dos et une petite intro au fait que c'est un pb compliqué à résoudre.

"Hybridation de schémas de sous gradient par des métaheuristiques pour ..." Ce n'est pas si compliqué. On va commencer par le schéma de sous gradient. imaginez juste une fonction du type y = f(x). Représentez vous sa courbe. (on prendra une fonction non monotone...). Si vous prenez la tengeante en chaque point, vous vous apercevez qu'elle penche soit vers la droite, soit vers la gauche. Plus grossièrement encore, si vous regardez chaque petit bout de la courbe, soit la courbe monte, soit elle descend. Moi, dans ma résolution de problème, ce qui m'intéresse, c'est quand la courbe monte, monte... puis redescend. juste avant de redescendre, elle est sur un point haut. c'est à dire que les points juste à droite, ou juste à gauche, sont plus bas... c'est un peu cela. Alors que cette courbe est dans un plan (ie un espace à 2 dimensions), moi je travaille dans des hyper-espaces (pour le louvre, dans un espace à 1001 dimensions). Sur certains critères que je ne vais pas développer ici, je sais que la courbe descend ou monte (si tenté que cela ait encore un sens...) et je sais isoler les points hauts.
Mais pas sur n'importe quel problème en fait. reprenons le problème initial du voleur du louvre a deux contraintes (poids et volume). En fait, juste avant de résoudre ce pb, je vais en extraire un plus simple : je vais relacher une contrainte. Par exemple, ne plus tenir compte du poids. En fait si, mais plus comme avant : cette contrainte de poids, je vais la pondérer par un reel, et essayer de trouver la pondération qui m'arrange le mieux. L'intérêt ? c'est que d'un pb de sac à dos à deux contraintes, je passe à un sac à dos à une contrainte. Et ça, on sait bien le résoudre. C'est à partir de deux contraintes que cela devient difficile. Mais on est bien d'accord : résoudre le sac à dos sans tenir compte du poids effectif miximum possible ne nous donne pas une solution pour le pb quand je tiens compte du poids. En effet, il se peut que la solution fournie viole la contrainte de poids, auquel cas, la solution n'est plus admissible. Mais ce qui est interessant, c'est qu'on risque d'avoir un majorant du pb intéressant. Si on ne sait pas résoudre le pb à deux contraintes, on sait néanmoins par exemple que sa valeur n'excédera pas telle autre... Par exemple, on ne sait pas que Z* vaut 31415€ mais on sait que Z* est inférieur à 31555. Le schéma de sous gradient rentre alors en jeu. Dans un premier temps, on a transformé notre pb initial en un problème auxiliaire sur lequel je vais essayer de regarder la "gueule de la courbe". (sachant que ce problème auxiliaire, c'est en fait la suite des pb initiaux pour laquelle on essaie de trouver le reel le meilleur pour la pondération du poids)

Qu'est ce qu'une métaheuristique ? une métaheuristique est une sorte d'heuristique suffisemment générale pour qu'elle en devienne indépendante du problème. Je vous donne un exemple. Dans le pb de sac à dos à 1 contrainte, il existe une heuristique qui dit que si on met les objet les plus denses d'abord, alors on aura un remplissage qui sera dans le pire des cas égale à 11/9 de la solution optimale. En gros, quand vous mettez vos valises dans le coffre pour partir en vacances, vous mettez les plus grosse d'abord. Cela, c'est une heuristique. Elle est dépendante du pb. Maintenant, introduisons la notion de voisinage pour ce pb : on dit que deux solutions sont dans un 1-voisinage si elle ne diffère que d'un objet. un 2-voisinage si ... 2 objets... etc. Par exemple, je mets dans mon coffre les objets (et dans cet ordre) 1-5-4-2-3. une autre solution qui consite à essayer l'ordre : 1-5-4-3-2 (on a permuté le 2 et le 3), sont dans un 1-voisinage, parceque je n'ai besoin que d'une permutation pour passer de l'une à l'autre. Une métaheuristique pourrait être alors pour résoudre ce pb :
- a) prendre une solution au hasard.
- b) pour chaque solution dans le 1-voisinage de la solution du a) : l'essayer !
- c) si on ne trouve pas mieux dans l'étape b) que ce qu'à générer l'étape a), alors essayer les solution de 2-voisinage.
et cette technique est bien une métaheuristique puisqu'elle travaille essentiellement sur des voisinages qui eux, sont indépendants des objets. Par exemple, si on cherche un trajet qui passe par des villes selon un critère donné, on peut reprendre le même algorithme de voisinage. les voisins, cette fois ci ne seront plus des objets mais des villes !

Pourquoi une hybridation ? Comme je l'ai dit, on ne cherche pas à résoudre exactement notre pb de sac à dos à 2 ou 40 contraintes ! on cherche un algorithme qui nous donnera une bonne solution très rapidement. la bonne solution étant la considération de l'encadrement trouvé. d'une part, on cherche un minorant, d'autre part on cherche un majorant.
En fait, la méthode de sous gradient converge d'autant plus rapidement que l'on possède un bon minorant. C'est pourquoi, avant de commencer le sous gradient, je fais tourner une métaheuristique, qui non seulement va me donner une bon minorant, mais en plus va m'assurer une convergence rapide vers un bon majorant.

Du coup, pour un pb donné, au lieu de savoir que Z*, la solution optimale vaut 31415 €, je ne saurai "seulement" que la valeur de Z* est comprise entre 31410 et 31419 par exemple. Sauf que cet encadrement, je l'ai en quelques secondes, alors que pour avoir 31415, il me faudra souvent plusieurs jours, quand ce n'est pas plusieurs mois...

Que dire de plus ?
pas grand chose. j'ai presque fini mon proto, qui marche bien pour deux contraintes. Mais récemment, je me suis vu arriver 300 instances de 10, 30 et 50 contraintes. Et là, pb : mon proto, générique pour deux contraintes, ne l'est plus pour 50. (car là, il ne s'agit pas de relacher 1 contrainte, mais d'en relacher 49 : et ça, ça change bcp de chose : la plupart des structures de données prend une dimension de plus...)
CPLEX est un solveur commercial. Probablement à ce jour le meilleur du monde. En gros, vous lui filez un pb, et il vous crache une réponse. Mais c'est une boite noire : pas question de savoir comment il fait !!! L'un des buts de mon mémoire, c'est aussi de montrer que l'algo que j'utilise, dont une partie a été créée par moi (la métaheuristique), est aussi compétitif que CPLEX. Sauf que mon code, il est libre, gratuit, décrit, etc... CPLEX, lui, vous coute (cher) à l'achat... Et on est bien d'accord, je me bats contre CPLEX, mais sur une seule catégorie de pb : les sac à dos à plusieurs contraintes.

Voila, c'est en gros ce qui m'occupe depuis un an... et pour l'avenir aussi j'espère...