Convierte a booleano, para programación lineal entera

11

Quiero expresar la siguiente restricción, en un programa lineal entero:

y={0if x=01if x0.

Ya tengo las variables enteras y me prometieron que . ¿Cómo puedo expresar la restricción anterior, en una forma adecuada para usar con un solucionador de programación lineal entero?x,y100x100

Presumiblemente, esto requerirá la introducción de algunas variables adicionales. ¿Qué nuevas variables y restricciones necesito agregar? ¿Se puede hacer limpiamente con una nueva variable? ¿Dos?

De manera equivalente, esto es preguntar cómo hacer cumplir la restricción

y0 if and only if x0.

en el contexto donde ya tengo restricciones que implican y .|x|1000y1


(Mi objetivo es corregir un error en /cs//a/12118/755 ).

DW
fuente
1
Que has intentado ¿Has intentado trabajar con algunos ejemplos para ver si ves un patrón? En caso afirmativo, ¿ha intentado adivinar y luego intentó probarlo?
Brika
1
Je! Ya veo lo que hiciste allí , @Brika. Si tiene curiosidad por ver lo que intenté, vea aquí , así como esta explicación de por qué eso estaba realmente mal . Si quieres ver mi próximo intento, mira mi respuesta . Gracias por leer mis viejas preguntas, y si pueden mejorarse para el futuro, ¡me encantaría escuchar cualquier sugerencia que pueda tener!
DW
Eso es muy bueno. ;)
Brika

Respuestas:

4

Creo que puedo hacerlo con una variable binaria adicional :δ{0,1}

100yx100y
0.001y100.001δx0.001y+100.001(1δ)

Actualizar

Esto supone que es una variable continua . Si restringimos para que tenga un valor entero , entonces la segunda restricción se puede simplificar a: xx y - 101 δ x - y + 101 ( 1 - δ )x

y101δxy+101(1δ)

Erwin Kalvelagen
fuente
1
Verifiqué esto correctamente probándolo exhaustivamente con un pequeño programa. ¡Gracias por la solución!
DW
@ErwinKalvelagen, ¿podría explicar su lógica con la variable binaria delta, para un caso más general, por ejemplo, si y = {a: x> 0, b: x <0}.
Nick
1
@Nick La variable binaria se usa para modelar una construcción 'OR'. Consulte aquí para obtener una respuesta a su pregunta.
Erwin Kalvelagen
@ErwinKalvelagen, la gran respuesta, traté de aplicar su enfoque a mi pregunta aquí cs.stackexchange.com/questions/64794/… .
Nick
1
@GonzaloSolera En realidad estaba equivocado: asumí que era una variable continua. De hecho, cuando tiene un valor entero, podemos mover 0.001 hasta 1 como usted sugirió. xxx
Erwin Kalvelagen
1

Lo siguiente no es bonito de ninguna manera, pero funciona. Sea , en el caso específico de la pregunta. Entonces tenemos las siguientes restricciones.N = 1000xNN=100

  1. 0z1,z2,z1
  2. xN(1z1)0
  3. xNz11
  4. xN(1z2)0
  5. xNz21
  6. z1+z21z
  7. zz1
  8. zz2

La intuición es la siguiente. . Esto está codificado en las restricciones 2 y 3. De manera similar, las restricciones 4 y 5 codifican . Las últimas tres restricciones expresan .z1=1x0z2=1x0z=z1z2

Pramod
fuente
Esto parece tener un error. Supongo que tiene la intención de . Sin embargo, todavía está mal para : queremos forzar ( ) en este caso, pero no hay opción para que satisfaga todas las ecuaciones, como la ecuación requiere (es decir, ). Por lo tanto, este ILP da el resultado incorrecto cuando : queremos , pero tenemos . También el intervalo deseado para como aparece en la pregunta es , no . z=1yx=100y=1z=0z1,z2xNz21x<Nx99x=99y=1y=0xNxN0xN
DW
1

Aquí hay una solución que usa dos variables temporales. Supongamos que sea ​​una variable entera de cero o uno, con el significado deseado de que si , si , y . Estos pueden hacerse cumplir con las siguientes restricciones:t,ut=1x0u=1x0y=¬(tu)

0t,u,y11+x101t101+x1x101u101xt+u11y1yt1yu
DW
fuente
Esta respuesta es incorrecta, desafortunadamente. Restringirá por la primera parte de la primera restricción no trivial cuando la pregunta se haga con . ¿No son divertidos los errores de poste de la cerca? (Lo mismo para .)x 100 x - 99x99x100x99
TLW
@TLW, ¡gracias por atrapar eso! He editado mi respuesta para corregir el error. Lo probé exhaustivamente con un pequeño programa y creo que debería ser correcto ahora.
DW