Programación entera y problemas de redes

"Cuando una variable es '¿asignar o no?' la matemática se vuelve mucho más expresiva — y mucho más costosa de resolver."

Qué vas a aprender en este capítulo

PL continua resuelve cuando "media unidad" tiene sentido (kg de harina, litros de pintura). Pero en muchos problemas reales las variables son discretas:

¿Construir una sucursal en este sitio? Sí/No ( $0$ o $1$ ).
¿Cuántos buses asignar a una ruta? Entero positivo.
¿Cuál pedido va a qué camión? Asignación discreta.

Eso es Programación Entera (PE). En este capítulo:

Formulación con variables enteras y binarias.
Branch & Bound (B&B) — el algoritmo central de PE.
Cuatro problemas de redes clásicos (transporte, asignación, MST, ruta crítica).
Modelar restricciones lógicas con binarias.
Resolución práctica.

4.1 Variables enteras y binarias

📐 Fundamento

Una variable entera: $x \in \mathbb{Z}, x \geq 0$ .

Una variable binaria: $x \in {0, 1}$ . Caso especial pero brutalmente útil:

$x_j = 1$ si se elige la opción $j$ , $0$ si no.
$y_i = 1$ si se abre la sucursal $i$ .
$z_{ij} = 1$ si el camión $i$ visita el cliente $j$ .

Mixed Integer Program (MIP): mezcla variables continuas y enteras.

El gran problema: complejidad

PL continua: polinomial ( $O(n^{3.5})$ con interior point). PE/MIP: NP-difícil. El espacio de soluciones es discreto, no podés moverte continuamente.

En la práctica: solvers modernos (Gurobi, CPLEX, HiGHS) resuelven MIPs con millones de variables en minutos gracias a B&B + heurísticas. Pero un MIP "pequeño" mal modelado puede tardar horas.

4.2 Branch & Bound

💡 Intuición

Tenés el problema entero $P$ . Lo resolvés ignorando la integralidad — esto se llama relajación LP. Da una solución que probablemente tiene valores fraccionarios.

Tomás una variable fraccional $x_j = 3.7$ y te ramificás en dos subproblemas:

$P_1$ : $P + \text{restricción } x_j \leq 3$ .
$P_2$ : $P + \text{restricción } x_j \geq 4$ .

Resolvés ambos. Si uno da solución entera, la guardás como mejor candidato. Si no, ramificás de nuevo.

Clave: si la relajación LP de un subproblema da un valor peor que el mejor candidato entero conocido, podés podarlo (no seguir ramificando). De ahí "bound".

El proceso es una búsqueda en árbol: combina enumeración inteligente con poda agresiva.

📝 Ejemplo trabajado — B&B chico

\max Z = 5 x_1 + 4 x_2,\; 6 x_1 + 4 x_2 \leq 24,\; x_1 + 2 x_2 \leq 6,\; x_j \in \mathbb{Z}_{\geq 0}

Paso 1: relajación LP. Resolvés sin la restricción de enteros. Solución: $x_1 = 3, x_2 = 1.5$ , $Z = 21$ . ( $x_2$ fraccional.)

Paso 2: ramificar en $x_2$ .

Rama A: $x_2 \leq 1$ . LP da $x_1 = 3.33, x_2 = 1$ $x_{1} = 3.33, x_{2} = 1$ , $Z = 20.67$ $Z = 20.67$ . Sigue fraccional. Ramificás en $x_1$ $x_{1}$ :
- $x_1 \leq 3$ : LP da $(3, 1)$ , $Z = 19$ . Entero. Candidato.
- $x_1 \geq 4$ : LP da $(4, 0)$ , $Z = 20$ . Entero. Mejor candidato.
Rama B: $x_2 \geq 2$ . LP da $x_1 = 2.67, x_2 = 2$ $x_{1} = 2.67, x_{2} = 2$ , $Z = 21.33$ $Z = 21.33$ . Sigue fraccional. Ramificás en $x_1$ $x_{1}$ :
- $x_1 \leq 2$ : LP da $(2, 2)$ , $Z = 18$ . Entero, pero peor que 20. Descartar.
- $x_1 \geq 3$ : LP da $(3, 1.5)$ — pero $x_2 \geq 2$ , infactible. Descartar.

Óptimo entero: $(4, 0)$ con $Z = 20$ .

Notá que la solución entera NO es "redondear" la LP $(3, 1.5)$ → $(3, 1)$ . Redondear ingenuamente cuesta $Z = 19$ , peor que el verdadero óptimo $(4, 0) = 20$ .

Esta es la razón clave por la que PE requiere algoritmos, no atajos: redondeo es a menudo subóptimo y a veces incluso infactible.

4.3 Problema de Transporte

📐 Fundamento

Setup: $m$ orígenes con oferta $s_i$ , $n$ destinos con demanda $d_j$ . Costo $c_{ij}$ de enviar 1 unidad desde origen $i$ a destino $j$ . Minimizar costo total.

Variables: $x_{ij}$ = unidades enviadas desde $i$ a $j$ .

\min Z = \sum_{i,j} c_{ij} x_{ij}

\sum_j x_{ij} \leq s_i \quad \forall i \quad (\text{oferta})

\sum_i x_{ij} \geq d_j \quad \forall j \quad (\text{demanda})

x_{ij} \geq 0

Casos:

Si $\sum s_i = \sum d_j$ (balanceado): las restricciones de oferta y demanda son igualdades.
Si oferta > demanda: agregás un destino ficticio que absorba el excedente, costo $0$ .
Si demanda > oferta: infactible en la forma básica. Tenés que decidir qué demanda no satisfacer.

Hecho asombroso: aunque parece PE (cantidades de cajas son enteras), la matriz de restricciones es totalmente unimodular, lo que garantiza que la solución LP siempre es entera. Resolvés con Simplex normal y nunca tenés que ramificar.

Ejemplo:

Costo $/u	Tienda1	Tienda2	Tienda3	Oferta
Fábrica A	4	6	8	100
Fábrica B	5	3	7	150
Demanda	80	120	50

Modelo: 6 variables ( $x_{A1}, \ldots, x_{B3}$ ), 5 restricciones (2 oferta + 3 demanda). Resolvés con scipy.optimize.linprog, networkx.min_cost_flow, o cualquier solver MIP.

4.4 Problema de Asignación

📐 Fundamento

Setup: $n$ tareas, $n$ trabajadores. Costo $c_{ij}$ de asignar trabajador $i$ a tarea $j$ . Asignar exactamente uno a uno, minimizando costo total.

Variables binarias: $x_{ij} \in {0, 1}$ , $= 1$ si $i$ va a tarea $j$ .

\min Z = \sum_{ij} c_{ij} x_{ij}

\sum_j x_{ij} = 1 \quad \forall i \quad (\text{cada trabajador a una tarea})

\sum_i x_{ij} = 1 \quad \forall j \quad (\text{cada tarea a un trabajador})

x_{ij} \in \{0, 1\}

Algoritmo dedicado: método húngaro ( $O(n^3)$ ). Más rápido que B&B para este caso particular.

Aplicaciones:

Asignar pilotos a vuelos.
Asignar cirugías a quirófanos.
Asignar repartidores a zonas en una ciudad.
Matching en sitios de citas (LP relajado).

4.5 Árbol generador mínimo (MST)

📐 Fundamento

Setup: Un grafo conexo no dirigido con pesos en las aristas. Encontrar un subgrafo que conecte todos los nodos con peso total mínimo, sin ciclos.

Algoritmos clásicos:

Kruskal ( $O(E \log E)$ ): ordenar aristas por peso, agregar la más barata que no forme ciclo.
Prim ( $O(E \log V)$ ): empezar de un nodo, expandir incluyendo siempre la arista más barata hacia un nodo no incluido.

Aplicaciones:

Cablear $n$ pueblos con fibra óptica mínimo costo total (proyecto INTERNET RURAL en SV).
Diseño de circuitos integrados (rutas de cobre mínimo).
Clustering jerárquico (eliminar la arista más cara da clusters).

Ejemplo: 5 pueblos en SV, costos de conexión:

	SM	LU	CHL	SJO	PE
SM	-	30	45	60	80
LU	30	-	50	70	90
CHL	45	50	-	25	65
SJO	60	70	25	-	35
PE	80	90	65	35	-

MST (Kruskal):

Arista más barata: CHL-SJO (25). Acepta.
SM-LU (30). Acepta.
SJO-PE (35). Acepta.
SM-CHL (45). Acepta (4 aristas, conecta 5 nodos — listo).

Costo MST: 25 + 30 + 35 + 45 = 135.

4.6 Camino más corto y ruta crítica

📐 Fundamento

Camino más corto: ya lo vimos en Estructuras de Datos (Dijkstra). En IO se usa para:

GPS / ruteo logístico.
Planificación de paquetes en redes.

Ruta crítica (CPM): caso especial sobre un DAG de tareas con duraciones. Para un proyecto con tareas y precedencias:

Para cada tarea calculás ES (Earliest Start) y EF (Earliest Finish).
Para cada tarea calculás LS y LF (Latest Start/Finish) hacia atrás.
Holgura = $LS - ES$ . Tareas con holgura $= 0$ están en la ruta crítica.
La duración del proyecto = EF del nodo final = LF del nodo final.

Aplicación: gestión de proyectos. La ruta crítica te dice qué tareas no pueden atrasarse sin atrasar todo el proyecto. Se cubre en detalle en Gestión de Proyectos de TI.

Ejemplo (5 tareas):

Tarea	Duración	Predecesoras
A	3	—
B	5	A
C	4	A
D	2	B, C
E	3	D

ES/EF hacia adelante:

A: ES=0, EF=3.
B: ES=3, EF=8. C: ES=3, EF=7.
D: ES=max(8,7)=8, EF=10.
E: ES=10, EF=13.

Duración proyecto: 13 días. Ruta crítica: A → B → D → E (todas con holgura 0). C tiene holgura 1.

4.7 Restricciones lógicas con binarias

🛠️ Aplicado

Las binarias permiten modelar lógica combinatoria dentro de PL. Algunas plantillas útiles:

If-then ("si abro fábrica $i$ , máximo $M$ unidades")

x_i \leq M y_i

donde $y_i \in {0, 1}$ es "abro fábrica $i$ ". Si $y_i = 0$ , $x_i$ debe ser $0$ . Si $y_i = 1$ , $x_i \leq M$ . $M$ es un número grande (big-M).

Al menos $k$ de $n$ opciones

\sum_i y_i \geq k

Exactamente uno

\sum_i y_i = 1

Implicación ( $y_1 = 1$ ⇒ $y_2 = 1$ )

y_2 \geq y_1

Disyunción ("restricción A o B")

Difícil en PL puro; con binaria $z$ :

\text{Restricción A: } a^T x \leq b_A + M(1-z)

\text{Restricción B: } a^T x \leq b_B + Mz

Si $z = 1$ : A activa, B "se relaja". Si $z = 0$ : B activa, A "se relaja". El solver elige $z$ óptimamente.

Cuidado con big-M: valores muy grandes hacen la relajación LP débil y B&B lento. Usá el mínimo M que aún funcione.

4.8 Resolución práctica

🛠️ Aplicado

PuLP — programación entera

import pulp

m = pulp.LpProblem("plant_location", pulp.LpMinimize)

# Variables: y_i abrir fábrica, x_ij unidades enviadas
y = {i: pulp.LpVariable(f"y_{i}", cat='Binary') for i in range(3)}
x = {(i, j): pulp.LpVariable(f"x_{i}_{j}", lowBound=0)
     for i in range(3) for j in range(5)}

# Objetivo: costo apertura + costo envío
m += pulp.lpSum(F[i] * y[i] for i in range(3)) + \
     pulp.lpSum(c[i][j] * x[i, j] for i in range(3) for j in range(5))

# Restricciones
for j in range(5):
    m += pulp.lpSum(x[i, j] for i in range(3)) >= d[j]      # demanda
for i in range(3):
    m += pulp.lpSum(x[i, j] for j in range(5)) <= K[i] * y[i]  # capacidad si abierta

m.solve()

NetworkX — redes

import networkx as nx

G = nx.Graph()
G.add_weighted_edges_from([('SM','LU',30), ('SM','CHL',45), ('CHL','SJO',25), ...])

mst = nx.minimum_spanning_tree(G)         # MST
print(sorted(mst.edges(data=True)))

camino = nx.shortest_path(G, 'SM', 'PE', weight='weight')   # Dijkstra

NetworkX no es el más rápido pero es el más fácil para empezar.

4.9 Errores comunes

⚠️ Trampa común

Big-M demasiado grande. Usás $M = 10^9$ "por seguridad" en una restricción tipo $x \leq My$ . La relajación LP queda muy débil: $y$ puede ser casi 0 y $x$ casi $10^9$ . El árbol B&B explota explorando ramas inútiles.

Tip: elegí el M más chico que aún sea válido. Si en el peor caso $x \leq 100$ , usá $M = 100$ . Lo difícil es saber el peor caso — sale del análisis del problema.

⚠️ Trampa común

Asumir que MIP es como LP "con un poco más de tiempo". El tiempo de resolución de MIPs es muy sensible a la formulación. Un mismo problema con dos formulaciones puede tardar 1 s o 1 día. La formulación "natural" no siempre es la mejor.

Tip: si tu MIP no resuelve en tiempo razonable, reformulá antes de pedir más hardware. Técnicas: agregación de restricciones, cortes válidos, ordenamiento de variables.

⚠️ Trampa común

Confundir "óptimo de la relajación LP" con "óptimo entero". Tras correr LP, ves $x = 3.5$ y redondeás a $4$ . Pero $4$ puede ser infactible (otra restricción se viola) o subóptimo (otra combinación entera es mejor).

Tip: el redondeo solo es seguro si todas las restricciones se satisfacen. Si no, usá B&B (cualquier solver MIP lo hace por vos).

4.10 Resumen visual

                  PL continua (cap. 2-3)
                          │
                          ▼  agregás x ∈ ℤ
                  Programación Entera
                          │
                          ├── Branch & Bound
                          │     │
                          │     ├── relajación LP
                          │     ├── ramificar en x_j fraccional
                          │     └── podar con bound
                          │
                          ├── Casos especiales:
                          │     ├── transporte (matriz unimodular → LP da entero)
                          │     ├── asignación (algoritmo húngaro)
                          │     ├── MST (Kruskal/Prim)
                          │     ├── camino más corto (Dijkstra)
                          │     └── ruta crítica (CPM)
                          │
                          └── Lógica con binarias:
                                ├── if-then (big-M)
                                ├── k de n
                                ├── implicaciones
                                └── disyunciones

4.11 Ejercicios

Una empresa debe decidir abrir 2 de 5 sucursales (binario). Cada una tiene costo de apertura $F_i$ y atiende demanda $d$ del área. Formulá el modelo.
Resolvé el problema de transporte del cap. 4.3 con NetworkX o PuLP. Verificá que la solución es entera.
Aplicá el algoritmo húngaro a un problema de asignación 4×4 con la matriz que vos elijas.
Construí el grafo de carreteras entre 6 ciudades de El Salvador (datos aproximados). Calculá Dijkstra entre dos extremos y MST.
Modelá una restricción "exactamente 2 de 5 alternativas". Implementala.
Para tu pénsum: modelá el orden de cursos como DAG, calculá la ruta crítica (camino más largo). ¿Cuántos ciclos mínimo necesitás?

4.12 Para profundizar

Wolsey, Integer Programming — el libro de referencia académico.
Williams, Model Building in Mathematical Programming — formulación creativa, muchos ejemplos.
NetworkX docs (networkx.org) — implementaciones listas para grafos.
OR-Tools (Google) — solvers + interfaces para Python, Java, C++. Gratuito y muy potente.
Siguiente capítulo: Teoría de decisiones.

4.13 Mini-proyecto integrador

🏗️ Avance del proyecto — Agregar restricciones discretas

Entregables (cap. 4):

Identificá 3 restricciones lógicas o decisiones binarias en tu caso original.
Reformulá el modelo con esas variables.
Resolvé con PuLP. Compará la solución entera con la solución continua del cap. 2.
Reportá la degradación del objetivo al imponer integralidad (si la hay).
Identificá un problema de redes auxiliar en tu caso (transporte, asignación, ruta) y resolvelo.

Definiciones nuevas: programación entera, programación binaria, MIP (Mixed Integer Program), Branch & Bound, relajación LP, bound, problema de transporte, balanceado, totalmente unimodular, problema de asignación, método húngaro, MST (Minimum Spanning Tree), Kruskal, Prim, camino más corto, CPM (Critical Path Method), holgura del proyecto, big-M.

← Anterior Dualidad y análisis de sensibilidad Siguiente → Teoría de decisiones

Reportar error en este capítulo · Patrocinar este libro

Programación entera y problemas de redes

Qué vas a aprender en este capítulo

4.1 Variables enteras y binarias

El gran problema: complejidad

4.2 Branch & Bound

4.3 Problema de Transporte

4.4 Problema de Asignación

4.5 Árbol generador mínimo (MST)

4.6 Camino más corto y ruta crítica

4.7 Restricciones lógicas con binarias

If-then ("si abro fábrica iii, máximo MMM unidades")

Al menos kkk de nnn opciones

Exactamente uno

Implicación (y1=1y_1 = 1y1​=1 ⇒ y2=1y_2 = 1y2​=1)

Disyunción ("restricción A o B")

4.8 Resolución práctica

PuLP — programación entera

NetworkX — redes

4.9 Errores comunes

4.10 Resumen visual

4.11 Ejercicios

4.12 Para profundizar

4.13 Mini-proyecto integrador

If-then ("si abro fábrica $i$ , máximo $M$ unidades")

Al menos $k$ de $n$ opciones

Implicación ( $y_1 = 1$ ⇒ $y_2 = 1$ )