Programmation linéaire - Valeur absolue supérieure à une constante

Question

Comment convertir la contrainte | x | > = 2 pour que cela fonctionne dans un programme linéaire (en particulier, résoudre en utilisant Simplex).

Je comprends comment convertir | x | < = 2 comme cela deviendrait x < = 2 et -x < = 2

Cependant, la même logique ne fonctionne pas lorsque vous avez une constante minimale.

Answer 1

Il n'existe aucun moyen de créer une équation comme |x|>=2 dans un LP pur (continu). Vous devez formuler x <= -2 OR x >= 2 qui est non-convexe. Cela nécessitera une variable binaire rendant le problème MIP.

Une formulation peut être:

x >= 2 - delta*M 
x <= -2 + (1-delta)*M 
delta in {0,1} 

où M est judicieusement choisi grand nombre. Par exemple. si -100<=x<=100 alors vous pouvez choisir M=102.