Go to the documentation of this file.
8 from gams
import SolveLink
14 self.
opt = ws.add_options()
15 self.
_cutstock_data = ws.add_database(in_model_name =
"gdxincname")
17 self.
opt.solvelink = SolveLink.LoadLibrary
18 self.
opt.defines[
"dbOut1"] =
"dbOut1"
27 def run(self, output = None):
29 self.
_dbout = self.
_ws.add_database_from_gdx(self.
opt.defines[
"dbOut1"] +
".gdx")
34 $Title Cutting Stock - A Column Generation Approach (CUTSTOCK,SEQ=294)
37 The task is to cut out some paper products of different sizes from a
38 large raw paper roll, in order to meet a customer's order. The objective
39 is to minimize the required number of paper rolls.
42 P. C. Gilmore and R. E. Gomory, A linear programming approach to the
43 cutting stock problem, Part I, Operations Research 9 (1961), 849-859.
45 P. C. Gilmore and R. E. Gomory, A linear programming approach to the
46 cutting stock problem, Part II, Operations Research 11 (1963), 863-888.
55 $if not set gdxincname $abort 'no include file name for data file provided'
60 * Gilmore-Gomory column generation algorithm
62 Set p possible patterns /p1*p1000/
63 pp(p) dynamic subset of p
65 aip(i,p) number of width i in pattern growing in p;
69 Variable xp(p) patterns used
71 Integer variable xp; xp.up(p) = sum(i, d(i));
73 Equation numpat number of patterns used
74 demand(i) meet demand;
76 numpat.. z =e= sum(pp, xp(pp));
77 demand(i).. sum(pp, aip(i,pp)*xp(pp)) =g= d(i);
79 model master /numpat, demand/;
81 * Pricing problem - Knapsack model
82 Variable y(i) new pattern;
83 Integer variable y; y.up(i) = ceil(r/w(i));
86 knapsack knapsack constraint;
88 defobj.. z =e= 1 - sum(i, demand.m(i)*y(i));
89 knapsack.. sum(i, w(i)*y(i)) =l= r;
91 model pricing /defobj, knapsack/;
93 * Initialization - the initial patterns have a single width
94 pp(p) = ord(p)<=card(i);
95 aip(i,pp(p))$(ord(i)=ord(p)) = floor(r/w(i));
98 Scalar done loop indicator /0/
99 Set pi(p) set of the last pattern; pi(p) = ord(p)=card(pp)+1;
101 option optcr=0,limrow=0,limcol=0,solprint=off;
103 While(not done and card(pp)<card(p),
104 solve master using rmip minimizing z;
105 solve pricing using mip minimizing z;
107 * pattern that might improve the master model found?
109 aip(i,pi) = round(y.l(i));
110 pp(pi) = yes; pi(p) = pi(p-1);
115 display 'lower bound for number of rolls', master.objval;
118 solve master using mip minimizing z;
120 Parameter patrep Solution pattern report
121 demrep Solution demand supply report;
123 patrep('# produced',p) = round(xp.l(p));
124 patrep(i,p)$patrep('# produced',p) = aip(i,p);
125 patrep(i,'total') = sum(p, patrep(i,p));
126 patrep('# produced','total') = sum(p, patrep('# produced',p));
128 demrep(i,'produced') = sum(p,patrep(i,p)*patrep('# produced',p));
129 demrep(i,'demand') = d(i);
130 demrep(i,'over') = demrep(i,'produced') - demrep(i,'demand');
132 display patrep, demrep;
134 $if not set dbOut1 $abort 'no file name for out-database 1 file provided'
135 execute_unload '%dbOut1%', patrep;
def get_model_source(self)
def run(self, output=None)