tÉcnicas de descomposiciÓn en programaciÓn …
Post on 16-Oct-2021
12 Views
Preview:
TRANSCRIPT
TÉCNICAS DE DESCOMPOSICIÓN
EN PROGRAMACIÓN MATEMÁTICA
Dr. Víctor M. Albornoz S.
Departamento de Industrias.
Campus Santiago Vitacura, Chile.
Universidad Técnica Federico Santa María
Instituto de Computación, Facultad de Ingeniería, UdelaR.
Montevideo, lunes 14 al viernes 18 de Octubre de 2019
CONTENIDOS
1. Introducción.
2. Formulación y resolución de modelos en AMPL.
3. Método de Benders.
4. Generación de Columnas.
5. Método de Dantzig & Wolfe.
6. Extensiones.
5.- Método de Dantzig & Wolfe.
Para detallar este método consideramos
primeramente el siguiente modelo de P. Lineal:
Min cTx (5.1)
s.a. Ax = b
xX
donde A es una matriz cualquiera que define las
restricciones complicadas del problema y X un
poliedro acotado que reúne las restantes
restricciones lineales del problema.
Denotando por x1,...,xt los vértices de X, para
cada xX se cumple:
x = 1x1 + 2x
2 + ... + txt
con escalares 10, 20, …, t0 tales que:
1 + 2 + ... + t = 1
De este modo el problema (5.1) es equivalente a
resolver el siguiente Problema Maestro:
Min (cTx1)1 + (cTx2)2+ ... + (cTxt)t (5.2)
s.a. (Ax1)1 + (Ax2)2
+ ... + (Axt)t = b
1+ 2 + ... + t = 1
10, 20, …, t0.
Sea B una matriz de base asociada a una solución
básica factible del Problema Maestro.
Sean y las respectivas variables duales
asociadas a las restricciones en (5.2), entonces:
[T ] = cBTB-1 cB: vector de costos básicos
Las condiciones de optimalidad que deben
verificarse para cada variable no-básica j son:
(cTxj) – [T ][Axj ] = (cTxj) - T(Axj) - = (cT - TA)xj - 0
[ 1 ]
Para verificar lo anterior no es necesario conocer
todos los vértices de X pues basta con resolver el
siguiente Subproblema:
Min (cT - TA)x - (5.3)
s.a. xX
En efecto, si xk es el vértice donde se alcanza la
solución óptima del Subproblema y cumple que:
(cT - TA)xk - 0,
entonces todos los otros vértices le verifican y
hemos alcanzado la solución óptima al problema.
En caso contrario, tenemos una nueva columna para
el Maestro Reducido asociada a la variable no-
básica k que entra a la base del nuevo problema.
En el contexto del Simplex Revisado, se calcula el
vector yk para determinar la variable que deja la
base. Este determina la columna de la variable
entrante k como combinación de las actuales
columnas en B, resolviendo: ByK = [Axk ]
[ 1 ]
y se sigue con una nueva iteración del método.
Algoritmo.
0. Obtener una solución factible inicial del P. Maestro, que
define un Maestro Reducido con las columnas dadas.
1. Calcular coeficientes de la función objetivo del
Subproblema, que define el costo reducido de la solución.
2. Resolver el Subproblema. En caso de tener un valor
óptimo positivo STOP. En caso contrario, obtener nueva
variable básica para el Maestro Reducido (nueva
columna a ser incorporada en el Maestro Reducido).
3. Resolver el P. Maestro Reducido. En el contexto del
M.Simplex esto pasa por determinar qué variable básica
deja la base y obtener el vector de precios duales. Ir a 1.
Ejemplo. Resolveremos el siguiente problema
mediante el Método de Dantzig & Wolfe:
Min -2x1 - 4x2 - 3x3 - 2x4
s.a.
6x1 + 5x2 + 4x3 + 3x4 50
x1 + x2 + x3 + x4 12
2x1 + 4x2 10
x3 6
x4 6
x10, x20, x30, x40.
Problema de Transporte con múltiples productos.
Otro problema interesante relacionado con el
problema de transporte consiste en decidir
cuántas unidades trasladar de distintos productos
desde ciertos puntos de origen a ciertos puntos
de destino.
Dados los costos unitarios de transporte, la oferta
y demanda en dichos puntos para cada uno de
los productos, el problema consiste en minimizar
los costos de transporte de modo de satisfacer la
demanda por los distintos productos.
Variables de decisión.
Ti,j,p: unidades transportadas desde el origen i al destino j
del proucto p
Modelo
Min ∑i ∑j ∑p ci,j,p Ti,j,p
s.a.
∑j Ti,j p ≤ si,p para i=1,…,m; p=1,…,P
∑i Ti,j,p = dj,p para j=1,…,n; p=1,…,P
∑p Ti,j,p ≤ limiti,j para i=1,…,m; j=1,…,n;
Ti,j,p ≥ 0 i=1,…,m; j=1,…,n; p=1,…,P
Ge
sti
ón
de In
vesti
gació
n d
e O
pera
cio
nes
Si muestra a continuación instancia del problema en AMPL en base a los archivos MULTI.MOD y MULTI.DAT:
Implementación del algoritmo de Dantzig y Wolfe
en AMPL, aplicado al mismo problema de
transporte para múltiples productos
multi1.mod ### SUBPROBLEM ###
set ORIG; # origins
set DEST; # destinations
set PROD; # products
param supply {ORIG,PROD} >= 0; # amounts available at origins
param demand {DEST,PROD} >= 0; # amounts required at
destinations
check {p in PROD}:
sum {i in ORIG} supply[i,p] = sum {j in DEST} demand[j,p];
param price_convex; # dual price on convexity
constr
param price {ORIG,DEST} <= 0.000001; # dual price on shipment
limit
param cost {ORIG,DEST,PROD} >= 0; # shipment costs per unit
var Trans {ORIG,DEST,PROD} >= 0; # units to be shipped
minimize Artif_Reduced_Cost:
sum {i in ORIG, j in DEST, p in PROD}
(- price[i,j]) * Trans[i,j,p] - price_convex;
minimize Reduced_Cost:
sum {i in ORIG, j in DEST, p in PROD}
(cost[i,j,p] - price[i,j]) * Trans[i,j,p] - price_convex;
subject to Supply {i in ORIG, p in PROD}:
sum {j in DEST} Trans[i,j,p] = supply[i,p];
subject to Demand {j in DEST, p in PROD}:
sum {i in ORIG} Trans[i,j,p] = demand[j,p];
multi1.mod (cont.)
### MASTER PROBLEM ###
param limit {ORIG,DEST} >= 0; # max shipped on each link
param nPROP integer >= 0;
param prop_ship {ORIG,DEST,1..nPROP} >= -0.000001;
param prop_cost {1..nPROP} >= 0;
# For each proposal from the subproblem:
# amount it ships over each link, and its cost
var Weight {1..nPROP} >= 0;
var Excess >= 0;
minimize Artificial: Excess;
minimize Total_Cost:
sum {k in 1..nPROP} prop_cost[k] * Weight[k];
subject to Multi {i in ORIG, j in DEST}:
sum {k in 1..nPROP} prop_ship[i,j,k] * Weight[k] - Excess <=
limit[i,j];
subject to Convex: sum {k in 1..nPROP} Weight[k] = 1;
### PHASE III PROBLEM ###
param opt_ship {ORIG,DEST} >= -0.000001;
minimize Opt_Cost:
sum {i in ORIG, j in DEST, p in PROD} cost[i,j,p] * Trans
[i,j,p];
subject to Opt_Multi {i in ORIG, j in DEST}:
sum {p in PROD} Trans[i,j,p] = opt_ship[i,j];
multi1.dat
set ORIG := GARY CLEV PITT ;
set DEST := FRA DET LAN WIN STL FRE LAF ;
set PROD := bands coils plate ;
param supply (tr): GARY CLEV PITT :=
bands 400 700 800
coils 800 1600 1800
plate 200 300 300 ;
param demand (tr):
FRA DET LAN WIN STL FRE LAF :=
bands 300 300 100 75 650 225 250
coils 500 750 400 250 950 850 500
plate 100 100 0 50 200 100 250 ;
param limit default 625 ;
param cost :=
[*,*,bands]: FRA DET LAN WIN STL FRE LAF :=
GARY 30 10 8 10 11 71 6
CLEV 22 7 10 7 21 82 13
PITT 19 11 12 10 25 83 15
[*,*,coils]: FRA DET LAN WIN STL FRE LAF :=
GARY 39 14 11 14 16 82 8
CLEV 27 9 12 9 26 95 17
PITT 24 14 17 13 28 99 20
[*,*,plate]: FRA DET LAN WIN STL FRE LAF :=
GARY 41 15 12 16 17 86 8
CLEV 29 9 13 9 28 99 18
PITT 26 14 17 13 31 104 20 ;
multi1.run
model multi1.mod;
data multi1.dat;
let nPROP := 0;
let price_convex := 1;
let {i in ORIG, j in DEST} price[i,j] := 0;
option solver minos;
option omit_zero_rows 1;
option display_1col 10;
option display_eps .000001;
# ----------------------------------------------------------
problem MasterI: Artificial, Weight, Excess, Multi, Convex;
problem SubI: Artif_Reduced_Cost, Trans, Supply, Demand;
repeat { printf "\nPHASE I -- ITERATION %d\n\n", nPROP+1;
solve SubI;
printf "\n";
display Trans;
if Artif_Reduced_Cost >= - 0.00001 then {
printf "\n*** NO FEASIBLE SOLUTION ***\n";
break;
}
else {
let nPROP := nPROP + 1;
let {i in ORIG, j in DEST}
prop_ship[i,j,nPROP] := sum {p in PROD} Trans[i,j,p];
let prop_cost[nPROP] :=
sum {i in ORIG,j in DEST,p in PROD} cost[i,j,p]*Trans[i,j,p];
};
solve MasterI;
printf "\n";
display Weight; display Multi.dual;
display {i in ORIG, j in DEST}
limit[i,j] - sum {k in 1..nPROP} prop_ship[i,j,k] * Weight[k];
if Excess <= 0.00001 then break;
else {
let {i in ORIG, j in DEST} price[i,j] := Multi[i,j].dual;
let price_convex := Convex.dual;
};
};
multi1.run
printf "\nSETTING UP FOR PHASE II\n\n";
problem MasterII: Total_Cost, Weight, Multi, Convex;
problem SubII: Reduced_Cost, Trans, Supply, Demand;
solve MasterII;
printf "\n";
display Weight; display Multi.dual; display Multi.slack;
let {i in ORIG, j in DEST} price[i,j] := Multi[i,j].dual;
let price_convex := Convex.dual;
repeat { printf "\nPHASE II -- ITERATION %d\n\n", nPROP+1;
solve SubII;
printf "\n";
display Trans;
if Reduced_Cost >= - 0.00001 then {
printf "\n*** OPTIMAL SOLUTION ***\n";
break;
}
else {
let nPROP := nPROP + 1;
let {i in ORIG, j in DEST}
prop_ship[i,j,nPROP] := sum {p in PROD} Trans[i,j,p];
let prop_cost[nPROP] :=
sum{i in ORIG,j in DEST,p in PROD} cost[i,j,p]*Trans[i,j,p];
};
solve MasterII;
printf "\n";
display Weight;
let {i in ORIG, j in DEST} price[i,j] := Multi[i,j].dual;
let price_convex := Convex.dual;
};
# ----------------------------------------------------------
printf "\nPHASE III\n\n";
problem MasterIII: Opt_Cost, Trans, Supply, Demand, Opt_Multi;
let {i in ORIG, j in DEST}
opt_ship[i,j] := sum {k in 1..nPROP} prop_ship[i,j,k] * Weight[k];
solve MasterIII;
printf "\n";
display Trans;
Dantzig & Wolfe propusieron originalmente esta
idea aplicada a problemas de programación
lineal con una estructura de restricciones bloque
angular que se detalla a continuación.
(5.4)
(5.4)
(5.1)
(5.4)
(5.5)
(5.5)
(5.5)
(5.6)
Implementación del algoritmo en AMPL, usando
ahora varios subproblemas está implementado
para ejemplo anterior en archivos multi2.mod,
multi2.run y multi2.dat
Referencias:
Generación de Columnas
Bertsimas, D. y Titsiklis, J. "Introduction to Linear
Optimization". Cap. 6, secciones 1 y 2.
Método de Descomposición de Dantzig & Wolfe
Bertsimas, D. y Titsiklis, J. "Introduction to Linear
Optimization". Cap. 6, Sección 4.
Bazaraa, M., Jarvis, J. and Sherali, H. Linear
programming and network flows, Cap 7, sección 7.1,
7.2, 7.3, 7.4 y 7.5.
CONTENIDOS
1. Introducción.
2. Formulación y resolución de modelos en AMPL.
3. Método de Benders.
4. Generación de Columnas.
5. Método de Dantzig & Wolfe.
6. Extensiones y palabras finales.
6.- Extensiones y palabras finales.
Como hemos comentado, existen problemas de
gran tamaño donde la presencia de
restricciones con una determinada estructura
facilita su resolución al emplear métodos de
descomposición.
Sin embargo hemos revisado únicamente
técnicas clásicas de descomposición en
modelos de programación lineal.
Otros métodos de descomposición incluyen a:
L-Shaped decomposition method of van Slyke & Wets (1969).
Generalized Benders Decomposition of Geoffrion (1972).
Simplicial decomposition of von Hohembalken (1977).
Cross Decomposition of van Roy (1983).
Horizontal Decomposition of Meijboom (1986).
Lagrangean decomposition of Guignard and Kim (1987).
Local Decomposition of van de Panne (1987).
Nested Decomposition, Robinson (1989).
Stochastic Decomposition, Higle and Sen (1991).
Column Generation in IP, Vanderveck and Wolsey (1996).
L-Shaped Method for IPSP, Caroe and Tind (1998).
Branch-and-price, Barnhart et al. (1998).
Benders and BFC for 0-1 mixed SP, Escudero et al. (2007).
Two-Stage Column Generation, Salani and Vacca (2008).
Stochastic Scenario Decomposition (MSSP), Higle et al. (2010)
Cluster Benders Decomposition, Aramburu et al. (2012).
Primal-dual column generation method, Gondzio et al. (2013).
Bi-objective column generation algorithm, Moradi et al. (2015).
Benders method for bilevel programs, Bagloee et al. (2016),
Fontaine and Minner (2017) and Che et al. (2019).
Existen numerosos problemas que contribuyen a
la toma de decisiones y que pueden ser
abordados con modelos de optimización, pero
cuya resolución plantea desafíos algorítmicos.
Los Métodos de Descomposición proveen
técnicas numéricas de optimización para resolver
adecuadamente problemas de gran tamaño.
TÉCNICAS DE DESCOMPOSICIÓN
EN PROGRAMACIÓN MATEMÁTICA
Dr. Víctor M. Albornoz S.
Departamento de Industrias.
Campus Santiago Vitacura, Chile.
Universidad Técnica Federico Santa María
Instituto de Computación, Facultad de Ingeniería, UdelaR.
Montevideo, lunes 14 al viernes 18 de Octubre de 2019
G P S I Y
R O U N
A R T A
C E S
I R I
A É S
S S T
E
N
C
I A
top related