Linéarisation de contrainte valeur absolue

[Cliffe]

Salut, j'essaye de linéariser la valeur absolue pour un programme linéaire.

Soit la variable réelle , tel que - avec et . On veut linéariser la valeur absolue de :

On introduit la variable : de sorte que :

Soit la variable binaire :
[CENTER][/CENTER]

on a alors les contraintes :
[CENTER][/CENTER]

Soit les deux variables et tel que : . On a alors les contraintes :

[CENTER][/CENTER]

avec .

Enfin la valeur absolue est donnée par la variable réelle positive : .

Qu'en pensez vous ?

[fatal_error]

hi,

ne peut on pas simplement ecrire

x <= a
x <= 0
y <= -a
y <= 0

max x+y

si a < 0
x vaut 0, y vaut -a
x+y vaut |a|
si a > 0
x vaut a, y vaut 0
x+y vaut |a|

[Cliffe]

Ton modèle est faux.
Si je prend :

[CENTER] [/CENTER]

Si on prend le max on a

Et puis, je ne veux pas forcément de valeur absolue dans la fonction objectif. Il y déjà des méthodes pour cela. Je veux la remplacer par une variable. Si je simplifie mon modèle, j'ai :

[CENTER] [/CENTER]

Si je prend et :

[CENTER] [/CENTER]

[CENTER] [/CENTER]

[CENTER]Et donc .[/CENTER]

[fatal_error]

Ton modèle est faux.

ouais certes,
après tu peux jouer un peu avec les inégalités...

L'idée que j'ai foirée c'est juste de satisfaire au mieux les deux inégalités concernant une variable.

Ici, on peut prendre
x>=a
x>=-a
idem x>=max(a,-a)

et prendre min x pour avoir abs(a)

Je mets pas en cause ton modèle qui apparemment à l'air de marcher (j'ai pas regardé). Par contre il est juste overkill

PS: l'idée de sommer des variables, ca vient d'un vague souvenir avec le tsp résoud en simplexe (sans les cutting planes). Mais bon, c'est pas nécessaire ici

[Cliffe]

Je mets pas en cause ton modèle qui apparemment à l'air de marcher (j'ai pas regardé). Par contre il est juste overkill

Mon modèle est très simple. On pose où représente la partie positive et la partie négatif. Suivant le signe de , on a ou qui est nul. Pour cela j'utilise une variable binaire qui vaut 1 si est positif 0 sinon.

Pour obtenir , il suffit de l'encadrer par 2 fonctions linéaire :

[CENTER] [/CENTER]