Programación entera

La idea

Muchas decisiones no admiten fracciones: no se compran 2,4 camiones ni se abren 1,7 fábricas, y una variable binaria que decide «sí o no» solo puede valer 0 o 1. Añadir la condición x ∈ ℤ a un problema lineal produce un problema de programación entera, que ya no es convexo: la región factible pasa de ser un poliedro continuo a una nube de puntos aislados dentro de él.

La tentación es resolver la relajación lineal (ignorando la integralidad) y redondear. Es un error: el punto redondeado puede ser infactible (si el óptimo continuo está sobre una restricción, subir una coordenada la viola) y, aunque sea factible, puede estar muy lejos del óptimo entero, que a veces se encuentra en un vértice completamente distinto de la región. La diferencia entre el valor de la relajación y el del óptimo entero se llama brecha de integralidad, y la relajación siempre proporciona una cota: en un problema de maximización, z_LP ≥ z_ENT.

El algoritmo estándar es ramificación y acotación (branch and bound). Se resuelve la relajación; si la solución ya es entera, hemos terminado. Si alguna variable sale fraccionaria, digamos x = 3,4, se ramifica creando dos subproblemas con x ≤ 3 y con x ≥ 4, que juntos contienen todos los puntos enteros y excluyen el fraccionario. Cada rama se resuelve y se poda cuando su cota es peor que la mejor solución entera conocida, cuando es infactible o cuando ya da una solución entera. El árbol puede crecer exponencialmente —estos problemas son NP-difíciles—, pero las buenas cotas y los planos de corte permiten resolver en la práctica modelos con millones de variables binarias.

Fórmulas clave

• Problema enteromax cᵀx s.a. A x ≤ b, x ≥ 0, x ∈ ℤⁿ
• Relajación lineal (cota)z_LP ≥ z_ENT (en maximización)
• Brecha de integralidadbrecha = z_LP − z_ENT ≥ 0
• Ramificación sobre xⱼ = vrama A: xⱼ ≤ ⌊v⌋ rama B: xⱼ ≥ ⌈v⌉
• Poda por cotasi z_LP(nodo) ≤ z_mejor → se descarta el nodo
• Variable binariax ∈ {0, 1} ⇔ 0 ≤ x ≤ 1, x ∈ ℤ

Dónde se aplica

La planificación de turnos de hospitales y aerolíneas se formula con variables binarias «este empleado cubre este turno», y la localización de instalaciones decide con binarias qué almacenes abrir. En telecomunicaciones, asignar frecuencias a antenas sin interferencias es un problema entero equivalente a colorear un grafo. En finanzas, seleccionar una cartera con un número máximo de activos distintos exige binarias de «entra o no entra». Y los compiladores asignan registros a variables resolviendo, otra vez, un problema entero disfrazado de coloreado.

Con programación (Python)

# max z = 5x + 4y  s.a.  6x + 4y <= 24,  x + 2y <= 6,  x, y >= 0 enteros
def z(x, y):
    return 5 * x + 4 * y

def factible(x, y):
    return 6 * x + 4 * y <= 24 + 1e-9 and x + 2 * y <= 6 + 1e-9 and x >= 0 and y >= 0

# Optimo continuo: interseccion de las dos restricciones activas
xc, yc = 3.0, 1.5
print("Relajacion lineal: (%.2f, %.2f)  z = %.2f" % (xc, yc, z(xc, yc)))
print("Redondeo abajo (3, 1): factible =", factible(3, 1), " z =", z(3, 1))
print("Redondeo cercano (3, 2): factible =", factible(3, 2))

mejor = None
for x in range(0, 5):
    for y in range(0, 4):
        if factible(x, y) and (mejor is None or z(x, y) > z(mejor[0], mejor[1])):
            mejor = (x, y)
print("Optimo entero:", mejor, " z =", z(mejor[0], mejor[1]))
print("Brecha de integralidad:", z(xc, yc) - z(mejor[0], mejor[1]))
print("El optimo entero NO es el redondeo del continuo")

La versión en JavaScript, editable y ejecutable en el navegador, está en la página interactiva del tema.

Temas relacionados

Programación lineal · El problema de la mochila · Combinatoria y triángulo de Pascal