Linealizar la sentencia if en la programación lineal

Question

Estoy teniendo problemas para averiguar cómo formular la siguiente función objetivo en LP

a + b + (if(c < d) then e else 0)

Donde a, b, c, d y e son algunas sumas o diferencias de variables multiplicadas por algunas constantes reales. He pensado que tal vez introduciendo una variable binaria x Podría redefinirlo como

a + b + xe

Pero eso ya no sería lineal, por no mencionar que ni siquiera entonces se me ocurriría qué restricciones x necesitaría tener...

Cualquier ayuda con esto sería muy apreciada, he estado devanando los sesos y buscando en Google a diestro y siniestro durante horas, pero sin una solución clara a la vista.

Editar: Para el contexto completo, estoy tratando de minimizar la distancia y tratando de utilizar la última fórmula de aproximación de distancia que se encuentra aquí: http://www.flipcode.com/archives/Fast_Approximate_Distance_Functions.shtml

Answer 1

Que el objetivo sea $a + b + q$ y utilizar el truco de la gran M.

Dejar $\delta$ sea la variable binaria, primero definimos restricciones tales que $\delta = 0$ si $c \leq d$ et $\delta = 1$ de lo contrario.

$$ c \leq d + M \delta \\ c \geq d - M (1 - \delta) $$ donde $M$ es un número grande. A continuación, definimos restricciones tales que $q$ da los valores necesarios.

$$ e - M\delta \leq q \leq e + M \delta \\ - M(1 - \delta) \leq q \leq e + M (1 + \delta) $$