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





coco3.mos

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

   file coco3.mos
   ``````````````
   Coco Problem, mid-term model.

   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, r2001, ev. Apr. 2005
*******************************************************!)

model "Coco3"
 uses "mmxprs"

 parameters
  DATAFILE = "coco2.dat"
 end-parameters
 
 declarations                         
  NPROD, NFACT, NRAW, NT: integer
 end-declarations                      

 initializations from 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,FACT,TIME) of mpvar ! Amount of products made at factories
  sell: array(PRODS,FACT,TIME) of mpvar ! Amount of product sold from factories
  buy: array(RAW,FACT,TIME) of mpvar    ! Amount of raw material bought
  pstock: array(PRODS,FACT,1..NT+1) of mpvar ! Product stock levels at start
                                             ! of period t
  rstock: array(RAW,FACT,1..NT+1) of mpvar   ! Raw material stock levels
                                             ! at start of period t
 end-declarations

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

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

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

! Limit on the amount of prod. p to be sold
 forall(p in PRODS,t in TIME) sum(f in FACT) sell(p,f,t) <= MXSELL(p,t)

! Raw material stock limit
 forall(f in FACT,t in 2..NT+1) 
  MxRStock(f,t):= sum(r in RAW) rstock(r,f,t) <= MXRSTOCK

! Initial product and raw material stock levels
 forall(p in PRODS,f in FACT) pstock(p,f,1) = IPSTOCK(p,f)
 forall(r in RAW,f in FACT) rstock(r,f,1) = IRSTOCK(r,f)

! Objective: maximize total profit
 Profit:= 
  sum(p in PRODS,f in FACT,t in TIME) REV(p,t) * sell(p,f,t) -     ! revenue
  sum(p in PRODS,f in FACT,t in TIME) CMAKE(p,f) * make(p,f,t) -   ! prod. cost
  sum(r in RAW,f in FACT,t in TIME) CBUY(r,t) * buy(r,f,t) -       ! raw mat.
  sum(p in PRODS,f in FACT,t in 2..NT+1) CPSTOCK * pstock(p,f,t) - ! p storage
  sum(r in RAW,f in FACT,t in 2..NT+1) CRSTOCK * rstock(r,f,t)     ! r storage
   
! Solve the problem
 maximize(Profit)

! Solution printing
 writeln("Total profit: ", getobjval)
 writeln("Finished products:")
 forall(f in FACT) do
  writeln("Factory ", f, ":") 
  forall(p in PRODS) do
   write("  ", p, ": ")
   forall(t in TIME) write(strfmt(getsol(make(p,f,t)),6,1), "(", 
                           strfmt(getsol(pstock(p,f,t+1)),5,1), ")")
   writeln
  end-do 
 end-do 

 writeln("Raw material:")
 forall(f in FACT) do
  writeln("Factory ", f, ":") 
  forall(r in RAW) do
   write("  ", r, ": ")
   forall(t in TIME) write(strfmt(getsol(buy(r,f,t)),6,1), "(", 
                           strfmt(getsol(rstock(r,f,t+1)),5,1), ")")
   writeln
  end-do 
 end-do 

 writeln("Sales:")
 forall(f in FACT) do
  writeln("Factory ", f, ":") 
  forall(p in PRODS) do
   write("  ", p, ": ")
   forall(t in TIME) write(strfmt(getsol(sell(p,f,t)),4))
   writeln
  end-do 
 end-do 

end-model

Back to examples browserPrevious exampleNext example