16 $Title Cutting Stock - Master problem
27 $if not set pmax $set pmax 1000
28 Set p possible patterns /1*%pmax%/
29 pp(p) dynamic subset of p
31 aip(i,p) number of width i in pattern growing in p;
34 Variable xp(p) patterns used
36 Integer variable xp; xp.up(p) = sum(i, d(i));
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);
41 model master /numpat, demand/;'''
45 $Title Cutting Stock - Pricing problem is a knapsack model
57 demdual(i) duals of master demand constraint /#i eps/;
59 Variable z, y(i) new pattern;
60 Integer variable y; y.up(i) = ceil(r/w(i));
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/;'''
68 if __name__ ==
"__main__":
70 ws = GamsWorkspace(system_directory = sys.argv[1])
74 opt = ws.add_options()
75 cutstock_data = ws.add_database(
"csdata")
76 opt.all_model_types =
"Cplex"
80 opt.defines[
"pmax"] = str(maxpattern)
81 opt.defines[
"solveMasterAs"] =
"RMIP"
83 d = {
"i1": 97,
"i2": 610,
"i3":395,
"i4": 211}
84 w = {
"i1": 47,
"i2": 36,
"i3": 31,
"i4": 14}
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")
92 raw_width.add_record().value = 100
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
100 master_cp = ws.add_checkpoint()
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)
105 pattern = cutstock_data.add_set(
"pp", 1,
"pattern index")
106 pattern_data = cutstock_data.add_parameter(
"aip", 2,
"pattern data")
110 for k, v
in iter(w.items()):
112 pattern_data.add_record((k, pattern.add_record(str(pattern_count)).
key(0))).value = (int)(r / v)
114 sub_cp = ws.add_checkpoint()
116 sub_job.run(opt, sub_cp, databases=cutstock_data)
117 sub_mi = sub_cp.add_modelinstance()
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)
127 master_job.run(opt, master_cp, databases=cutstock_data)
130 for dem
in master_job.out_db[
"demand"]:
131 demand_dual.add_record(dem.key(0)).value = dem.marginal
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
138 print(
"New pattern! Value: " + str(sub_mi.sync_db[
"z"][()].level))
140 s = pattern.add_record(str(pattern_count))
141 for y
in sub_mi.sync_db[
"y"]:
143 pattern_data.add_record((y.key(0), s.key(0))).value = round(y.level)
146 pattern_added =
False
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"]:
154 print(
" pattern " + xp.key(0) +
" " + str(xp.level) +
" times: ", end=
"")
155 aip = master_job.out_db[
"aip"].first_record((
" ", xp.key(0)))
157 print (aip.key(0) +
": " + str(aip.value), end=
" ")
158 if not aip.move_next():