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