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

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_cont.mos (!******************************************************* Mosel Example Problems ====================== file benders_cont.mos ````````````````````` Benders decomposition for solving a simple MIP. - Solve the primal problem for given solution values of the integer variable (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 (continuous problem)" uses "mmxprs", "mmjobs" parameters NCTVAR = 3 NINTVAR = 3 NC = 4 BIGM = 1000 end-parameters declarations STEP_0=2 ! Event codes sent to submodels STEP_2=4 STEP_3=5 EVENT_SOLVED=6 ! Event codes sent by submodels 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 Ctr: array(Ctrs) of linctr ! Constraints of orig. problem 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) x: array(CtVars) of mpvar ! Continuous variables end-declarations initializations from "bin:shmem:probdata" A B b C end-initializations Obj:= sum(i in CtVars) C(i)*x(i) send(EVENT_READY,0) ! Model is ready (= running) ! (Re)solve this model until it is stopped by event "STEP_3" repeat wait dropnextevent initializations from "bin:shmem:sol" sol_y end-initializations forall(j in Ctrs) Ctr(j):= sum(i in CtVars) A(j,i)*x(i) + sum(i in IntVars) B(j,i)*sol_y(i) >= b(j) minimize(Obj) ! Solve the problem ! Store values of u and x forall(j in Ctrs) sol_u(j):= getdual(Ctr(j)) forall(i in CtVars) sol_x(i):= getsol(x(i)) initializations to "bin:shmem:sol" sol_u sol_x end-initializations send(EVENT_SOLVED, getobjval) write("Step 2: ", getobjval, "\n u: ") forall(j in Ctrs) write(sol_u(j), " ") write("\n x: ") forall(i in CtVars) write(getsol(x(i)), " ") writeln fflush until false end-model | |||||||||||||||||||

Copyright 2017 Fair Isaac Corporation. |