Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
diffn_util.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_UTIL_H_
15#define OR_TOOLS_SAT_DIFFN_UTIL_H_
16
17#include <algorithm>
18#include <cmath>
19#include <cstdlib>
20#include <limits>
21#include <optional>
22#include <string>
23#include <string_view>
24#include <tuple>
25#include <utility>
26#include <vector>
27
28#include "absl/container/flat_hash_set.h"
29#include "absl/container/inlined_vector.h"
30#include "absl/log/check.h"
31#include "absl/random/bit_gen_ref.h"
32#include "absl/strings/str_format.h"
33#include "absl/types/optional.h"
34#include "absl/types/span.h"
37#include "ortools/sat/util.h"
40
41namespace operations_research {
42namespace sat {
43
44struct Rectangle {
45 IntegerValue x_min;
46 IntegerValue x_max;
47 IntegerValue y_min;
48 IntegerValue y_max;
49
50 void GrowToInclude(const Rectangle& other) {
51 x_min = std::min(x_min, other.x_min);
52 y_min = std::min(y_min, other.y_min);
53 x_max = std::max(x_max, other.x_max);
54 y_max = std::max(y_max, other.y_max);
55 }
56
57 IntegerValue Area() const { return SizeX() * SizeY(); }
58
59 IntegerValue CapArea() const {
61 }
62
63 IntegerValue SizeX() const { return x_max - x_min; }
64 IntegerValue SizeY() const { return y_max - y_min; }
65
66 bool IsDisjoint(const Rectangle& other) const;
67
68 // The methods below are not meant to be used with zero-area rectangles.
69
70 // Returns an empty rectangle if no intersection.
71 Rectangle Intersect(const Rectangle& other) const;
72 IntegerValue IntersectArea(const Rectangle& other) const;
73
74 bool IsInsideOf(const Rectangle& other) const {
75 return x_min >= other.x_min && x_max <= other.x_max &&
76 y_min >= other.y_min && y_max <= other.y_max;
77 }
78
79 // Returns `this \ other` as a set of disjoint rectangles of non-empty area.
80 // The resulting vector will have at most four elements.
81 absl::InlinedVector<Rectangle, 4> RegionDifference(
82 const Rectangle& other) const;
83
84 template <typename Sink>
85 friend void AbslStringify(Sink& sink, const Rectangle& r) {
86 absl::Format(&sink, "rectangle(x(%i..%i), y(%i..%i))", r.x_min.value(),
87 r.x_max.value(), r.y_min.value(), r.y_max.value());
88 }
89
90 bool operator==(const Rectangle& other) const {
91 return std::tie(x_min, x_max, y_min, y_max) ==
92 std::tie(other.x_min, other.x_max, other.y_min, other.y_max);
93 }
94
95 bool operator!=(const Rectangle& other) const { return !(other == *this); }
96
98 return Rectangle{.x_min = IntegerValue(0),
99 .x_max = IntegerValue(0),
100 .y_min = IntegerValue(0),
101 .y_max = IntegerValue(0)};
102 }
103};
104
105inline Rectangle Rectangle::Intersect(const Rectangle& other) const {
106 const IntegerValue ret_x_min = std::max(x_min, other.x_min);
107 const IntegerValue ret_y_min = std::max(y_min, other.y_min);
108 const IntegerValue ret_x_max = std::min(x_max, other.x_max);
109 const IntegerValue ret_y_max = std::min(y_max, other.y_max);
110
111 if (ret_x_min >= ret_x_max || ret_y_min >= ret_y_max) {
112 return GetEmpty();
113 } else {
114 return Rectangle{.x_min = ret_x_min,
115 .x_max = ret_x_max,
116 .y_min = ret_y_min,
117 .y_max = ret_y_max};
118 }
119}
120
121inline IntegerValue Rectangle::IntersectArea(const Rectangle& other) const {
122 const IntegerValue ret_x_min = std::max(x_min, other.x_min);
123 const IntegerValue ret_y_min = std::max(y_min, other.y_min);
124 const IntegerValue ret_x_max = std::min(x_max, other.x_max);
125 const IntegerValue ret_y_max = std::min(y_max, other.y_max);
126
127 if (ret_x_min >= ret_x_max || ret_y_min >= ret_y_max) {
128 return 0;
129 } else {
130 return (ret_x_max - ret_x_min) * (ret_y_max - ret_y_min);
131 }
132}
133
134// Returns the L2 distance between the centers of the two rectangles.
135inline double CenterToCenterL2Distance(const Rectangle& a, const Rectangle& b) {
136 const double diff_x =
137 (static_cast<double>(a.x_min.value()) + a.x_max.value()) / 2.0 -
138 (static_cast<double>(b.x_min.value()) + b.x_max.value()) / 2.0;
139 const double diff_y =
140 (static_cast<double>(a.y_min.value()) + a.y_max.value()) / 2.0 -
141 (static_cast<double>(b.y_min.value()) + b.y_max.value()) / 2.0;
142 return std::sqrt(diff_x * diff_x + diff_y * diff_y);
143}
144
146 const Rectangle& b) {
147 const double diff_x =
148 (static_cast<double>(a.x_min.value()) + a.x_max.value()) / 2.0 -
149 (static_cast<double>(b.x_min.value()) + b.x_max.value()) / 2.0;
150 const double diff_y =
151 (static_cast<double>(a.y_min.value()) + a.y_max.value()) / 2.0 -
152 (static_cast<double>(b.y_min.value()) + b.y_max.value()) / 2.0;
153 return std::max(std::abs(diff_x), std::abs(diff_y));
154}
155
156// Creates a graph when two nodes are connected iff their rectangles overlap.
157// Then partition into connected components.
158CompactVectorVector<int> GetOverlappingRectangleComponents(
159 absl::Span<const Rectangle> rectangles);
160
161// Visible for testing. The algo is in O(n^4) so shouldn't be used directly.
162// Returns true if there exist a bounding box with too much energy.
163bool BoxesAreInEnergyConflict(absl::Span<const Rectangle> rectangles,
164 absl::Span<const IntegerValue> energies,
165 absl::Span<const int> boxes,
166 Rectangle* conflict = nullptr);
167
168// Checks that there is indeed a conflict for the given bounding_box and
169// report it. This returns false for convenience as we usually want to return
170// false on a conflict.
171//
172// TODO(user): relax the bounding box dimension to have a relaxed explanation.
173// We can also minimize the number of required intervals.
174bool ReportEnergyConflict(Rectangle bounding_box, absl::Span<const int> boxes,
175 SchedulingConstraintHelper* x,
176 SchedulingConstraintHelper* y);
177
178// A O(n^2) algorithm to analyze all the relevant X intervals and infer a
179// threshold of the y size of a bounding box after which there is no point
180// checking for energy overload.
181//
182// Returns false on conflict, and fill the bounding box that caused the
183// conflict.
184//
185// If transpose is true, we analyze the relevant Y intervals instead.
186bool AnalyzeIntervals(bool transpose, absl::Span<const int> boxes,
187 absl::Span<const Rectangle> rectangles,
188 absl::Span<const IntegerValue> rectangle_energies,
189 IntegerValue* x_threshold, IntegerValue* y_threshold,
190 Rectangle* conflict = nullptr);
191
192// Removes boxes with a size above the thresholds. Also randomize the order.
193// Because we rely on various heuristic, this allow to change the order from
194// one call to the next.
195absl::Span<int> FilterBoxesAndRandomize(
196 absl::Span<const Rectangle> cached_rectangles, absl::Span<int> boxes,
197 IntegerValue threshold_x, IntegerValue threshold_y, absl::BitGenRef random);
198
199// Given the total energy of all rectangles (sum of energies[box]) we know that
200// any box with an area greater than that cannot participate in any "bounding
201// box" conflict. As we remove this box, the total energy decrease, so we might
202// remove more. This works in O(n log n).
203absl::Span<int> FilterBoxesThatAreTooLarge(
204 absl::Span<const Rectangle> cached_rectangles,
205 absl::Span<const IntegerValue> energies, absl::Span<int> boxes);
206
208 int index;
209 IntegerValue start;
210 IntegerValue end;
211
212 bool operator==(const IndexedInterval& rhs) const {
213 return std::tie(start, end, index) ==
214 std::tie(rhs.start, rhs.end, rhs.index);
215 }
216
217 // NOTE(user): We would like to use TUPLE_DEFINE_STRUCT, but sadly it doesn't
218 // support //buildenv/target:non_prod.
220 bool operator()(const IndexedInterval& a, const IndexedInterval& b) const {
221 return std::tie(a.start, a.end, a.index) <
222 std::tie(b.start, b.end, b.index);
223 }
224 };
226 bool operator()(const IndexedInterval& a, const IndexedInterval& b) const {
227 return a.start < b.start;
228 }
229 };
230
231 template <typename Sink>
232 friend void AbslStringify(Sink& sink, const IndexedInterval& interval) {
233 absl::Format(&sink, "[%v..%v] (#%v)", interval.start, interval.end,
234 interval.index);
235 }
236};
237
238// Given n fixed intervals that must be sorted by
239// IndexedInterval::ComparatorByStart(), returns the subsets of intervals that
240// overlap during at least one time unit. Note that we only return "maximal"
241// subset and filter subset strictly included in another.
242//
243// IMPORTANT: The span of intervals will not be usable after this function! this
244// could be changed if needed with an extra copy.
245//
246// All Intervals must have a positive size.
247//
248// The algo is in O(n log n) + O(result_size) which is usually O(n^2).
249//
250// If the last argument is not empty, we will sort the interval in the result
251// according to the given order, i.e. i will be before j if order[i] < order[j].
252void ConstructOverlappingSets(absl::Span<IndexedInterval> intervals,
253 CompactVectorVector<int>* result,
254 absl::Span<const int> order = {});
255
256// Given n intervals, returns the set of connected components (using the overlap
257// relation between 2 intervals). Components are sorted by their start, and
258// inside a component, the intervals are also sorted by start.
259// `intervals` is only sorted (by start), and not modified otherwise.
261 std::vector<IndexedInterval>* intervals,
262 std::vector<std::vector<int>>* components);
263
264// Similar to GetOverlappingIntervalComponents(), but returns the indices of
265// all intervals whose removal would create one more connected component in the
266// interval graph. Those are sorted by start. See:
267// https://en.wikipedia.org/wiki/Glossary_of_graph_theory#articulation_point.
268std::vector<int> GetIntervalArticulationPoints(
269 std::vector<IndexedInterval>* intervals);
270
272 struct Interval {
273 bool IsFixed() const {
274 return start_min == start_max && end_min == end_max;
275 }
276
277 IntegerValue start_min;
278 IntegerValue start_max;
279 IntegerValue end_min;
280 IntegerValue end_max;
281 };
282
283 bool IsFixed() const { return x.IsFixed() && y.IsFixed(); }
284
285 template <typename Sink>
286 friend void AbslStringify(Sink& sink, const ItemWithVariableSize& item) {
287 absl::Format(&sink, "Item %v: [(%v..%v)-(%v..%v)] x [(%v..%v)-(%v..%v)]",
288 item.index, item.x.start_min, item.x.start_max, item.x.end_min,
289 item.x.end_max, item.y.start_min, item.y.start_max,
290 item.y.end_min, item.y.end_max);
291 }
292
293 int index;
296};
297
316
317// Find pair of items that are either in conflict or could have their range
318// shrinked to avoid conflict.
319void AppendPairwiseRestrictions(absl::Span<const ItemWithVariableSize> items,
320 std::vector<PairwiseRestriction>* result);
321
322// Same as above, but test `items` against `other_items` and append the
323// restrictions found to `result`.
325 absl::Span<const ItemWithVariableSize> items,
326 absl::Span<const ItemWithVariableSize> other_items,
327 std::vector<PairwiseRestriction>* result);
328
329// This class is used by the no_overlap_2d constraint to maintain the envelope
330// of a set of rectangles. This envelope is not the convex hull, but the exact
331// polyline (aligned with the x and y axis) that contains all the rectangles
332// passed with the AddRectangle() call.
334 public:
335 // Simple start of a rectangle. This is used to represent the residual
336 // capacity profile.
337 struct Rectangle {
338 Rectangle(IntegerValue start, IntegerValue height)
339 : start(start), height(height) {}
340
341 bool operator<(const Rectangle& other) const { return start < other.start; }
342 bool operator==(const Rectangle& other) const {
343 return start == other.start && height == other.height;
344 }
345
346 IntegerValue start = IntegerValue(0);
347 IntegerValue height = IntegerValue(0);
348 };
349
350 void Clear();
351
352 // Adds a rectangle to the current shape.
353 void AddRectangle(IntegerValue x_min, IntegerValue x_max, IntegerValue y_min,
354 IntegerValue y_max);
355
356 // Adds a mandatory profile consumption. All mandatory usages will be
357 // subtracted from the y_max-y_min profile to build the residual capacity.
358 void AddMandatoryConsumption(IntegerValue x_min, IntegerValue x_max,
359 IntegerValue y_height);
360
361 // Returns the profile of the function:
362 // capacity(x) = max(y_max of rectangles overlapping x) - min(y_min of
363 // rectangle overlapping x) - sum(y_height of mandatory rectangles
364 // overlapping x) where a rectangle overlaps x if x_min <= x < x_max.
365 //
366 // Note the profile can contain negative heights in case the mandatory part
367 // exceeds the range on the y axis.
368 //
369 // Note that it adds a sentinel (kMinIntegerValue, 0) at the start. It is
370 // useful when we reverse the direction on the x axis.
371 void BuildResidualCapacityProfile(std::vector<Rectangle>* result);
372
373 // Returns the exact area of the bounding polyline of all rectangles added.
374 //
375 // Note that this will redo the computation each time.
376 IntegerValue GetBoundingArea();
377
378 private:
379 // Type for the capacity events.
380 enum EventType { START_RECTANGLE, END_RECTANGLE, CHANGE_MANDATORY_PROFILE };
381
382 // Individual events.
383 struct Event {
384 IntegerValue time;
385 IntegerValue y_min;
386 IntegerValue y_max;
387 EventType type;
388 int index;
389
390 bool operator<(const Event& other) const { return time < other.time; }
391 };
392
393 // Element of the integer_pq heap.
394 struct QueueElement {
395 int Index() const { return index; }
396 bool operator<(const QueueElement& o) const { return value < o.value; }
397
398 int index;
399 IntegerValue value;
400 };
401
402 static Event StartRectangleEvent(int index, IntegerValue x_min,
403 IntegerValue y_min, IntegerValue y_max) {
404 return {x_min, y_min, y_max, START_RECTANGLE, index};
405 }
406
407 static Event EndRectangleEvent(int index, IntegerValue x_max) {
408 return {x_max, kMinIntegerValue, kMinIntegerValue, END_RECTANGLE, index};
409 }
410
411 static Event ChangeMandatoryProfileEvent(IntegerValue x, IntegerValue delta) {
412 return {x, /*y_min=*/delta, /*y_max=*/kMinIntegerValue,
413 CHANGE_MANDATORY_PROFILE, /*index=*/-1};
414 }
415
416 std::vector<Event> events_;
417 int num_rectangles_added_ = 0;
418};
419
420// 1D counterpart of RectangleInRange::GetMinimumIntersectionArea.
421// Finds the minimum possible overlap of a interval of size `size` that fits in
422// [range_min, range_max] and a second interval [interval_min, interval_max].
423IntegerValue Smallest1DIntersection(IntegerValue range_min,
424 IntegerValue range_max, IntegerValue size,
425 IntegerValue interval_min,
426 IntegerValue interval_max);
427
428// A rectangle of size (`x_size`, `y_size`) that can freely move inside the
429// `bounding_area` rectangle.
433 IntegerValue x_size;
434 IntegerValue y_size;
435
442
443 bool operator==(const RectangleInRange& other) const {
444 return box_index == other.box_index &&
445 bounding_area == other.bounding_area && x_size == other.x_size &&
446 y_size == other.y_size;
447 }
448
449 // Returns the position of the rectangle fixed to one of the corner of its
450 // range.
452 switch (p) {
454 return Rectangle{.x_min = bounding_area.x_min,
455 .x_max = bounding_area.x_min + x_size,
456 .y_min = bounding_area.y_min,
457 .y_max = bounding_area.y_min + y_size};
458 case Corner::TOP_LEFT:
459 return Rectangle{.x_min = bounding_area.x_min,
460 .x_max = bounding_area.x_min + x_size,
461 .y_min = bounding_area.y_max - y_size,
462 .y_max = bounding_area.y_max};
464 return Rectangle{.x_min = bounding_area.x_max - x_size,
465 .x_max = bounding_area.x_max,
466 .y_min = bounding_area.y_min,
467 .y_max = bounding_area.y_min + y_size};
469 return Rectangle{.x_min = bounding_area.x_max - x_size,
470 .x_max = bounding_area.x_max,
471 .y_min = bounding_area.y_max - y_size,
472 .y_max = bounding_area.y_max};
473 }
474 }
475
477
478 // Returns an empty rectangle if it is possible for no intersection to happen.
479 Rectangle GetMinimumIntersection(const Rectangle& containing_area) const {
480 IntegerValue smallest_area = std::numeric_limits<IntegerValue>::max();
481 Rectangle best_intersection;
482 for (int corner_idx = 0; corner_idx < 4; ++corner_idx) {
483 const Corner p = static_cast<Corner>(corner_idx);
484 Rectangle intersection = containing_area.Intersect(GetAtCorner(p));
485 const IntegerValue intersection_area = intersection.Area();
486 if (intersection_area == 0) {
487 return Rectangle::GetEmpty();
488 }
489 if (intersection_area < smallest_area) {
490 smallest_area = intersection_area;
491 best_intersection = std::move(intersection);
492 }
493 }
494 return best_intersection;
495 }
496
498 const Rectangle& containing_area) const {
500 x_size, containing_area.x_min,
501 containing_area.x_max) *
503 y_size, containing_area.y_min,
504 containing_area.y_max);
505 }
506
508 // Weird math to avoid overflow.
509 if (bounding_area.SizeX() - x_size >= x_size ||
510 bounding_area.SizeY() - y_size >= y_size) {
511 return Rectangle::GetEmpty();
512 }
513 return Rectangle{.x_min = bounding_area.x_max - x_size,
514 .x_max = bounding_area.x_min + x_size,
515 .y_min = bounding_area.y_max - y_size,
516 .y_max = bounding_area.y_min + y_size};
517 }
518
520 const Rectangle& containing_area, const RectangleInRange& original,
521 const IntegerValue& min_intersect_x,
522 const IntegerValue& min_intersect_y) {
523 const IntegerValue x_size = original.x_size;
524 const IntegerValue y_size = original.y_size;
525
526 RectangleInRange result;
527 result.x_size = x_size;
528 result.y_size = y_size;
529 result.box_index = original.box_index;
530
531 // We cannot intersect more units than the whole item.
532 DCHECK_GE(x_size, min_intersect_x);
533 DCHECK_GE(y_size, min_intersect_y);
534
535 // Units that can *not* intersect per dimension.
536 const IntegerValue x_headroom = x_size - min_intersect_x;
537 const IntegerValue y_headroom = y_size - min_intersect_y;
538
539 result.bounding_area.x_min = containing_area.x_min - x_headroom;
540 result.bounding_area.x_max = containing_area.x_max + x_headroom;
541 result.bounding_area.y_min = containing_area.y_min - y_headroom;
542 result.bounding_area.y_max = containing_area.y_max + y_headroom;
543
544 return result;
545 }
546
547 template <typename Sink>
548 friend void AbslStringify(Sink& sink, const RectangleInRange& r) {
549 absl::Format(&sink, "item(size=%vx%v, BB=%v)", r.x_size, r.y_size,
550 r.bounding_area);
551 }
552};
553
554// Cheaply test several increasingly smaller rectangles for energy conflict.
555// More precisely, each call to `Shrink()` cost O(k + n) operations, where k is
556// the number of points that shrinking the probing rectangle will cross and n is
557// the number of items which are in a range that overlaps the probing rectangle
558// in both sides in the dimension that is getting shrinked. When calling
559// repeatedely `Shrink()` until the probing rectangle collapse into a single
560// point, the O(k) component adds up to a O(M) cost, where M is the number of
561// items. This means this procedure is linear in time if the ranges of the items
562// are small.
563//
564// The energy is defined as the minimum occupied area inside the probing
565// rectangle. For more details, see Clautiaux, François, et al. "A new
566// constraint programming approach for the orthogonal packing problem."
567// Computers & Operations Research 35.3 (2008): 944-959.
568//
569// This is used by FindRectanglesWithEnergyConflictMC() below.
571 public:
572 // It will initialize with the bounding box of the whole set.
573 explicit ProbingRectangle(const std::vector<RectangleInRange>& intervals);
574
575 enum Edge { TOP = 0, LEFT = 1, BOTTOM = 2, RIGHT = 3 };
576
577 // Reset to the bounding box of the whole set.
578 void Reset();
579
580 // Shrink the rectangle by moving one of its four edges to the next
581 // "interesting" value. The interesting values for x or y are the ones that
582 // correspond to a boundary, ie., a value that corresponds to one of {min,
583 // min + size, max - size, max} of a rectangle.
584 void Shrink(Edge edge);
585
586 bool CanShrink(Edge edge) const;
587
588 bool IsMinimal() const {
589 // We only need to know if there is slack on both dimensions. Actually
590 // CanShrink(BOTTOM) == CanShrink(TOP) and conversely.
592 }
593
594 // Test-only method that check that all internal incremental counts are
595 // correct by comparing with recalculating them from scratch.
596 void ValidateInvariants() const;
597
598 // How much of GetMinimumEnergy() will change if Shrink() is called.
599 IntegerValue GetShrinkDeltaEnergy(Edge edge) const {
600 return cached_delta_energy_[edge];
601 }
602
603 // How much of GetCurrentRectangleArea() will change if Shrink() is called.
604 IntegerValue GetShrinkDeltaArea(Edge edge) const;
605
607 IntegerValue GetCurrentRectangleArea() const { return probe_area_; }
608
609 // This is equivalent of, for every item:
610 // - Call GetMinimumIntersectionArea() with GetCurrentRectangle().
611 // - Return the total sum of the areas.
612 IntegerValue GetMinimumEnergy() const { return minimum_energy_; }
613
614 const std::vector<RectangleInRange>& Intervals() const { return intervals_; }
615
620
621 private:
622 void CacheShrinkDeltaEnergy(int dimension);
623
624 template <Edge edge>
625 void ShrinkImpl();
626
627 struct IntervalPoint {
628 IntegerValue value;
629 int index;
630 };
631
632 std::vector<IntervalPoint> interval_points_sorted_by_x_;
633 std::vector<IntervalPoint> interval_points_sorted_by_y_;
634
635 // Those two vectors are not strictly needed, we could instead iterate
636 // directly on the two vectors above, but the code would be much uglier.
637 struct PointsForCoordinate {
638 IntegerValue coordinate;
639 absl::Span<IntervalPoint> items_touching_coordinate;
640 };
641 std::vector<PointsForCoordinate> grouped_intervals_sorted_by_x_;
642 std::vector<PointsForCoordinate> grouped_intervals_sorted_by_y_;
643
644 const std::vector<RectangleInRange>& intervals_;
645
646 IntegerValue full_energy_;
647 IntegerValue minimum_energy_;
648 IntegerValue probe_area_;
649 int indexes_[4];
650 int next_indexes_[4];
651
652 absl::flat_hash_set<int> ranges_touching_both_boundaries_[2];
653 IntegerValue corner_count_[4] = {0, 0, 0, 0};
654 IntegerValue intersect_length_[4] = {0, 0, 0, 0};
655 IntegerValue cached_delta_energy_[4];
656};
657
658// Monte-Carlo inspired heuristic to find a rectangles with an energy conflict:
659// - start with a rectangle equals to the full bounding box of the elements;
660// - shrink the rectangle by an edge to the next "interesting" value. Choose
661// the edge randomly, but biased towards the change that increases the ratio
662// area_inside / area_rectangle;
663// - collect a result at every conflict or every time the ratio
664// used_energy/available_energy is more than `candidate_energy_usage_factor`;
665// - stop when the rectangle is empty.
667 // Known conflicts: the minimal energy used inside the rectangle is larger
668 // than the area of the rectangle.
669 std::vector<Rectangle> conflicts;
670 // Rectangles without a conflict but having used_energy/available_energy >
671 // candidate_energy_usage_factor. Those are good candidates for finding
672 // conflicts using more sophisticated heuristics. Those rectangles are
673 // ordered so the n-th rectangle is always fully inside the n-1-th one.
674 std::vector<Rectangle> candidates;
675};
677 const std::vector<RectangleInRange>& intervals, absl::BitGenRef random,
678 double temperature, double candidate_energy_usage_factor);
679
680// Render a packing solution as a Graphviz dot file. Only works in the "neato"
681// or "fdp" Graphviz backends.
682std::string RenderDot(std::optional<Rectangle> bb,
683 absl::Span<const Rectangle> solution,
684 std::string_view extra_dot_payload = "");
685
686// Given a bounding box and a list of rectangles inside that bounding box,
687// returns a list of rectangles partitioning the empty area inside the bounding
688// box.
689std::vector<Rectangle> FindEmptySpaces(
690 const Rectangle& bounding_box, std::vector<Rectangle> ocupied_rectangles);
691
692// Given two regions, each one of them defined by a vector of non-overlapping
693// rectangles paving them, returns a vector of non-overlapping rectangles that
694// paves the points that were part of the first region but not of the second.
695// This can also be seen as the set difference of the points of the regions.
696std::vector<Rectangle> PavedRegionDifference(
697 std::vector<Rectangle> original_region,
698 absl::Span<const Rectangle> area_to_remove);
699
700// The two regions must be defined by non-overlapping rectangles.
701inline bool RegionIncludesOther(absl::Span<const Rectangle> region,
702 absl::Span<const Rectangle> other) {
703 return PavedRegionDifference({other.begin(), other.end()}, region).empty();
704}
705
706// For a given a set of N rectangles in `rectangles`, there might be up to
707// N*(N-1)/2 pairs of rectangles that intersect one another. If each of these
708// pairs describe an arc and each rectangle describe a node, the rectangles and
709// their intersections describe a graph. This function returns the full spanning
710// forest for this graph (ie., a spanning tree for each connected component).
711// This function allows to know if a set of rectangles has any intersection,
712// find an example intersection for each rectangle that has one, or split the
713// rectangles into connected components according to their intersections.
714//
715// The returned tuples are the arcs of the spanning forest represented by their
716// indices in the input vector.
717//
718// This function works with degenerate rectangles (ie., points or lines) and
719// have the same semantics for overlap as Rectangle::IsDisjoint().
720//
721// Note: This function runs in O(N (log N)^2) time on the input size, which
722// would be impossible to do if we were to return all the intersections, which
723// can be quadratic in number.
724std::vector<std::pair<int, int>> FindPartialRectangleIntersections(
725 absl::Span<const Rectangle> rectangles);
726
727// This function is faster that the FindPartialRectangleIntersections() if one
728// only want to know if there is at least one intersection. It is in O(N log N).
729//
730// IMPORTANT: this assumes rectangles are already sorted by their x_min and does
731// not support degenerate rectangles with zero area.
732//
733// If a pair {i, j} is returned, we will have i < j, and no intersection in
734// the subset of rectanges in [0, j).
735std::optional<std::pair<int, int>> FindOneIntersectionIfPresent(
736 absl::Span<const Rectangle> rectangles);
737
738// Same as FindOneIntersectionIfPresent() but supports degenerate rectangles
739// with zero area.
740std::optional<std::pair<int, int>> FindOneIntersectionIfPresentWithZeroArea(
741 absl::Span<const Rectangle> rectangles);
742
743} // namespace sat
744} // namespace operations_research
745
746#endif // OR_TOOLS_SAT_DIFFN_UTIL_H_
void AddMandatoryConsumption(IntegerValue x_min, IntegerValue x_max, IntegerValue y_height)
void AddRectangle(IntegerValue x_min, IntegerValue x_max, IntegerValue y_min, IntegerValue y_max)
Adds a rectangle to the current shape.
void BuildResidualCapacityProfile(std::vector< Rectangle > *result)
IntegerValue GetShrinkDeltaEnergy(Edge edge) const
How much of GetMinimumEnergy() will change if Shrink() is called.
Definition diffn_util.h:599
void Reset()
Reset to the bounding box of the whole set.
IntegerValue GetShrinkDeltaArea(Edge edge) const
How much of GetCurrentRectangleArea() will change if Shrink() is called.
const std::vector< RectangleInRange > & Intervals() const
Definition diffn_util.h:614
ProbingRectangle(const std::vector< RectangleInRange > &intervals)
It will initialize with the bounding box of the whole set.
bool RegionIncludesOther(absl::Span< const Rectangle > region, absl::Span< const Rectangle > other)
The two regions must be defined by non-overlapping rectangles.
Definition diffn_util.h:701
CompactVectorVector< int > GetOverlappingRectangleComponents(absl::Span< const Rectangle > rectangles)
absl::Span< int > FilterBoxesAndRandomize(absl::Span< const Rectangle > cached_rectangles, absl::Span< int > boxes, IntegerValue threshold_x, IntegerValue threshold_y, absl::BitGenRef random)
bool AnalyzeIntervals(bool transpose, absl::Span< const int > local_boxes, absl::Span< const Rectangle > rectangles, absl::Span< const IntegerValue > rectangle_energies, IntegerValue *x_threshold, IntegerValue *y_threshold, Rectangle *conflict)
std::optional< std::pair< int, int > > FindOneIntersectionIfPresent(absl::Span< const Rectangle > rectangles)
double CenterToCenterLInfinityDistance(const Rectangle &a, const Rectangle &b)
Definition diffn_util.h:145
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue.value())
std::vector< Rectangle > FindEmptySpaces(const Rectangle &bounding_box, std::vector< Rectangle > ocupied_rectangles)
absl::Span< int > FilterBoxesThatAreTooLarge(absl::Span< const Rectangle > cached_rectangles, absl::Span< const IntegerValue > energies, absl::Span< int > boxes)
std::vector< int > GetIntervalArticulationPoints(std::vector< IndexedInterval > *intervals)
double CenterToCenterL2Distance(const Rectangle &a, const Rectangle &b)
Returns the L2 distance between the centers of the two rectangles.
Definition diffn_util.h:135
void AppendPairwiseRestrictions(absl::Span< const ItemWithVariableSize > items, std::vector< PairwiseRestriction > *result)
void ConstructOverlappingSets(absl::Span< IndexedInterval > intervals, CompactVectorVector< int > *result, absl::Span< const int > order)
bool ReportEnergyConflict(Rectangle bounding_box, absl::Span< const int > boxes, SchedulingConstraintHelper *x, SchedulingConstraintHelper *y)
FindRectanglesResult FindRectanglesWithEnergyConflictMC(const std::vector< RectangleInRange > &intervals, absl::BitGenRef random, double temperature, double candidate_energy_usage_factor)
std::vector< Rectangle > PavedRegionDifference(std::vector< Rectangle > original_region, absl::Span< const Rectangle > area_to_remove)
bool BoxesAreInEnergyConflict(absl::Span< const Rectangle > rectangles, absl::Span< const IntegerValue > energies, absl::Span< const int > boxes, Rectangle *conflict)
std::optional< std::pair< int, int > > FindOneIntersectionIfPresentWithZeroArea(absl::Span< const Rectangle > rectangles)
std::vector< std::pair< int, int > > FindPartialRectangleIntersections(absl::Span< const Rectangle > rectangles)
IntegerValue Smallest1DIntersection(IntegerValue range_min, IntegerValue range_max, IntegerValue size, IntegerValue interval_min, IntegerValue interval_max)
void GetOverlappingIntervalComponents(std::vector< IndexedInterval > *intervals, std::vector< std::vector< int > > *components)
IntegerValue CapSubI(IntegerValue a, IntegerValue b)
IntegerValue CapProdI(IntegerValue a, IntegerValue b)
Overflows and saturated arithmetic.
std::string RenderDot(std::optional< Rectangle > bb, absl::Span< const Rectangle > solution, std::string_view extra_dot_payload)
In SWIG mode, we don't want anything besides these top-level includes.
Select next search node to expand Select next item_i to add this new search node to the search Generate a new search node where item_i is not in the knapsack Check validity of this new partial solution(using propagators) - If valid
bool operator==(const Rectangle &other) const
Definition diffn_util.h:342
bool operator<(const Rectangle &other) const
Definition diffn_util.h:341
Rectangle(IntegerValue start, IntegerValue height)
Definition diffn_util.h:338
bool operator()(const IndexedInterval &a, const IndexedInterval &b) const
Definition diffn_util.h:220
bool operator()(const IndexedInterval &a, const IndexedInterval &b) const
Definition diffn_util.h:226
bool operator==(const IndexedInterval &rhs) const
Definition diffn_util.h:212
friend void AbslStringify(Sink &sink, const IndexedInterval &interval)
Definition diffn_util.h:232
friend void AbslStringify(Sink &sink, const ItemWithVariableSize &item)
Definition diffn_util.h:286
bool operator==(const PairwiseRestriction &rhs) const
Definition diffn_util.h:311
Rectangle GetMinimumIntersection(const Rectangle &containing_area) const
Returns an empty rectangle if it is possible for no intersection to happen.
Definition diffn_util.h:479
IntegerValue GetMinimumIntersectionArea(const Rectangle &containing_area) const
Definition diffn_util.h:497
friend void AbslStringify(Sink &sink, const RectangleInRange &r)
Definition diffn_util.h:548
static RectangleInRange BiggestWithMinIntersection(const Rectangle &containing_area, const RectangleInRange &original, const IntegerValue &min_intersect_x, const IntegerValue &min_intersect_y)
Definition diffn_util.h:519
bool operator==(const RectangleInRange &other) const
Definition diffn_util.h:443
Rectangle GetAtCorner(Corner p) const
Definition diffn_util.h:451
bool operator==(const Rectangle &other) const
Definition diffn_util.h:90
void GrowToInclude(const Rectangle &other)
Definition diffn_util.h:50
bool operator!=(const Rectangle &other) const
Definition diffn_util.h:95
absl::InlinedVector< Rectangle, 4 > RegionDifference(const Rectangle &other) const
Definition diffn_util.cc:64
bool IsInsideOf(const Rectangle &other) const
Definition diffn_util.h:74
bool IsDisjoint(const Rectangle &other) const
Definition diffn_util.cc:59
Rectangle Intersect(const Rectangle &other) const
The methods below are not meant to be used with zero-area rectangles.
Definition diffn_util.h:105
IntegerValue IntersectArea(const Rectangle &other) const
Definition diffn_util.h:121
friend void AbslStringify(Sink &sink, const Rectangle &r)
Definition diffn_util.h:85