Le 22/04/2011 par athrus :

Bonjours,
Dans les programme linéaire on retrouve souvent des contraintes de type big-M pour les seuils de la forme:

min ax+b
sc
x<=b*M (avec M qui majore x) : contrainte big M
x réel (ou entier)
b booleen

cette contrainte traduit le fait que si x>0 alors b=1 et b=0 sinon. Le problème de cette contrainte est qu'elle rends la relaxation linéaire du problème un peu pourri selon la valeur de M. Et donc déteriore les performances du branch and bound.

En refléchissant un peu j'ai trouvé une formulation alternative ( je sais pas ce que vous en penserez):

max -ax + x1+b
sc
x=x1+x2
x2>=b*eps ( eps etant une valeur tres faible)
x1<=0
x2>=0
x, x1, x2 réels
b booleen


J'aimerai lancer ce topic pour discuter et partager des différentes formalution possible pour traduire la contrainte de seuil en MIP.

Le 22/04/2011 par YGaoua :

1- Votre problème a pour solution optimale le point (0,0)
2- Je pense que le problème a au moins une contrainte supplémentaire que la contrainte BIG M
3- Ajuster les grands M (cas binaire):considérons un problème binaire mixte,x ∈ R+, y ∈ {0, 1} x <= 9999 y, 0 <= x <= 5 ==>
x <= min{5, 9999} y
4-Ajuster les grand M (cas entier): considérons un problème binaire mixte, x ∈ R+, y ∈ N, x ≤ 5 y, 0 ≤ x ≤ 14
=>x ≤ 14 − 4 (3 − y)

Le 26/04/2011 par athrus :

1>> par nécéssairment cela dépends du signe de a.
2>> je suis d'accord, je n'ai pas été suffisament précis, il faut comprendre: x est définit sur un intervalle de R sur les 2 PL et non pas sur R tout entier.
Dans le cas usuel x est dans Rn et x est définit sur un polyedre.
3>> justement je me demandais si on pouvait faire mieu que ca. Du point de vue de la relaxation linéaire de manière à ce qu'elle soit la meilleure possible.
4>> ici je vois l'idée

Le 10/05/2011 par Hocine Bouarab :

Je ne vois pas de façon simple pour modifier ce programme afin d'améliorer la qualité de son relaxé mais ce que je te conseille c'est de bien choisir ta méthode de résolution. Suggestion:
on voit ici que si on fixe la valeur de y, le problème devient trop facile. La décomposition de Benders te permettra dans ce cas d'avoir rapidement une solution optimale.

Le 10/05/2011 par Hocine Bouarab :

pardon, ta variable binaire est "b" et non "y".