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