src/inform-or/inform_or_models/place_items_in_box.py

   1 # Copyright (c) 2020 Moritz Dederichs
   2 # Copyright (c) 2020 Janos Piddubnij
   3
   4 from gurobipy import Model, GRB, quicksum
   5 from typing import Dict, Tuple, Any
   6
   7
   8 def __termination_criterion(model, where):
   9     """ This termination criterion ensures that the optimizer will not get stuck trying all optimal solutions if there
  10         are multiple possible solutions.
  11
  12     Parameters
  13     ----------
  14     model
  15     where
  16
  17     Returns
  18     -------
  19     """
  20     if where == GRB.Callback.MIP:
  21         if model._last_sol_time is not None:
  22             now = model.cbGet(GRB.Callback.RUNTIME)
  23             if now - model._last_sol_time > 5:
  24                 model.terminate()
  25
  26     if where == GRB.Callback.MIPSOL:
  27         if not model._time_limit_disabled:
  28             model.params.TimeLimit = GRB.INFINITY
  29             model._time_limit_disabled = True
  30         now = model.cbGet(GRB.Callback.RUNTIME)
  31         model._last_sol_time = now
  32
  33
  34 def __formalise_solution(model: Model, items: list, width_items: dict, height_items: dict, length_items: dict) -> Dict[Tuple, Tuple]:
  35     """ This function transform the optimal solution of a model into a processable and readable dictionary.
  36
  37     Parameters
  38     ----------
  39     model: gurobipy.Model
  40         The model whose solution should be formalised.
  41
  42     items: list
  43         The list of items that have been packed in the given box.
  44
  45     width_items: dict
  46         A dictionary specifying the width of each item type.
  47
  48     height_items: dict
  49         A dictionary specifying the height of each item type.
  50
  51     length_items: dict
  52         A dictionary specifying the length of each item type.
  53
  54     Returns
  55     -------
  56     Dict[Tuple, Tuple]
  57         The dictionary specifying the placement coordinates and orientation of each item within the box.
  58     """
  59     formalised_solution = dict()
  60     if model.status in (GRB.status.OPTIMAL, GRB.status.INTERRUPTED):
  61         align = {
  62             1: 'W',
  63             2: 'H',
  64             3: 'L'
  65         }
  66         for i in items:
  67             x_begin = model.getVarByName(f'x_{i}')
  68             y_begin = model.getVarByName(f'y_{i}')
  69             z_begin = model.getVarByName(f'z_{i}')
  70             w_x = model.getVarByName(f'w_x_{i}')
  71             w_y = model.getVarByName(f'w_y_{i}')
  72             w_z = model.getVarByName(f'w_z_{i}')
  73             h_x = model.getVarByName(f'h_x_{i}')
  74             h_y = model.getVarByName(f'h_y_{i}')
  75             h_z = model.getVarByName(f'h_z_{i}')
  76             l_x = model.getVarByName(f'l_x_{i}')
  77             l_y = model.getVarByName(f'l_y_{i}')
  78             l_z = model.getVarByName(f'l_z_{i}')
  79             x_end = x_begin.x + w_x.x * width_items[i[0]] + h_x.x * height_items[i[0]] + l_x.x * length_items[i[0]]
  80             y_end = y_begin.x + w_y.x * width_items[i[0]] + h_y.x * height_items[i[0]] + l_y.x * length_items[i[0]]
  81             z_end = z_begin.x + w_z.x * width_items[i[0]] + h_z.x * height_items[i[0]] + l_z.x * length_items[i[0]]
  82             x_align = 1 * w_x.x + 2 * h_x.x + 3 * l_x.x
  83             y_align = 1 * w_y.x + 2 * h_y.x + 3 * l_y.x
  84             z_align = 1 * w_z.x + 2 * h_z.x + 3 * l_z.x
  85             formalised_solution[i] = (x_begin.x, y_begin.x, z_begin.x, x_end, y_end, z_end, align.get(x_align), align.get(y_align), align.get(z_align))
  86     return formalised_solution
  87
  88
  89 def place_items_in_box(items: list, width_items: Dict[str, int], height_items: Dict[str, int],
  90                        length_items: Dict[str, int], width_box: int, height_box: int,
  91                        length_box: int) -> Dict[Any, Tuple[float, float, float, str, str, str]]:
  92     """ This function tries to place a given set of items into a given box.
  93         The minimisation criterion for this model is to reduce the overall sum of z-coordinates (height)
  94         to simulate gravity.
  95
  96     Parameters
  97     ----------
  98     items: list
  99         The list of items that should be packed in the given box.
 100
 101     width_items: Dict[str, int]
 102         A dictionary defining the width of each item type.
 103
 104     height_items: Dict[str, int]
 105         A dictionary defining the height of each item type.
 106
 107     length_items: Dict[str, int]
 108         A dictionary defining the length of each item type.
 109
 110     width_box: int
 111         The width of the box to pack.
 112
 113     height_box: int
 114         The height of the box to pack.
 115
 116     length_box: int
 117         The length of the box to pack.
 118
 119     Returns
 120     -------
 121     Dict[Any, Tuple[float, float, float, str, str, str]]
 122         A dictionary specifying for each item the exact coordinates and the item orientation.
 123         1. x-coordinate of the item.
 124         2. y-coordinate of the item.
 125         3. z-coordinate of the item.
 126         4. Whether height (h), length (l) or width (w) of the item is aligned to the length of the box.
 127         5. Whether height (h), length (l) or width (w) of the item is aligned to the width of the box.
 128         6. Whether height (h), length (l) or width (w) of the item is aligned to the height of the box.
 129     """
 130     model = Model('Single_Box_INFORM')
 131     model.params.TimeLimit = 15
 132
 133     # Calculating the upper bound for the item coordinates within a box
 134     big_m = 0
 135     if height_box > big_m:
 136         big_m = height_box
 137     if length_box > big_m:
 138         big_m = length_box
 139     if width_box > big_m:
 140         big_m = width_box
 141     # big_m = max([width_box, height_box, length_box])
 142
 143     # Variables
 144
 145     # Variables representing the x-, y- and z-coordinates of item i within the box
 146     x = {}
 147     y = {}
 148     z = {}
 149     # Variables indicating whether the width of the item is aligned to the x-, y- or z-side of the box
 150     w_x = {}
 151     w_y = {}
 152     w_z = {}
 153     # Variables indicating whether the height of the item is aligned to the x-, y- or z-side of the box
 154     h_x = {}
 155     h_y = {}
 156     h_z = {}
 157     # Variables indicating whether the length of the item is aligned to the x-, y- or z-side of the box
 158     l_x = {}
 159     l_y = {}
 160     l_z = {}
 161     for i in items:
 162         x[i] = model.addVar(name=f'x_{i}', vtype=GRB.INTEGER, lb=0, ub=big_m)
 163         y[i] = model.addVar(name=f'y_{i}', vtype=GRB.INTEGER, lb=0, ub=big_m)
 164         z[i] = model.addVar(name=f'z_{i}', vtype=GRB.INTEGER, lb=0, ub=big_m)
 165         w_x[i] = model.addVar(name=f'w_x_{i}', vtype=GRB.BINARY)
 166         w_y[i] = model.addVar(name=f'w_y_{i}', vtype=GRB.BINARY)
 167         w_z[i] = model.addVar(name=f'w_z_{i}', vtype=GRB.BINARY)
 168         h_x[i] = model.addVar(name=f'h_x_{i}', vtype=GRB.BINARY)
 169         h_y[i] = model.addVar(name=f'h_y_{i}', vtype=GRB.BINARY)
 170         h_z[i] = model.addVar(name=f'h_z_{i}', vtype=GRB.BINARY)
 171         l_x[i] = model.addVar(name=f'l_x_{i}', vtype=GRB.BINARY)
 172         l_y[i] = model.addVar(name=f'l_y_{i}', vtype=GRB.BINARY)
 173         l_z[i] = model.addVar(name=f'l_z_{i}', vtype=GRB.BINARY)
 174
 175     # Variables indicating the relative position of two items i and j to each other
 176     a = {}
 177     b = {}
 178     c = {}
 179     d = {}
 180     e = {}
 181     f = {}
 182     for i in items:
 183         for j in items:
 184             if i != j:
 185                 a[i, j] = model.addVar(name=f'a_{i}_{j}', vtype=GRB.INTEGER)
 186                 b[i, j] = model.addVar(name=f'b_{i}_{j}', vtype=GRB.INTEGER)
 187                 c[i, j] = model.addVar(name=f'c_{i}_{j}', vtype=GRB.INTEGER)
 188                 d[i, j] = model.addVar(name=f'd_{i}_{j}', vtype=GRB.INTEGER)
 189                 e[i, j] = model.addVar(name=f'e_{i}_{j}', vtype=GRB.INTEGER)
 190                 f[i, j] = model.addVar(name=f'f_{i}_{j}', vtype=GRB.INTEGER)
 191
 192     # Constraints
 193
 194     # Items are not allowed to overlap
 195     # Additionally items must have at least one positional relation to any other item
 196     for i in items:
 197         for j in items:
 198             if i != j:
 199                 model.addConstr(x[i] + width_items[i[0]] * w_x[i] + height_items[i[0]] * h_x[i] + length_items[i[0]] * l_x[i] <= x[j] + (1 - a[i, j]) * big_m)
 200                 model.addConstr(x[j] + width_items[j[0]] * w_x[j] + height_items[j[0]] * h_x[j] + length_items[j[0]] * l_x[j] <= x[i] + (1 - b[i, j]) * big_m)
 201                 model.addConstr(y[i] + width_items[i[0]] * w_y[i] + height_items[i[0]] * h_y[i] + length_items[i[0]] * l_y[i] <= y[j] + (1 - c[i, j]) * big_m)
 202                 model.addConstr(y[j] + width_items[j[0]] * w_y[j] + height_items[j[0]] * h_y[j] + length_items[j[0]] * l_y[j] <= y[i] + (1 - d[i, j]) * big_m)
 203                 model.addConstr(z[i] + width_items[i[0]] * w_z[i] + height_items[i[0]] * h_z[i] + length_items[i[0]] * l_z[i] <= z[j] + (1 - e[i, j]) * big_m)
 204                 model.addConstr(z[j] + width_items[j[0]] * w_z[j] + height_items[j[0]] * h_z[j] + length_items[j[0]] * l_z[j] <= z[i] + (1 - f[i, j]) * big_m)
 205                 model.addConstr(a[i, j] + b[i, j] + c[i, j] + d[i, j] + e[i, j] + f[i, j] >= 1)
 206
 207     # No item i may be packed over the boundaries of the box
 208     for i in items:
 209         model.addConstr(x[i] + width_items[i[0]] * w_x[i] + height_items[i[0]] * h_x[i] + length_items[i[0]] * l_x[i] <= length_box)
 210         model.addConstr(y[i] + width_items[i[0]] * w_y[i] + height_items[i[0]] * h_y[i] + length_items[i[0]] * l_y[i] <= width_box)
 211         model.addConstr(z[i] + width_items[i[0]] * w_z[i] + height_items[i[0]] * h_z[i] + length_items[i[0]] * l_z[i] <= height_box)
 212
 213     # Each side of an item i may only be aligned to one side of the box
 214     for i in items:
 215         model.addConstr(w_x[i] + w_y[i] + w_z[i] == 1)
 216         model.addConstr(h_x[i] + h_y[i] + h_z[i] == 1)
 217         model.addConstr(l_x[i] + l_y[i] + l_z[i] == 1)
 218         model.addConstr(w_x[i] + h_x[i] + l_x[i] == 1)
 219         model.addConstr(w_y[i] + h_y[i] + l_y[i] == 1)
 220         model.addConstr(w_z[i] + h_z[i] + l_z[i] == 1)
 221
 222     model._last_sol_time = None
 223     model._time_limit_disabled = False
 224
 225     model.setObjective(quicksum(z[i] for i in items), GRB.MINIMIZE)
 226
 227     model.optimize(__termination_criterion)
 228
 229     return __formalise_solution(model, items, width_items, height_items, length_items)