 FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home   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.
An implementation using a single model is also presented (benders_single.mos).

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_int.mos

```(!*******************************************************
Mosel Example Problems
======================

file benders_int.mos
````````````````````
Benders decomposition for solving a simple MIP.
- Solve the primal problem for given solution values
of the continuous variables (Step 1 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 (integer problem)"
uses "mmxprs", "mmjobs"

parameters
NINTVAR = 3
NC = 4
BIGM = 1000
end-parameters

declarations
STEP_0=2                            ! Event codes sent to submodels
STEP_1=3
EVENT_SOLVED=6                      ! Event codes sent by submodels

IntVars = 1..NINTVAR                ! Discrete variables
Ctrs = 1..NC                        ! Set of constraints (orig. problem)

B: array(Ctrs,IntVars) of integer   ! Coeff.s of discrete variables
b: array(Ctrs) of integer           ! RHS values
D: array(IntVars) of integer        ! Obj. coeff.s of discrete variables
MC: array(range) of linctr          ! Constraints generated by alg.

sol_u: array(Ctrs) of real          ! Solution of dual problem
sol_y: array(IntVars) of real       ! Solution of primal prob.

y: array(IntVars) of mpvar          ! Discrete variables
z: mpvar                            ! Objective function variable
end-declarations

initializations from "bin:shmem:probdata"
B  b  D
end-initializations

z is_free                            ! Objective is a free variable
forall(i in IntVars) y(i) is_integer ! Integrality condition
forall(i in IntVars) y(i) <= BIGM    ! Set (large) upper bound

repeat
wait
ev:= getnextevent
ct:= integer(getvalue(ev))

initializations from "bin:shmem:sol"
sol_u
end-initializations

MC(ct):= z >= sum(i in IntVars) D(i)*y(i) +
sum(j in Ctrs) sol_u(j)*(b(j) - sum(i in IntVars) B(j,i)*y(i))

minimize(z)

! Store solution values of y
forall(i in IntVars) sol_y(i):= getsol(y(i))

initializations to "bin:shmem:sol"
sol_y
end-initializations

send(EVENT_SOLVED, getobjval)

write("Step 1: ", getobjval, "\n  y: ")
forall(i in IntVars) write(sol_y(i), " ")

write("\n  Slack: ")
forall(j in 1..ct) write(getslack(MC(j)), " ")
writeln
fflush

until false

end-model

```   