OR-Tools  8.2
diffn.h
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#ifndef OR_TOOLS_SAT_DIFFN_H_
15#define OR_TOOLS_SAT_DIFFN_H_
16
17#include <vector>
18
22#include "ortools/base/macros.h"
24#include "ortools/sat/integer.h"
26#include "ortools/sat/model.h"
28
29namespace operations_research {
30namespace sat {
31
32// Propagates using a box energy reasoning.
34 public:
35 // The strict parameters indicates how to place zero width or zero height
36 // boxes. If strict is true, these boxes must not 'cross' another box, and are
37 // pushed by the other boxes.
40 : x_(*x), y_(*y) {}
42
43 bool Propagate() final;
45
46 private:
47 void SortBoxesIntoNeighbors(int box, absl::Span<const int> local_boxes,
48 IntegerValue total_sum_of_areas);
49 bool FailWhenEnergyIsTooLarge(int box, absl::Span<const int> local_boxes,
50 IntegerValue total_sum_of_areas);
51
54
55 std::vector<absl::Span<int>> x_split_;
56 std::vector<absl::Span<int>> y_split_;
57
58 std::vector<int> active_boxes_;
59 std::vector<IntegerValue> cached_areas_;
60
61 struct Dimension {
62 IntegerValue x_min;
63 IntegerValue x_max;
64 IntegerValue y_min;
65 IntegerValue y_max;
66
67 void TakeUnionWith(const Dimension& other) {
68 x_min = std::min(x_min, other.x_min);
69 y_min = std::min(y_min, other.y_min);
70 x_max = std::max(x_max, other.x_max);
71 y_max = std::max(y_max, other.y_max);
72 }
73 };
74 std::vector<Dimension> cached_dimensions_;
75
76 struct Neighbor {
77 int box;
78 IntegerValue distance_to_bounding_box;
79 bool operator<(const Neighbor& o) const {
80 return distance_to_bounding_box < o.distance_to_bounding_box;
81 }
82 };
83 std::vector<Neighbor> neighbors_;
84
89};
90
91// Non overlapping rectangles.
93 : public PropagatorInterface {
94 public:
95 // The strict parameters indicates how to place zero width or zero height
96 // boxes. If strict is true, these boxes must not 'cross' another box, and are
97 // pushed by the other boxes.
98 // The slow_propagators select which disjunctive algorithms to propagate.
102 Model* model);
104
105 bool Propagate() final;
106 void Register(int fast_priority, int slow_priority);
107
108 private:
109 bool PropagateTwoBoxes();
110 bool FindBoxesThatMustOverlapAHorizontalLineAndPropagate(
112 std::function<bool()> inner_propagate);
113
118 const bool strict_;
119
120 GenericLiteralWatcher* watcher_;
121 int fast_id_; // Propagator id of the "fast" version.
122
123 std::vector<int> active_boxes_;
124 std::vector<IntegerValue> events_time_;
125 std::vector<std::vector<int>> events_overlapping_boxes_;
126
127 absl::flat_hash_set<absl::Span<int>> reduced_overlapping_boxes_;
128 std::vector<absl::Span<int>> boxes_to_propagate_;
129 std::vector<absl::Span<int>> disjoint_boxes_;
130
131 DisjunctiveOverloadChecker overload_checker_;
132 DisjunctiveDetectablePrecedences forward_detectable_precedences_;
133 DisjunctiveDetectablePrecedences backward_detectable_precedences_;
134 DisjunctiveNotLast forward_not_last_;
135 DisjunctiveNotLast backward_not_last_;
136 DisjunctiveEdgeFinding forward_edge_finding_;
137 DisjunctiveEdgeFinding backward_edge_finding_;
138
143};
144
145// Add a cumulative relaxation. That is, on one dimension, it does not enforce
146// the rectangle aspect, allowing vertical slices to move freely.
147void AddCumulativeRelaxation(const std::vector<IntervalVariable>& x_intervals,
150
151// Enforces that the boxes with corners in (x, y), (x + dx, y), (x, y + dy)
152// and (x + dx, y + dy) do not overlap.
153// If strict is true, and if one box has a zero dimension, it still cannot
154// intersect another box.
155inline std::function<void(Model*)> NonOverlappingRectangles(
156 const std::vector<IntervalVariable>& x,
157 const std::vector<IntervalVariable>& y, bool is_strict) {
158 return [=](Model* model) {
163 model->TakeOwnership(x_helper);
164 model->TakeOwnership(y_helper);
165
167 new NonOverlappingRectanglesEnergyPropagator(x_helper, y_helper);
168 GenericLiteralWatcher* const watcher =
169 model->GetOrCreate<GenericLiteralWatcher>();
170 watcher->SetPropagatorPriority(energy_constraint->RegisterWith(watcher), 3);
171 model->TakeOwnership(energy_constraint);
172
174 new NonOverlappingRectanglesDisjunctivePropagator(is_strict, x_helper,
175 y_helper, model);
176 constraint->Register(/*fast_priority=*/3, /*slow_priority=*/4);
177 model->TakeOwnership(constraint);
178
179 AddCumulativeRelaxation(x, x_helper, y_helper, model);
180 AddCumulativeRelaxation(y, y_helper, x_helper, model);
181 };
182}
183
184} // namespace sat
185} // namespace operations_research
186
187#endif // OR_TOOLS_SAT_DIFFN_H_
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
void SetPropagatorPriority(int id, int priority)
Definition: integer.cc:1962
Class that owns everything related to a particular optimization model.
Definition: sat/model.h:38
NonOverlappingRectanglesDisjunctivePropagator(bool strict, SchedulingConstraintHelper *x, SchedulingConstraintHelper *y, Model *model)
Definition: sat/diffn.cc:295
NonOverlappingRectanglesEnergyPropagator(SchedulingConstraintHelper *x, SchedulingConstraintHelper *y)
Definition: diffn.h:38
GRBmodel * model
Definition: cleanup.h:22
std::function< void(Model *)> NonOverlappingRectangles(const std::vector< IntervalVariable > &x, const std::vector< IntervalVariable > &y, bool is_strict)
Definition: diffn.h:155
void AddCumulativeRelaxation(const std::vector< IntervalVariable > &x_intervals, SchedulingConstraintHelper *x, SchedulingConstraintHelper *y, Model *model)
Definition: sat/diffn.cc:77
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
STL namespace.