1 // Copyright 2010-2021 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13
14 #include <algorithm>
15 #include <cstdint>
16 #include <limits>
17 #include <string>
18 #include <vector>
19
20 #include "absl/strings/str_format.h"
21 #include "ortools/base/hash.h"
22 #include "ortools/base/int_type.h"
23 #include "ortools/base/integral_types.h"
24 #include "ortools/base/logging.h"
25 #include "ortools/constraint_solver/constraint_solver.h"
26 #include "ortools/constraint_solver/constraint_solveri.h"
27 #include "ortools/util/string_array.h"
28
29 namespace operations_research {
30 // Diffn constraint, Non overlapping boxs.
31 namespace {
32 DEFINE_INT_TYPE(Box, int);
33 class Diffn : public Constraint {
34 public:
Diffn(Solver * const solver,const std::vector<IntVar * > & x_vars,const std::vector<IntVar * > & y_vars,const std::vector<IntVar * > & x_size,const std::vector<IntVar * > & y_size,bool strict)35 Diffn(Solver* const solver, const std::vector<IntVar*>& x_vars,
36 const std::vector<IntVar*>& y_vars, const std::vector<IntVar*>& x_size,
37 const std::vector<IntVar*>& y_size, bool strict)
38 : Constraint(solver),
39 x_(x_vars),
40 y_(y_vars),
41 dx_(x_size),
42 dy_(y_size),
43 strict_(strict),
44 size_(x_vars.size()),
45 fail_stamp_(0) {
46 CHECK_EQ(x_vars.size(), y_vars.size());
47 CHECK_EQ(x_vars.size(), x_size.size());
48 CHECK_EQ(x_vars.size(), y_size.size());
49 }
50
~Diffn()51 ~Diffn() override {}
52
Post()53 void Post() override {
54 Solver* const s = solver();
55 for (int i = 0; i < size_; ++i) {
56 Demon* const demon = MakeConstraintDemon1(
57 s, this, &Diffn::OnBoxRangeChange, "OnBoxRangeChange", i);
58 x_[i]->WhenRange(demon);
59 y_[i]->WhenRange(demon);
60 dx_[i]->WhenRange(demon);
61 dy_[i]->WhenRange(demon);
62 }
63 delayed_demon_ = MakeDelayedConstraintDemon0(s, this, &Diffn::PropagateAll,
64 "PropagateAll");
65 if (solver()->parameters().diffn_use_cumulative() &&
66 IsArrayInRange<int64_t>(x_, 0, std::numeric_limits<int64_t>::max()) &&
67 IsArrayInRange<int64_t>(y_, 0, std::numeric_limits<int64_t>::max())) {
68 Constraint* ct1 = nullptr;
69 Constraint* ct2 = nullptr;
70 {
71 // We can add redundant cumulative constraints. This is done
72 // inside a c++ block to avoid leaking memory if adding the
73 // constraints leads to a failure. A cumulative constraint is
74 // a scheduling constraint that will perform finer energy
75 // based reasoning to do more propagation. (see Solver::MakeCumulative).
76 const int64_t min_x = MinVarArray(x_);
77 const int64_t max_x = MaxVarArray(x_);
78 const int64_t max_size_x = MaxVarArray(dx_);
79 const int64_t min_y = MinVarArray(y_);
80 const int64_t max_y = MaxVarArray(y_);
81 const int64_t max_size_y = MaxVarArray(dy_);
82 if (AreAllBound(dx_)) {
83 std::vector<int64_t> size_x;
84 FillValues(dx_, &size_x);
85 ct1 = MakeCumulativeConstraint(x_, size_x, dy_,
86 max_size_y + max_y - min_y);
87 }
88 if (AreAllBound(dy_)) {
89 std::vector<int64_t> size_y;
90 FillValues(dy_, &size_y);
91 ct2 = MakeCumulativeConstraint(y_, size_y, dx_,
92 max_size_x + max_x - min_x);
93 }
94 }
95 if (ct1 != nullptr) {
96 s->AddConstraint(ct1);
97 }
98 if (ct2 != nullptr) {
99 s->AddConstraint(ct2);
100 }
101 }
102 }
103
InitialPropagate()104 void InitialPropagate() override {
105 // All sizes should be >= 0.
106 for (int i = 0; i < size_; ++i) {
107 dx_[i]->SetMin(0);
108 dy_[i]->SetMin(0);
109 }
110
111 // Force propagation on all boxes.
112 to_propagate_.clear();
113 for (int i = 0; i < size_; i++) {
114 to_propagate_.insert(i);
115 }
116 PropagateAll();
117 }
118
DebugString() const119 std::string DebugString() const override {
120 return absl::StrFormat(
121 "Diffn(x = [%s], y = [%s], dx = [%s], dy = [%s]))",
122 JoinDebugStringPtr(x_, ", "), JoinDebugStringPtr(y_, ", "),
123 JoinDebugStringPtr(dx_, ", "), JoinDebugStringPtr(dy_, ", "));
124 }
125
Accept(ModelVisitor * const visitor) const126 void Accept(ModelVisitor* const visitor) const override {
127 visitor->BeginVisitConstraint(ModelVisitor::kDisjunctive, this);
128 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kPositionXArgument,
129 x_);
130 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kPositionYArgument,
131 y_);
132 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kSizeXArgument,
133 dx_);
134 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kSizeYArgument,
135 dy_);
136 visitor->EndVisitConstraint(ModelVisitor::kDisjunctive, this);
137 }
138
139 private:
PropagateAll()140 void PropagateAll() {
141 for (const int box : to_propagate_) {
142 FillNeighbors(box);
143 FailWhenEnergyIsTooLarge(box);
144 PushOverlappingBoxes(box);
145 }
146 to_propagate_.clear();
147 fail_stamp_ = solver()->fail_stamp();
148 }
149
OnBoxRangeChange(int box)150 void OnBoxRangeChange(int box) {
151 if (solver()->fail_stamp() > fail_stamp_ && !to_propagate_.empty()) {
152 // We have failed in the last propagation and the to_propagate_
153 // was not cleared.
154 fail_stamp_ = solver()->fail_stamp();
155 to_propagate_.clear();
156 }
157 to_propagate_.insert(box);
158 EnqueueDelayedDemon(delayed_demon_);
159 }
160
CanBoxedOverlap(int i,int j) const161 bool CanBoxedOverlap(int i, int j) const {
162 if (AreBoxedDisjoingHorizontallyForSure(i, j) ||
163 AreBoxedDisjoingVerticallyForSure(i, j)) {
164 return false;
165 }
166 return true;
167 }
168
AreBoxedDisjoingHorizontallyForSure(int i,int j) const169 bool AreBoxedDisjoingHorizontallyForSure(int i, int j) const {
170 return (x_[i]->Min() >= x_[j]->Max() + dx_[j]->Max()) ||
171 (x_[j]->Min() >= x_[i]->Max() + dx_[i]->Max()) ||
172 (!strict_ && (dx_[i]->Min() == 0 || dx_[j]->Min() == 0));
173 }
174
AreBoxedDisjoingVerticallyForSure(int i,int j) const175 bool AreBoxedDisjoingVerticallyForSure(int i, int j) const {
176 return (y_[i]->Min() >= y_[j]->Max() + dy_[j]->Max()) ||
177 (y_[j]->Min() >= y_[i]->Max() + dy_[i]->Max()) ||
178 (!strict_ && (dy_[i]->Min() == 0 || dy_[j]->Min() == 0));
179 }
180
181 // Fill neighbors_ with all boxes that can overlap the given box.
FillNeighbors(int box)182 void FillNeighbors(int box) {
183 // TODO(user): We could maintain a non reversible list of
184 // neighbors and clean it after each failure.
185 neighbors_.clear();
186 for (int other = 0; other < size_; ++other) {
187 if (other != box && CanBoxedOverlap(other, box)) {
188 neighbors_.push_back(other);
189 }
190 }
191 }
192
193 // Fails if the minimum area of the given box plus the area of its neighbors
194 // (that must already be computed in neighbors_) is greater than the area of a
195 // bounding box that necessarily contains all these boxes.
FailWhenEnergyIsTooLarge(int box)196 void FailWhenEnergyIsTooLarge(int box) {
197 int64_t area_min_x = x_[box]->Min();
198 int64_t area_max_x = x_[box]->Max() + dx_[box]->Max();
199 int64_t area_min_y = y_[box]->Min();
200 int64_t area_max_y = y_[box]->Max() + dy_[box]->Max();
201 int64_t sum_of_areas = dx_[box]->Min() * dy_[box]->Min();
202 // TODO(user): Is there a better order, maybe sort by distance
203 // with the current box.
204 for (int i = 0; i < neighbors_.size(); ++i) {
205 const int other = neighbors_[i];
206 // Update Bounding box.
207 area_min_x = std::min(area_min_x, x_[other]->Min());
208 area_max_x = std::max(area_max_x, x_[other]->Max() + dx_[other]->Max());
209 area_min_y = std::min(area_min_y, y_[other]->Min());
210 area_max_y = std::max(area_max_y, y_[other]->Max() + dy_[other]->Max());
211 // Update sum of areas.
212 sum_of_areas += dx_[other]->Min() * dy_[other]->Min();
213 const int64_t bounding_area =
214 (area_max_x - area_min_x) * (area_max_y - area_min_y);
215 if (sum_of_areas > bounding_area) {
216 solver()->Fail();
217 }
218 }
219 }
220
221 // Changes the domain of all the neighbors of a given box (that must
222 // already be computed in neighbors_) so that they can't overlap the
223 // mandatory part of the given box.
PushOverlappingBoxes(int box)224 void PushOverlappingBoxes(int box) {
225 for (int i = 0; i < neighbors_.size(); ++i) {
226 PushOneBox(box, neighbors_[i]);
227 }
228 }
229
230 // Changes the domain of the two given box by excluding the value that
231 // make them overlap for sure. Note that this function is symmetric in
232 // the sense that its argument can be swapped for the same result.
PushOneBox(int box,int other)233 void PushOneBox(int box, int other) {
234 const int state =
235 (x_[box]->Min() + dx_[box]->Min() <= x_[other]->Max()) +
236 2 * (x_[other]->Min() + dx_[other]->Min() <= x_[box]->Max()) +
237 4 * (y_[box]->Min() + dy_[box]->Min() <= y_[other]->Max()) +
238 8 * (y_[other]->Min() + dy_[other]->Min() <= y_[box]->Max());
239 // This is an "hack" to be able to easily test for none or for one
240 // and only one of the conditions below.
241 switch (state) {
242 case 0: {
243 solver()->Fail();
244 break;
245 }
246 case 1: { // We push other left (x increasing).
247 x_[other]->SetMin(x_[box]->Min() + dx_[box]->Min());
248 x_[box]->SetMax(x_[other]->Max() - dx_[box]->Min());
249 dx_[box]->SetMax(x_[other]->Max() - x_[box]->Min());
250 break;
251 }
252 case 2: { // We push other right (x decreasing).
253 x_[box]->SetMin(x_[other]->Min() + dx_[other]->Min());
254 x_[other]->SetMax(x_[box]->Max() - dx_[other]->Min());
255 dx_[other]->SetMax(x_[box]->Max() - x_[other]->Min());
256 break;
257 }
258 case 4: { // We push other up (y increasing).
259 y_[other]->SetMin(y_[box]->Min() + dy_[box]->Min());
260 y_[box]->SetMax(y_[other]->Max() - dy_[box]->Min());
261 dy_[box]->SetMax(y_[other]->Max() - y_[box]->Min());
262 break;
263 }
264 case 8: { // We push other down (y decreasing).
265 y_[box]->SetMin(y_[other]->Min() + dy_[other]->Min());
266 y_[other]->SetMax(y_[box]->Max() - dy_[other]->Min());
267 dy_[other]->SetMax(y_[box]->Max() - y_[other]->Min());
268 break;
269 }
270 default: {
271 break;
272 }
273 }
274 }
275
MakeCumulativeConstraint(const std::vector<IntVar * > & positions,const std::vector<int64_t> & sizes,const std::vector<IntVar * > & demands,int64_t capacity)276 Constraint* MakeCumulativeConstraint(const std::vector<IntVar*>& positions,
277 const std::vector<int64_t>& sizes,
278 const std::vector<IntVar*>& demands,
279 int64_t capacity) {
280 std::vector<IntervalVar*> intervals;
281 solver()->MakeFixedDurationIntervalVarArray(positions, sizes, "interval",
282 &intervals);
283 return solver()->MakeCumulative(intervals, demands, capacity, "cumul");
284 }
285
286 std::vector<IntVar*> x_;
287 std::vector<IntVar*> y_;
288 std::vector<IntVar*> dx_;
289 std::vector<IntVar*> dy_;
290 const bool strict_;
291 const int64_t size_;
292 Demon* delayed_demon_;
293 absl::flat_hash_set<int> to_propagate_;
294 std::vector<int> neighbors_;
295 uint64_t fail_stamp_;
296 };
297 } // namespace
298
MakeNonOverlappingBoxesConstraint(const std::vector<IntVar * > & x_vars,const std::vector<IntVar * > & y_vars,const std::vector<IntVar * > & x_size,const std::vector<IntVar * > & y_size)299 Constraint* Solver::MakeNonOverlappingBoxesConstraint(
300 const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
301 const std::vector<IntVar*>& x_size, const std::vector<IntVar*>& y_size) {
302 return RevAlloc(new Diffn(this, x_vars, y_vars, x_size, y_size, true));
303 }
304
MakeNonOverlappingBoxesConstraint(const std::vector<IntVar * > & x_vars,const std::vector<IntVar * > & y_vars,const std::vector<int64_t> & x_size,const std::vector<int64_t> & y_size)305 Constraint* Solver::MakeNonOverlappingBoxesConstraint(
306 const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
307 const std::vector<int64_t>& x_size, const std::vector<int64_t>& y_size) {
308 std::vector<IntVar*> dx(x_size.size());
309 std::vector<IntVar*> dy(y_size.size());
310 for (int i = 0; i < x_size.size(); ++i) {
311 dx[i] = MakeIntConst(x_size[i]);
312 dy[i] = MakeIntConst(y_size[i]);
313 }
314 return RevAlloc(new Diffn(this, x_vars, y_vars, dx, dy, true));
315 }
316
MakeNonOverlappingBoxesConstraint(const std::vector<IntVar * > & x_vars,const std::vector<IntVar * > & y_vars,const std::vector<int> & x_size,const std::vector<int> & y_size)317 Constraint* Solver::MakeNonOverlappingBoxesConstraint(
318 const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
319 const std::vector<int>& x_size, const std::vector<int>& y_size) {
320 std::vector<IntVar*> dx(x_size.size());
321 std::vector<IntVar*> dy(y_size.size());
322 for (int i = 0; i < x_size.size(); ++i) {
323 dx[i] = MakeIntConst(x_size[i]);
324 dy[i] = MakeIntConst(y_size[i]);
325 }
326 return RevAlloc(new Diffn(this, x_vars, y_vars, dx, dy, true));
327 }
328
MakeNonOverlappingNonStrictBoxesConstraint(const std::vector<IntVar * > & x_vars,const std::vector<IntVar * > & y_vars,const std::vector<IntVar * > & x_size,const std::vector<IntVar * > & y_size)329 Constraint* Solver::MakeNonOverlappingNonStrictBoxesConstraint(
330 const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
331 const std::vector<IntVar*>& x_size, const std::vector<IntVar*>& y_size) {
332 return RevAlloc(new Diffn(this, x_vars, y_vars, x_size, y_size, false));
333 }
334
MakeNonOverlappingNonStrictBoxesConstraint(const std::vector<IntVar * > & x_vars,const std::vector<IntVar * > & y_vars,const std::vector<int64_t> & x_size,const std::vector<int64_t> & y_size)335 Constraint* Solver::MakeNonOverlappingNonStrictBoxesConstraint(
336 const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
337 const std::vector<int64_t>& x_size, const std::vector<int64_t>& y_size) {
338 std::vector<IntVar*> dx(x_size.size());
339 std::vector<IntVar*> dy(y_size.size());
340 for (int i = 0; i < x_size.size(); ++i) {
341 dx[i] = MakeIntConst(x_size[i]);
342 dy[i] = MakeIntConst(y_size[i]);
343 }
344 return RevAlloc(new Diffn(this, x_vars, y_vars, dx, dy, false));
345 }
346
MakeNonOverlappingNonStrictBoxesConstraint(const std::vector<IntVar * > & x_vars,const std::vector<IntVar * > & y_vars,const std::vector<int> & x_size,const std::vector<int> & y_size)347 Constraint* Solver::MakeNonOverlappingNonStrictBoxesConstraint(
348 const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
349 const std::vector<int>& x_size, const std::vector<int>& y_size) {
350 std::vector<IntVar*> dx(x_size.size());
351 std::vector<IntVar*> dy(y_size.size());
352 for (int i = 0; i < x_size.size(); ++i) {
353 dx[i] = MakeIntConst(x_size[i]);
354 dy[i] = MakeIntConst(y_size[i]);
355 }
356 return RevAlloc(new Diffn(this, x_vars, y_vars, dx, dy, false));
357 }
358 } // namespace operations_research
359