$TITLE Descomposición de Danztig-Wolfe (DW)

* Andrés Ramos, Santiago Cerisola Optimización Estocástica
* http://www.doi.icai.upcomillas.es/simio/apuntes/a_sp.pdf

SETS
   L    máximo numero de iteraciones / iter-1 * iter-5 /
   J(l) iteración actual
   N1   variables

SCALAR
   Z_INF cota inferior de la solución             / -INF /
   Z_SUP cota superior de la solución             /  INF /
   TOL   tolerancia en optimalidad                / 1e-6 /
   PNLZ  penalización restricciones primera etapa / 1000 /

PARAMETERS
   X1_L(l,n1) soluciones del subproblema

* comienzo datos del problema

SETS
   M1 número restricciones primera etapa / rdos-1          /
   M2 número restricciones segunda etapa / runo-1 * runo-5 /
   N1 variables                          / xuno-1 * xuno-4 /

PARAMETERS
   C1(n1)     coeficientes función objetivo primera etapa
              / xuno-1     -1
                xuno-2     -1
                xuno-3     -2
                xuno-4     -1 /
   B1(m1)     cotas restricciones primera etapa
              / rdos-1     10 /
   B2(m2)     cotas restricciones segunda etapa
              / runo-1     40
                runo-2     30
                runo-3     10
                runo-4     10
                runo-5     15 /

TABLE A1(m1,n1)  matriz de restricciones primera etapa
                    xuno-1  xuno-2  xuno-3  xuno-4
          rdos-1      1       2       2       1

TABLE A2(m2,n1) matriz de restricciones segunda etapa
                    xuno-1  xuno-2  xuno-3  xuno-4
          runo-1      1       3
          runo-2      2       1
          runo-3                      1
          runo-4                              1
          runo-5                      1       1

* fin datos del problema

POSITIVE VARIABLES
   X1(n1)    variables primera etapa
   LAMBDA(l) pesos de las soluciones
   EXC(m1)   variables de exceso en restricciones primera etapa <=

VARIABLES
   Z2 función objetivo subproblema y completo
   Z1 función objetivo maestro

EQUATIONS
   FOM     función objetivo maestro
   FOS     función objetivo subproblema
   FOC     función objetivo problema completo
   R1(m1)  restricciones primera etapa
   R1C(m1) restricciones primera etapa
   R2(m2)  restricciones segunda etapa
   COMBLIN combinación lineal de los pesos de las soluciones ;

FOM     .. Z1 =E= SUM((j,n1), C1(n1)*X1_L(j,n1)*LAMBDA(j)) + PNLZ * SUM(m1, EXC(m1)) ;

FOS     .. Z2 =E= SUM(n1, (C1(n1) - SUM(m1, R1.M(m1)*A1(m1,n1)))*X1(n1)) - COMBLIN.M ;

FOC     .. Z2 =E= SUM(n1, C1(n1)*X1(n1)) ;

R1C(m1) .. SUM(n1, A1(m1,n1)*X1(n1)) =L= B1(m1) ;

* se introducen variables de exceso en restricciones primera etapa <=
* para evitar infactibilidad

R1(m1)  .. SUM((j,n1), A1(m1,n1)*X1_L(j,n1)*LAMBDA(j)) - EXC(m1) =L= B1(m1) ;

R2(m2)  .. SUM(n1, A2(m2,n1)*X1(n1)) =L= B2(m2) ;

COMBLIN .. SUM(j, LAMBDA(j)) =E= 1 ;

MODEL MAESTRO  / FOM, R1, COMBLIN /
MODEL SUB      / FOS, R2          /
MODEL COMPLETO / FOC, R1C, R2     /

FILE COPT / cplex.opt /
PUT COPT PUT 'preind 0' / 'epopt 1.1e-9' / 'eprhs 1.1e-9'
PUTCLOSE COPT ;

SUB.OPTFILE     = 1 ;
MAESTRO.OPTFILE = 1 ;

J(l)       = NO ;

X1_L(l,n1) = 0 ;
LAMBDA.UP(l) = 1 ;

* inicialización de variables

Z2.L = - 10 * TOL ;

R1.M(m1)  = 0 ;
COMBLIN.M = 0 ;

LOOP(l $(abs(Z2.L) > TOL),

   IF (ORD(l) > 1,
      SOLVE MAESTRO USING LP MINIMIZING Z1 ;
      Z_SUP = Z1.L ;
   ) ;

   SOLVE SUB USING LP MINIMIZING Z2 ;
   X1_L(l,n1) = X1.L(n1) ;
   Z_INF = Z2.L + COMBLIN.M + SUM(m1, R1.M(m1)*B1(m1)) ;
   DISPLAY Z_INF, Z_SUP ;

   J(l) = YES ;

) ;
ABORT $(abs(Z2.L) > TOL) 'Máximo numero de iteraciones alcanzado' ;

* resultados de la descomposición

X1.L(n1) = SUM(j, X1_L(j,n1)*LAMBDA.L(j)) ;
DISPLAY X1.L ;

* resolución del problema completo

SOLVE COMPLETO USING LP MINIMIZING Z2 ;