PDF de programación - Optimización bajo incertidumbre. Técnicas de descomposición y aplicación en Grid

xx-xx_Optimizacion 26/8/08 12:51 Página 28

Jesús María Latorre Canteli
Ingeniero Industrial del ICAI (1995) y
Doctor Ingeniero Industrial del ICAI
(2007). Es investigador en el Instituto
de Investigación Tecnológica.

Andrés Ramos Galán
Ingeniero Industrial del ICAI (1982) y
Doctor Ingeniero Industrial por la
UPM (1990). Es investigador del Insti-
tuto de Investigación Tecnológica y
Profesor Propio Ordinario de la ETS
de Ingeniería (ICAI) de la Universidad
Pontificia Comillas.

Rafael Palacios Hielscher
Ingeniero Industrial del ICAI (1990) y
Doctor Ingeniero (1998). Es investiga-
dor del Instituto de Investigación Tec-
nológica y Profesor Propio del Depar-
tamento de Sistemas Informáticos.
Imparte clases de programación y de
seguridad informática en las titulacio-
nes de Ingeniero Industrial y de Inge-
niero en Informática del ICAI.

Comentarios a:
[email protected]

Optimización bajo incertidumbre.
Técnicas de descomposición y
aplicación en Grid

Al optimizar procesos cuyo compor ta-
miento no está determinado a priori, es ne-
cesario considerar la incertidumbre asociada
a la predicción de dicho comportamiento.
Esto conlleva la construcción de modelos de
gran tamaño que tengan en cuenta esa in-
certidumbre y ofrezcan resultados que sean
óptimos frente al abanico de situaciones po-
sibles. Ejemplos de este tipo de problemas
son la planificación y operación de sistemas
eléctricos, la planificación de la producción, la
logística del transporte, la gestión de carte-
ras de valores… Como consecuencia de su
gran tamaño, en muchas ocasiones es nece-
sario descomponer los problemas de optimi-
zación estocástica para poder resolverlos. En
este artículo se revisan las técnicas más habi-
tuales de descomposición aplicadas a proble-
mas lineales y se presenta una variante que
permite aprovechar las posibilidades que
ofrecen los grid, que son entornos de cálculo
distribuido que reúnen gran cantidad de re-
cursos de cálculo. El enfoque empleado para
este artículo se centra en la descripción de
los conceptos básicos de los algoritmos de

descomposición, aunque para una explica-
ción formal y detallada pueden consultarse
[Birge,1997] o [Kall, 1994].

Optimización estocástica

La optimización es una herramienta de
ayuda en la toma de decisiones que permi-
te escoger la mejor estrategia para alcanzar
un objetivo. Para esto es necesario modelar
como problema de optimización el entorno
en el que se produce esa toma de decisión.
Este problema de optimización puede invo-
lucrar parámetros cuyo valor no es conoci-
do exactamente en el momento de decidir.
Cuando existe incertidumbre sobre los da-
tos del problema se habla de optimización
estocástica, a diferencia de la optimización
determinista en la que todos los paráme-
tros son conocidos en el momento de to-
mar la decisión. Ejemplos de parámetros
con incertidumbre son la demanda espera-
da de un producto en el mercado o los
precios de una materia prima. La estocasti-
cidad puede influir en muchos aspectos re-
lacionados directa o indirectamente con el

28

anales de mecánica y electricidad / julio-agosto 2008

xx-xx_Optimizacion 26/8/08 12:52 Página 29

problema que se considere, aunque desde
el punto de vista de la optimización esto-
cástica sólo es relevante representar cómo
afecta esta estocasticidad a los parámetros
del problema.

Suele considerarse que el proceso de to-
ma de decisiones está dividido en etapas,
entre las cuales tiene lugar la realización de
una parte de la incertidumbre. Por ejemplo,
si se considera la gestión trimestral de un
embalse hidráulico durante un año, las eta-
pas son los trimestres al comienzo de los
cuales debe decidirse cuánta agua gastar, y a
lo largo de cada trimestre se producen las
lluvias que modifican las reservas disponi-
bles para los siguientes trimestres. Las deci-
siones en cada etapa futura dependen tanto
de la incer tidumbre en etapas anteriores
como de las decisiones tomadas en esa eta-
pa; en consecuencia, el proceso polietápico
de toma de decisiones se desarrolla de la
siguiente forma:
• Se toma la decisión inicial de la primera
etapa. En esta etapa no se considera estocas-
ticidad pues representa la situación inicial co-
nocida.
• Se produce la realización de las variables
aleatorias de la segunda etapa.
• Considerando las decisiones de la primera
etapa y la aleatoriedad ya conocida, se toma
la decisión de la segunda etapa.
• Se produce la realización de las variables
aleatorias de la tercera etapa.
• Continúa el proceso, tomando las decisio-
nes de cada etapa tras conocerse la realiza-
ción de la incertidumbre en esa etapa.

Un escenario es una realización de la alea-
toriedad a lo largo de todas las etapas en
que se divide el proceso de toma de deci-
sión, y está compuesto por nodos, que co-
rresponden con los valores que toma el es-
cenario en cada etapa. En la Figura 1 se
muestra un escenario para el problema de
gestión hidráulica mencionado anteriormen-
te, en el que cada círculo representa un no-
do (es decir el problema de decisión de un
trimestre) y el escenario, que comprende los
nodos de las cuatro etapas, es el problema
de un año completo.

Una de las maneras más habituales de re-
presentar la estocasticidad en los problemas
de optimización es mediante el empleo de
árboles de escenarios. La peculiaridad de los
árboles es que cuando dichos escenarios
consideran la misma realización de la incerti-
dumbre en las etapas iniciales, comparten los
nodos de esas etapas y ramifican en etapas

Figura 1. Ejemplo de escenario de cuatro nodos

Etapas (trimestres)

Figura 2. Ejemplo de árbol de escenarios

Etapas

posteriores. Esto da lugar a una estructura en
árbol como la que se ve en la Figura 2, en la
que se ha señalado el escenario 2 con una lí-
nea de puntos. La estructura del árbol repre-
senta que:
• Se parte de una situación inicial conocida y
por ello hay un solo nodo inicial.
• Según se avanza hacia el futuro, el transcur-
so de los procesos aleatorios es menos co-
nocido. Por eso se producen ramificaciones
en los escenarios y aumenta el número de
nodos en las siguientes etapas.

Técnicas de descomposición

Cuando se trata con problemas de gran
tamaño que no pueden ser resueltos en los
equipos informáticos disponibles, suele recu-
rrirse a técnicas de descomposición, que
permiten fragmentar el problema y coordi-
nar la resolución de los subproblemas para
alcanzar la solución del problema completo.
En este sentido, las técnicas de descomposi-
ción se pueden ver como estrategias de
partición del grafo que representa el árbol
de escenarios y de resolución coordinada

Optimización bajo incertidumbre. Técnicas de descomposición y aplicación en grid 29

xx-xx_Optimizacion 26/8/08 12:52 Página 30

de los fragmentos del grafo. Este proceso de
resolución es de naturaleza iterativa y am-
plía el tiempo de solución total, por lo que
debe ser evitado siempre que sea posible la
resolución directa. En el caso de los proble-
mas de optimización estocástica, el empleo
de técnicas de descomposición permite la
consideración de gran cantidad de escena-
rios o de problemas con un mayor nivel de
detalle en el modelado.

Existen dos técnicas principales de des-
composición que pueden considerarse como
duales entre sí, ya que realizan la descompo-
sición en dos dimensiones transversales. Estas
dos técnicas son la descomposición de Ben-
ders y la relajación lagrangiana, que se expli-
can en los dos siguientes apartados.

Descomposición de Benders

La descomposición de Benders [Ben-
ders,1962], [VanSlyke,1969] propone separar
en subproblemas las decisiones tomadas en
diferentes etapas. Para ello se necesita que las
decisiones de una etapa sólo dependan de
las consecuencias de las decisiones tomadas
en la etapa anterior. Con esta descomposi-
ción se plantea un problema por cada etapa,
y en ese problema se incluye tanto la parte
correspondiente a la propia etapa como la
parte que liga esa etapa a las decisiones to-
madas en la etapa anterior.

Cuando se aplica esta técnica de des-
composición al caso bietapa, se calculan las
decisiones de la primera etapa de forma

independiente, ya que no hay una etapa an-
terior que la condicione. Posteriormente, se
comunica esa solución a la segunda etapa, y
ésta resuelve su problema y devuelve las con-
secuencias de esa decisión de la primera eta-
pa. Repitiendo el proceso, la primera etapa
vuelve a proponer otras decisiones, conside-
rando esta vez además la nueva información
devuelta por la segunda etapa. Comienza un
procedimiento iterativo de resolución que fi-
naliza cuando la primera etapa tiene una des-
cripción suficientemente aproximada de có-
mo afectan sus decisiones a la siguiente etapa.
En ese momento, las decisiones que toma la
primera etapa se consideran óptimas o sufi-
cientemente cercanas a ellas.

En problemas de este tipo se puede ver
que si se fijasen las variables de la primera
etapa, resolver el problema de la segunda
etapa sería más sencillo. Esto es más evidente
en los casos en los que la primera etapa tie-
ne un tamaño reducido y la segunda etapa
está a su vez formada por varios conjuntos
de variables no relacionados entre sí. Un
ejemplo de problemas de este tipo es el pro-
blema clásico de inversión en el sector eléc-
trico: en la primera etapa decide las inversio-
nes en nuevos grupos de generación,
mientras que en la segunda etapa se decide
la producción eléctrica con los grupos dispo-
nibles, frente a diferentes escenarios de de-
manda de energía. En ese caso los diferentes
conjuntos de variables de la segunda etapa
(decisiones de gestión del sistema en cada
escenario de demanda) sólo están relaciona-
das con las variables de la primera etapa (de-
cisiones de inversión). Entonces es claro que
fijando el pequeño grupo de variables de la
primera etapa se obtiene una gran ventaja en
la resolución, al poder resolver cada conjunto
de variables de la segunda etapa de forma in-
dependiente. Por ello, suelen denominarse
variables de complicación a las variables que