PM5.tex

\documentclass[PM.tex]{subfiles}
\begin{document}

\chapter{Programación Lineal Entera}

\section{Poliedros enteros y matrices totalmente unimodulares}
Sean $A \in \R^{m \times n}$, $b\in\R^m$ y $c\in\R^n$, consideramos el problema:

\begin{align*}
(PE) & \min c'x\\
	 & A x = b\\
	 & x \in \mathbb{Z}_+^n
\end{align*}

Denotaremos por $z_{PE}$ al valor óptimo de este problema. (PE) tiene asociado otro problema que denominaremos el ``problema relajado lineal'' y denotamos por (LP) que consiste;

\begin{align*}
(LP) & \min c'x\\
	 & A x = b\\
	 & x \in \mathbb{R}_+^n
\end{align*}

\begin{obser}
Si $x$ es factible en $PE$ entonces también lo es en $LP$.
\[ \{x \in \mathbb{Z}_+^n : Ax=b \} \subset \{x \in \mathbb{R}_+^n : Ax=b \} \]

Esto implica que $z_{LP} ≤ z_{PE}$, donde $z_{LP} $ es el valor óptimo de $LP$.
\end{obser}
\begin{defi}
Un problema es de \textbf{programación binaria} ó $\{0,1\}$ si sus variables están restringidas a tomar valores en $\{0,1\}$.
\end{defi}
\newpage
\begin{defi}
Decimos que un problema es \textbf{entero-mixto} $(PME)$ si:

\begin{align*}
(PME) & \min c'x+d'y\\
	  & A_1 x + A_2 y = b\\
	  & x \in \Z_+^{n_1}, y \in \R_+^{n_2}\\
	  & A_1 \in \R^{m\times n_1}, A_2 \in \R^{m \times n_2}, b \in \R^m, c \in \R^{n_1}, d \in \R^{n_2}
\end{align*}
\end{defi}
\begin{example}
Veamos que no siempre coincide $z_{PE}$ con un redondeo de $z_{LP}$.

\begin{align*}
(PME) & \min 21x_1+11x_2\\
	  & 6x_1+4x_2 ≤ 13\\
	  & x_1,x_2 \in \Z_+\\
(LP) & x_1,x_2 \in \R_+
\end{align*}

La solución óptima de $LP$ es $(\frac{13}{7},0)$. El redondeo más cercano es $(2,0)$. El redondeo por abajo es $(1,0)$. Ninguno es la solución óptima, que es $(0,3)$, como se puede comprobar evaluando la función en cada uno de los puntos de coordenadas enteras señalados en la figura.

\begin{center}
\definecolor{qqqqff}{rgb}{0.,0.,1.}
\definecolor{zzttqq}{rgb}{0.6,0.2,0.}
\definecolor{uuuuuu}{rgb}{0.26666666666666666,0.26666666666666666,0.26666666666666666}
\definecolor{cqcqcq}{rgb}{0.7529411764705882,0.7529411764705882,0.7529411764705882}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
\draw [color=cqcqcq,, xstep=1.0cm,ystep=1.0cm] (-4.3,-1.3) grid (5.3,4.3);
\draw[color=black] (-4,0.) -- (5,0.);
\foreach \x in {-4,-3.,-2.,-1.,1.,2.,3.,4.,5.}
\draw[shift={(\x,0)},color=black] (0pt,2pt) -- (0pt,-2pt) node[below] {\footnotesize $\x$};
\draw[color=black] (0.,-1.) -- (0.,4.752470459668063);
\foreach \y in {-1.,1.,2.,3.,4.}
\draw[shift={(0,\y)},color=black] (2pt,0pt) -- (-2pt,0pt) node[left] {\footnotesize $\y$};
\draw[color=black] (0pt,-10pt) node[right] {\footnotesize $0$};
\clip(-3.969088632379392,-1.385270587163902) rectangle (8.703087676160555,4.752470459668063);
\fill[color=zzttqq,fill=zzttqq,fill opacity=0.10000000149011612] (0.,3.25) -- (0.,0.) -- (2.1666666666666665,0.) -- cycle;
\draw [domain=-3.969088632379392:8.703087676160555] plot(\x,{(--13.-6.*\x)/4.});
\draw [color=zzttqq] (0.,3.25)-- (0.,0.);
\draw [color=zzttqq] (0.,0.)-- (2.1666666666666665,0.);
\draw [color=zzttqq] (2.1666666666666665,0.)-- (0.,3.25);
\draw [dash pattern=on 3pt off 3pt,domain=-3.969088632379392:8.703087676160555] plot(\x,{(--46.-21.*\x)/11.});
\begin{scriptsize}
\draw [fill=uuuuuu] (0.,3.25) circle (1.5pt);
\draw [fill=uuuuuu] (0.,0.) circle (1.5pt);
\draw [fill=uuuuuu] (2.1666666666666665,0.) circle (1.5pt);
\draw [fill=qqqqff] (0.,3.) circle (2.5pt);
\draw [fill=qqqqff] (0.,2.) circle (2.5pt);
\draw [fill=qqqqff] (0.,1.) circle (2.5pt);
\draw [fill=qqqqff] (1.,0.) circle (2.5pt);
\draw [fill=qqqqff] (2.,0.) circle (2.5pt);
\draw [fill=qqqqff] (1.,1.) circle (2.5pt);
\end{scriptsize}
\end{tikzpicture}
\end{center}

\end{example}

\begin{obser}
Sea $X=\{x \in \R^n : Ax=b, x \in x \in \Z_+^n\}$. La solución óptima del $PME$ coincide con la solución del problema de optimización:
\[
\begin{aligned}
& \min
& & c'x \\
& \text{sujeto a}
& & x \in CO(X)\end{aligned}
\]
Sin embargo, calcular la envolvente convexa se puede volver muy costoso en dimensiones superiores.
\end{obser}
\newpage
\begin{example}[Problema de la mochila]
Un conjunto de productos numerados de $1$ a $n$. El producto $i$ ocupa un volumen $a_i$ y reporta una satisfacción $p_i$. Dada una mochila con capacidad $V$ determinar la carga que maximiza la satisfacción. Definimos las variables $x_i$ con $x_i = 1$ si decido incluir el producto $i$ y $x_i = 0$ en caso contrario. Podemos definir el problema binario:
\[
\begin{aligned}
& \max
& & \sum_{i=1}^n p_i x_i \\
& \text{sujeto a}
& & \sum_{i=1}^n a_i x_i ≤ V\\
& & & x_i \in \{0,1\}\ \forall i 
\end{aligned}
\]
\end{example}

\begin{example}[Problema de transporte]
Consideramos $m$ puntos de suministro y $n$ puntos de consumo. Cada punto de suministro $i$ dispone de una oferta $o_i$ con $i = 1,\dots,m$. Cada punto de consumo $j$ tiene una demanda $d_j$ con $j = 1,\dots,n$. Supongamos que $o_i,d_j \in \Z_+\ \forall i,j$ (los productos son indivisibles). Además, $\sum_{i=1}^m o_i = \sum_{j=1}^m d_j$. El coste unitario de enviar una unidad desde $i$ a $j$ es $c_{ij}$. El problema consiste en deterinar el plan de transporte que minimiza el coste total de distribución. Definimos $x_{ij}$ como la cantidad enviada desde $i$ a $j$, de manera que el problema consiste en:
\[
\begin{aligned}
& \min
& & \sum_{i=1}^m \sum_{j=1}^n c_{ij}x_{ij} \\
& \text{sujeto a}
& & \sum_{j=1}^n x_{ij} = o_i \ \forall i\\
& & & \sum_{i=1}^n x_{ij} = d_j \ \forall j\\
& & & x_{ij} \in \Z_+ \ \forall i,j
\end{aligned}
\]
\end{example}

\begin{nota}
En general, seguiremos el siguiente proceso para modelar un problema de optimización.
\begin{enumerate}
	\item Definir varibales.
	\item Utilizar las variables para definir el conjunto factible mediante restricciones lineales
	\item Utilizar las variables para la definir la función objetivo
\end{enumerate}
Si al final aparecen dificultades, definir más variables o restricciones.
\end{nota}

\begin{defi}
Un poliedro $P = \{x \in \R^n : Ax≤b \}$ se dice \textbf{entero} si todos sus puntos extremos tienen coordenadas enteras.
\end{defi}

\begin{theorem}
Sea $p$ un poliedro y $z_{LP}$ el valor óptimo de $\min \{c'x : x \in P\}$, $c \in \R^n$. Son equivalentes:
\begin{enumerate}
	\item $P$ es entero
	\item $\forall c \in \R^n$ tal que $z_{LP} > -\infty$, la solución óptima $x^* \in \Z^n$.
	\item $\forall c \in \R^n$ tal que $z_{LP} > -\infty$, $x^* \in \Z^n$.
	\item $\forall c \in \R^n$ tal que $z_{LP} > -\infty$, $c'x^*=z_{LP}\in \Z$.
\end{enumerate}
\end{theorem}

\begin{dem}
\begin{itemize}
\item[]
	\item[$(1 \to 2)$] Obvio por teorema fundamental de la programación lineal.
	\item[$(2 \to 3)$] Obvio
	\item[$(3 \to 4)$] Si $\forall c \in \Z^n \to x^* \in \Z^n$, entonces $z_{LP} = c'x^* \in \Z$.
	\item[$(4 \to 1)$] Supongamos que $P$ no es entero. Entonces existe una función objetivo $\tilde{c}\in \Z^n$ tal que su óptimo es el vértice $\tilde{x} \in P$ que tiene al menos una coordenada no entera. Supongamos que es $\tilde{x_i} \notin \Z$. Por $(4)$, $\tilde{c}'\tilde{x} \in \Z$. Consdero $\hat{c} = \tilde{c} + \frac{1}{q} e_i$, con $q >> 0$, de forma que $\tilde{x}$ es también óptimo para $\hat{c}$. Como $q \in \Z$, entonces $q\tilde{c}$ también optimiza en $\tilde{x}$. Igualmente $q\hat{c}$ optimiza en $\tilde{x}$. Por $(4)$, $q\hat{c}'\tilde{x} \in \Z$ y $q\tilde{c}\tilde{x} \in \Z$. Así pues,
	\[ \Z \ni q\tilde{c}'\tilde{x} - q\hat{c}\tilde{x} = q\tilde{c}\tilde{x}-q\tilde{c}\tilde{x}-\tilde{x_i} = -\tilde{x_i} \notin \Z \]
	Por lo que llegamos a un absurdo.
\end{itemize}
\end{dem}

\begin{defi}
Un sistema de desigualdades $Ax ≤ b$ $x \in \R^n$ es Totalmente Dual Entero (TDE) si para cualquier $c \in \Z$ tal que $z_{LP} = \min \{ c'x : Ax≤b\} > -\infty$ entonces el problema dual asociado $\max \{u'b : u'A = c', u ≥ 0\}$ tiene solución óptima $u^* \in \Z^m$.
\end{defi}

\begin{theorem}
Si $P$ es un poliedro entero entonces existe $A$ y $b$ tal que $P = \{ x \in \R^n : Ax ≤ b \}$ y $Ax≤ b$ es TDE. (Demostración no incluida)
\end{theorem}

\begin{example}
Dado un grafo, determinar el menor número de aristas necesarias para que todos los vértices tengan alguna arista incidente en él. Supongamos que el grafo es $K_4$ y los vértices están etiquetados con $1,2,3,4$. Sea $x_{ij} = 1$ si la arista $(i,j)$ está en la solución y $x_{ij}=0$ en caso contrario. El problema consiste en: 

\[
\begin{aligned}
& \min
& & \sum_{i=1}^4 \sum_{j>i} x_{ij} \\
& \text{sujeto a}
& & x_{12}+x_{13}+x_{14} ≥ 1\\
& & & x_{12} + x_{23} + x_{24} ≥ 1\\
& & & x_{13} + x_{23} + x_{34} ≥ 1\\
& & & x_{14} + x_{24} + x_{34} ≥ 1\\
& & & x_{ij} \in \{0,1\}\ \forall i,j
\end{aligned}
\]

Todos los vértices de este poliedro son enteros. Su dual es:
\[
\begin{aligned}
& \max
& & y_1+y_2+y_3+y_4 \\
& \text{sujeto a}
& & y_1+y_2 ≤ 1\\
& & & y_1+y_3 ≤ 1\\
& & & y_1 + y_4 ≤ 1\\
& & & y_2 + y_3 ≤ 1\\
& & & y_2 + y_3 ≤ 1\\
& & & y_2 + y_4 ≤ 1\\
& & & y_3 + y_4 ≤ 1
\end{aligned}
\]

Si el sistema original fuese $TDE$ los vértices del dual serían enteros pero podemos comprobar que la solución óptima es $y_1=y_2=y_3=y_4 = 1/2$, no entera.
\end{example}
\begin{defi}
A es una matriz Totalmente Unimodular si y solo si $\forall B\subset A$, B cuadrada, entonces $det(B)\in\{-1,0,1\}$. 
\end{defi}
\begin{nota}
Si A es TU entonces $a_{ij}\in\{0,\pm1\}$.
\end{nota}
\begin{theorem}
Son equivalentes:
\begin{enumerate}
\item $A$ es TU
\item $A'$ es TU
\item $[A\;I]$ es TU
\item La matriz resultante de eliminar una fila o columna de A que corresponda a la matriz identidad es TU.
\item La matriz resultante de multiplicar una fila o columna de A por $-1$ es TU.
\item La matriz resultante de intercambiar filas o columnas de A es TU.
\item La matriz resultante de duplicar filas o columnas de A es TU.
\item La matriz resultante de realizar un pivotaje sobre elementos de A es TU.
\end{enumerate}
\end{theorem}
\begin{dem}
Veamos que son equivalentes:
\begin{itemize}
\item [$1 \leftrightarrow 2$] Es clara la implicación (y el recíproco) usando que trasponer mantiene el valor del determinante.
\item [$1 \leftrightarrow 3$] Es clara la implicación (y el recíproco) discutiendo los casos de submatrices posibles.
\item [$1 \leftrightarrow 4$] Es clara la implicación (y el recíproco), pues a lo sumo cambia el signo del determinante.
\item [$1 \leftrightarrow 5$] Es clara la implicación (y el recíproco), si esa fila no aparece en B no cambia el determinante y, si aparecen, entonces el determinante cambia de signo.
\item [$1 \leftrightarrow 6$] Es clara la implicación (y el recíproco), pues esta operación cambia el signo de los determinantes.
\item [$1 \leftrightarrow 7$] Es clara la implicación (y el recíproco), pues tenemos una nueva fila o columna linealmente dependiente.
\item [$1 \leftrightarrow 8$] Supongamos que pivotamos sobre $a_{ij}\neq 0$ (en el método del simplex no se puede pivotar sobre un elemento nulo). Sea $\overline{A}$ la matriz tras el pivotaje. Entonces:
\[
\overline{a}_{i\cdot}=
\begin{cases}
a_{i\cdot} & a_{ij}=1\\
-a_{i\cdot} & a_{ij}=-1
\end{cases}
\qquad
\overline{a}_{k\cdot}=
\begin{cases}
{a}_{k\cdot}+\overline{a}_{i\cdot} & a_{kj}=-1\\
{a}_{k\cdot}-\overline{a}_{i\cdot} & a_{kj}=1\\
{a}_{k\cdot} & a_{kj}=0
\end{cases}
\]
Sea $B\subset A$ distinguimos los siguientes casos:
\begin{itemize}
\item La fila $i$ forma parte de $B$. En tal caso $|det(B)|=|det(\overline{B})|$.
\item La columna $j$ forma parte de $B$ pero la fila $i$ no. En este caso $det(\overline{B})=0$.
\item B no contine partes de la fila $i$ ni partes de la fila $j$. Entonces consideramos:
\[
C=
\begin{pmatrix}
a_{ij} & \cdots\\
\vdots & B
\end{pmatrix} \Rightarrow \overline{C} = 
\begin{pmatrix}
1 & \cdots\\
0 & \overline{B}
\end{pmatrix} \Rightarrow |det(C)| = |det(\overline{B})|
\]
\end{itemize}
\end{itemize}
\end{dem}
\begin{theorem}
Sea A TU y $P(b)=\{x \in \R^n_+ \mid Ax\leq b\} \neq \emptyset$, $b\in \Z^n$. Entonces $P(b)$ es entero.
\end{theorem}
\begin{dem}Consideramos:
\[
Ax +Ix_h = b, \; \begin{bmatrix} A & I \end{bmatrix} \begin{bmatrix}
x\\
x_h
\end{bmatrix} = b
\]
Sabemos que $[A I]$ es TU. Todo punto extremo corresponde a una submatriz cuadrada de $[A | I]$, B $m\times m$, $det(B)\neq 0$, $x_B=B^{-1}b\geq 0$. En partiular, $B x_B = b$. Como A es TU, $\det(B)\in\{\pm1\}$ por lo que $det(B^{-1})\in\{\mp1\}$. Aplicamos Cramer:
\[
x_{B_i}=\frac{det(\text{B con la i-ésima columna reemplazada por b})}{det(B)}=\frac{\text{Suma de productos de números entero}}{\pm1}
\]\QED
\end{dem}
\begin{coro} Sea $P(b)=\{x \in \R^n_+ \mid \overline{b}\leq Ax\leq b,\; \overline{d}\leq x \leq d\} \neq \emptyset$ con $b,d,\overline{b},\overline{d}\in\Z^n$. Entonces $P(b)$ es entero.
\end{coro}
\begin{dem}
Las desigualdades que definen $P(B)$ se pueden expresar como:
\[
\begin{matrix}
Ax \leq b\\
-Ax\leq -\overline{b}\\
x\leq d\\
-x\leq -\overline{d}
\end{matrix}\quad
\equiv\quad
\begin{bmatrix}
A\\
-A\\
I\\
-I
\end{bmatrix}
x\leq
\begin{bmatrix}
b\\
-\overline{b}\\
d\\
-\overline{d}
\end{bmatrix} = \delta \in \Z^{4n}
\]
La matriz columna sabemos que es TU por construcción (y el Teorema de las matrices TU) y que $\delta$ tiene coordenadas enteras, luego aplicamos el Teorema anterior.\QED
\end{dem}
\begin{coro}
Si A es TU entonces $Q(c) = \{u\in\R^m_+ \mid u'A\leq c'\}\neq\emptyset$ con $c\in\Z^n$ entonces $Q(c)$ es entero.
\end{coro}
\begin{dem}
$u'A \leq c' \Leftrightarrow A'u \leq c$. \QED
\end{dem}
\begin{theorem}
Si $P(b)=\{x\in\R^n_+ \mid Ax\leq b\}$ es entero $\forall b\in\Z^n$ con $P(b)\neq\emptyset$ y $A$ con coordenadas enteras entonces A es TU.
\end{theorem}
\begin{dem}
Sea $A_1$ submatriz cuadrada de A de tamaño $k\times k$ ($ k \leq m$) y $det(A_1)\neq 0$. Construimos la siguiente matriz:
\[
\overline{A}_1 = 
\begin{bmatrix}
A_1 & 0\\
A_2 & I_{m-k}
\end{bmatrix}
\]
De forma que $\overline{A}_1$ sea una matriz $m\times m$ con $A_2$ la ampliación de las columnas. Se tiene además que $det(\overline{A}_1)\neq 0$. Sea un $i$ $(1\leq i \leq k)$ arbitrario pero fijo y sea $b\in \Z^m$ de la siguiente forma: $b=\overline{A}_1 z + e_i$, $z\in\Z^m_+$. Entonces $\overline{A}_1^{-1}b=z+\overline{A}_1^{-1}e_i$. Es más, podemos tomar $z$ lo suficientemente grande para que $\overline{A}_1^{-1} b\geq 0$. Como $P(b)$ es entero, entonces $\overline{A}_1^{-1}b \in \Z^m$ (pues es punto extremo). Entonces $ \overline{A}_1^{-1}e_i=\overline{A}_1^{-1}b-z\in\Z^m$. Por tanto, la columna i-ésima de la matriz $\overline{A}_1^{-1}$ es de elementos enteros e, inductivamente, $\overline{A}_1^{-1}$. Además $\overline{A}_1$ también lo es por construcción e hipótesis. Finalmente, $1 = det(\overline{A}_1)det(\overline{A}_1^{-1})$, como ambos elementos son enteros, ambos son $\pm 1$. \QED
\end{dem}
\begin{theorem}
$A\in\Z^{m\times n}$ es TU si y solo si $\forall J\subset\{1,\dotsc,n\}$ existe una partición de $J$ en $J_1$ y $J_2$ tal que 
\[
\left| \sum_{j\in J_1}a_{ij}-\sum_{j\in J_2}a_{ij} \right| \leq 1 \quad \forall i=1,\dotsc,m
\]
\end{theorem}
\begin{prop}\label{propo}
Sea A una matriz de elementos $\{0,\pm1\}$ en la que a lo sumo hay dos elementos no nulos por cada columna. Si existe una partición de las filas de A en $F_1,F_2$ tal que en cada columna con 2 elementos no nulos se cumple:
\begin{itemize}
\item Si los dos tienen igual signo están en conjuntos diferentes.
\item Si tienen distinto signo están en el mismo conjunto de la partición.
\end{itemize}
Entonces A es TU.
\end{prop}
\begin{dem}
Aplicamos el Teorema por Filas. Fijamos una columna j, entonces es claro que:
\[
\left| \sum_{i\in F_1}a_{ij}-\sum_{i\in F_2}a_{ij} \right| =
\begin{cases}
1 & \text{j tiene un único elemento no nulo}\\
0 & \text{j tiene dos no nulos de igual signo}\\
0 & \text{j tiene dos no nulos de distinto signo}
\end{cases}
\]
\end{dem}
\begin{prop}
Si A es de componentes $\{0,\pm1\}$ tal que por columnas verifica que tiene a lo sumo dos componentes no nulas y $\sum_{i=1}^m a_{ij}=0$, entonces $A$ es TU.
\end{prop}
\begin{dem}
Es un corolario inmediato de la proposición anterior pues puede aplicarse la descomposición del enunciado anterior.
\end{dem}
\begin{example}
El problema del transporte:
\begin{align*}
 \min\ & \sum_{i=1}^m\sum_{j=1}^n c_{ij}x_{ij} &\\
sa:& \sum_{j=1}^n x_{ij}= O_i \quad\forall i =1,\dots, m & \\
& \sum_{i=1}^m x_{ij}= D_j \quad \forall j =1,\dots,n &   \\
& x_{ij}\in\{0,1\} &
\end{align*}
Entonces $\overline{A}$ es:
\[\left(
\begin{array}{cccccccccccccccc}
1 & 1 & \cdots & 1 & 1 & 0 & 0 &\cdots  		& 0 & 0 & \cdots & 0 & 0 &  \cdots 	& 0 	& 0\\
0 &	0 & \cdots & 0 & 0 & 1 & 1 & \cdots 		& 1 & 1 & \cdots & 0 & 0 & \cdots 	& 0 	& 0\\
\vdots & &\vdots & \vdots &\vdots & & &\vdots 	&   &   &\vdots & & \ 				&   	& \vdots\\
0 & 0 & \cdots & 0 & 0 & 0 & 0 & \cdots			& 0 & 0 & \cdots & 1 & 1 & \cdots 	& 1 	& 1\\
1 & 0 & \cdots & 0 & 0 & 1 & 0& \cdots 			& 0 & 0 & \cdots  & 1 & 0 & \cdots 	& 0 	& 0 \\
0 & 1 & \cdots & 0 & 0 & 0 & 1& \cdots 			& 0 & 0 & \cdots  & 0 & 1 & \cdots 	& 0 	& 0 \\
\vdots & &\vdots & \vdots &\vdots 				&   &    & &\vdots & &\vdots &   &  &    	& \vdots\\
0 & 0 & \cdots & 1 & 0 & 0 & 0& \cdots 			& 1 & 0 & \cdots  & 0 & 0 & \cdots 	& 1 	& 0\\
0 & 0 & \cdots & 0 & 1 & 0 & 0& \cdots 			& 0 & 1 & \cdots  & 0 & 0 & \cdots 	& 0 	& 1
\end{array}\right)
\]
\end{example}

\begin{prop}
$A\in\{0,1\}^{m\times n}$ tal que todos los valores no nulos de cada fila (o columna) son consecutivos entonces $A$ es T.U. 
\end{prop}
\begin{dem}
Se puede hacer una partición de las columnas de $A$, $J_1=\{$columnas pares$\}$, $J_2=\{$columnas impares$\}$. Para cada $i=1,\dots,m$ $|\sum_{j\in J_1}a_{ij}-\sum_{j\in J_2}a_{ij}|\leq 1$. Por la proposición \ref{propo} se tiene el resultado. 
\end{dem}

\section{Esquemas de ramificación y acotación}

En esta sección se muestra un algoritmo para hallar la solución óptima de un problema de programación entera
\begin{align*}
(PE)\quad z_{PE} = & \max\ c'x\\
               & sa:\ Ax=b\\
     		&x\in\Z_+^n.
\end{align*}
El algoritmo se basa en la proposición siguiente. 
\begin{prop}
Consideremos el problema $z=\max\{c'x:x\in X\}$, con $c\in\R^n$ y $X\subset\R^n$. Sea $X=X_1\cup X_2\cup\dots\cup X_K$ una descomposición de $X$ en conjuntos más pequeños y sea $z^k=\max\{c'x:x\in X_k\}$ para $k=1,\dots,K$. Entonces $z=\underset{k=1,\dots,K}{\max} z^k$.
\end{prop}

\begin{center}
{\bf Algoritmo de ramificación y acotación (Branch and Bound-B\&B)}
\end{center}

\begin{tabbing}


Paso 1: \= Obtener el valor óptimo $z_{LP}^*$ y la solución óptima $x_{LP}^*$ del problema relajado\\ \> lineal (LP) asociado al problema de programación entera. Establecer $(P_0)=(LP)$,\\ \> la solución $x^*=x^*_{LP}$ y el valor $z^*=z^*_{LP}$ como elementos del nodo raíz $n_0$.\\ \> Tomar $z_{LB}=-\infty$ (en el árbol completo) y $z_{UB}=\lfloor z^*\rfloor$ (en el árbol completo).\\

Paso 2: \= 2.1) Si $x^*\in\Z_+^n$: STOP. La solución óptima del problema de programación entera es $x^*$. \\ \>
2.2) Si $x^*\not\in\Z_*^n$: Entonces existe al menos una componente $x^*_i$ de $x^*$ tal que\\ \> $x^*_i\notin\Z_+$. Establecer dos ramas que conecten el nodo $n_0$, por un lado, con\\ \> el nodo $n_1$ constituido por el problema $(P_1)$ resultante de añadir al problema\\ \> $(P_0)$ la restricción $x_i\leq\lfloor x^*_i\rfloor$, la solución óptima $(x^1)^*$ de $(P_1)$ y el valor\\ \> óptimo $z^*_1$ de $(P_1)$, y por otro lado, con el nodo $n_2$ constituido por el problema\\ \> $(P_2)$ resultante de añadir al problema $(P)$ la restricción $x_i\geq\lceil x^*_i\rceil$, la\\ \> solución óptima $(x^2)^*$ de $(P_2)$ y el valor óptimo $z^*_2$ de $(P_2)$. \\ \>
- Si $(P_i)$, $i=1$ ó $2$, es infactible podamos la rama que conecta $n_0$ con $n_i$.\\ \>
- Si $z^*_i<z_{LB}$, $i=1$ ó $2$, podamos la rama que conecta $n_0$ con $n_i$.\\ \>
- Si $(x^i)^*\notin \Z^n_+$, $i=1$ ó $2$, tomar $z_{UB}=\lfloor z^*_i\rfloor$ (en el subárbol que se va a generar)\\ \> y repetir el Paso 2.2 tomando $n_i$ como $n_0$. \\ \>
- Si $(x^i)^*\in \Z^n_+$, $i=1$ ó $2$, establecemos $n_i$ como nodo hoja. Si $z_i^*=z_{UB}$ entonces\\ \> $(x^i)^*$ es la solución óptima del problema de programación entera.\\ \> En caso contrario y si $z^*_i>z_{LB}$ (en el árbol completo) establecer $z_{LB}=z_i^*$.\\

\end{tabbing}


\subsection{Corte fraccional de Gomory}
Este método es aplicable solo si todas las variables de decisión son enteras, además
todos los coeficientes que aparezcan en el problema deben ser enteros, es decir, solo es
aplicable a problemas del tipo:
\begin{center}
\begin{tabular}{c c l l}
$(P)$& $\min$ & $c'x$ &$c\in\Z^n$\\
   & sa:  & $Ax=b$ & $A\in\Z^{m\times n}$\\
   &      & $x\in\Z^n_+$ &$b\in\Z^m$
\end{tabular}
\end{center}
Supongamos que resolvemos el relajado lineal de $(P)$ y obtenemos una solución
óptima $x^*$ con alguna componente fraccional ($\exists k : x^*_k\in\Q\setminus\Z$). Sea $B$ la base asociada a
la solución óptima $x^*$, $x^*_B = B^{-1}b = \bar{b} \geq 0, x^*_N = 0$. Dado que:
\[
Ax=b\equiv [B\ N]\begin{bmatrix}
x_B\\
x_N
\end{bmatrix}=b\equiv Bx_B+Nx_N=b
\]
cualquier solución factible $x$ del problema $(P)$ se puede representar de la forma:
\[
x_B = B^{-1}b-\underbrace{B^{-1}N}_{Y}\underbrace{x_N}_{w}=\bar{b}-Yw.
\]
Entonces
\[
x_k=\bar{b}_k-\sum_{j\in N}y_{kj}w_j.
\]
Además, podemos hacer la descomposición 
\begin{align*}
&\bar{b}_k=\lfloor\bar{b}_k\rfloor +f_k,\ 1>f_k>0\\
& y_{kj}=\lfloor y_{kj}\rfloor+f_{kj},\ 1>f_{kj}\geq 0
\end{align*}
con lo que se tendría
\[
x_k=\lfloor\bar{b}_k\rfloor +f_k-\sum_{j\in N}(\lfloor y_{kj}\rfloor+f_{kj})w_j=\lfloor\bar{b}_k\rfloor-\sum_{j\in N}\lfloor y_{kj}\rfloor w_j+(f_k-\sum_{j\in N}f_{kj}w_j),
\]
lo que implica que $$f_k-\sum_{j\in N}f_{kj}w_j\in\Z,$$ pues buscamos que $x_k\in\Z$ y sea factible, y se tiene $\lfloor\bar{b}_k\rfloor-\sum_{j\in N}\lfloor y_{kj}\rfloor w_j\in\Z$. Como $\sum_{j\in N}f_{kj}w_j\geq 0$, $f_k-\sum_{j\in N}f_{kj}w_j\leq f_k<1$, por lo tanto:
\[
f_k-\sum_{j\in N}f_{kj}w_j\leq 0.
\]
Finalmente, si añadimos una variable de holgura $s_k\in\Z_+$, podemos escribir la restricción:
\[
s_k-\sum_{j\in N}f_{kj}w_j=-f_k.
\]
Al evaluar $x^*$ sobre esta restricción tenemos que $w=x^*_N=0$, lo que implica $s_k=-f_k$, lo cual es una contradcción pues $s_k\in\Z_+$ y $f_k\in(0,1)$, luego $x^*$ no verifica la restricción. 

El método consiste en reforzar el problema entero añadiendo restricciones como la
anterior hasta que se obtiene una solución óptima en variables entera. Esto se consigue
en un número finito de pasos.

\subsection{Corte mixto de Gomory}

Consideremos el problema:
\[
\begin{aligned}
& \min
& & c_1'x_1+c_2'x_2 \\
& \text{sujeto a}
& & A \begin{pmatrix}x_1\\x_2\end{pmatrix} = b\\
& & & x_1 \in \Z_+^{n_1},\ x_2 \in \R_+^{n_2}
\end{aligned}
\]
A las $x_i$ las llamaremos variables del grupo $i$, con $i=1,2$. Supongamos que $x^*$ es una solución óptima del relajado lineal de $(P)$. Si existe $x_k^* \in$ Grupo 1 tal que $x_k^* \in \mathbb{Q} \setminus \Z$ entonces $x^*$ no es solución de $(P)$.  Sea $B$ la base asocada a $x^*$. Entonces toda solución factible se puede expresar en términos de esta base:
\[ x_B = B^{-1}b - B^{-1} N x_N \quad (Bx_B + Nx_n = b) \]
Denotamos $x_N = w$, $\overline{b} = B^{-1}b$, $Y = B^{-1}N$ de manera que $x_B = \overline{b} - Y w$. Así pues, en cualquier solución factible de $(P)$, la componente $k$ es\ de la forma:
\[ x_k = \overline{b}_k - \sum_{j \in N} y_{kj}w_j = \lfloor \overline{b}_k \rfloor + f_k - \sum_{j \in N} y_{kj}w_j \]
Donde $f_k = \overline{b}_k-\lfloor \overline{b}_k \rfloor$. De ahí, que:
\[ x_k - \lfloor \overline{b}_k \rfloor = f_k - \sum_{j \in N} y_{kj}w_j \]
Como el miembro izquierdo de la ecuación es entera, el miembro derecho debe ser entero. Por lo tanto, se debe verificar una y solo una de las desigualdades siguientes:
\begin{enumerate}
	\item $f_k - \sum\limits_{j \in N} y_{kj} w_j ≤ 0 \Rightarrow - \sum\limits_{j \in N} y_{kj} w_j ≤ -f_k \Rightarrow - \sum\limits_{j \in N_1} y_{kj} w_j ≤ -f_k$
	\item $f_k - \sum\limits_{j \in N} y_{kj} w_j ≥ 1 \Rightarrow - \sum\limits_{j \in N} y_{kj} w_j ≥ 1-f_k \Rightarrow - \sum\limits_{j \in N_2} y_{kj} w_j ≥ 1-f_k$
\end{enumerate}
donde $N_1 = \{j \in N : y_{kj} > 0\}$ y $N_2 = \{j \in N : y_{kj} ≤ 0\}$. Por lo tanto:
\[ \frac{-f_k}{f_k-1} \sum_{j \in N_2} y_{kj} w_j ≤ -f_k \]
Luego, como sólo se puede dar uno de los casos:
\[ -\sum_{j \in N_1} y_{kj} w_j - \frac{f_k}{f_k -1} \sum_{j \in N_2} y_{kj} w_j ≤ -f_k \]
Introduciendo la variable de holgura $s_k ≥ 0$, lo transformamos en la ecuación:
\[ s_k-\sum_{j \in N_1} y_{kj} w_j - \frac{f_k}{f_k -1} \sum_{j \in N_2} y_{kj} w_j ≤ -f_k \]
Si evaluamos $x^*$ sobre la desigualdad, podemos observar que: $w^* = x_N^* = 0$. Luego $0 ≥ s_k = -f_k < 0$. Hemos llegado a una contradicción. Por tanto $x^*$ no cumple la nueva restricción, es decir es un plano de corte para la misma. El corte mixto de Gomory "más profundo"
\[ s_k - \sum_{j \in N} λ_j w_j - f_k \text{ con}\]
\[ λ_j = \begin{cases}
	y_{kj}, &\text{ si }y_{kj} ≥ 0, w_j \notin \text{Grupo 1}\\
	\frac{f_k}{f_k-1}y_{kj}, &\text{ si }y_{kj} < 0, w_j \notin \text{Grupo 1}\\
	f_{kj}, &\text{ si } f_{kj} ≤ f_k, w_j \in \text{Grupo 1}\\
	\frac{1-f_{kj}}{1-f_k} ,&\text{ si } f_{kj} > f_k, w_j \in \text{Grupo 1}
\end{cases}\]
donde $f_{kj}$ es la parte fraccional de $y_{kj}$.
\begin{example}

\[
\begin{aligned}
& \min
& & 5x_2 + 10x_4 \\
& \text{sujeto a}
& & x_1-\frac{5}{3}x_2 - \frac{1}{5}x_4 = \frac{5}{3}\\
& & & -\frac{4}{3}x_2 + x_3 + \frac{11}{3} x_4 0 \frac{7}{3}\\
& & & x_1, x_2 ≥ 0,\ x_3,x_4 \in \Z_+
\end{aligned}
\]


\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
	$x_B$ & $c_B$ & $x_1$ & $x_2$ & $x_3$ & $x_4$ & $\overline{b}$\\
\hline
	$x_1$ & $0$ & $1$ & $-\frac{5}{3}$ & $0$ & $-\frac{1}{3}$ & $\frac{5}{3}$\\
	$x_3$ & $0$ & $0$ & $-\frac{4}{3}$ & $1$ & $\frac{11}{3}$ & $\frac{7}{3}$\\
\hline
	$c_j-z_j$ & & $0$ & $5$ & $0$ & $10$ & \\
\hline
\end{tabular}



La solución del relajado lineal es: $x_1 = \frac{7}{3}$, $x_3 = \frac{5}{3}$. Cortamos sobre $x_3$:
\[ \overline{b}_3 = \frac{7}{3} = 2 + \frac{1}{3} \]
\[ y_{32} = - \frac{4}{3} = -2 + \frac{2}{3} \]
\[ y_{34} = \frac{11}{3} = 3 + \frac{2}{3} \]
\[ s_5 - λ_2 x_2 - λ_4 x_4 = -\frac{1}{3} \]
Como $x_2 \notin$ Grupo 1 e $y_{32} < 0$, entonces $λ_2 = \frac{\frac{1}{3}}{\frac{1}{3}-1}\cdot\frac{-4}{3} = \frac{2}{3}$. Como $x_4 \in$ Grupo 1 y $\frac{2}{3} > \frac{1}{3}$, entonces $λ_4 = -\frac{1-\frac{2}{3}}{1-\frac{1}{3}} = \frac{1}{6}$

\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
	$x_B$ & $c_B$ & $x_1$ & $x_2$ & $x_3$ & $x_4$ & $s_5$ & $\overline{b}$\\
\hline
	$x_4$ & $0$ & $1$ & $-\frac{5}{3}$ & $0$ & $-\frac{1}{3}$ & $0$ & $\frac{5}{3}$\\
	$x_3$ & $0$ & $0$ & $-\frac{4}{3}$ & $1$ & $\frac{11}{3}$ & $0$ & $\frac{7}{3}$\\
	$s_5$ & $0$ & $0$ & $-\frac{2}{3}$ & $0$ & $-\frac{1}{6}$ & $1$ & $-\frac{1}{3}$\\
\hline
	$c_j-z_j$ & & $0$ & $5$ & $0$ & $10$ & $0$ & \\
\hline
\end{tabular}

Pivotando dualmente:

\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
	$x_B$ & $c_B$ & $x_1$ & $x_2$ & $x_3$ & $x_4$ & $s_5$ & $\overline{b}$\\
\hline
	$x_1$ & $0$ & $1$ & $0$ & $0$ & $\frac{1}{12}$ & $0$ & $\frac{10}{3}$\\
	$x_3$ & $0$ & $0$ & $0$ & $1$ & $\frac{11}{3}$ & $0$ & $3$\\
	$x_2$ & $5$ & $0$ & $1$ & $0$ & $\frac{1}{4}$ & $-\frac{3}{2}$ & $\frac{1}{2}$\\
\hline
	$c_j-z_j$ & & $0$ & $0$ & $\frac{3}{4}$ & $\frac{15}{2}$ & $0$ & \\
\hline
\end{tabular}
\end{example}
\end{document}