$TITLE Descomposición de relajación lagrangiana (RL) * Andrés Ramos, Santiago Cerisola Optimización Estocástica * http://www.doi.icai.upcomillas.es/simio/apuntes/a_sp.pdf SETS L máximo número de iteraciones / iter-1 * iter-5 / J(l) iteración actual IT iteraciones del algoritmo / iter-1 * iter-9 / 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 / GAMMA coeficiente cotas restricciones subproblema / 1 / * fase 1 obtiene cortes hasta que el maestro resulte acotado INFACT fase 1 (0) o fase 2 (1) de relajación lagrangiana / 0 / N_CORTES número de cortes / 0 / FORMUL tipo de formulación relajación lagrangiana / 2 / PARAMETERS DELTA1(l) coeficiente para cortes de acotamiento (subproblema no acotado) X1_L(l,n1) soluciones del subproblema * comienzo datos del problema SETS M1 restricciones primera etapa / runo-1 / M2 restricciones segunda etapa / rdos-1 * rdos-6 / N1 variables / xuno-1 * xuno-3 / PARAMETERS C1(n1) coeficientes función objetivo / xuno-1 -4 xuno-2 -1 xuno-3 -6 / B1(m1) cotas restricciones primera etapa / runo-1 17 / B2(m2) cotas restricciones segunda etapa / rdos-1 -1 rdos-2 -1 rdos-3 -1 rdos-4 2 rdos-5 2 rdos-6 2 / TABLE A1(m1,n1) matriz de restricciones primera etapa xuno-1 xuno-2 xuno-3 runo-1 3 2 4 TABLE A2(m2,n1) matriz de restricciones segunda etapa xuno-1 xuno-2 xuno-3 rdos-1 -1 rdos-2 -1 rdos-3 -1 rdos-4 1 rdos-5 1 rdos-6 1 * fin datos del problema VARIABLES X1(n1) variables primera etapa Z2 función objetivo subproblema y completo Z1 función objetivo maestro TT función objetivo maestro PI2(m1) variables duales restricciones primera etapa MU variable dual de la combinación lineal EQUATIONS FOM1 función objetivo maestro FOM2 función objetivo maestro FOS1 función objetivo subproblema FOS2 función objetivo subproblema FOC función objetivo problema completo R1(m1) restricciones primera etapa R2(m2) restricciones segunda etapa CORTES1(l) cortes de relajación lagrangiana CORTES2(l) cortes de relajación lagrangiana ; FOM1 .. Z1 =E= SUM(m1, B1(m1)*PI2(m1)) + MU ; FOM2 .. Z1 =E= TT ; FOS1 .. Z2 =E= - SUM(m1, PI2.L(m1)*(SUM(n1, A1(m1,n1)*X1(n1)))) - MU.L + INFACT*SUM(n1, C1(n1)*X1(n1)) ; FOS2 .. Z2 =E= - SUM(m1, PI2.L(m1)*(SUM(n1, A1(m1,n1)*X1(n1))-B1(m1)*GAMMA)) + INFACT*SUM(n1, C1(n1)*X1(n1)) ; FOC .. Z2 =E= SUM(n1, C1(n1)*X1(n1)) ; R1(m1) .. SUM(n1, A1(m1,n1) * X1(n1)) =L= B1(m1) ; R2(m2) .. SUM(n1, A2(m2,n1) * X1(n1)) =L= B2(m2) * GAMMA ; CORTES1(j) .. SUM(m1, PI2(m1)*(SUM(n1, A1(m1,n1)*X1_L(j,n1)))) + DELTA1(j)*MU =L= INFACT*SUM(n1, C1(n1)*X1_L(j,n1)) ; CORTES2(j) .. SUM(m1, PI2(m1)*(SUM(n1, A1(m1,n1)*X1_L(j,n1))-DELTA1(j)*B1(m1))) + DELTA1(j)*TT =L= INFACT*SUM(n1, C1(n1)*X1_L(j,n1)) ; MODEL MAESTRO1 / FOM1, CORTES1 / MODEL MAESTRO2 / FOM2, CORTES2 / MODEL SUB1 / FOS1, R2 / MODEL SUB2 / FOS2, R2 / MODEL COMPLETO / FOC, R1, R2 / FILE COPT / cplex.opt / PUT COPT PUT 'scaind -1' / 'lpmethod 1' / 'preind 0' / 'epopt 1.1e-9' / 'eprhs 1.1e-9' PUTCLOSE COPT ; SUB1.OPTFILE = 1 ; SUB2.OPTFILE = 1 ; MAESTRO1.OPTFILE = 1 ; MAESTRO2.OPTFILE = 1 ; J(l) = NO ; X1_L(l,n1) = 0 ; DELTA1(l) = 1 ; Z1.L = 1e3 ; * inicialización de variables duales para subproblema MU.L = 0 ; PI2.L(m1) = 0 ; * cotas de variables maestro en fase 1 (para acotar maestro) TT.LO = - 1e3 ; TT.UP = 1e3 ; PI2.LO(m1) = - 1 ; PI2.UP(m1) = 0 ; MU.LO = - 1 ; MU.UP = 1 ; LOOP(it $(INFACT = 0 OR Z_INF < Z_SUP), IF (ORD(it) > 1, IF (FORMUL = 1, SOLVE MAESTRO1 USING LP MAXIMIZING Z1 ELSE SOLVE MAESTRO2 USING LP MAXIMIZING Z1 ) ; Z_SUP = Z1.L ) ; DISPLAY Z_SUP * se resuelve el subproblema salvo si en fase 1 el maestro es 0 IF (INFACT = 1 OR Z_SUP > TOL, DELTA1(l) $(ORD(l) = N_CORTES + 1) = 1 ; IF (FORMUL = 1, SOLVE SUB1 USING LP MINIMIZING Z2 ; Z_INF $(SUB1.MODELSTAT = 1) = Z2.L + MU.L + SUM(m1, PI2.L(m1)*B1(m1)) ; * cálculo del rayo de forma correcta IF (SUB1.MODELSTAT = 3 OR SUB1.MODELSTAT = 19, GAMMA = 0 ; X1.LO(n1) = -1 ; X1.UP(n1) = 1 ; SOLVE SUB1 USING LP MINIMIZING Z2 ; GAMMA = 1 ; X1.LO(n1) = -INF ; X1.UP(n1) = INF ; Z_INF = -INF ; DELTA1(l) $(ORD(l) = N_CORTES + 1) = 0 ; ) ; ELSE SOLVE SUB2 USING LP MINIMIZING Z2 ; Z_INF $(SUB2.MODELSTAT = 1) = Z2.L ; * cálculo del rayo de forma correcta IF (SUB2.MODELSTAT = 3 OR SUB2.MODELSTAT = 19, GAMMA = 0 ; X1.LO(n1) = -1 ; X1.UP(n1) = 1 ; SOLVE SUB2 USING LP MINIMIZING Z2 ; GAMMA = 1 ; X1.LO(n1) = -INF ; X1.UP(n1) = INF ; Z_INF = -INF ; DELTA1(l) $(ORD(l) = N_CORTES + 1) = 0 ; ) ; ) ; DISPLAY Z_INF * sólo se genera un corte si el valor del maestro es superior al del subproblema IF(Z_SUP > Z_INF, X1_L(l,n1) $(ORD(l) = N_CORTES + 1) = X1.L(n1) ; J(l) $(ORD(l) = N_CORTES + 1) = YES ; N_CORTES = N_CORTES + 1 ; ) ; ) ; * paso a la fase 2 de la RL cuando z1.l=0 IF (INFACT = 0 AND Z_SUP < TOL, INFACT = 1 ; PI2.LO(m1) = -INF ; PI2.UP(m1) = 0 ; MU.LO = -INF ; MU.UP = INF ; Z_SUP = 1e3 ; Z_INF = -INF ; ); ) ; ABORT $(ABS(Z_INF-Z_SUP) > TOL) 'Máximo número de iteraciones alcanzado' ; * resultados descomposición IF (FORMUL = 1, X1.L(n1) = SUM(j, X1_L(j,n1)*CORTES1.M(j)) ELSE X1.L(n1) = SUM(j, X1_L(j,n1)*CORTES2.M(j)) ) ; * resolución del problema completo SOLVE COMPLETO USING LP MINIMIZING Z2