cutstock.py
Go to the documentation of this file.
10 
11 from gams import *
12 import sys
13 
15  return '''
16 $Title Cutting Stock - Master problem
17 
18 Set i widths
19 Parameter
20  w(i) width
21  d(i) demand
22 Scalar
23  r raw width;
24 $gdxin csdata
25 $load i w d r
26 
27 $if not set pmax $set pmax 1000
28 Set p possible patterns /1*%pmax%/
29  pp(p) dynamic subset of p
30 Parameter
31  aip(i,p) number of width i in pattern growing in p;
32 
33 * Master model
34 Variable xp(p) patterns used
35  z objective variable
36 Integer variable xp; xp.up(p) = sum(i, d(i));
37 
38 Equation numpat; numpat.. z =e= sum(pp, xp(pp));
39 Equation demand(i); demand(i).. sum(pp, aip(i,pp)*xp(pp)) =g= d(i);
40 
41 model master /numpat, demand/;'''
42 
44  return '''
45 $Title Cutting Stock - Pricing problem is a knapsack model
46 
47 Set i widths
48 Parameter
49  w(i) width;
50 Scalar
51  r raw width;
52 
53 $gdxin csdata
54 $load i w r
55 
56 Parameter
57  demdual(i) duals of master demand constraint /#i eps/;
58 
59 Variable z, y(i) new pattern;
60 Integer variable y; y.up(i) = ceil(r/w(i));
61 
62 Equation defobj; defobj.. z =e= 1 - sum(i, demdual(i)*y(i));
63 Equation knapsack; knapsack.. sum(i, w(i)*y(i)) =l= r;
64 model pricing /defobj, knapsack/;'''
65 
66 
67 
68 if __name__ == "__main__":
69  if len(sys.argv) > 1:
70  ws = GamsWorkspace(system_directory = sys.argv[1])
71  else:
72  ws = GamsWorkspace()
73 
74  opt = ws.add_options()
75  cutstock_data = ws.add_database("csdata")
76  opt.all_model_types = "Cplex"
77  opt.optcr = 0.0 # Solve to optimality
78  maxpattern = 35
79 
80  opt.defines["pmax"] = str(maxpattern)
81  opt.defines["solveMasterAs"] = "RMIP"
82 
83  d = {"i1": 97, "i2": 610, "i3":395, "i4": 211}
84  w = {"i1": 47, "i2": 36, "i3": 31, "i4": 14}
85  r = 100 # raw width
86 
87  widths = cutstock_data.add_set("i", 1, "widths")
88  raw_width = cutstock_data.add_parameter("r", 0, "raw width")
89  demand = cutstock_data.add_parameter("d", 1, "demand")
90  width = cutstock_data.add_parameter("w", 1, "width")
91 
92  raw_width.add_record().value = 100
93  for i in d:
94  widths.add_record(i)
95  for k,v in iter(d.items()):
96  demand.add_record(k).value = v
97  for k,v in iter(w.items()):
98  width.add_record(k).value = v
99 
100  master_cp = ws.add_checkpoint()
101  master_init_job = ws.add_job_from_string(get_master_model())
102  master_init_job.run(opt, master_cp, databases=cutstock_data)
103  master_job = ws.add_job_from_string("execute_load 'csdata', aip, pp; solve master min z using %solveMasterAs%;", master_cp)
104 
105  pattern = cutstock_data.add_set("pp", 1, "pattern index")
106  pattern_data = cutstock_data.add_parameter("aip", 2, "pattern data")
107 
108  # Initial pattern: pattern i hold width i
109  pattern_count = 0
110  for k, v in iter(w.items()):
111  pattern_count += 1
112  pattern_data.add_record((k, pattern.add_record(str(pattern_count)).key(0))).value = (int)(r / v)
113 
114  sub_cp = ws.add_checkpoint()
115  sub_job = ws.add_job_from_string(get_sub_model())
116  sub_job.run(opt, sub_cp, databases=cutstock_data)
117  sub_mi = sub_cp.add_modelinstance()
118 
119  # define modifier demdual
120  demand_dual = sub_mi.sync_db.add_parameter("demdual", 1, "dual of demand from master")
121  sub_mi.instantiate("pricing min z using mip", GamsModifier(demand_dual), opt)
122 
123  # find new pattern
124  pattern_added = True
125 
126  while pattern_added:
127  master_job.run(opt, master_cp, databases=cutstock_data)
128  # Copy duals into sub_mi.sync_db DB
129  demand_dual.clear()
130  for dem in master_job.out_db["demand"]:
131  demand_dual.add_record(dem.key(0)).value = dem.marginal
132  sub_mi.solve()
133  if sub_mi.sync_db["z"][()].level < -0.00001:
134  if pattern_count == maxpattern:
135  print("Out of pattern. Increase maxpattern (currently " + str(maxpattern) + ").")
136  pattern_added = False
137  else:
138  print("New pattern! Value: " + str(sub_mi.sync_db["z"][()].level))
139  pattern_count += 1
140  s = pattern.add_record(str(pattern_count))
141  for y in sub_mi.sync_db["y"]:
142  if y.level > 0.5:
143  pattern_data.add_record((y.key(0), s.key(0))).value = round(y.level)
144 
145  else:
146  pattern_added = False
147 
148  # solve final MIP
149  opt.defines["solveMasterAs"] = "MIP"
150  master_job.run(opt, databases=cutstock_data)
151  print("Optimal Solution: " + str(master_job.out_db["z"][()].level))
152  for xp in master_job.out_db["xp"]:
153  if xp.level > 0.5:
154  print(" pattern " + xp.key(0) + " " + str(xp.level) + " times: ", end="")
155  aip = master_job.out_db["aip"].first_record((" ", xp.key(0)))
156  while True:
157  print (aip.key(0) + ": " + str(aip.value), end=" ")
158  if not aip.move_next():
159  break
160  print("")
161 
162  # clean up of unmanaged resources
163  del cutstock_data
164  del sub_mi
165  del opt
166 
def get_sub_model()
Definition: cutstock.py:43
def get_master_model()
Definition: cutstock.py:14