8from gams
import GamsWorkspace, SolveLink
11$title Cutting Stock - A Column Generation Approach (CUTSTOCK,SEQ=294)
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.
19P. C. Gilmore and R. E. Gomory, A linear programming approach to the
20cutting stock problem, Part I, Operations Research 9 (1961), 849-859.
22P. C. Gilmore and R. E. Gomory, A linear programming approach to the
23cutting stock problem, Part II, Operations Research 11 (1963), 863-888.
25Keywords: mixed integer linear programming, cutting stock, column generation,
36$
if not set gdxincname $abort
'no include file name for data file provided'
41* Gilmore-Gomory column generation algorithm
44 p
'possible patterns' / p1*p1000 /
45 pp(p)
'dynamic subset of p';
47Parameter aip(i,p)
'number of width i in pattern growing in p';
52 z
'objective variable';
55xp.up(p) = sum(i, d(i));
58 numpat
'number of patterns used'
59 demand(i)
'meet demand';
61numpat.. z =e= sum(pp, xp(pp));
63demand(i).. sum(pp, aip(i,pp)*xp(pp)) =g= d(i);
65Model master / numpat, demand /;
67* Pricing problem - Knapsack model
68Variable y(i)
'new pattern';
71y.up(i) = ceil(r/w(i));
75 knapsack
'knapsack constraint';
77defobj.. z =e= 1 - sum(i, demand.m(i)*y(i));
79knapsack.. sum(i, w(i)*y(i)) =l= r;
81Model pricing / defobj, knapsack /;
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));
88Set pi(p)
'set of the last pattern';
89pi(p) = ord(p) = card(pp) + 1;
91option optCr = 0, limRow = 0, limCol = 0, solPrint = off;
93while(card(pp) < card(p),
94 solve master using rmip minimizing z;
95 solve pricing using mip minimizing z;
97 break$(z.l >= -0.001);
99* pattern that might improve the master model found
100 aip(i,pi) = round(y.l(i));
104display
'lower bound for number of rolls', master.objVal;
108solve master using mip minimizing z;
111 patrep
'solution pattern report'
112 demrep
'solution demand supply report';
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));
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');
123display patrep, demrep;
125$
if not set dbOut1 $abort
'no file name for out-database 1 file provided'
126execute_unload
'%dbOut1%', patrep;
132 self.
_ws = GamsWorkspace(system_directory=system_directory)
136 self.
opt.solvelink = SolveLink.LoadLibrary
137 self.
opt.defines[
"dbOut1"] =
"dbOut1"
144 self.
_job = self.
_ws.add_job_from_string(GAMS_MODEL)
149 def run(self, output=None):
151 self.
_dbout = self.
_ws.add_database_from_gdx(
152 self.
opt.defines[
"dbOut1"] +
".gdx"
def run(self, output=None)
def __init__(self, system_directory)
