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()