| |||||||||||||||||||||||||||
| |||||||||||||||||||||||||||
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:
Further explanation of this example: Xpress Whitepaper 'Multiple models and parallel solving with Mosel', Section 'Dantzig-Wolfe decomposition: sequential and parallel solving'.
Source Files By clicking on a file name, a preview is opened at the bottom of this page.
Data Files cocoMd.mos
(!*******************************************************
Mosel Example Problems
======================
file cocoMd.mos
```````````````
Coco Problem, main model.
-- Distributed computing version --
-- File-based data exchange --
Before running this model, you need to set up the list
NODES with machine names/addresses of your local network.
All nodes that are used need to have the same version of
Xpress installed and suitably licensed, and the server
"xprmsrv" must have been started on these machines.
All files are local to the root node, no write access is
required at remote nodes.
(c) 2010 Fair Isaac Corporation
author: S. Heipcke, May 2010, rev. Jun. 2023
*******************************************************!)
model "Coco3 Main"
uses "mmxprs","mmjobs","mmsystem"
parameters
DATAFILE = "coco2.dat"
ALG = 1 ! 0: stop phase with 1st failed subpb.
! 1: stop when all subprob.s fail
end-parameters
forward procedure process_sub_result(num: integer)
forward procedure solve_main(phase: integer)
forward procedure process_main_result
forward function true_solution:real
forward function calc_solution:real
forward procedure print_solution
declarations
NODES: list of string ! Set of available nodes
end-declarations
NODES:= [""]
!!! This list must have at least 1 element.
!!! Use machine names within your local network, IP addresses, or
!!! empty string for the current node running this model.
! Optionally, associate other connections than default with node names:
! sethostalias("localnode","rcmd:mosel -r")
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
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)
PERIODS = 1..NT ! time periods (t)
REV: array(PRODS,PERIODS) 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,PERIODS) of real ! Unit cost to buy raw materials
MXSELL: array(PRODS,PERIODS) of real ! Max. amount of p that can be sold
CPSTOCK: real ! Unit cost to store any product p
CRSTOCK: real ! Unit cost to store any raw mat. r
submod: array(FACT) of Model ! One subproblem per factory
nIter: integer ! Iteration counter
nPROP: array(FACT) of integer ! Counters of proposals from subprob.s
Prop_make: array(PRODS,FACT,PERIODS,range) of real ! Amount of products made
Prop_sell: array(PRODS,FACT,PERIODS,range) of real ! Amount of product sold
Prop_buy: array(RAW,FACT,PERIODS,range) of real ! Amount of raw mat. bought
Prop_pstock: array(PRODS,FACT,1..NT+1,range) of real ! Product stock levels
Prop_rstock: array(RAW,FACT,1..NT+1,range) of real ! Raw mat. stock levels
Prop_cost: array(FACT,range) of real ! Cost/profit of each proposal
Price_convex: array(FACT) of real ! Dual price on convexity constraints
Price_sell: array(PRODS,PERIODS) of real ! Dual price on sales limits
Sol_make: array(PRODS,FACT,PERIODS) of real ! Solution value (products made)
Sol_sell: array(PRODS,FACT,PERIODS) of real ! Solution value (product sold)
Sol_buy: array(RAW,FACT,PERIODS) of real ! Solution value (raw mat. bought)
Sol_pstock: array(PRODS,FACT,1..NT+1) of real ! Sol. value (prod. stock)
Sol_rstock: array(RAW,FACT,1..NT+1) of real ! Sol. value (raw mat. stock)
moselInst: dynamic array(set of string) of Mosel ! Mosel instances on remote nodes
nct: integer
end-declarations
initializations from DATAFILE
CMAKE REV CBUY MXSELL CPSTOCK CRSTOCK
end-initializations
initializations to "bin:Price_sell.dat" ! Initial price data for submodels
Price_sell
end-initializations
!**** Setting up remote Mosel instances ****
forall(n in NODES, nct as counter) do
create(moselInst(n))
if connect(moselInst(n), n)<>0 then exit(1); end-if
if nct>= NFACT then break; end-if ! Stop when started enough
end-do
!**** Main problem ****
declarations
excessS: mpvar ! Violation of sales/buying limits
weight: dynamic array(FACT,range) of mpvar ! Weights for proposals
MxSell: array(PRODS,PERIODS) of linctr ! Sales limit constraints
Convex: array(FACT) of linctr ! Convexity constraints
end-declarations
!**** Submodels ****
declarations
Stopped: set of integer
end-declarations
res:= compile("g","cocoSubFd.mos") ! Compile the submodel file locally
ct:=0
forall(f in FACT) do ! Load & run one submodel per product
Price_convex(f):= 1
ct:= if(ct<NODES.size, ct+1, 1) ! Get next node in list or restart
n:= getlast(gethead(NODES,ct)) ! from beginning when end is reached
load(moselInst(n), submod(f), "rmt:cocoSubFd.bim")
! Load model on remote node
submod(f).uid:= f
run(submod(f), "Factory=" + f + ",DATAFILE=" + DATAFILE)
wait ! Wait for child model to be ready
ev:=getnextevent
if ev.class=EVENT_END then
writeln("*** Cannot start all necessary models - aborting ***")
exit(1)
end-if
end-do
!**** Phase 0: Crash ****
nIter:=1; finished:=false
writeln("\nPHASE 0 -- Iteration ", nIter); fflush
forall(f in FACT) ! Start solving all submodels (Phase 1)
send(submod(f), PHASE_0, 0)
forall(f in FACT) do
wait ! Wait for child (termination) events
ev:= getnextevent
if getclass(ev)=EVENT_SOLVED then
m:=ev.fromuid
process_sub_result(m) ! Add new proposal to main problem
elif getclass(ev)=EVENT_FAILED then
finished:= true
end-if
end-do
if finished then
writeln("Problem is infeasible")
exit(1)
end-if
solve_main(1) ! Solve the updated Ph. 1 main problem
process_main_result ! Store initial pricing data for submodels
!**** Phase 1: proposal generation (feasibility) ****
repeat
noimprove:= 0
nIter+=1
writeln("\nPHASE 1 -- Iteration ", nIter); fflush
forall(f in FACT) ! Start solving all submodels (Phase 1)
send(submod(f), PHASE_1, Price_convex(f))
forall(f in FACT) do
wait ! Wait for child (termination) events
ev:= getnextevent
if getclass(ev)=EVENT_SOLVED then
m:=ev.fromuid
process_sub_result(m) ! Add new proposal to main problem
elif getclass(ev)=EVENT_FAILED then
noimprove += 1
end-if
end-do
if noimprove = NFACT then
writeln("Problem is infeasible")
exit(2)
end-if
if ALG=0 and noimprove > 0 then
writeln("No improvement by some subproblem(s)")
break
end-if
solve_main(1) ! Solve the updated Ph. 1 main problem
if getobjval>0.00001 then
process_main_result ! Store new pricing data for submodels
end-if
until getobjval <= 0.00001
!**** Phase 2: proposal generation (optimization) ****
writeln("\n**** PHASE 2 ****")
finished:=false
repeat
solve_main(2) ! Solve Phase 2 main problem
process_main_result ! Store new pricing data for submodels
nIter+=1
writeln("\nPHASE 2 -- Iteration ", nIter); fflush
forall(f in FACT) ! Start solving all submodels (Phase 2)
send(submod(f), PHASE_2, Price_convex(f))
forall(f in FACT) do
wait ! Wait for child (termination) events
ev:= getnextevent
if getclass(ev)=EVENT_SOLVED then
m:= ev.fromuid
process_sub_result(m) ! Add new proposal to main problem
elif getclass(ev)=EVENT_FAILED then
if ALG=0 then
finished:=true ! 1st submodel w/o prop. stops phase 2
else
Stopped += {ev.fromuid} ! Stop phase 2 only when no submodel
! generates a new proposal
end-if
end-if
end-do
if getsize(Stopped) = NFACT then finished:= true; end-if
until finished
!**** Phase 3: solution to the original problem ****
writeln("\n**** PHASE 3 ****")
forall(f in FACT) do
send(submod(f), PHASE_3, 0) ! Stop all submodels
wait
dropnextevent
end-do
! writeln("Total Profit=", calc_solution)
writeln("Total Profit=", true_solution)
print_solution
!**** Cleaning up temporary files
forall(f in FACT) fdelete("sol_"+f+".dat")
fdelete("cocoSubFd.bim")
fdelete("Price_sell.dat")
!-----------------------------------------------------------
! Process the proposal generated by a subproblem
procedure process_sub_result(f: integer)
declarations ! Solution values of the proposal:
sol_make: array(PRODS,PERIODS) of real ! Amount of products made
sol_sell: array(PRODS,PERIODS) of real ! Amount of product sold
sol_buy: array(RAW,PERIODS) 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
pc: real ! Cost of the proposal
end-declarations
! Read proposal data
initializations from "bin:sol_"+f+".dat"
sol_make sol_sell sol_buy sol_pstock sol_rstock
pc as "Prop_cost"
end-initializations
! Add the new proposal to the main problem
nPROP(f)+=1
create(weight(f,nPROP(f)))
forall(p in PRODS,t in PERIODS) do
Prop_make(p,f,t,nPROP(f)):= sol_make(p,t)
Prop_sell(p,f,t,nPROP(f)):= sol_sell(p,t)
end-do
forall(r in RAW,t in PERIODS) Prop_buy(r,f,t,nPROP(f)):= sol_buy(r,t)
forall(p in PRODS,t in 1..NT+1) Prop_pstock(p,f,t,nPROP(f)):= sol_pstock(p,t)
forall(r in RAW,t in 1..NT+1) Prop_rstock(r,f,t,nPROP(f)):= sol_rstock(r,t)
Prop_cost(f,nPROP(f)):= pc
writeln("Sol. for factory ", f, ":\n make: ", sol_make, "\n sell: ",
sol_sell, "\n buy: ", sol_buy, "\n pstock: ", sol_pstock,
"\n rstock: ", sol_rstock)
end-procedure
!-----------------------------------------------------------
! (Re)solve the main problem
procedure solve_main(phase: integer)
forall(f in FACT)
Convex(f):= sum (k in 1..nPROP(f)) weight(f,k) = 1
if phase=1 then
forall(p in PRODS,t in PERIODS)
MxSell(p,t):=
sum(f in FACT,k in 1..nPROP(f)) Prop_sell(p,f,t,k)*weight(f,k) -
excessS <= MXSELL(p,t)
minimize(excessS)
else
forall(p in PRODS,t in PERIODS)
MxSell(p,t):=
sum(f in FACT,k in 1..nPROP(f)) Prop_sell(p,f,t,k)*weight(f,k) <=
MXSELL(p,t)
maximize(sum(f in FACT, k in 1..nPROP(f)) Prop_cost(f,k) * weight(f,k))
end-if
writeln("Main problem objective: ", getobjval)
write(" Weights:")
forall(f in FACT,k in 1..nPROP(f)) write(" ", getsol(weight(f,k)))
writeln
end-procedure
!-----------------------------------------------------------
! Update pricing data for subproblems
procedure process_main_result
forall(p in PRODS,t in PERIODS) Price_sell(p,t):=getdual(MxSell(p,t))
forall(f in FACT) Price_convex(f):=getdual(Convex(f))
initializations to "bin:Price_sell.dat"
Price_sell
end-initializations
end-procedure
!-----------------------------------------------------------
! Calculate solution to the original problem
function true_solution: real
forall(p in PRODS,f in FACT,t in PERIODS) do
Sol_sell(p,f,t):=
sum(k in 1..nPROP(f)) Prop_sell(p,f,t,k) * getsol(weight(f,k))
Sol_make(p,f,t):=
sum(k in 1..nPROP(f)) Prop_make(p,f,t,k) * getsol(weight(f,k))
end-do
forall(r in RAW,f in FACT,t in PERIODS) Sol_buy(r,f,t):=
sum(k in 1..nPROP(f)) Prop_buy(r,f,t,k) * getsol(weight(f,k))
forall(p in PRODS,f in FACT,t in 1..NT+1) Sol_pstock(p,f,t):=
sum(k in 1..nPROP(f)) Prop_pstock(p,f,t,k) * getsol(weight(f,k))
forall(r in RAW,f in FACT,t in 1..NT+1) Sol_rstock(r,f,t):=
sum(k in 1..nPROP(f)) Prop_rstock(r,f,t,k) * getsol(weight(f,k))
returned:=
sum(p in PRODS,f in FACT,t in PERIODS) REV(p,t) * Sol_sell(p,f,t) -
sum(p in PRODS,f in FACT,t in PERIODS) CMAKE(p,f) * Sol_make(p,f,t) -
sum(r in RAW,f in FACT,t in PERIODS) CBUY(r,t) * Sol_buy(r,f,t) -
sum(p in PRODS,f in FACT,t in 2..NT+1) CPSTOCK * Sol_pstock(p,f,t) -
sum(r in RAW,f in FACT,t in 2..NT+1) CRSTOCK * Sol_rstock(r,f,t)
end-function
! Solve the original problem
function calc_solution: real
declarations
make: array(PRODS,FACT,PERIODS) of mpvar ! Amount of products made
sell: array(PRODS,FACT,PERIODS) of mpvar ! Amount of product sold
buy: array(RAW,FACT,PERIODS) 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
forall(p in PRODS,f in FACT,t in PERIODS) do
sell(p,f,t) = sum(k in 1..nPROP(f)) Prop_sell(p,f,t,k) * weight(f,k)
make(p,f,t) = sum(k in 1..nPROP(f)) Prop_make(p,f,t,k) * weight(f,k)
end-do
forall(r in RAW,f in FACT,t in PERIODS)
buy(r,f,t) = sum(k in 1..nPROP(f)) Prop_buy(r,f,t,k) * weight(f,k)
forall(p in PRODS,f in FACT,t in 1..NT+1)
pstock(p,f,t) = sum(k in 1..nPROP(f)) Prop_pstock(p,f,t,k) * weight(f,k)
forall(r in RAW,f in FACT,t in 1..NT+1)
rstock(r,f,t) = sum(k in 1..nPROP(f)) Prop_rstock(r,f,t,k) * weight(f,k)
MaxProfit:=
sum(p in PRODS,f in FACT,t in PERIODS) REV(p,t) * sell(p,f,t) - ! revenue
sum(p in PRODS,f in FACT,t in PERIODS) CMAKE(p,f) * make(p,f,t) - ! prod. cost
sum(r in RAW,f in FACT,t in PERIODS) 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
maximize(MaxProfit)
returned:= getobjval
forall(p in PRODS,f in FACT,t in PERIODS) do
Sol_sell(p,f,t):= getsol(sell(p,f,t))
Sol_make(p,f,t):= getsol(make(p,f,t))
end-do
forall(r in RAW,f in FACT,t in PERIODS) Sol_buy(r,f,t):= getsol(buy(r,f,t))
forall(p in PRODS,f in FACT,t in 1..NT+1)
Sol_pstock(p,f,t):= getsol(pstock(p,f,t))
forall(r in RAW,f in FACT,t in 1..NT+1)
Sol_rstock(r,f,t):= getsol(rstock(r,f,t))
end-function
!-----------------------------------------------------------
procedure print_solution
writeln("Finished products:")
forall(f in FACT) do
writeln("Factory ", f, ":")
forall(p in PRODS) do
write(" ", p, ": ")
forall(t in PERIODS) write(strfmt(Sol_make(p,f,t),6,1), "(",
strfmt(Sol_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 PERIODS) write(strfmt(Sol_buy(r,f,t),6,1), "(",
strfmt(Sol_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 PERIODS) write(strfmt(Sol_sell(p,f,t),4))
writeln
end-do
end-do
writeln("\nComputation time: ", gettime)
end-procedure
end-model
| |||||||||||||||||||||||||||
| © Copyright 2023 Fair Isaac Corporation. |
