MIP et contrainte de seuil
Forum 'Discussions' - Sujet créé le 2011-04-22
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.
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.