OR-Tools  8.2
timetable.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_TIMETABLE_H_
15#define OR_TOOLS_SAT_TIMETABLE_H_
16
17#include <vector>
18
19#include "ortools/base/macros.h"
20#include "ortools/sat/integer.h"
22#include "ortools/util/rev.h"
23
24namespace operations_research {
25namespace sat {
26
27// Adds a reservoir constraint to the model. Note that to account for level not
28// containing zero at time zero, we might needs to create an artificial fixed
29// event.
30//
31// This instantiate one or more ReservoirTimeTabling class to perform the
32// propagation.
33void AddReservoirConstraint(std::vector<AffineExpression> times,
34 std::vector<IntegerValue> deltas,
35 std::vector<Literal> presences, int64 min_level,
36 int64 max_level, Model* model);
37
38// The piecewise constant function must be below the given capacity. The initial
39// function value is zero. Note that a negative capacity will thus be trivially
40// infeasible.
41//
42// Note that we take for the definition of the function at time t to be the sum
43// of all delta with time <= t. But because we check for the capacity over the
44// full horizon, we could have taken < t with no behavior change.
46 public:
47 ReservoirTimeTabling(const std::vector<AffineExpression>& times,
48 const std::vector<IntegerValue>& deltas,
49 const std::vector<Literal>& presences,
50 IntegerValue capacity, Model* model);
51
52 bool Propagate() final;
53
54 private:
55 // The rectangle will be ordered by start, and the end of each rectangle
56 // will be equal to the start of the next one. The height correspond to the
57 // one from start (inclusive) until the next one (exclusive).
58 struct ProfileRectangle {
59 ProfileRectangle() {}
60 ProfileRectangle(IntegerValue start, IntegerValue height)
61 : start(start), height(height) {}
62
63 bool operator<(const ProfileRectangle& other) const {
64 return start < other.start;
65 }
66
67 /* const */ IntegerValue start = IntegerValue(0);
68 /* const */ IntegerValue height = IntegerValue(0);
69 };
70
71 // Builds the profile and increases the lower bound of the capacity
72 // variable accordingly.
73 bool BuildProfile();
74
75 // Explanation of the profile minimum value at time t, eventually ignoring the
76 // given event.
77 void FillReasonForProfileAtGivenTime(IntegerValue t,
78 int event_to_ignore = -1);
79
80 // Tries to tighten the min/max time of the given event depending on the sign
81 // of the delta associated with this event.
82 bool TryToIncreaseMin(int event);
83 bool TryToDecreaseMax(int event);
84
85 // Input.
86 std::vector<AffineExpression> times_;
87 std::vector<IntegerValue> deltas_;
88 std::vector<Literal> presences_;
89 IntegerValue capacity_;
90
91 // Model class.
92 const VariablesAssignment& assignment_;
93 IntegerTrail* integer_trail_;
94
95 // Temporary data.
96 std::vector<Literal> literal_reason_;
97 std::vector<IntegerLiteral> integer_reason_;
98 std::vector<ProfileRectangle> profile_;
99};
100
101// A strongly quadratic version of Time Tabling filtering. This propagator
102// is similar to the CumulativeTimeTable propagator of the constraint solver.
104 public:
105 TimeTablingPerTask(const std::vector<AffineExpression>& demands,
106 AffineExpression capacity, IntegerTrail* integer_trail,
108
109 bool Propagate() final;
110
111 void RegisterWith(GenericLiteralWatcher* watcher);
112
113 private:
114 // The rectangle will be ordered by start, and the end of each rectangle
115 // will be equal to the start of the next one. The height correspond to the
116 // one from start (inclusive) until the next one (exclusive).
117 struct ProfileRectangle {
118 /* const */ IntegerValue start;
119 /* const */ IntegerValue height;
120
121 ProfileRectangle(IntegerValue start, IntegerValue height)
122 : start(start), height(height) {}
123
124 bool operator<(const ProfileRectangle& other) const {
125 return start < other.start;
126 }
127 };
128
129 // Builds the profile and increases the lower bound of the capacity
130 // variable accordingly.
131 bool BuildProfile();
132
133 // Reverses the profile. This is needed to reuse a given profile to update
134 // both the start and end times.
135 void ReverseProfile();
136
137 // Tries to increase the minimum start time of each task according to the
138 // current profile. This function can be called after ReverseProfile() and
139 // ReverseVariables to update the maximum end time of each task.
140 bool SweepAllTasks(bool is_forward);
141
142 // Tries to increase the minimum start time of task_id.
143 bool SweepTask(int task_id);
144
145 // Updates the starting time of task_id to right and explain it. The reason is
146 // all the mandatory parts contained in [left, right).
147 bool UpdateStartingTime(int task_id, IntegerValue left, IntegerValue right);
148
149 // Increases the minimum capacity to new_min and explain it. The reason is all
150 // the mandatory parts that overlap time.
151 bool IncreaseCapacity(IntegerValue time, IntegerValue new_min);
152
153 // Explains the state of the profile in the time interval [left, right). The
154 // reason is all the mandatory parts that overlap the interval. The current
155 // reason is not cleared when this method is called.
156 void AddProfileReason(IntegerValue left, IntegerValue right);
157
158 IntegerValue CapacityMin() const {
159 return integer_trail_->LowerBound(capacity_);
160 }
161
162 IntegerValue CapacityMax() const {
163 return integer_trail_->UpperBound(capacity_);
164 }
165
166 IntegerValue DemandMin(int task_id) const {
167 return integer_trail_->LowerBound(demands_[task_id]);
168 }
169
170 IntegerValue DemandMax(int task_id) const {
171 return integer_trail_->UpperBound(demands_[task_id]);
172 }
173
174 // Returns true if the tasks is present and has a mantatory part.
175 bool IsInProfile(int t) const {
176 return positions_in_profile_tasks_[t] < num_profile_tasks_;
177 }
178
179 // Number of tasks.
180 const int num_tasks_;
181
182 // The demand variables of the tasks.
183 std::vector<AffineExpression> demands_;
184
185 // Capacity of the resource.
186 const AffineExpression capacity_;
187
188 IntegerTrail* integer_trail_;
190
191 // Optimistic profile of the resource consumption over time.
192 std::vector<ProfileRectangle> profile_;
193 IntegerValue profile_max_height_;
194
195 // Reversible starting height of the reduced profile. This corresponds to the
196 // height of the leftmost profile rectangle that can be used for propagation.
197 IntegerValue starting_profile_height_;
198
199 // Reversible sets of tasks to consider for the forward (resp. backward)
200 // propagation. A task with a fixed start do not need to be considered for the
201 // forward pass, same for task with fixed end for the backward pass. It is why
202 // we use two sets.
203 std::vector<int> forward_tasks_to_sweep_;
204 std::vector<int> backward_tasks_to_sweep_;
205 int forward_num_tasks_to_sweep_;
206 int backward_num_tasks_to_sweep_;
207
208 // Reversible set (with random access) of tasks to consider for building the
209 // profile. The set contains the tasks in the [0, num_profile_tasks_) prefix
210 // of profile_tasks_. The positions of a task in profile_tasks_ is contained
211 // in positions_in_profile_tasks_.
212 std::vector<int> profile_tasks_;
213 std::vector<int> positions_in_profile_tasks_;
214 int num_profile_tasks_;
215
216 DISALLOW_COPY_AND_ASSIGN(TimeTablingPerTask);
217};
218
219} // namespace sat
220} // namespace operations_research
221
222#endif // OR_TOOLS_SAT_TIMETABLE_H_
IntegerValue UpperBound(IntegerVariable i) const
Definition: integer.h:1304
IntegerValue LowerBound(IntegerVariable i) const
Definition: integer.h:1300
Class that owns everything related to a particular optimization model.
Definition: sat/model.h:38
ReservoirTimeTabling(const std::vector< AffineExpression > &times, const std::vector< IntegerValue > &deltas, const std::vector< Literal > &presences, IntegerValue capacity, Model *model)
Definition: timetable.cc:52
void RegisterWith(GenericLiteralWatcher *watcher)
Definition: timetable.cc:313
TimeTablingPerTask(const std::vector< AffineExpression > &demands, AffineExpression capacity, IntegerTrail *integer_trail, SchedulingConstraintHelper *helper)
Definition: timetable.cc:279
GRBmodel * model
int64_t int64
void AddReservoirConstraint(std::vector< AffineExpression > times, std::vector< IntegerValue > deltas, std::vector< Literal > presences, int64 min_level, int64 max_level, Model *model)
Definition: timetable.cc:27
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 time
Definition: resource.cc:1683
int64 capacity