OR-Tools  8.1
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 // A strongly quadratic version of Time Tabling filtering. This propagator
28 // is similar to the CumulativeTimeTable propagator of the constraint solver.
30  public:
31  TimeTablingPerTask(const std::vector<AffineExpression>& demands,
32  AffineExpression capacity, IntegerTrail* integer_trail,
34 
35  bool Propagate() final;
36 
37  void RegisterWith(GenericLiteralWatcher* watcher);
38 
39  private:
40  // The rectangle will be ordered by start, and the end of each rectangle
41  // will be equal to the start of the next one.
42  struct ProfileRectangle {
43  /* const */ IntegerValue start;
44  /* const */ IntegerValue height;
45 
46  ProfileRectangle(IntegerValue start, IntegerValue height)
47  : start(start), height(height) {}
48 
49  bool operator<(const ProfileRectangle& other) const {
50  return start < other.start;
51  }
52  };
53 
54  // Builds the profile and increases the lower bound of the capacity
55  // variable accordingly.
56  bool BuildProfile();
57 
58  // Reverses the profile. This is needed to reuse a given profile to update
59  // both the start and end times.
60  void ReverseProfile();
61 
62  // Tries to increase the minimum start time of each task according to the
63  // current profile. This function can be called after ReverseProfile() and
64  // ReverseVariables to update the maximum end time of each task.
65  bool SweepAllTasks(bool is_forward);
66 
67  // Tries to increase the minimum start time of task_id.
68  bool SweepTask(int task_id);
69 
70  // Updates the starting time of task_id to right and explain it. The reason is
71  // all the mandatory parts contained in [left, right).
72  bool UpdateStartingTime(int task_id, IntegerValue left, IntegerValue right);
73 
74  // Increases the minimum capacity to new_min and explain it. The reason is all
75  // the mandatory parts that overlap time.
76  bool IncreaseCapacity(IntegerValue time, IntegerValue new_min);
77 
78  // Explains the state of the profile in the time interval [left, right). The
79  // reason is all the mandatory parts that overlap the interval. The current
80  // reason is not cleared when this method is called.
81  void AddProfileReason(IntegerValue left, IntegerValue right);
82 
83  IntegerValue CapacityMin() const {
84  return integer_trail_->LowerBound(capacity_);
85  }
86 
87  IntegerValue CapacityMax() const {
88  return integer_trail_->UpperBound(capacity_);
89  }
90 
91  IntegerValue DemandMin(int task_id) const {
92  return integer_trail_->LowerBound(demands_[task_id]);
93  }
94 
95  IntegerValue DemandMax(int task_id) const {
96  return integer_trail_->UpperBound(demands_[task_id]);
97  }
98 
99  // Returns true if the tasks is present and has a mantatory part.
100  bool IsInProfile(int t) const {
101  return positions_in_profile_tasks_[t] < num_profile_tasks_;
102  }
103 
104  // Number of tasks.
105  const int num_tasks_;
106 
107  // The demand variables of the tasks.
108  std::vector<AffineExpression> demands_;
109 
110  // Capacity of the resource.
111  const AffineExpression capacity_;
112 
113  IntegerTrail* integer_trail_;
115 
116  // Optimistic profile of the resource consumption over time.
117  std::vector<ProfileRectangle> profile_;
118  IntegerValue profile_max_height_;
119 
120  // Reversible starting height of the reduced profile. This corresponds to the
121  // height of the leftmost profile rectangle that can be used for propagation.
122  IntegerValue starting_profile_height_;
123 
124  // Reversible sets of tasks to consider for the forward (resp. backward)
125  // propagation. A task with a fixed start do not need to be considered for the
126  // forward pass, same for task with fixed end for the backward pass. It is why
127  // we use two sets.
128  std::vector<int> forward_tasks_to_sweep_;
129  std::vector<int> backward_tasks_to_sweep_;
130  int forward_num_tasks_to_sweep_;
131  int backward_num_tasks_to_sweep_;
132 
133  // Reversible set (with random access) of tasks to consider for building the
134  // profile. The set contains the tasks in the [0, num_profile_tasks_) prefix
135  // of profile_tasks_. The positions of a task in profile_tasks_ is contained
136  // in positions_in_profile_tasks_.
137  std::vector<int> profile_tasks_;
138  std::vector<int> positions_in_profile_tasks_;
139  int num_profile_tasks_;
140 
141  DISALLOW_COPY_AND_ASSIGN(TimeTablingPerTask);
142 };
143 
144 } // namespace sat
145 } // namespace operations_research
146 
147 #endif // OR_TOOLS_SAT_TIMETABLE_H_
operations_research::sat::TimeTablingPerTask::TimeTablingPerTask
TimeTablingPerTask(const std::vector< AffineExpression > &demands, AffineExpression capacity, IntegerTrail *integer_trail, SchedulingConstraintHelper *helper)
Definition: timetable.cc:27
operations_research::sat::AffineExpression
Definition: integer.h:205
operations_research::sat::IntegerTrail
Definition: integer.h:533
operations_research::sat::PropagatorInterface
Definition: integer.h:1043
macros.h
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
operations_research::sat::GenericLiteralWatcher
Definition: integer.h:1091
operations_research::sat::SchedulingConstraintHelper
Definition: intervals.h:172
operations_research::sat::IntegerTrail::UpperBound
IntegerValue UpperBound(IntegerVariable i) const
Definition: integer.h:1287
intervals.h
rev.h
operations_research::sat::TimeTablingPerTask::Propagate
bool Propagate() final
Definition: timetable.cc:78
capacity
int64 capacity
Definition: routing_flow.cc:129
operations_research::sat::IntegerTrail::LowerBound
IntegerValue LowerBound(IntegerVariable i) const
Definition: integer.h:1283
integer.h
operations_research::sat::TimeTablingPerTask::RegisterWith
void RegisterWith(GenericLiteralWatcher *watcher)
Definition: timetable.cc:61
operations_research::sat::TimeTablingPerTask
Definition: timetable.h:29
time
int64 time
Definition: resource.cc:1683