Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
disjunctive.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_DISJUNCTIVE_H_
15#define OR_TOOLS_SAT_DISJUNCTIVE_H_
16
17#include <algorithm>
18#include <cstdint>
19#include <memory>
20#include <string>
21#include <utility>
22#include <vector>
23
24#include "absl/log/log.h"
25#include "absl/log/vlog_is_on.h"
26#include "absl/strings/str_cat.h"
27#include "absl/types/span.h"
28#include "ortools/sat/integer.h"
31#include "ortools/sat/model.h"
34#include "ortools/sat/util.h"
37
38namespace operations_research {
39namespace sat {
40
41// Enforces a disjunctive (or no overlap) constraint on the given interval
42// variables. The intervals are interpreted as [start, end) and the constraint
43// enforces that no time point belongs to two intervals.
44//
45// TODO(user): This is not completely true for empty intervals (start == end).
46// Make sure such intervals are ignored by the constraint.
47void AddDisjunctive(const std::vector<IntervalVariable>& intervals,
48 Model* model);
49
50// Creates Boolean variables for all the possible precedences of the form (task
51// i is before task j) and forces that, for each couple of task (i,j), either i
52// is before j or j is before i. Do not create any other propagators.
54 absl::Span<const IntervalVariable> intervals, Model* model);
55
56// Helper class to compute the end-min of a set of tasks given their start-min
57// and size-min. In Petr Vilim's PhD "Global Constraints in Scheduling",
58// this corresponds to his Theta-tree except that we use a O(n) implementation
59// for most of the function here, not a O(log(n)) one.
60class TaskSet {
61 public:
62 explicit TaskSet(int num_tasks) { sorted_tasks_.ClearAndReserve(num_tasks); }
63
64 struct Entry {
65 int task;
66 IntegerValue start_min;
67 IntegerValue size_min;
68
69 // Note that the tie-breaking is not important here.
70 bool operator<(Entry other) const { return start_min < other.start_min; }
71 };
72
73 // Insertion and modification. These leave sorted_tasks_ sorted.
74 void Clear() {
75 sorted_tasks_.clear();
76 optimized_restart_ = 0;
77 }
78 void AddEntry(const Entry& e);
79
80 // Same as AddEntry({t, helper->ShiftedStartMin(t), helper->SizeMin(t)}).
81 // This is a minor optimization to not call SizeMin(t) twice.
82 void AddShiftedStartMinEntry(const SchedulingConstraintHelper& helper, int t);
83
84 // Advanced usage, if the entry is present, this assumes that its start_min is
85 // >= the end min without it, and update the datastructure accordingly.
86 void NotifyEntryIsNowLastIfPresent(const Entry& e);
87
88 // Advanced usage. Instead of calling many AddEntry(), it is more efficient to
89 // call AddUnsortedEntry() instead, but then Sort() MUST be called just after
90 // the insertions. Nothing is checked here, so it is up to the client to do
91 // that properly.
92 void AddUnsortedEntry(const Entry& e) { sorted_tasks_.push_back(e); }
93 void Sort() { std::sort(sorted_tasks_.begin(), sorted_tasks_.end()); }
94
95 // Returns the end-min for the task in the set. The time profile of the tasks
96 // packed to the left will always be a set of contiguous tasks separated by
97 // empty space:
98 //
99 // [Bunch of tasks] ... [Bunch of tasks] ... [critical tasks].
100 //
101 // We call "critical tasks" the last group. These tasks will be solely
102 // responsible for the end-min of the whole set. The returned
103 // critical_index will be the index of the first critical task in
104 // SortedTasks().
105 //
106 // A reason for the min end is:
107 // - The size-min of all the critical tasks.
108 // - The fact that all critical tasks have a start-min greater or equal to the
109 // first of them, that is SortedTasks()[critical_index].start_min.
110 //
111 // It is possible to behave like if one task was not in the set by setting
112 // task_to_ignore to the id of this task. This returns 0 if the set is empty
113 // in which case critical_index will be left unchanged.
114 IntegerValue ComputeEndMin(int task_to_ignore, int* critical_index) const;
115 IntegerValue ComputeEndMin() const;
116
117 // Warning, this is only valid if ComputeEndMin() was just called. It is the
118 // same index as if one called ComputeEndMin(-1, &critical_index), but saves
119 // another unneeded loop.
120 int GetCriticalIndex() const { return optimized_restart_; }
121
122 absl::Span<const Entry> SortedTasks() const { return sorted_tasks_; }
123
124 private:
125 FixedCapacityVector<Entry> sorted_tasks_;
126 mutable int optimized_restart_ = 0;
127};
128
129// Simple class to display statistics at the end if --v=1.
131 explicit PropagationStatistics(std::string _name, Model* model = nullptr)
132 : name(_name),
133 shared_stats(model == nullptr
134 ? nullptr
135 : model->GetOrCreate<SharedStatistics>()) {};
136
138 if (shared_stats == nullptr) return;
139 if (!VLOG_IS_ON(1)) return;
140 std::vector<std::pair<std::string, int64_t>> stats;
141 stats.push_back({absl::StrCat(name, "/num_calls"), num_calls});
142 stats.push_back({absl::StrCat(name, "/num_calls_with_propagation"),
144 stats.push_back(
145 {absl::StrCat(name, "/num_calls_with_conflicts"), num_conflicts});
146 stats.push_back(
147 {absl::StrCat(name, "/num_propagations"), num_propagations});
148 shared_stats->AddStats(stats);
149 }
150
155
161
162 const std::string name;
165
166 int64_t num_calls = 0;
167 int64_t num_calls_with_propagation = 0; // Only count if we did something.
168 int64_t num_conflicts = 0;
169 int64_t num_propagations = 0;
170};
171
172// ============================================================================
173// Below are many of the known propagation techniques for the disjunctive, each
174// implemented in only one time direction and in its own propagator class. The
175// Disjunctive() model function above will instantiate the used ones (according
176// to the solver parameters) in both time directions.
177//
178// See Petr Vilim PhD "Global Constraints in Scheduling" for a description of
179// some of the algorithm.
180// ============================================================================
181
183 public:
185 Model* model = nullptr)
186 : helper_(helper),
187 window_(new TaskTime[helper->NumTasks()]),
188 task_to_event_(new int[helper->NumTasks()]),
189 stats_("DisjunctiveOverloadChecker", model) {
190 task_by_increasing_end_max_.ClearAndReserve(helper->NumTasks());
191 }
192
193 bool Propagate() final;
195
196 private:
197 bool PropagateSubwindow(int relevant_size, IntegerValue global_window_end);
198
200
201 // Size assigned at construction, stay fixed afterwards.
202 std::unique_ptr<TaskTime[]> window_;
203 std::unique_ptr<int[]> task_to_event_;
204
205 FixedCapacityVector<TaskTime> task_by_increasing_end_max_;
206
207 ThetaLambdaTree<IntegerValue> theta_tree_;
209};
210
211// This one is a simpler version of DisjunctiveDetectablePrecedences, it
212// detect all implied precedences between TWO tasks and push bounds accordingly.
213// If we created all pairwise precedence Booleans, this would already be
214// propagated and in this case we don't create this propagator.
215//
216// Otherwise, this generate short reason and is good to do early as it
217// propagates a lot.
219 public:
221 Model* model = nullptr)
222 : helper_(helper), stats_("DisjunctiveSimplePrecedences", model) {}
223 bool Propagate() final;
225
226 private:
227 bool PropagateOneDirection();
228 bool Push(TaskTime before, int t);
229
232};
233
235 public:
238 Model* model = nullptr)
239 : time_direction_(time_direction),
240 helper_(helper),
241 task_set_(helper->NumTasks()),
242 stats_("DisjunctiveDetectablePrecedences", model) {
243 ranks_.resize(helper->NumTasks());
244 to_add_.ClearAndReserve(helper->NumTasks());
245 }
246 bool Propagate() final;
248
249 private:
250 bool PropagateWithRanks();
251 bool Push(IntegerValue task_set_end_min, int t);
252
253 FixedCapacityVector<int> to_add_;
254 std::vector<int> ranks_;
255
256 const bool time_direction_;
258 TaskSet task_set_;
260};
261
262// This propagates the same things as DisjunctiveDetectablePrecedences, except
263// that it only sort the full set of intervals once and then work on a combined
264// set of disjunctives.
265template <bool time_direction>
267 public:
268 explicit CombinedDisjunctive(Model* model);
269
270 // After creation, this must be called for all the disjunctive constraints
271 // in the model.
272 void AddNoOverlap(absl::Span<const IntervalVariable> var);
273
274 bool Propagate() final;
275
276 private:
278 std::vector<std::vector<int>> task_to_disjunctives_;
279 std::vector<bool> task_is_added_;
280 std::vector<TaskSet> task_sets_;
281 std::vector<IntegerValue> end_mins_;
282};
283
285 public:
286 DisjunctiveNotLast(bool time_direction, SchedulingConstraintHelper* helper,
287 Model* model = nullptr)
288 : time_direction_(time_direction),
289 helper_(helper),
290 task_set_(helper->NumTasks()),
291 stats_("DisjunctiveNotLast", model) {
292 start_min_window_.ClearAndReserve(helper->NumTasks());
293 start_max_window_.ClearAndReserve(helper->NumTasks());
294 }
295 bool Propagate() final;
297
298 private:
299 bool PropagateSubwindow();
300
301 FixedCapacityVector<TaskTime> start_min_window_;
302 FixedCapacityVector<TaskTime> start_max_window_;
303
304 const bool time_direction_;
306 TaskSet task_set_;
308};
309
311 public:
312 DisjunctiveEdgeFinding(bool time_direction,
314 Model* model = nullptr)
315 : time_direction_(time_direction),
316 helper_(helper),
317 stats_("DisjunctiveEdgeFinding", model) {
318 task_by_increasing_end_max_.ClearAndReserve(helper->NumTasks());
319 window_.ClearAndReserve(helper->NumTasks());
320 event_size_.ClearAndReserve(helper->NumTasks());
321 }
322 bool Propagate() final;
324
325 private:
326 bool PropagateSubwindow(IntegerValue window_end_min);
327
328 const bool time_direction_;
330
331 // This only contains non-gray tasks.
332 FixedCapacityVector<TaskTime> task_by_increasing_end_max_;
333
334 // All these member are indexed in the same way.
336 ThetaLambdaTree<IntegerValue> theta_tree_;
337 FixedCapacityVector<IntegerValue> event_size_;
338
339 // Task indexed.
340 std::vector<int> non_gray_task_to_event_;
341 std::vector<bool> is_gray_;
342
344};
345
346// Exploits the precedences relations of the form "this set of disjoint
347// IntervalVariables must be performed before a given IntegerVariable". The
348// relations are computed with PrecedencesPropagator::ComputePrecedences().
350 public:
351 DisjunctivePrecedences(bool time_direction,
352 SchedulingConstraintHelper* helper, Model* model)
353 : time_direction_(time_direction),
354 helper_(helper),
355 integer_trail_(model->GetOrCreate<IntegerTrail>()),
356 precedence_relations_(model->GetOrCreate<PrecedenceRelations>()),
357 stats_("DisjunctivePrecedences", model) {
358 window_.ClearAndReserve(helper->NumTasks());
359 index_to_end_vars_.ClearAndReserve(helper->NumTasks());
360 indices_before_.ClearAndReserve(helper->NumTasks());
361 }
362
363 bool Propagate() final;
365
366 private:
367 bool PropagateSubwindow();
368
369 const bool time_direction_;
371 IntegerTrail* integer_trail_;
372 PrecedenceRelations* precedence_relations_;
373
375 FixedCapacityVector<IntegerVariable> index_to_end_vars_;
376
377 FixedCapacityVector<int> indices_before_;
378 std::vector<bool> skip_;
379 std::vector<PrecedenceRelations::PrecedenceData> before_;
380
382};
383
384// This is an optimization for the case when we have a big number of such
385// pairwise constraints. This should be roughtly equivalent to what the general
386// disjunctive case is doing, but it dealt with variable size better and has a
387// lot less overhead.
389 public:
391 : helper_(helper) {}
392 bool Propagate() final;
394
395 private:
397};
398
399} // namespace sat
400} // namespace operations_research
401
402#endif // OR_TOOLS_SAT_DISJUNCTIVE_H_
void AddNoOverlap(absl::Span< const IntervalVariable > var)
DisjunctiveDetectablePrecedences(bool time_direction, SchedulingConstraintHelper *helper, Model *model=nullptr)
DisjunctiveEdgeFinding(bool time_direction, SchedulingConstraintHelper *helper, Model *model=nullptr)
DisjunctiveNotLast(bool time_direction, SchedulingConstraintHelper *helper, Model *model=nullptr)
int RegisterWith(GenericLiteralWatcher *watcher)
DisjunctiveOverloadChecker(SchedulingConstraintHelper *helper, Model *model=nullptr)
DisjunctivePrecedences(bool time_direction, SchedulingConstraintHelper *helper, Model *model)
DisjunctiveSimplePrecedences(SchedulingConstraintHelper *helper, Model *model=nullptr)
DisjunctiveWithTwoItems(SchedulingConstraintHelper *helper)
int RegisterWith(GenericLiteralWatcher *watcher)
Base class for CP like propagators.
Definition integer.h:1056
int NumTasks() const
Returns the number of task.
Simple class to add statistics by name and print them at the end.
void NotifyEntryIsNowLastIfPresent(const Entry &e)
void AddUnsortedEntry(const Entry &e)
Definition disjunctive.h:92
IntegerValue ComputeEndMin() const
absl::Span< const Entry > SortedTasks() const
void AddShiftedStartMinEntry(const SchedulingConstraintHelper &helper, int t)
void Clear()
Insertion and modification. These leave sorted_tasks_ sorted.
Definition disjunctive.h:74
void AddDisjunctive(const std::vector< IntervalVariable > &intervals, Model *model)
void AddDisjunctiveWithBooleanPrecedencesOnly(absl::Span< const IntervalVariable > intervals, Model *model)
In SWIG mode, we don't want anything besides these top-level includes.
STL namespace.
Simple class to display statistics at the end if –v=1.
PropagationStatistics(std::string _name, Model *model=nullptr)