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"
20 #include "ortools/base/int_type.h"
22 #include "ortools/base/logging.h"
26 
27 namespace operations_research {
28 // Diffn constraint, Non overlapping boxs.
29 namespace {
30 DEFINE_INT_TYPE(Box, int);
31 class 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.
T * RevAlloc(T *object)
Registers the given object as being reversible.
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.
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...
Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
int64 MinVarArray(const std::vector< IntVar * > &vars)
void FillValues(const std::vector< IntVar * > &vars, std::vector< int64 > *const values)
Demon * MakeDelayedConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
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)
bool AreAllBound(const std::vector< IntVar * > &vars)
int64 capacity