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_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
  EVENT_READY=8

  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

 send(EVENT_READY,0)                  ! Model is ready (= running)

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

  initializations from "bin:shmem:sol"
   sol_u
  end-initializations
    
  ! Add a new constraint
  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