-
Notifications
You must be signed in to change notification settings - Fork 30
/
knapsack_wo_rotations.py
85 lines (77 loc) · 3.56 KB
/
knapsack_wo_rotations.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
from ._instance import Instance, Solution, Placement
from ortools.sat.python import cp_model
from typing import Optional
class RectangleKnapsackWithoutRotationsModel:
def __init__(self, instance: Instance) -> None:
self.instance = instance
self.model = cp_model.CpModel()
# We have to create the variable for the bottom left corner of the boxes.
# We directly limit their range, such that the boxes are inside the container
self.x_vars = [
self.model.new_int_var(
0, instance.container.width - box.width, name=f"x1_{i}"
)
for i, box in enumerate(instance.rectangles)
]
self.y_vars = [
self.model.new_int_var(
0, instance.container.height - box.height, name=f"y1_{i}"
)
for i, box in enumerate(instance.rectangles)
]
# The packed variable is a boolean variable that is true if the rectangle is packed
self.packed_vars = [
self.model.new_bool_var(f"packed_{i}")
for i in range(len(instance.rectangles))
]
# Interval variables are actually more like constraint containers, that are then passed to the no overlap constraint
# Note that we could also make size and end variables, but we don't need them here
x_interval_vars = [
self.model.new_optional_fixed_size_interval_var(
start=self.x_vars[i], # the x value of the bottom left corner
size=box.width, # the width of the rectangle
is_present=self.packed_vars[i], # whether the rectangle is packed
name=f"x_interval_{i}",
)
for i, box in enumerate(instance.rectangles)
]
y_interval_vars = [
self.model.new_optional_fixed_size_interval_var(
start=self.y_vars[i], # the y value of the bottom left corner
size=box.height, # the height of the rectangle
is_present=self.packed_vars[i], # whether the rectangle is packed
name=f"y_interval_{i}",
)
for i, box in enumerate(instance.rectangles)
]
# Enforce that no two rectangles overlap
self.model.add_no_overlap_2d(x_interval_vars, y_interval_vars)
# maximize the number of packed rectangles
self.model.maximize(
sum(
box.value * self.packed_vars[i]
for i, box in enumerate(instance.rectangles)
)
)
def _extract_solution(self, solver: cp_model.CpSolver) -> Optional[Solution]:
if self.status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
return None
placements = []
for i, box in enumerate(self.instance.rectangles):
if solver.value(self.packed_vars[i]):
x = solver.value(self.x_vars[i])
y = solver.value(self.y_vars[i])
placements.append(Placement(x=x, y=y))
else:
placements.append(None)
return Solution(placements=placements)
def solve(self, time_limit: float = 900.0, opt_tol: float = 0.01):
solver = cp_model.CpSolver()
solver.parameters.log_search_progress = True
solver.parameters.max_time_in_seconds = time_limit
solver.parameters.relative_gap_limit = opt_tol
self.status = solver.solve(self.model)
self.solution = self._extract_solution(solver)
self.upper_bound = solver.best_objective_bound
self.objective_value = solver.objective_value
return self.status