Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
scheduling_cuts.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_SCHEDULING_CUTS_H_
15#define OR_TOOLS_SAT_SCHEDULING_CUTS_H_
16
17#include <optional>
18#include <string>
19#include <utility>
20#include <vector>
21
22#include "absl/types/span.h"
23#include "ortools/sat/cuts.h"
24#include "ortools/sat/integer.h"
26#include "ortools/sat/model.h"
28#include "ortools/sat/util.h"
29
30namespace operations_research {
31namespace sat {
32
33// For a given set of intervals and demands, we compute the energy of
34// each task and make sure their sum fits in the span of the intervals * its
35// capacity.
36//
37// If an interval is optional, it contributes
38// min_demand * min_size * presence_literal
39// amount of total energy.
40//
41// If an interval is performed, we use the linear energy formulation (if
42// defined, that is if different from a constant -1), or the McCormick
43// relaxation of the product size * demand if not defined.
44//
45// The maximum energy is capacity * span of intervals at level 0.
48 const AffineExpression& capacity,
49 const std::optional<AffineExpression>& makespan, Model* model);
50
51// For a given set of intervals and demands, we first compute the mandatory part
52// of the interval as [start_max , end_min]. We use this to calculate mandatory
53// demands for each start_max time points for eligible intervals.
54// Since the sum of these mandatory demands must be smaller or equal to the
55// capacity, we create a cut representing that.
56//
57// If an interval is optional, it contributes min_demand * presence_literal
58// amount of demand to the mandatory demands sum. So the final cut is generated
59// as follows:
60// sum(demands of always present intervals)
61// + sum(presence_literal * min_of_demand) <= capacity.
64 const AffineExpression& capacity, Model* model);
65
66// Completion time cuts for the cumulative constraint. It is a simple relaxation
67// where we replace a cumulative task with demand k and duration d by a
68// no_overlap task with duration d * k / capacity_max.
71 const AffineExpression& capacity, Model* model);
72
73// For a given set of intervals in a cumulative constraint, we detect violated
74// mandatory precedences and create a cut for these.
77 const AffineExpression& capacity, Model* model);
78
79// For a given set of intervals, we first compute the min and max of all
80// intervals. Then we create a cut that indicates that all intervals must fit
81// in that span.
82//
83// If an interval is optional, it contributes min_size * presence_literal
84// amount of demand to the mandatory demands sum. So the final cut is generated
85// as follows:
86// sum(sizes of always present intervals)
87// + sum(presence_literal * min_of_size) <= span of all intervals.
90 const std::optional<AffineExpression>& makespan, Model* model);
91
92// For a given set of intervals in a no_overlap constraint, we detect violated
93// mandatory precedences and create a cut for these.
95 SchedulingConstraintHelper* helper, Model* model);
96
97// For a given set of intervals in a no_overlap constraint, we detect violated
98// area based cuts from Queyranne 93 [see note in the code] and create a cut for
99// these.
101 SchedulingConstraintHelper* helper, Model* model);
102
103// Internal methods and data structures, useful for testing.
104
105// Stores the event for a task (interval, demand).
106// For a no_overlap constraint, demand is always between 0 and 1.
107// For a cumulative constraint, demand must be between 0 and capacity_max.
110 SchedulingDemandHelper* demands_helper);
111
112 // The index of the task in the helper.
114
115 // Cache of the bounds of the interval.
116 IntegerValue start_min;
117 IntegerValue start_max;
118 IntegerValue end_min;
119 IntegerValue end_max;
120 IntegerValue size_min;
121
122 // Start and end affine expressions and lp value of the end of the interval.
125 double lp_end = 0.0;
126
127 // Cache of the bounds of the demand.
128 IntegerValue demand_min;
129
130 // If we know that the size on y is fixed, we can use some heuristic to
131 // compute the maximum subset sums under the capacity and use that instead
132 // of the full capacity.
133 bool demand_is_fixed = false;
134
135 // The energy min of this event.
136 IntegerValue energy_min;
137
138 // If non empty, a decomposed view of the energy of this event.
139 // First value in each pair is x_size, second is y_size.
140 std::vector<LiteralValueValue> decomposed_energy;
141
142 // Indicates if the events used the optional energy information from the
143 // model.
145
146 // Indicates if the cut is lifted, that is if it includes tasks that are not
147 // strictly contained in the current time window.
148 bool lifted = false;
149
150 std::string DebugString() const;
151};
152
154 public:
156
157 int max_task_index() const { return max_task_index_; }
158 const CompactVectorVector<int>& predecessors() const { return predecessors_; }
159
160 // Temporary data.
161 std::vector<std::pair<IntegerValue, IntegerValue>> profile_;
162 std::vector<std::pair<IntegerValue, IntegerValue>> new_profile_;
163 std::vector<IntegerValue> assigned_ends_;
164 std::vector<int> task_to_index_;
166 std::vector<CompletionTimeEvent> residual_events_;
167
168 // Collect precedences, set max_task_index.
169 // TODO(user): Do some transitive closure.
170 void Init(absl::Span<const CompletionTimeEvent> events, Model* model);
171
173 absl::Span<const CompletionTimeEvent> events,
174 absl::Span<const int> permutation);
175
176 private:
177 CompactVectorVector<int> predecessors_;
178 int max_task_index_ = 0;
179 std::vector<bool> visited_;
180};
181
187
188template <typename Sink>
189void AbslStringify(Sink& sink, const CompletionTimeExplorationStatus& status) {
190 switch (status) {
192 sink.Append("FINISHED");
193 break;
195 sink.Append("ABORTED");
196 break;
198 sink.Append("NO_VALID_PERMUTATION");
199 break;
200 }
201}
202
203// Computes the minimum sum of the end min and the minimum sum of the end min
204// weighted by weight of all events. It returns false if no permutation is
205// valid w.r.t. the range of starts.
206//
207// Note that this is an exhaustive algorithm, so the number of events should be
208// small, like <= 10. They should also starts in index order.
209//
210// Optim: If both sums are proven <= to the corresponding threshold, we abort.
212 absl::Span<const CompletionTimeEvent> events, IntegerValue capacity_max,
213 double unweighted_threshold, double weighted_threshold,
214 CtExhaustiveHelper& helper, double& min_sum_of_ends,
215 double& min_sum_of_weighted_ends, bool& cut_use_precedences,
216 int& exploration_credit);
217
218} // namespace sat
219} // namespace operations_research
220
221#endif // OR_TOOLS_SAT_SCHEDULING_CUTS_H_
const CompactVectorVector< int > & predecessors() const
void Init(absl::Span< const CompletionTimeEvent > events, Model *model)
std::vector< std::pair< IntegerValue, IntegerValue > > profile_
Temporary data.
bool PermutationIsCompatibleWithPrecedences(absl::Span< const CompletionTimeEvent > events, absl::Span< const int > permutation)
std::vector< CompletionTimeEvent > residual_events_
DagTopologicalSortIterator valid_permutation_iterator_
std::vector< std::pair< IntegerValue, IntegerValue > > new_profile_
CutGenerator CreateCumulativeCompletionTimeCutGenerator(SchedulingConstraintHelper *helper, SchedulingDemandHelper *demands_helper, const AffineExpression &capacity, Model *model)
CompletionTimeExplorationStatus ComputeMinSumOfWeightedEndMins(absl::Span< const CompletionTimeEvent > events, IntegerValue capacity_max, double unweighted_threshold, double weighted_threshold, CtExhaustiveHelper &helper, double &min_sum_of_ends, double &min_sum_of_weighted_ends, bool &cut_use_precedences, int &exploration_credit)
CutGenerator CreateCumulativePrecedenceCutGenerator(SchedulingConstraintHelper *helper, SchedulingDemandHelper *demands_helper, const AffineExpression &capacity, Model *model)
CutGenerator CreateCumulativeEnergyCutGenerator(SchedulingConstraintHelper *helper, SchedulingDemandHelper *demands_helper, const AffineExpression &capacity, const std::optional< AffineExpression > &makespan, Model *model)
CutGenerator CreateCumulativeTimeTableCutGenerator(SchedulingConstraintHelper *helper, SchedulingDemandHelper *demands_helper, const AffineExpression &capacity, Model *model)
CutGenerator CreateNoOverlapCompletionTimeCutGenerator(SchedulingConstraintHelper *helper, Model *model)
CutGenerator CreateNoOverlapEnergyCutGenerator(SchedulingConstraintHelper *helper, const std::optional< AffineExpression > &makespan, Model *model)
CutGenerator CreateNoOverlapPrecedenceCutGenerator(SchedulingConstraintHelper *helper, Model *model)
void AbslStringify(Sink &sink, EdgePosition e)
In SWIG mode, we don't want anything besides these top-level includes.
std::vector< LiteralValueValue > decomposed_energy
AffineExpression start
Start and end affine expressions and lp value of the end of the interval.
IntegerValue energy_min
The energy min of this event.
CompletionTimeEvent(int t, SchedulingConstraintHelper *x_helper, SchedulingDemandHelper *demands_helper)
IntegerValue start_min
Cache of the bounds of the interval.
int task_index
The index of the task in the helper.
IntegerValue demand_min
Cache of the bounds of the demand.