Searching...
No Matches
cutstock_class.py
Go to the documentation of this file.
7
8from gams import GamsWorkspace, SolveLink
9
10GAMS_MODEL = """
11\$title Cutting Stock - A Column Generation Approach (CUTSTOCK,SEQ=294)
12
13\$onText
14The task is to cut out some paper products of different sizes from a
15large raw paper roll, in order to meet a customer's order. The objective
16is to minimize the required number of paper rolls.
17
18
19P. C. Gilmore and R. E. Gomory, A linear programming approach to the
20cutting stock problem, Part I, Operations Research 9 (1961), 849-859.
21
22P. C. Gilmore and R. E. Gomory, A linear programming approach to the
23cutting stock problem, Part II, Operations Research 11 (1963), 863-888.
24
25Keywords: mixed integer linear programming, cutting stock, column generation,
26 paper industry
27\$offText
28
29Set i 'widths';
30
31Parameter
32 r 'raw width'
33 w(i) 'width'
34 d(i) 'demand';
35
36\$if not set gdxincname \$abort 'no include file name for data file provided'
37\$gdxIn %gdxincname%
38\$load r i w d
39\$gdxIn
40
41* Gilmore-Gomory column generation algorithm
42
43Set
44 p 'possible patterns' / p1*p1000 /
45 pp(p) 'dynamic subset of p';
46
47Parameter aip(i,p) 'number of width i in pattern growing in p';
48
49* Master model
50Variable
51 xp(p) 'patterns used'
52 z 'objective variable';
53
54Integer Variable xp;
55xp.up(p) = sum(i, d(i));
56
57Equation
58 numpat 'number of patterns used'
59 demand(i) 'meet demand';
60
61numpat.. z =e= sum(pp, xp(pp));
62
63demand(i).. sum(pp, aip(i,pp)*xp(pp)) =g= d(i);
64
65Model master / numpat, demand /;
66
67* Pricing problem - Knapsack model
68Variable y(i) 'new pattern';
69
70Integer Variable y;
71y.up(i) = ceil(r/w(i));
72
73Equation
74 defobj
75 knapsack 'knapsack constraint';
76
77defobj.. z =e= 1 - sum(i, demand.m(i)*y(i));
78
79knapsack.. sum(i, w(i)*y(i)) =l= r;
80
81Model pricing / defobj, knapsack /;
82
83* Initialization - the initial patterns have a single width
84pp(p) = ord(p) <= card(i);
85aip(i,pp(p))\$(ord(i) = ord(p)) = floor(r/w(i));
86*display aip;
87
88Set pi(p) 'set of the last pattern';
89pi(p) = ord(p) = card(pp) + 1;
90
91option optCr = 0, limRow = 0, limCol = 0, solPrint = off;
92
93while(card(pp) < card(p),
94 solve master using rmip minimizing z;
95 solve pricing using mip minimizing z;
96
97 break\$(z.l >= -0.001);
98
99* pattern that might improve the master model found
100 aip(i,pi) = round(y.l(i));
101 pp(pi) = yes;
102 pi(p) = pi(p-1);
103);
104display 'lower bound for number of rolls', master.objVal;
105
106option solPrint = on;
107
108solve master using mip minimizing z;
109
110Parameter
111 patrep 'solution pattern report'
112 demrep 'solution demand supply report';
113
114patrep('# produced',p) = round(xp.l(p));
115patrep(i,p)\$patrep('# produced',p) = aip(i,p);
116patrep(i,'total') = sum(p, patrep(i,p));
117patrep('# produced','total') = sum(p, patrep('# produced',p));
118
119demrep(i,'produced') = sum(p, patrep(i,p)*patrep('# produced',p));
120demrep(i,'demand') = d(i);
121demrep(i,'over') = demrep(i,'produced') - demrep(i,'demand');
122
123display patrep, demrep;
124
125\$if not set dbOut1 \$abort 'no file name for out-database 1 file provided'
127"""
128
129
130class Cutstock():
131 def __init__(self, system_directory):
132 self._ws = GamsWorkspace(system_directory=system_directory)
133 self.opt = self._ws.add_options()
134 self._cutstock_data = self._ws.add_database(in_model_name="gdxincname")
135
137 self.opt.defines["dbOut1"] = "dbOut1"
138
139 self.widths = self._cutstock_data.add_set("i", 1, "widths")
140 self.raw_width = self._cutstock_data.add_parameter("r", 0, "raw width")
141 self.demand = self._cutstock_data.add_parameter_dc("d", [self.widths], "demand")
142 self.width = self._cutstock_data.add_parameter_dc("w", [self.widths], "width")
143
144 self._job = self._ws.add_job_from_string(GAMS_MODEL)
145
146 self._dbout = None
147 self.pat_rep = None
148
149 def run(self, output=None):
150 self._job.run(self.opt, output=output, databases=self._cutstock_data)
151 self._dbout = self._ws.add_database_from_gdx(
152 self.opt.defines["dbOut1"] + ".gdx"
153 )
154 self.pat_rep = self._dbout.get_parameter("patrep")
def run(self, output=None)
def __init__(self, system_directory)
GAMS Development Corp.
GAMS Software GmbH

General Information and Sales
U.S. (+1) 202 342-0180
Europe: (+49) 221 949-9170
GAMS is a registered trademark of GAMS Software GmbH in the European Union