cutstock.py¶
Column generation is a solution process that begins with a small, manageable part of a problem (specifically, a few of the variables), solves that part, analyzes the partial solution to determine the next part of the problem (specifically, one or more variables) to add to the model, and then solves the new, enlarged model. Column generation repeats the process until a satisfactory solution to the whole problem is achieved.
1# --------------------------------------------------------------------------
2# Source file provided under Apache License, Version 2.0, January 2004,
3# http://www.apache.org/licenses/
4# (c) Copyright IBM Corp. 2015, 2022
5# --------------------------------------------------------------------------
6
7from collections import namedtuple
8import json
9
10from docplex.util.environment import get_environment
11from docplex.mp.model import Model
12
13
14# ----------------------------------------------------------------------------
15# Initialize the problem data
16# ----------------------------------------------------------------------------
17DEFAULT_ROLL_WIDTH = 110
18DEFAULT_ITEMS = [(1, 20, 48), (2, 45, 35), (3, 50, 24), (4, 55, 10), (5, 75, 8)]
19DEFAULT_PATTERNS = [(i, 1) for i in range(1, 6)] # (1, 1), (2, 1) etc
20DEFAULT_PATTERN_ITEM_FILLED = [(p, p, 1) for p in range(1, 6)] # pattern1 for item1, pattern2 for item2, etc.
21
22FIRST_GENERATION_DUALS = [1, 1, 1, 1, 0]
23
24
25# ----------------------------------------------------------------------------
26# Build the model
27# ----------------------------------------------------------------------------
28class TItem(object):
29 def __init__(self, item_id, item_size, demand):
30 self.id = item_id
31 self.size = item_size
32 self.demand = demand
33 self.dual_value = -1
34
35 @classmethod
36 def make(cls, args):
37 arg_id = args[0]
38 arg_size = args[1]
39 arg_demand = args[2]
40 return cls(arg_id, arg_size, arg_demand)
41
42 def __str__(self):
43 return 'item%d' % self.id
44
45
46class TPattern(namedtuple("TPattern", ["id", "cost"])):
47 def __str__(self):
48 return 'pattern%d' % self.id
49
50# ---
51
52
53def make_cutstock_pattern_generation_model(items, roll_width, **kwargs):
54 gen_model = Model(name='cutstock_generate_patterns', **kwargs)
55 # store data
56 gen_model.items = items
57 gen_model.roll_width = roll_width
58 # default values
59 gen_model.duals = [1] * len(items)
60 # 1. create variables: one per item
61 gen_model.use_vars = gen_model.integer_var_list(keys=items, ub=999999, name='use')
62 # 2 setup constraint:
63 # --- sum of item usage times item sizes must be less than roll width
64 gen_model.add(gen_model.dot(gen_model.use_vars, (it.size for it in items)) <= roll_width)
65
66 # store dual expression for dynamic edition
67 gen_model.use_dual_expr = 1 - gen_model.dot(gen_model.use_vars, gen_model.duals)
68 # minimize
69 gen_model.minimize(gen_model.use_dual_expr)
70
71 return gen_model
72
73
74def cutstock_update_duals(gmodel, new_duals):
75 # update the duals array and the the duals expression...
76 # edition is propagated to the objective of the model.
77 gmodel.duals = new_duals
78 use_vars = gmodel.use_vars
79 assert len(new_duals) == len(use_vars)
80 updated_used = [(use, -new_duals[u]) for u, use in enumerate(use_vars)]
81 # this modification is notified to the objective.
82 gmodel.use_dual_expr.set_coefficients(updated_used)
83 return gmodel
84
85
86def make_custstock_master_model(item_table, pattern_table, fill_table, roll_width, **kwargs):
87 m = Model(name='custock_master', **kwargs)
88
89 # store data as properties
90 m.items = [TItem.make(it_row) for it_row in item_table]
91 m.items_by_id = {it.id: it for it in m.items}
92 m.patterns = [TPattern(*pattern_row) for pattern_row in pattern_table]
93 m.patterns_by_id = {pat.id: pat for pat in m.patterns}
94 m.max_pattern_id = max(pt.id for pt in m.patterns)
95
96 # build a dictionary storing how much each pattern fills each item.
97 m.pattern_item_filled = {(m.patterns_by_id[p], m.items_by_id[i]): f for (p, i, f) in fill_table}
98 m.roll_width = roll_width
99
100 # --- variables
101 # one cut var per pattern...
102 m.MAX_CUT = 9999
103 m.cut_vars = m.continuous_var_dict(m.patterns, lb=0, ub=m.MAX_CUT, name="cut")
104
105 # --- add fill constraints
106 #
107 all_patterns = m.patterns
108 all_items = m.items
109 m.item_fill_cts = []
110 for item in all_items:
111 item_fill_ct = m.sum(
112 m.cut_vars[p] * m.pattern_item_filled.get((p, item), 0) for p in all_patterns) >= item.demand
113 item_fill_ct.name = 'ct_fill_{0!s}'.format(item)
114 m.item_fill_cts.append(item_fill_ct)
115 m.add_constraints(m.item_fill_cts)
116
117 # --- minimize total cut stock
118 m.total_cutting_cost = m.sum(m.cut_vars[p] * p.cost for p in all_patterns)
119 m.minimize(m.total_cutting_cost)
120
121 return m
122
123
124def add_pattern_to_master_model(master_model, item_usages):
125 """ Adds a new pattern to the master model.
126
127 This function performs the following:
128
129 1. build a new pattern instance from item usages (taken from sub-model)
130 2. add it to the master model
131 3. update decision objects with this new pattern.
132 """
133 new_pattern_id = max(pt.id for pt in master_model.patterns) + 1
134 new_pattern = TPattern(new_pattern_id, 1)
135 master_model.patterns.append(new_pattern)
136 for used, item in zip(item_usages, master_model.items):
137 master_model.pattern_item_filled[new_pattern, item] = used
138
139 # --- add one decision variable, linked to the new pattern.
140 new_pattern_cut_var = master_model.continuous_var(lb=0, ub=master_model.MAX_CUT,
141 name='cut_{0}'.format(new_pattern_id))
142 master_model.cut_vars[new_pattern] = new_pattern_cut_var
143
144 # update constraints
145 for item, ct in zip(master_model.items, master_model.item_fill_cts):
146 # update fill constraint by changing lhs
147 ctlhs = ct.lhs
148 filled = master_model.pattern_item_filled[new_pattern, item]
149 if filled:
150 ctlhs += new_pattern_cut_var * filled
151
152 # update objective:
153 # side-effect on the total cutting cost expr propagates to the objective.
154 cost_expr = master_model.total_cutting_cost
155 cost_expr += new_pattern_cut_var * new_pattern.cost # this performw a side effect!
156
157 return master_model
158
159
160def cutstock_print_solution(cutstock_model):
161 patterns = cutstock_model.patterns
162 cut_var_values = {p: cutstock_model.cut_vars[p].solution_value for p in patterns}
163 pattern_item_filled = cutstock_model.pattern_item_filled
164 print("| Nb of cuts | Pattern | Pattern's detail (# of item1,item2,...) |")
165 print("| {} |".format("-" * 70))
166 for p in patterns:
167 if cut_var_values[p] >= 1e-3:
168 pattern_detail = {b.id: pattern_item_filled[a, b] for a, b in pattern_item_filled if
169 a == p}
170 print(
171 "| {:<10g} | {!s:9} | {!s:45} |".format(cut_var_values[p],
172 p,
173 pattern_detail))
174 print("| {} |".format("-" * 70))
175
176
177def cutstock_save_as_json(model, json_file):
178 patterns = model.patterns
179 cut_var_values = {p: model.cut_vars[p].solution_value for p in patterns}
180 solution = []
181 for p in patterns:
182 if cut_var_values[p] >= 1e-3:
183 pattern_detail = {b.id: model.pattern_item_filled[(a, b)] for (a, b) in model.pattern_item_filled if
184 a == p}
185 n = {'pattern': str(p),
186 'cuts': "%g" % cut_var_values[p],
187 'details': pattern_detail}
188 solution.append(n)
189 json_file.write(json.dumps(solution, indent=3).encode('utf-8'))
190
191
192def cutstock_solve(item_table, pattern_table, fill_table, roll_width, **kwargs):
193 verbose = kwargs.pop('verbose', True)
194 master_model = make_custstock_master_model(item_table, pattern_table, fill_table, roll_width, **kwargs)
195
196 # these two fields contain named tuples
197 items = master_model.items
198 patterns = master_model.patterns
199 gen_model = make_cutstock_pattern_generation_model(items, roll_width, **kwargs)
200
201 rc_eps = 1e-6
202 obj_eps = 1e-4
203 loop_count = 0
204 best = 0
205 curr = 1e+20
206 ms = None
207
208 while loop_count < 100 and abs(best - curr) >= obj_eps:
209 ms = master_model.solve(**kwargs)
210 loop_count += 1
211 best = curr
212 if not ms:
213 print('{}> master model fails, stop'.format(loop_count))
214 break
215 else:
216 assert ms
217 curr = master_model.objective_value
218 if verbose:
219 print('{}> new column generation iteration, #patterns={}, best={:g}, curr={:g}'
220 .format(loop_count, len(patterns), best, curr))
221 duals = master_model.dual_values(master_model.item_fill_cts)
222 if verbose:
223 print('{0}> moving duals from master to sub model: {1}'
224 .format(loop_count, list(map(lambda x: float('%0.2f' % x), duals))))
225 cutstock_update_duals(gen_model, duals)
226 gs = gen_model.solve(**kwargs)
227 if not gs:
228 print('{}> slave model fails, stop'.format(loop_count))
229 break
230
231 rc_cost = gen_model.objective_value
232 if rc_cost <= -rc_eps:
233 if verbose:
234 print('{}> slave model runs with obj={:g}'.format(loop_count, rc_cost))
235 else:
236 if verbose:
237 print('{}> pattern-generator model stops, obj={:g}'.format(loop_count, rc_cost))
238 break
239
240 use_values = gen_model.solution.get_values(gen_model.use_vars)
241 if verbose:
242 print('{}> add new pattern to master data: {}'.format(loop_count, str(use_values)))
243 # make a new pattern with use values
244 if not (loop_count < 100 and abs(best - curr) >= obj_eps):
245 print('* terminating: best-curr={:g}'.format(abs(best - curr)))
246 break
247 add_pattern_to_master_model(master_model, use_values)
248
249 ret = None
250 if ms:
251 if verbose:
252 print('\n* Cutting-stock column generation terminates, best={:g}, #loops={}'.format(curr, loop_count))
253 cutstock_print_solution(master_model)
254 ret = ms
255 else:
256 print("!!!! Cutting-stock column generation fails !!!!")
257 ret = None
258 gen_model.end()
259
260 return (master_model, ret)
261
262def cutstock_solve_default(**kwargs):
263 return cutstock_solve(DEFAULT_ITEMS, DEFAULT_PATTERNS, DEFAULT_PATTERN_ITEM_FILLED, DEFAULT_ROLL_WIDTH,
264 **kwargs)
265
266
267# -----------------------------------------------------------------------------
268# Solve the model and display the result
269# -----------------------------------------------------------------------------
270if __name__ == '__main__':
271 m,s = cutstock_solve_default()
272 assert abs(s.objective_value - 46.25) <= 0.1
273 # Save the solution as "solution.json" program output.
274 with get_environment().get_output_stream("solution.json") as fp:
275 cutstock_save_as_json(m, fp)
276 m.end()