FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

Dantzig-Wolfe decomposition: combining sequential and parallel solving

Description
Dantzig-Wolfe decomposition is a method for solving large LP 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
  • coordination of several models via events
Two different implementations are proposed. The first one runs on a single node allowing to execute multiple concurrent solves (cocoMs.mos and cocoSubFs.mos) and the second one executes on multiple nodes (cocoMd.mos and cocoSubFd.mos). Extending the single node model to support distributed architecture requires only few lines of new code to setup the list of nodes and define which node solves which subproblem.

Further explanation of this example: Xpress Whitepaper 'Multiple models and parallel solving with Mosel', Section 'Dantzig-Wolfe decomposition: sequential and parallel solving'.


Source Files

Data Files





cocoSubFd.mos

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

   file cocoSubFd.mos
   ``````````````````
   Coco Problem, single factory subproblem.
   -- Distributed computing version --

   *** Not intended to be run standalone - run from cocoMd.mos ***

   (c) 2010 Fair Isaac Corporation
       author: S. Heipcke, May 2010
*******************************************************!)

model "Coco Subproblem (factory based decomp.)"
 uses "mmxprs", "mmjobs"

 parameters
  Factory = 0
  TOL = 0.00001
  DATAFILE = "coco3.dat"
  RMT = "rmt:"                          ! Files are on (remote) root node
 end-parameters

 forward procedure process_solution
 
 declarations                         
  PHASE_0=2                             ! Event codes sent to submodels
  PHASE_1=3
  PHASE_2=4
  PHASE_3=5
  EVENT_SOLVED=6                        ! Event codes sent by submodels
  EVENT_FAILED=7
  EVENT_READY=8
  NPROD, NFACT, NRAW, NT: integer
 end-declarations                      

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

 initializations from RMT+DATAFILE
  NPROD NFACT NRAW NT
 end-initializations

 declarations
  PRODS = 1..NPROD                      ! Range of products (p)
  FACT = 1..NFACT                       !          factories (f)
  RAW = 1..NRAW                         !          raw materials (r)
  TIME = 1..NT                          !          time periods (t)

  REV: array(PRODS,TIME) of real        ! Unit selling price of products
  CMAKE: array(PRODS,FACT) of real      ! Unit cost to make product p
                                        ! at factory f
  CBUY: array(RAW,TIME) of real         ! Unit cost to buy raw materials
  REQ: array(PRODS,RAW) of real         ! Requirement by unit of product p
                                        ! for raw material r
  MXSELL: array(PRODS,TIME) of real     ! Max. amount of p that can be sold
  MXMAKE: array(FACT) of real           ! Max. amount factory f can make
                                        ! over all products
  IPSTOCK: array(PRODS,FACT) of real    ! Initial product stock levels
  IRSTOCK: array(RAW,FACT) of real      ! Initial raw material stock levels
  CPSTOCK: real                         ! Unit cost to store any product p
  CRSTOCK: real                         ! Unit cost to store any raw mat. r
  MXRSTOCK: real                        ! Raw material storage capacity
  
  make: array(PRODS,TIME) of mpvar      ! Amount of products made at factory
  sell: array(PRODS,TIME) of mpvar      ! Amount of product sold from factory
  buy: array(RAW,TIME) of mpvar         ! Amount of raw material bought
  pstock: array(PRODS,1..NT+1) of mpvar ! Product stock levels at start
                                        ! of period t
  rstock: array(RAW,1..NT+1) of mpvar   ! Raw material stock levels
                                        ! at start of period t

  sol_make: array(PRODS,TIME) of real   ! Amount of products made
  sol_sell: array(PRODS,TIME) of real   ! Amount of product sold
  sol_buy: array(RAW,TIME) of real      ! Amount of raw mat. bought
  sol_pstock: array(PRODS,1..NT+1) of real ! Product stock levels
  sol_rstock: array(RAW,1..NT+1) of real   ! Raw mat. stock levels
   
  Profit: linctr                        ! Profit of proposal
  Price_sell: array(PRODS,TIME) of real ! Dual price on sales limits
 end-declarations

 initializations from RMT+DATAFILE
  REV CMAKE CBUY REQ MXSELL MXMAKE
  IPSTOCK IRSTOCK MXRSTOCK CPSTOCK CRSTOCK
 end-initializations
 
! Product stock balance
 forall(p in PRODS,t in TIME)
  PBal(p,t):= pstock(p,t+1) = pstock(p,t) + make(p,t) - sell(p,t)

! Raw material stock balance
 forall(r in RAW,t in TIME) 
  RBal(r,t):= rstock(r,t+1) = 
   rstock(r,t) + buy(r,t) - sum(p in PRODS) REQ(p,r)*make(p,t)

! Capacity limit at factories
 forall(t in TIME) 
  MxMake(t):= sum(p in PRODS) make(p,t) <= MXMAKE(Factory)

! Limit on the amount of prod. p to be sold
 forall(p in PRODS,t in TIME) sell(p,t) <= MXSELL(p,t)
 
! Raw material stock limit
 forall(t in 2..NT+1) 
  MxRStock(t):= sum(r in RAW) rstock(r,t) <= MXRSTOCK

! Initial product and raw material stock levels
 forall(p in PRODS) pstock(p,1) = IPSTOCK(p,Factory)
 forall(r in RAW) rstock(r,1) = IRSTOCK(r,Factory)
 
! Total profit
 Profit:= 
  sum(p in PRODS,t in TIME) REV(p,t) * sell(p,t) -           ! revenue
  sum(p in PRODS,t in TIME) CMAKE(p,Factory) * make(p,t) -   ! prod. cost
  sum(r in RAW,t in TIME) CBUY(r,t) * buy(r,t) -             ! raw mat.
  sum(p in PRODS,t in 2..NT+1) CPSTOCK * pstock(p,t) -       ! p storage
  sum(r in RAW,t in 2..NT+1) CRSTOCK * rstock(r,t)           ! r storage

! (Re)solve this model until it is stopped by event "PHASE_3"
 repeat
  wait
  ev:= getnextevent
  Phase:= getclass(ev)
  if Phase=PHASE_3 then               ! Stop the execution of this model
   break
  end-if
  Price_convex:= getvalue(ev)         ! Get new pricing data

  if Phase<>PHASE_0 then
   initializations from "bin:" + RMT+ "Price_sell.dat"
    Price_sell
   end-initializations
  end-if
  
 ! (Re)solve this model
  if Phase=PHASE_0 then
   maximize(Profit)
  elif Phase=PHASE_1 then
   maximize(sum(p in PRODS,t in TIME) Price_sell(p,t)*sell(p,t) + Price_convex)
  else        ! PHASE 2
   maximize(
    Profit - sum(p in PRODS,t in TIME) Price_sell(p,t)*sell(p,t) - 
     Price_convex)
  end-if

  writeln("Factory ", Factory, " - Obj: ", getobjval, 
          " Profit: ", getsol(Profit), " Price_sell: ",
          getsol(sum(p in PRODS,t in TIME) Price_sell(p,t)*sell(p,t) ), 
          " Price_convex: ", Price_convex)
  fflush
  
  if getobjval > TOL then             ! Solution found: send values to master
   process_solution
  elif getobjval <= TOL then          ! Problem is infeasible (Phase 0/1) or
   send(EVENT_FAILED,0)               ! no improved solution found (Phase 2)
  else
   send(EVENT_READY,0)
  end-if   
 until false

!-----------------------------------------------------------
! Process solution data
 procedure process_solution
  forall(p in PRODS,t in TIME) do
   sol_make(p,t):= getsol(make(p,t))
   sol_sell(p,t):= getsol(sell(p,t))  
  end-do   
  forall(r in RAW,t in TIME) sol_buy(r,t):= getsol(buy(r,t))
  forall(p in PRODS,t in 1..NT+1) sol_pstock(p,t):= getsol(pstock(p,t))
  forall(r in RAW,t in 1..NT+1) sol_rstock(r,t):= getsol(rstock(r,t))
  Prop_cost:= getsol(Profit)

  initializations to "bin:" + RMT + "sol_"+Factory+".dat"
   sol_make sol_sell sol_buy sol_pstock sol_rstock
   Prop_cost
  end-initializations

  send(EVENT_SOLVED,0)

 end-procedure 
end-model

Back to examples browserPrevious exampleNext example