1#!/usr/bin/env python3
2# Copyright 2010-2021 Google LLC
3# Licensed under the Apache License, Version 2.0 (the "License");
4# you may not use this file except in compliance with the License.
5# You may obtain a copy of the License at
6#
7#     http://www.apache.org/licenses/LICENSE-2.0
8#
9# Unless required by applicable law or agreed to in writing, software
10# distributed under the License is distributed on an "AS IS" BASIS,
11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12# See the License for the specific language governing permissions and
13# limitations under the License.
14"""Solver a 2D rectangle knapsack problem.
15
16This code is adapted from
17https://yetanothermathprogrammingconsultant.blogspot.com/2021/10/2d-knapsack-problem.html
18"""
19
20import io
21
22from absl import app
23from absl import flags
24import numpy as np
25import pandas as pd
26
27from google.protobuf import text_format
28
29from ortools.sat.python import cp_model
30
31FLAGS = flags.FLAGS
32
33flags.DEFINE_string('output_proto', '',
34                    'Output file to write the cp_model proto to.')
35flags.DEFINE_string('params', 'num_search_workers:16,log_search_progress:true',
36                    'Sat solver parameters.')
37flags.DEFINE_string('model', 'rotation',
38                    '\'duplicate\' or \'rotation\' or \'optional\'')
39
40
41def build_data():
42    """Build the data frame."""
43    data = """
44    item         width    height available    value    color
45    k1             20       4       2        338.984   blue
46    k2             12      17       6        849.246   orange
47    k3             20      12       2        524.022   green
48    k4             16       7       9        263.303   red
49    k5              3       6       3        113.436   purple
50    k6             13       5       3        551.072   brown
51    k7              4       7       6         86.166   pink
52    k8              6      18       8        755.094   grey
53    k9             14       2       7        223.516   olive
54    k10             9      11       5        369.560   cyan
55    """
56
57    data = pd.read_table(io.StringIO(data), sep=r'\s+')
58    print('Input data')
59    print(data)
60
61    max_height = 20
62    max_width = 30
63
64    print(f'Container max_width:{max_width} max_height:{max_height}')
65    print(f'#Items: {len(data.index)}')
66    return (data, max_height, max_width)
67
68
69def solve_with_duplicate_items(data, max_height, max_width):
70    """Solve the problem by building 2 items (rotated or not) for each item."""
71    # Derived data (expanded to individual items).
72    data_widths = data['width'].to_numpy()
73    data_heights = data['height'].to_numpy()
74    data_availability = data['available'].to_numpy()
75    data_values = data['value'].to_numpy()
76
77    # Non duplicated items data.
78    base_item_widths = np.repeat(data_widths, data_availability)
79    base_item_heights = np.repeat(data_heights, data_availability)
80    base_item_values = np.repeat(data_values, data_availability)
81    num_data_items = len(base_item_values)
82
83    # Create rotated items by duplicating.
84    item_widths = np.concatenate((base_item_widths, base_item_heights))
85    item_heights = np.concatenate((base_item_heights, base_item_widths))
86    item_values = np.concatenate((base_item_values, base_item_values))
87
88    num_items = len(item_values)
89
90    # OR-Tools model
91    model = cp_model.CpModel()
92
93    # Variables
94    x_starts = []
95    x_ends = []
96    y_starts = []
97    y_ends = []
98    is_used = []
99    x_intervals = []
100    y_intervals = []
101
102    for i in range(num_items):
103        ## Is the item used?
104        is_used.append(model.NewBoolVar(f'is_used{i}'))
105
106        ## Item coordinates.
107        x_starts.append(model.NewIntVar(0, max_width, f'x_start{i}'))
108        x_ends.append(model.NewIntVar(0, max_width, f'x_end{i}'))
109        y_starts.append(model.NewIntVar(0, max_height, f'y_start{i}'))
110        y_ends.append(model.NewIntVar(0, max_height, f'y_end{i}'))
111
112        ## Interval variables.
113        x_intervals.append(
114            model.NewIntervalVar(x_starts[i], item_widths[i] * is_used[i],
115                                 x_ends[i], f'x_interval{i}'))
116        y_intervals.append(
117            model.NewIntervalVar(y_starts[i], item_heights[i] * is_used[i],
118                                 y_ends[i], f'y_interval{i}'))
119
120    # Constraints.
121
122    ## Only one of non-rotated/rotated pair can be used.
123    for i in range(num_data_items):
124        model.Add(is_used[i] + is_used[i + num_data_items] <= 1)
125
126    ## 2D no overlap.
127    model.AddNoOverlap2D(x_intervals, y_intervals)
128
129    ## Objective.
130    model.Maximize(cp_model.LinearExpr.ScalProd(is_used, item_values))
131
132    # Output proto to file.
133    if FLAGS.output_proto:
134        print('Writing proto to %s' % FLAGS.output_proto)
135        with open(FLAGS.output_proto, 'w') as text_file:
136            text_file.write(str(model))
137
138    # Solve model.
139    solver = cp_model.CpSolver()
140    if FLAGS.params:
141        text_format.Parse(FLAGS.params, solver.parameters)
142
143    status = solver.Solve(model)
144
145    # Report solution.
146    if status == cp_model.OPTIMAL:
147        used = {i for i in range(num_items) if solver.BooleanValue(is_used[i])}
148        data = pd.DataFrame({
149            'x_start': [solver.Value(x_starts[i]) for i in used],
150            'y_start': [solver.Value(y_starts[i]) for i in used],
151            'item_width': [item_widths[i] for i in used],
152            'item_height': [item_heights[i] for i in used],
153            'x_end': [solver.Value(x_ends[i]) for i in used],
154            'y_end': [solver.Value(y_ends[i]) for i in used],
155            'item_value': [item_values[i] for i in used]
156        })
157        print(data)
158
159
160def solve_with_duplicate_optional_items(data, max_height, max_width):
161    """Solve the problem by building 2 optional items (rotated or not) for each item."""
162    # Derived data (expanded to individual items).
163    data_widths = data['width'].to_numpy()
164    data_heights = data['height'].to_numpy()
165    data_availability = data['available'].to_numpy()
166    data_values = data['value'].to_numpy()
167
168    # Non duplicated items data.
169    base_item_widths = np.repeat(data_widths, data_availability)
170    base_item_heights = np.repeat(data_heights, data_availability)
171    base_item_values = np.repeat(data_values, data_availability)
172    num_data_items = len(base_item_values)
173
174    # Create rotated items by duplicating.
175    item_widths = np.concatenate((base_item_widths, base_item_heights))
176    item_heights = np.concatenate((base_item_heights, base_item_widths))
177    item_values = np.concatenate((base_item_values, base_item_values))
178
179    num_items = len(item_values)
180
181    # OR-Tools model
182    model = cp_model.CpModel()
183
184    # Variables
185    x_starts = []
186    y_starts = []
187    is_used = []
188    x_intervals = []
189    y_intervals = []
190
191    for i in range(num_items):
192        ## Is the item used?
193        is_used.append(model.NewBoolVar(f'is_used{i}'))
194
195        ## Item coordinates.
196        x_starts.append(
197            model.NewIntVar(0, max_width - int(item_widths[i]), f'x_start{i}'))
198        y_starts.append(
199            model.NewIntVar(0, max_height - int(item_heights[i]),
200                            f'y_start{i}'))
201
202        ## Interval variables.
203        x_intervals.append(
204            model.NewOptionalFixedSizeIntervalVar(x_starts[i], item_widths[i],
205                                                  is_used[i], f'x_interval{i}'))
206        y_intervals.append(
207            model.NewOptionalFixedSizeIntervalVar(y_starts[i], item_heights[i],
208                                                  is_used[i], f'y_interval{i}'))
209
210    # Constraints.
211
212    ## Only one of non-rotated/rotated pair can be used.
213    for i in range(num_data_items):
214        model.Add(is_used[i] + is_used[i + num_data_items] <= 1)
215
216    ## 2D no overlap.
217    model.AddNoOverlap2D(x_intervals, y_intervals)
218
219    ## Objective.
220    model.Maximize(cp_model.LinearExpr.ScalProd(is_used, item_values))
221
222    # Output proto to file.
223    if FLAGS.output_proto:
224        print('Writing proto to %s' % FLAGS.output_proto)
225        with open(FLAGS.output_proto, 'w') as text_file:
226            text_file.write(str(model))
227
228    # Solve model.
229    solver = cp_model.CpSolver()
230    if FLAGS.params:
231        text_format.Parse(FLAGS.params, solver.parameters)
232
233    status = solver.Solve(model)
234
235    # Report solution.
236    if status == cp_model.OPTIMAL:
237        used = {i for i in range(num_items) if solver.BooleanValue(is_used[i])}
238        data = pd.DataFrame({
239            'x_start': [solver.Value(x_starts[i]) for i in used],
240            'y_start': [solver.Value(y_starts[i]) for i in used],
241            'item_width': [item_widths[i] for i in used],
242            'item_height': [item_heights[i] for i in used],
243            'x_end': [solver.Value(x_starts[i]) + item_widths[i] for i in used],
244            'y_end': [
245                solver.Value(y_starts[i]) + item_heights[i] for i in used
246            ],
247            'item_value': [item_values[i] for i in used]
248        })
249        print(data)
250
251
252def solve_with_rotations(data, max_height, max_width):
253    """Solve the problem by rotating items."""
254    # Derived data (expanded to individual items).
255    data_widths = data['width'].to_numpy()
256    data_heights = data['height'].to_numpy()
257    data_availability = data['available'].to_numpy()
258    data_values = data['value'].to_numpy()
259
260    item_widths = np.repeat(data_widths, data_availability)
261    item_heights = np.repeat(data_heights, data_availability)
262    item_values = np.repeat(data_values, data_availability)
263
264    num_items = len(item_widths)
265
266    # OR-Tools model.
267    model = cp_model.CpModel()
268
269    # Coordinate variables for each rectangle.
270    x_starts = []
271    x_sizes = []
272    x_ends = []
273    y_starts = []
274    y_sizes = []
275    y_ends = []
276    x_intervals = []
277    y_intervals = []
278
279    for i in range(num_items):
280        sizes = [0, int(item_widths[i]), int(item_heights[i])]
281        # X coordinates.
282        x_starts.append(model.NewIntVar(0, max_width, f'x_start{i}'))
283        x_sizes.append(
284            model.NewIntVarFromDomain(cp_model.Domain.FromValues(sizes),
285                                      f'x_size{i}'))
286        x_ends.append(model.NewIntVar(0, max_width, f'x_end{i}'))
287
288        # Y coordinates.
289        y_starts.append(model.NewIntVar(0, max_height, f'y_start{i}'))
290        y_sizes.append(
291            model.NewIntVarFromDomain(cp_model.Domain.FromValues(sizes),
292                                      f'y_size{i}'))
293        y_ends.append(model.NewIntVar(0, max_height, f'y_end{i}'))
294
295        ## Interval variables
296        x_intervals.append(
297            model.NewIntervalVar(x_starts[i], x_sizes[i], x_ends[i],
298                                 f'x_interval{i}'))
299        y_intervals.append(
300            model.NewIntervalVar(y_starts[i], y_sizes[i], y_ends[i],
301                                 f'y_interval{i}'))
302
303    # is_used[i] == True if and only if item i is selected.
304    is_used = []
305
306    # Constraints.
307
308    ## for each item, decide is unselected, no_rotation, rotated.
309    for i in range(num_items):
310        not_selected = model.NewBoolVar(f'not_selected_{i}')
311        no_rotation = model.NewBoolVar(f'no_rotation_{i}')
312        rotated = model.NewBoolVar(f'rotated_{i}')
313
314        ### Exactly one state must be chosen.
315        model.Add(not_selected + no_rotation + rotated == 1)
316
317        ### Define height and width according to the state.
318        dim1 = item_widths[i]
319        dim2 = item_heights[i]
320        model.Add(x_sizes[i] == 0).OnlyEnforceIf(not_selected)
321        model.Add(y_sizes[i] == 0).OnlyEnforceIf(not_selected)
322        model.Add(x_sizes[i] == dim1).OnlyEnforceIf(no_rotation)
323        model.Add(y_sizes[i] == dim2).OnlyEnforceIf(no_rotation)
324        model.Add(x_sizes[i] == dim2).OnlyEnforceIf(rotated)
325        model.Add(y_sizes[i] == dim1).OnlyEnforceIf(rotated)
326
327        is_used.append(not_selected.Not())
328
329    ## 2D no overlap.
330    model.AddNoOverlap2D(x_intervals, y_intervals)
331
332    # Objective.
333    model.Maximize(cp_model.LinearExpr.ScalProd(is_used, item_values))
334
335    # Output proto to file.
336    if FLAGS.output_proto:
337        print('Writing proto to %s' % FLAGS.output_proto)
338        with open(FLAGS.output_proto, 'w') as text_file:
339            text_file.write(str(model))
340
341    # Solve model.
342    solver = cp_model.CpSolver()
343    if FLAGS.params:
344        text_format.Parse(FLAGS.params, solver.parameters)
345
346    status = solver.Solve(model)
347
348    # Report solution.
349    if status == cp_model.OPTIMAL:
350        used = {i for i in range(num_items) if solver.BooleanValue(is_used[i])}
351        data = pd.DataFrame({
352            'x_start': [solver.Value(x_starts[i]) for i in used],
353            'y_start': [solver.Value(y_starts[i]) for i in used],
354            'item_width': [solver.Value(x_sizes[i]) for i in used],
355            'item_height': [solver.Value(y_sizes[i]) for i in used],
356            'x_end': [solver.Value(x_ends[i]) for i in used],
357            'y_end': [solver.Value(y_ends[i]) for i in used],
358            'item_value': [item_values[i] for i in used]
359        })
360        print(data)
361
362
363def main(_):
364    """Solve the problem with all models."""
365    data, max_height, max_width = build_data()
366    if FLAGS.model == 'duplicate':
367        solve_with_duplicate_items(data, max_height, max_width)
368    elif FLAGS.model == 'optional':
369        solve_with_duplicate_optional_items(data, max_height, max_width)
370    else:
371        solve_with_rotations(data, max_height, max_width)
372
373
374if __name__ == '__main__':
375    app.run(main)
376