FICO Xpress Optimization Examples Repository: Benders decomposition: sequential solving of several different submodels

FICO Xpress Optimization Examples Repository

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'.

benders.zip

[download all files]

Source Files

By clicking on a file name, a preview is opened at the bottom of this page.

benders_main.mos	[download]
benders_dual.mos	[download]
benders_cont.mos	[download]
benders_int.mos	[download]
benders_single.mos	[download]

Data Files

bprob12.dat	[download]
bprob33.dat	[download]

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