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"
21 #include "ortools/sat/intervals.h"
22 #include "ortools/util/rev.h"
23 
24 namespace operations_research {
25 namespace 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.
33 void 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