Planos Cortantes: Gomory y cover
Cortes válidos que aprietan la relajación de un problema entero sin eliminar soluciones enteras: corte de Gomory desde el tableau (con el detalle del piso de coeficientes negativos) y desigualdades cover de mochila. Arquetipo E-B del Examen.
functions
La idea: cortar el fraccionario sin sacar enteros
Apretar la relajación con desigualdades válidas
Cuando la relajación lineal de un problema entero da un óptimo fraccionario, en vez de ramificar (como en Branch & Bound) podemos agregar una desigualdad nueva que recorte ese punto fraccionario del poliedro pero no elimine ningún punto entero factible. Esa desigualdad es un plano cortante.
Qué hace válido a un corte
Un corte es válido si toda solución entera factible lo satisface (es redundante para el conjunto entero). Lo útil es que además corta el óptimo fraccionario actual: lo deja fuera del nuevo poliedro.
Dos condiciones que todo corte debe cumplir: (1) no saca ningún punto entero factible (validez) y (2) sí saca el óptimo fraccionario de la relajación actual (si no, no sirve de nada). Acercan el poliedro a la envoltura convexa.
Las dos propiedades
Iterar acerca a la envoltura convexa
Cada corte aprieta el poliedro de la relajación hacia la envoltura convexa de los puntos enteros. Iterando cortes, la relajación lineal se va estrechando hasta que su óptimo cae en un entero. En la práctica se combinan con Branch & Bound: al método híbrido se le llama branch-and-cut, y es lo que usan los solvers modernos (Gurobi, CPLEX).
Cargando Quiz...
calculate
Corte de Gomory desde el tableau
Generar un corte a partir de una fila fraccionaria
El corte de Gomory se deriva del tableau óptimo de la relajación. Se elige la fila de una variable básica fraccionaria xBi:
xBi+j∑a^ijxj=b^i
Se toman las partes fraccionarias de cada coeficiente y del lado derecho. Para un número r, su parte fraccionaria es f=r−⌊r⌋∈[0,1):
fij=a^ij−⌊a^ij⌋,fi=b^i−⌊b^i⌋
El corte de Gomory es entonces:
j∑fijxj≥fi
Este corte elimina el óptimo fraccionario actual (en él las xj no básicas valen 0, así que el lado izquierdo da 0<fi, violando el corte) sin sacar ningún punto entero.
Coeficientes negativos: la parte fraccionaria SIEMPRE queda en [0,1), así que el piso de un negativo va hacia abajo, no hacia cero. Ejemplo: −49=−3+43 (no −2−41). Confundir esto es el error clásico del corte de Gomory.
El error típico
Ejemplo trabajado (de examen)
Sistema óptimo con no básicas x3,x4:
x1+417x3+45x4=49
Partes fraccionarias: 417=4+41, 45=1+41, 49=2+41. El corte queda:
41x3+41x4≥41 ⟹ x3+x4≥1
Si en cambio usamos la fila de x2 con −49x3, hay que descomponerla al entero inferior (−49=−3+43); reagrupando se llega al mismo corte x3+x4≥1. La elección de fila no cambia el resultado, pero el piso del negativo sí hay que tomarlo hacia abajo.
science
Desigualdades cover para la mochila
Cortes específicos del knapsack binario
Para una restricción de mochila con variables binarias:
i∑wixi≤W,xi∈{0,1}
un cover C es un subconjunto de objetos cuyo peso total excede la capacidad:
i∈C∑wi>W
Como no caben todos juntos, al menos uno debe quedar fuera. Eso da la desigualdad cover, un corte válido:
i∈C∑xi≤∣C∣−1
Cover minimal
Un cover es minimal si al quitarle cualquier objeto deja de exceder la capacidad. Los covers minimales dan los cortes más fuertes (usan el menor ∣C∣ posible).
El cover corta vértices fraccionarios "tramposos": la relajación puede dar algo como (0,8,0,7,0,6) que suma 2,1>2 y viola x1+x2+x3≤2. El corte lo elimina, apretando la relajación hacia la envoltura convexa.
Para qué sirve
Ejemplo trabajado
En un knapsack con covers minimales {1,2,3} y {1,2,4}, los cortes son ∑i∈Cxi≤∣C∣−1=2. La solución relajada (0,8,0,7,0,6,0,0) da x1+x2+x3=2,1, que viola el corte x1+x2+x3≤2: queda cortada.
Cargando Quiz...