 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_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

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)

! (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

```   