| |||||||||||||||||||||||||||
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 cocoMs.mos (!******************************************************* Mosel Example Problems ====================== file cocoMs.mos ``````````````` Coco Problem, main model. -- Standard version -- *** ATTENTION: This model will return an error if *** *** no more than one Xpress licence is available. *** (c) 2008 Fair Isaac Corporation author: S. Heipcke, 2005, 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 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 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) end-declarations initializations from DATAFILE CMAKE REV CBUY MXSELL CPSTOCK CRSTOCK end-initializations initializations to "bin:shmem:pricedata" ! Initial price data for submodels Price_sell end-initializations !**** Main problem **** declarations excessS: mpvar ! Violation of sales/buying limits weight: dynamic array(FACT,range) of mpvar ! Weights for propasals 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","cocoSubFs.mos") ! Compile the submodel file forall(f in FACT) do ! Load & run one submodel per product Price_convex(f):= 1 load(submod(f), "cocoSubFs.bim") submod(f).uid:= f setworkdir(submod(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 process_sub_result ! Add new proposal to main problem elif getclass(ev)=EVENT_FAILED then finished:= true else writeln("*** Unexpected event '", ev, "' received from of submodel ***") fflush exit(1) 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 process_sub_result ! Add new proposal to main problem elif getclass(ev)=EVENT_FAILED then noimprove += 1 else writeln("*** Unexpected event '", ev, "' received from of submodel ***") fflush exit(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 process_sub_result ! 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 else writeln("*** Unexpected event '", ev, "' received from of submodel ***") fflush exit(1) 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 fdelete("mempipe:sol") fdelete("cocoSubFs.bim") fdelete("shmem:pricedata") !----------------------------------------------------------- ! Process the proposal generated by a subproblem procedure process_sub_result declarations f: integer ! Factory index ! 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 from memory initializations from "bin:mempipe:sol" f as "Factory" 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:shmem:pricedata" 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 2024 Fair Isaac Corporation. |