18 #include "absl/strings/str_format.h"
31 class Diffn :
public Constraint {
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)
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());
51 void Post()
override {
52 Solver*
const s = solver();
53 for (
int i = 0; i < size_; ++i) {
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);
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;
81 std::vector<int64> size_x;
83 ct1 = MakeCumulativeConstraint(x_, size_x, dy_,
84 max_size_y + max_y - min_y);
87 std::vector<int64> size_y;
89 ct2 = MakeCumulativeConstraint(y_, size_y, dx_,
90 max_size_x + max_x - min_x);
94 s->AddConstraint(ct1);
97 s->AddConstraint(ct2);
102 void InitialPropagate()
override {
104 for (
int i = 0; i < size_; ++i) {
110 to_propagate_.clear();
111 for (
int i = 0; i < size_; i++) {
112 to_propagate_.insert(i);
117 std::string DebugString()
const override {
118 return absl::StrFormat(
119 "Diffn(x = [%s], y = [%s], dx = [%s], dy = [%s]))",
124 void Accept(ModelVisitor*
const visitor)
const override {
138 void PropagateAll() {
139 for (
const int box : to_propagate_) {
141 FailWhenEnergyIsTooLarge(box);
142 PushOverlappingBoxes(box);
144 to_propagate_.clear();
145 fail_stamp_ = solver()->fail_stamp();
148 void OnBoxRangeChange(
int box) {
149 if (solver()->fail_stamp() > fail_stamp_ && !to_propagate_.empty()) {
152 fail_stamp_ = solver()->fail_stamp();
153 to_propagate_.clear();
155 to_propagate_.insert(box);
156 EnqueueDelayedDemon(delayed_demon_);
159 bool CanBoxedOverlap(
int i,
int j)
const {
160 if (AreBoxedDisjoingHorizontallyForSure(i, j) ||
161 AreBoxedDisjoingVerticallyForSure(i, j)) {
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));
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));
180 void FillNeighbors(
int box) {
184 for (
int other = 0; other < size_; ++other) {
185 if (other != box && CanBoxedOverlap(other, box)) {
186 neighbors_.push_back(other);
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();
202 for (
int i = 0; i < neighbors_.size(); ++i) {
203 const int other = neighbors_[i];
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());
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) {
222 void PushOverlappingBoxes(
int box) {
223 for (
int i = 0; i < neighbors_.size(); ++i) {
224 PushOneBox(box, neighbors_[i]);
231 void PushOneBox(
int box,
int other) {
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());
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());
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());
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());
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());
274 Constraint* MakeCumulativeConstraint(
const std::vector<IntVar*>& positions,
275 const std::vector<int64>& sizes,
276 const std::vector<IntVar*>& demands,
278 std::vector<IntervalVar*> intervals;
279 solver()->MakeFixedDurationIntervalVarArray(positions, sizes,
"interval",
281 return solver()->MakeCumulative(intervals, demands,
capacity,
"cumul");
284 std::vector<IntVar*> x_;
285 std::vector<IntVar*> y_;
286 std::vector<IntVar*> dx_;
287 std::vector<IntVar*> dy_;
290 Demon* delayed_demon_;
291 absl::flat_hash_set<int> to_propagate_;
292 std::vector<int> neighbors_;
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));
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) {
312 return RevAlloc(
new Diffn(
this, x_vars, y_vars, dx, dy,
true));
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) {
324 return RevAlloc(
new Diffn(
this, x_vars, y_vars, dx, dy,
true));
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));
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) {
342 return RevAlloc(
new Diffn(
this, x_vars, y_vars, dx, dy,
false));
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) {
354 return RevAlloc(
new Diffn(
this, x_vars, y_vars, dx, dy,
false));
#define CHECK_EQ(val1, val2)
A constraint is the main modeling object.
static const char kDisjunctive[]
static const char kPositionXArgument[]
static const char kSizeXArgument[]
static const char kSizeYArgument[]
static const char kPositionYArgument[]
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.
static const int64 kint64max
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)
int64 MaxVarArray(const std::vector< IntVar * > &vars)
bool AreAllBound(const std::vector< IntVar * > &vars)