Generación de columnas

La generación de columnas o la generación de columnas retardada es un algoritmo eficiente para resolver grandes programas lineales . ^{[ 1 ]}

La idea principal es que muchos programas lineales son demasiado extensos para considerar explícitamente todas las variables. Por lo tanto, se propone comenzar resolviendo el programa considerando solo un subconjunto de sus variables. Luego, de forma iterativa, se añaden al programa variables que tienen el potencial de mejorar la función objetivo . Una vez que se demuestra que añadir nuevas variables ya no mejora el valor de la función objetivo, el procedimiento se detiene. Al aplicar un algoritmo de generación de columnas, se espera que solo se genere una fracción muy pequeña de las variables. Esta expectativa se ve respaldada por el hecho de que, en la solución óptima , la mayoría de las variables no serán básicas y tomarán un valor de cero, por lo que la solución óptima puede encontrarse sin ellas.

En muchos casos, este método permite resolver grandes programas lineales que de otro modo serían intratables. El ejemplo clásico de un problema donde se utiliza con éxito es el problema de corte de material . Una técnica particular en programación lineal que utiliza este tipo de enfoque es el algoritmo de descomposición de Dantzig-Wolfe . Además, la generación de columnas se ha aplicado a muchos problemas, como la programación de cuadrillas , el enrutamiento de vehículos y el problema de la p-mediana con capacidad limitada .

El algoritmo considera dos problemas: el problema principal y el subproblema. El problema principal es el problema original con solo un subconjunto de variables. El subproblema es un nuevo problema creado para identificar una variable que mejore la función objetivo del problema principal.

El algoritmo procede entonces de la siguiente manera:

1. Inicializar el problema maestro y el subproblema.
2. Resuelve el problema maestro
3. Búsqueda de una variable que mejore el subproblema.
4. Si se encuentra una variable que mejora: agréguela al problema principal y luego vaya al paso 2.
5. De lo contrario: La solución del problema principal es óptima. Detenerse.

La parte más difícil de este procedimiento es encontrar una variable que mejore la función objetivo del problema principal. Esto se puede lograr identificando la variable con el costo reducido más negativo (suponiendo, sin pérdida de generalidad , que el problema es de minimización). Si ninguna variable tiene un costo reducido negativo, entonces la solución actual del problema principal es óptima.

Cuando el número de variables es muy grande, no es posible encontrar una variable que mejore el rendimiento calculando todos los costos reducidos y eligiendo una variable con un costo reducido negativo. Por lo tanto, la idea es calcular solo la variable con el costo reducido mínimo. Esto se puede hacer utilizando un problema de optimización llamado subproblema de precios, que depende en gran medida de la estructura del problema original. La función objetivo del subproblema es el costo reducido de la variable buscada con respecto a las variables duales actuales, y las restricciones requieren que la variable cumpla con las restricciones que surgen naturalmente. El método de generación de columnas es particularmente eficiente cuando esta estructura permite resolver el subproblema con un algoritmo eficiente, típicamente un algoritmo combinatorio específico .

A continuación, detallamos cómo y por qué calcular el costo reducido de las variables. Consideremos el siguiente programa lineal en forma estándar:

${\displaystyle {\begin{aligned}&\min _{x}c^{T}x\\&{\text{sujeto a}}\\&Ax=b\\&x\in \mathbb {R} ^{+}\end{aligned}}}$

que denominaremos problema primal, así como su programa lineal dual :

${\displaystyle {\begin{aligned}&\max _{u}u^{T}b\\&{\text{sujeto a}}\\&u^{T}A\leq c\\&u\in \mathbb {R} \end{aligned}}}$

Además, dejemos${\displaystyle x^{*}}$y${\displaystyle u^{*}}$sean soluciones óptimas para estos dos problemas que pueden ser proporcionadas por cualquier solucionador lineal. Estas soluciones verifican las restricciones de su programa lineal y, por dualidad , tienen el mismo valor de función objetivo (${\displaystyle c^{T}x^{*}=u^{*T}b}$) que llamaremos${\displaystyle z^{*}}$Este valor óptimo es función de los diferentes coeficientes del problema primal:${\displaystyle z^{*}=z^{*}(c,A,b)}$Nótese que existe una variable dual.${\displaystyle u_{i}^{*}}$para cada restricción del modelo lineal primal. Es posible demostrar que una variable dual óptima${\displaystyle u_{i}^{*}}$puede interpretarse como la derivada parcial del valor óptimo${\displaystyle z^{*}}$de la función objetivo con respecto al coeficiente${\displaystyle b_{i}}$del lado derecho de las restricciones:${\displaystyle u_{i}^{*}={\frac {\partial z^{*}}{\partial b_{i}}}}$o de otro modo${\displaystyle u^{*}={\frac {\partial z^{*}}{\partial b}}}$Dicho de forma más sencilla,${\displaystyle u_{i}^{*}}$indica en cuánto aumenta localmente el valor óptimo de la función objetivo cuando el coeficiente${\displaystyle b_{i}}$aumenta en una unidad.

Consideremos ahora que una variable${\displaystyle y}$No se había considerado hasta entonces en el problema primal. Nótese que esto es equivalente a decir que la variable${\displaystyle y}$estaba presente en el modelo pero tomó un valor cero. Ahora observaremos el impacto en el problema primal de cambiar el valor de${\displaystyle y}$de${\displaystyle 0}$a${\displaystyle {\hat {y}}}$. Si${\displaystyle c_{y}}$y${\displaystyle A_{y}}$son respectivamente los coeficientes asociados con la variable${\displaystyle y}$En la función objetivo y en las restricciones, el programa lineal se modifica de la siguiente manera:

${\displaystyle {\begin{aligned}&\min _{x}c^{T}x+c_{y}{\hat {y}}\\&{\text{sujeto a}}\\&Ax=b-A_{y}{\hat {y}}\\&x\in \mathbb {R} ^{+}\end{aligned}}}$

Para saber si es interesante añadir la variable${\displaystyle y}$al problema ( es decir , dejar que tome un valor distinto de cero), queremos saber si el valor${\displaystyle z_{\sombrero {y}}^{*}}$de la función objetivo de este nuevo problema disminuye a medida que el valor${\displaystyle {\hat {y}}}$de la variable${\displaystyle y}$aumenta. En otras palabras, queremos saber${\displaystyle {\frac {\partial z_{\hat {y}}^{*}}{\partial {\hat {y}}}}}$Para ello, tenga en cuenta que${\displaystyle z_{\sombrero {y}}^{*}}$puede expresarse según el valor de la función objetivo del problema primal inicial:${\displaystyle z_{\hat {y}}^{*}=c_{y}{\hat {y}}+z^{*}(c,A,b-A_{y}{\hat {y}})}$. Entonces podemos calcular la derivada que nos interesa:

${\displaystyle {\begin{aligned}{\frac {\partial z_{\hat {y}}^{*}}{\partial {\hat {y}}}}&~=~&&c_{y}+{\frac {\partial z^{*}}{\partial {\hat {y}}}}\\&~=~&&c_{y}+{\frac {\partial z^{*}}{\partial c}}{\frac {dc}{d{\hat {y}}}}+{\frac {\partial z^{*}}{\partial A}}{\frac {dA}{d{\hat {y}}}}+{\frac {\partial z^{*}}{\partial b}}{\frac {db}{d{\hat {y}}}}\\&~=~&&c_{y}+{\frac {\partial z^{*}}{\partial b}}{\frac {db}{d{\hat {y}}}}\\&~=~&&c_{y}+u^{*}(-A_{y})\\&~=~&&c_{y}-u^{*}A_{y}\end{aligned}}}$

En otras palabras, el impacto de cambiar el valor${\displaystyle {\hat {y}}}$sobre el valor${\displaystyle z_{\sombrero {y}}^{*}}$Esto se traduce en dos términos. Primero, este cambio impacta directamente la función objetivo y, segundo, se modifica el lado derecho de las restricciones, lo que tiene un impacto en las variables óptimas.${\displaystyle x^{*}}$cuya magnitud se mide utilizando las variables duales${\displaystyle u^{*}}$. El derivado${\displaystyle {\frac {\partial z_{\hat {y}}^{*}}{\partial {\hat {y}}}}}$Generalmente se denomina costo reducido de la variable${\displaystyle y}$y se denotará por${\displaystyle cr_{y}}$en lo siguiente.