CPLEX sous Python

**StabiloHB** · 10/02/2020, 11h09

Bonjour à tous,

Je crée un nouveau thread après mon ancien à propos d'un Dial A Ride Problem solver.

J'utilise la librairie open source de CPLEX sur Python, à savoir docplex pour ceux qui chercheraient.

Quand CPLEX cherche les solutions en Cut and Bound, il y a le Best Integer et le >Best Bound qui convergent vers la solution optimale qui se trouve dans le gap entre les deux.

Je pense avoir compris le Best Integer, il me semble que c'est le chemin qui est pour l'instant le plus court.

Ma question se porte sur le Best Bound, qu'est ce que c'est ?

Merci d'avance et bonne journée à tous,

Stabilo.

**dourouc05** · 10/02/2020, 11h53

Lors de la résolution d'un problème, CPLEX calcule deux types de bornes : la borne primale et la borne duale. On se place dans le contexte d'une maximisation : la borne primale indique que l'optimum global est au moins aussi élevé ; la borne duale donne une limite supérieure à l'optimum global (sans qu'on sache si on peut l'atteindre ou pas).

La borne primale est mise à jour chaque fois que CPLEX trouve une solution entière (ou que tu lui en donnes une). La borne duale est obtenue à l'aide d'un relâchement du problème initial : on enlève les contraintes complexes (variables entières), ce qui donne un problème que l'on peut résoudre à l'optimalité facilement. Puisqu'on a enlevé des contraintes, l'objectif peut monter plus haut, mais on sait qu'on ne pourra pas aller plus haut que ce qu'on vient d'obtenir. (Lors de l'exploration de son arbre, CPLEX peut encore mettre à jour cette borne duale, chaque fois qu'il a commencé à explorer les deux enfants d'un nœud.)

**StabiloHB** · 10/02/2020, 13h47

Salut !

Merci pour ta réponse,

J'étais pas trop loin de la vérité alors !

Dernière petite question, connais tu la fonction pour arrêter CPLEX en fonction du Gap (sur python) ?
Par exemple dès que l'on rentre dans le Gap des 10% on stop et donne la solution. Dans le but d'éviter des temps de résolution trop long, je connais modele.parameter.timelimit=XXX pour le temps mais pas pour le Gap.

Merci d'avance et bonne journée,

Stabilo.