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