| |||||||||||||||||||

Benders decomposition: sequential solving of several different submodels Description Benders decomposition is a method for solving large
MIP problems. The model implementation shows the following
features:
- iterative sequence of concurrent solving of a set of subproblems,
- data exchange between several models via shared memory, and
- coordination of several models via events.
Further explanation of this example:
Xpress Whitepaper 'Multiple models and parallel
solving with Mosel', Section 'Benders decomposition:
working with several different submodels'.
Source Files
Data Files benders_dual.mos (!******************************************************* Mosel Example Problems ====================== file benders_dual.mos ````````````````````` Benders decomposition for solving a simple MIP. - Dual problem in the continuous variables for start solution and Step 2 of the algorithm - *** Not intended to be run standalone - run from benders_main.mos *** (c) 2008 Fair Isaac Corporation author: S. Heipcke, Jan. 2006, rev. Jan. 2013 *******************************************************!) model "Benders (dual problem)" uses "mmxprs", "mmjobs" parameters NCTVAR = 3 NINTVAR = 3 NC = 4 BIGM = 1000 end-parameters forward procedure save_solution declarations STEP_0=2 ! Event codes sent to submodels STEP_2=4 EVENT_SOLVED=6 ! Event codes sent by submodels EVENT_INFEAS=7 EVENT_READY=8 CtVars = 1..NCTVAR ! Continuous variables IntVars = 1..NINTVAR ! Discrete variables Ctrs = 1..NC ! Set of constraints (orig. problem) A: array(Ctrs,CtVars) of integer ! Coeff.s of continuous variables B: array(Ctrs,IntVars) of integer ! Coeff.s of discrete variables b: array(Ctrs) of integer ! RHS values C: array(CtVars) of integer ! Obj. coeff.s of continuous variables sol_u: array(Ctrs) of real ! Solution of dual problem sol_x: array(CtVars) of real ! Solution of primal prob. (cont.) sol_y: array(IntVars) of real ! Solution of primal prob. (integers) u: array(Ctrs) of mpvar ! Dual variables end-declarations initializations from "bin:shmem:probdata" A B b C end-initializations forall(i in CtVars) CtrD(i):= sum(j in Ctrs) u(j)*A(j,i) <= C(i) send(EVENT_READY,0) ! Model is ready (= running) ! (Re)solve this model until it is stopped by event "STEP_3" repeat wait ev:= getnextevent Alg:= getclass(ev) if Alg=STEP_0 then ! Produce an initial solution for the ! dual problem using a dummy objective maximize(sum(j in Ctrs) u(j)) if(getprobstat = XPRS_INF) then writeln("Problem is infeasible") send(EVENT_INFEAS,0) ! Problem is infeasible else write("**** Start solution: ") save_solution end-if else ! STEP 2: Solve the dual problem for ! given solution values of y initializations from "bin:shmem:sol" sol_y end-initializations Obj:= sum(j in Ctrs) u(j)* (b(j) - sum(i in IntVars) B(j,i)*sol_y(i)) maximize(XPRS_PRI, Obj) if(getprobstat=XPRS_UNB) then BigM:= sum(j in Ctrs) u(j) <= BIGM maximize(XPRS_PRI, Obj) end-if write("Step 2: ") save_solution ! Write solution to memory BigM:= 0 ! Reset the 'BigM' constraint end-if until false !----------------------------------------------------------- ! Process solution data procedure save_solution ! Store values of u and x forall(j in Ctrs) sol_u(j):= getsol(u(j)) forall(i in CtVars) sol_x(i):= getdual(CtrD(i)) initializations to "bin:shmem:sol" sol_u sol_x end-initializations send(EVENT_SOLVED, getobjval) write(getobjval, "\n u: ") forall(j in Ctrs) write(sol_u(j), " ") write("\n x: ") forall(i in CtVars) write(getdual(CtrD(i)), " ") writeln fflush end-procedure end-model | |||||||||||||||||||

Copyright 2017 Fair Isaac Corporation. |