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 ws = GamsWorkspace(system_directory=sys_dir)
87
88 opt = ws.add_options()
89 cutstock_data = ws.add_database("csdata")
90 opt.all_model_types = "Cplex"
91 opt.optcr = 0.0 # solve to optimality
92 max_pattern = 35
93
94 opt.defines["pmax"] = str(max_pattern)
95 opt.defines["solveMasterAs"] = "RMIP"
96
97 r = 100 # raw width
98 raw_width = cutstock_data.add_parameter("r", 0, "raw width")
99 raw_width.add_record().value = 100
100
101 d = {"i1": 97, "i2": 610, "i3": 395, "i4": 211}
102 demand = cutstock_data.add_parameter("d", 1, "demand")
103 widths = cutstock_data.add_set("i", 1, "widths")
104 for k, v in d.items():
105 widths.add_record(k)
106 demand.add_record(k).value = v
107
108 w = {"i1": 47, "i2": 36, "i3": 31, "i4": 14}
109 width = cutstock_data.add_parameter("w", 1, "width")
110 for k, v in w.items():
111 width.add_record(k).value = v
112
113 cp_master = ws.add_checkpoint()
114 job_master_init = ws.add_job_from_string(GAMS_MASTER_MODEL)
115 job_master_init.run(opt, cp_master, databases=cutstock_data)
116 job_master = ws.add_job_from_string(
117 "execute_load 'csdata', aip, pp; solve master min z using %solveMasterAs%;",
118 cp_master,
119 )
120
121 pattern = cutstock_data.add_set("pp", 1, "pattern index")
122 pattern_data = cutstock_data.add_parameter("aip", 2, "pattern data")
123
124 # initial pattern: pattern i hold width i
125 pattern_count = 0
126 for k, v in w.items():
127 pattern_count += 1
128 pattern_data.add_record(
129 (k, pattern.add_record(str(pattern_count)).key(0))
130 ).value = (int)(r / v)
131
132 cp_sub = ws.add_checkpoint()
133 job_sub = ws.add_job_from_string(GAMS_SUB_MODEL)
134 job_sub.run(opt, cp_sub, databases=cutstock_data)
135 mi_sub = cp_sub.add_modelinstance()
136
137 # define modifier demdual
138 demand_dual = mi_sub.sync_db.add_parameter(
139 "demdual", 1, "dual of demand from master"
140 )
141 mi_sub.instantiate("pricing min z using mip", GamsModifier(demand_dual), opt)
142
143 # find new pattern
144 while True:
145 job_master.run(opt, cp_master, databases=cutstock_data)
146 # copy duals into mi_sub.sync_db DB
147 demand_dual.clear()
148 for dem in job_master.out_db["demand"]:
149 demand_dual.add_record(dem.key(0)).value = dem.marginal
150 mi_sub.solve()
151 if mi_sub.sync_db["z"].first_record().level < -0.00001:
152 if pattern_count == max_pattern:
153 print(
154 f"Out of pattern. Increase max_pattern (currently {max_pattern})."
155 )
156 break
157 else:
158 print(f"New pattern! Value: {mi_sub.sync_db['z'].first_record().level}")
159 pattern_count += 1
160 s = pattern.add_record(str(pattern_count))
161 for y in mi_sub.sync_db["y"]:
162 if y.level > 0.5:
163 pattern_data.add_record((y.key(0), s.key(0))).value = round(
164 y.level
165 )
166 else:
167 break
168
169 # solve final MIP
170 opt.defines["solveMasterAs"] = "MIP"
171 job_master.run(opt, databases=cutstock_data)
172 print(f"Optimal Solution: {job_master.out_db['z'].first_record().level}")
173 for xp in job_master.out_db["xp"]:
174 if xp.level > 0.5:
175 print(f" pattern {xp.key(0)} {xp.level} times:")
176 aip = job_master.out_db["aip"].first_record((" ", xp.key(0)))
177 while True:
178 print(f" {aip.key(0)}: {aip.value}")
179 if not aip.move_next():
180 break
cutstock.w
dict w
Definition: cutstock.py:108
cutstock.demand
GamsWorkspace demand
Definition: cutstock.py:102
cutstock.aip
GamsWorkspace aip
Definition: cutstock.py:176
cutstock.d
dict d
Definition: cutstock.py:101