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