Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
diffn.h
Go to the documentation of this file.
1// Copyright 2010-2025 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 <cstdint>
18#include <optional>
19#include <vector>
20
21#include "absl/container/flat_hash_set.h"
22#include "absl/types/span.h"
26#include "ortools/sat/integer.h"
28#include "ortools/sat/model.h"
33#include "ortools/sat/util.h"
34#include "ortools/util/bitset.h"
36
37namespace operations_research {
38namespace sat {
39
40// Propagates using a box energy reasoning.
42 public:
44 Model* model)
45 : helper_(*helper),
46 random_(model->GetOrCreate<ModelRandomGenerator>()),
47 shared_stats_(model->GetOrCreate<SharedStatistics>()),
48 orthogonal_packing_checker_(*random_, shared_stats_) {}
49
51
52 bool Propagate() final;
54
55 private:
56 struct Conflict {
57 // The Orthogonal Packing subproblem we used.
58 std::vector<RectangleInRange> items_for_opp;
59 Rectangle rectangle_with_too_much_energy;
60 OrthogonalPackingResult opp_result;
61 };
62 std::optional<Conflict> FindConflict(
63 std::vector<RectangleInRange> active_box_ranges);
64
65 std::vector<RectangleInRange> GeneralizeExplanation(const Conflict& conflict);
66
67 bool BuildAndReportEnergyTooLarge(absl::Span<const RectangleInRange> ranges);
68
69 NoOverlap2DConstraintHelper& helper_;
70 ModelRandomGenerator* random_;
71 SharedStatistics* shared_stats_;
72 OrthogonalPackingInfeasibilityDetector orthogonal_packing_checker_;
73
74 int64_t num_calls_ = 0;
75 int64_t num_conflicts_ = 0;
76 int64_t num_conflicts_two_boxes_ = 0;
77 int64_t num_refined_conflicts_ = 0;
78 int64_t num_conflicts_with_slack_ = 0;
79
84};
85
86// Enforces that the boxes with corners in (x, y), (x + dx, y), (x, y + dy)
87// and (x + dx, y + dy) do not overlap.
88void AddNonOverlappingRectangles(const std::vector<IntervalVariable>& x,
89 const std::vector<IntervalVariable>& y,
90 Model* model);
91
92// Non overlapping rectangles. This includes box with zero-areas.
93// The following is forbidden:
94// - a point box inside a box with a non zero area
95// - a line box overlapping a box with a non zero area
96// - one vertical line box crossing an horizontal line box.
98 : public PropagatorInterface {
99 public:
100 // The slow_propagators select which disjunctive algorithms to propagate.
102 NoOverlap2DConstraintHelper* helper, Model* model);
104
105 bool Propagate() final;
106 void Register(int fast_priority, int slow_priority);
107
108 private:
109 bool FindBoxesThatMustOverlapAHorizontalLineAndPropagate(
110 bool fast_propagation, absl::Span<const int> boxes);
111
114
115 GenericLiteralWatcher* watcher_;
116 TimeLimit* time_limit_;
117 int fast_id_; // Propagator id of the "fast" version.
118
119 // Temporary data.
120 std::vector<IndexedInterval> indexed_boxes_;
121 std::vector<Rectangle> rectangles_;
122 std::vector<int> order_;
123 CompactVectorVector<int> events_overlapping_boxes_;
124
125 // List of box that are fully fixed in the current dive, and for which we
126 // know they are no conflict between them.
127 bool rev_is_in_dive_ = false;
128 Bitset64<int> already_checked_fixed_boxes_;
129 int last_helper_inprocessing_count_ = -1;
130
131 absl::flat_hash_set<absl::Span<const int>> reduced_overlapping_boxes_;
132 std::vector<absl::Span<const int>> boxes_to_propagate_;
133 std::vector<absl::Span<const int>> disjoint_boxes_;
134 std::vector<int> non_zero_area_boxes_;
135
136 DisjunctiveOverloadChecker overload_checker_;
137 DisjunctiveDetectablePrecedences forward_detectable_precedences_;
138 DisjunctiveDetectablePrecedences backward_detectable_precedences_;
139 DisjunctiveNotLast forward_not_last_;
140 DisjunctiveNotLast backward_not_last_;
141 DisjunctiveEdgeFinding forward_edge_finding_;
142 DisjunctiveEdgeFinding backward_edge_finding_;
143 DisjunctiveWithTwoItems disjunctive_with_two_items_;
144
149};
150
151// Propagator that compares the boxes pairwise.
153 public:
155 : helper_(helper),
156 shared_stats_(model->GetOrCreate<SharedStatistics>()),
157 params_(model->GetOrCreate<SatParameters>()) {}
158
160
161 bool Propagate() final;
162 int RegisterWith(GenericLiteralWatcher* watcher);
163
164 private:
167 delete;
168
169 // Return false if a conflict is found.
170 bool FindRestrictionsAndPropagateConflict(
171 absl::Span<const ItemWithVariableSize> items1,
172 absl::Span<const ItemWithVariableSize> items2,
173 std::vector<PairwiseRestriction>* restrictions);
174
175 bool PropagateTwoBoxes(const PairwiseRestriction& restriction);
176
178 SharedStatistics* shared_stats_;
179 const SatParameters* params_;
180
181 int64_t num_calls_ = 0;
182 int64_t num_pairwise_conflicts_ = 0;
183 int64_t num_pairwise_propagations_ = 0;
184
185 std::vector<ItemWithVariableSize> fixed_non_zero_area_boxes_;
186 std::vector<ItemWithVariableSize> non_fixed_non_zero_area_boxes_;
187 std::vector<ItemWithVariableSize> horizontal_zero_area_boxes_;
188 std::vector<ItemWithVariableSize> vertical_zero_area_boxes_;
189 std::vector<ItemWithVariableSize> point_zero_area_boxes_;
190};
191
192} // namespace sat
193} // namespace operations_research
194
195#endif // OR_TOOLS_SAT_DIFFN_H_
Definition model.h:341
NonOverlappingRectanglesDisjunctivePropagator(NoOverlap2DConstraintHelper *helper, Model *model)
The slow_propagators select which disjunctive algorithms to propagate.
Definition diffn.cc:669
void Register(int fast_priority, int slow_priority)
Definition diffn.cc:687
NonOverlappingRectanglesEnergyPropagator(NoOverlap2DConstraintHelper *helper, Model *model)
Definition diffn.h:43
Propagator that compares the boxes pairwise.
Definition diffn.h:152
RectanglePairwisePropagator(NoOverlap2DConstraintHelper *helper, Model *model)
Definition diffn.h:154
Simple class to add statistics by name and print them at the end.
void AddNonOverlappingRectangles(const std::vector< IntervalVariable > &x, const std::vector< IntervalVariable > &y, Model *model)
Definition diffn.cc:180
In SWIG mode, we don't want anything besides these top-level includes.
STL namespace.