cutstock_class.py
Go to the documentation of this file.
7 
8 from gams import *
9 
10 class Cutstock():
11 
12  def __init__(self, ws):
13  self._ws = ws
14  self.opt = ws.add_options()
15  self._cutstock_data = ws.add_database(in_model_name = "gdxincname")
16 
17  self.opt.solvelink = SolveLink.LoadLibrary
18  self.opt.defines["dbOut1"] = "dbOut1"
19 
20  self.widths = self._cutstock_data.add_set("i", 1, "widths")
21  self.raw_width = self._cutstock_data.add_parameter("r", 0, "raw width")
22  self.demand = self._cutstock_data.add_parameter_dc("d", [self.widths], "demand")
23  self.width = self._cutstock_data.add_parameter_dc("w", [self.widths], "width")
24 
25  self._job = ws.add_job_from_string(self.get_model_source())
26 
27  def run(self, output = None):
28  self._job.run(self.opt, None, output, databases=self._cutstock_data)
29  self._dbout = self._ws.add_database_from_gdx(self.opt.defines["dbOut1"] + ".gdx")
30  self.pat_rep = self._dbout.get_parameter("patrep")
31 
32  def get_model_source(self):
33  return '''
34 $Title Cutting Stock - A Column Generation Approach (CUTSTOCK,SEQ=294)
35 
36 $ontext
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.
40 
41 
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.
44 
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.
47 $offtext
48 
49 Set i widths
50 Parameter
51  r raw width
52  w(i) width
53  d(i) demand ;
54 
55 $if not set gdxincname $abort 'no include file name for data file provided'
56 $gdxin %gdxincname%
57 $load r i w d
58 $gdxin
59 
60 * Gilmore-Gomory column generation algorithm
61 
62 Set p possible patterns /p1*p1000/
63  pp(p) dynamic subset of p
64 Parameter
65  aip(i,p) number of width i in pattern growing in p;
66 
67 
68 * Master model
69 Variable xp(p) patterns used
70  z objective variable
71 Integer variable xp; xp.up(p) = sum(i, d(i));
72 
73 Equation numpat number of patterns used
74  demand(i) meet demand;
75 
76 numpat.. z =e= sum(pp, xp(pp));
77 demand(i).. sum(pp, aip(i,pp)*xp(pp)) =g= d(i);
78 
79 model master /numpat, demand/;
80 
81 * Pricing problem - Knapsack model
82 Variable y(i) new pattern;
83 Integer variable y; y.up(i) = ceil(r/w(i));
84 
85 Equation defobj
86  knapsack knapsack constraint;
87 
88 defobj.. z =e= 1 - sum(i, demand.m(i)*y(i));
89 knapsack.. sum(i, w(i)*y(i)) =l= r;
90 
91 model pricing /defobj, knapsack/;
92 
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));
96 *display aip;
97 
98 Scalar done loop indicator /0/
99 Set pi(p) set of the last pattern; pi(p) = ord(p)=card(pp)+1;
100 
101 option optcr=0,limrow=0,limcol=0,solprint=off;
102 
103 While(not done and card(pp)<card(p),
104  solve master using rmip minimizing z;
105  solve pricing using mip minimizing z;
106 
107 * pattern that might improve the master model found?
108  if(z.l < -0.001,
109  aip(i,pi) = round(y.l(i));
110  pp(pi) = yes; pi(p) = pi(p-1);
111  else
112  done = 1;
113  );
114 );
115 display 'lower bound for number of rolls', master.objval;
116 
117 option solprint=on;
118 solve master using mip minimizing z;
119 
120 Parameter patrep Solution pattern report
121  demrep Solution demand supply report;
122 
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));
127 
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');
131 
132 display patrep, demrep;
133 
134 $if not set dbOut1 $abort 'no file name for out-database 1 file provided'
135 execute_unload '%dbOut1%', patrep;
136 '''
def run(self, output=None)