OR-Tools  8.1
timetable_edgefinding.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_EDGEFINDING_H_
15 #define OR_TOOLS_SAT_TIMETABLE_EDGEFINDING_H_
16 
17 #include <vector>
18 
19 #include "ortools/base/int_type.h"
20 #include "ortools/base/macros.h"
21 #include "ortools/sat/integer.h"
22 #include "ortools/sat/intervals.h"
23 #include "ortools/sat/sat_base.h"
24 
25 namespace operations_research {
26 namespace sat {
27 
28 // TimeTableEdgeFinding implements the timetable edge finding filtering rule
29 // presented in Vilim Petr, "Timetable edge finding filtering algorithm for
30 // discrete cumulative resources", CPAIOR 2011,
31 // http://vilim.eu/petr/cpaior2011.pdf.
32 //
33 // This propagator runs in O(n^2) where n is the number of tasks. It increases
34 // both the start times and decreases the ending times of the tasks.
35 //
36 // Note that this propagator does not ensure that the cumulative constraint
37 // holds. It should thus always be used with at least a timetable propagator.
38 //
39 // ALOGRITHM:
40 //
41 // The algorithm relies on free tasks. A free task is basically a task without
42 // its mandatory part. For instance:
43 //
44 // s_min s_max e_min e_max
45 // v v v v
46 // task: =============================
47 // ^ ^ ^
48 // | free part | Mandatory part |
49 //
50 // Obviously, the free part of a task that has no mandatory part is equal to the
51 // task itself. Also, a free part cannot have a mandatory part by definition. A
52 // fixed task thus have no free part.
53 //
54 // The idea of the algorithm is to use free and mandatory parts separately to
55 // have a better estimation of the energy contained in a task interval.
56 //
57 // If the sum of the energy of all the free parts and mandatory subparts
58 // contained in a task interval exceeds the amount of energy available, then the
59 // problem is unfeasible. A task thus cannot be scheduled at its minimum start
60 // time if this would cause an overload in one of the task intervals.
62  public:
63  TimeTableEdgeFinding(const std::vector<AffineExpression>& demands,
66  IntegerTrail* integer_trail);
67 
68  bool Propagate() final;
69 
70  void RegisterWith(GenericLiteralWatcher* watcher);
71 
72  private:
73  // Build the timetable and fills the mandatory_energy_before_start_min_ and
74  // mandatory_energy_before_end_max_.
75  //
76  // TODO(user): Share the profile building code with TimeTablingPerTask ! we do
77  // not really need the mandatory_energy_before_* vectors and can recompute the
78  // profile integral in a window efficiently during TimeTableEdgeFindingPass().
79  void BuildTimeTable();
80 
81  // Performs a single pass of the Timetable Edge Finding filtering rule to
82  // updates the start time of the tasks. This same function can be used to
83  // update the end times by calling the SwitchToMirrorProblem method first.
84  bool TimeTableEdgeFindingPass();
85 
86  // Increases the start min of task_index with the proper explanation.
87  bool IncreaseStartMin(IntegerValue begin, IntegerValue end, int task_index,
88  IntegerValue new_start);
89 
90  IntegerValue DemandMin(int task_index) const {
91  return integer_trail_->LowerBound(demands_[task_index]);
92  }
93 
94  IntegerValue CapacityMax() const {
95  return integer_trail_->UpperBound(capacity_);
96  }
97 
98  // Number of tasks.
99  const int num_tasks_;
100 
101  // IntervalVariable and IntegerVariable of each tasks that must be considered
102  // in this constraint.
103  std::vector<AffineExpression> demands_;
104  const AffineExpression capacity_;
105 
107  IntegerTrail* integer_trail_;
108 
109  // Start (resp. end) of the compulsory parts used to build the profile.
110  std::vector<TaskTime> scp_;
111  std::vector<TaskTime> ecp_;
112 
113  // Sizes and energy of the free parts. One is just the other times the
114  // minimum demand.
115  std::vector<IntegerValue> size_free_;
116  std::vector<IntegerValue> energy_free_;
117 
118  // Energy contained in the time table before the start min (resp. end max)
119  // of each task.
120  std::vector<IntegerValue> mandatory_energy_before_start_min_;
121  std::vector<IntegerValue> mandatory_energy_before_end_max_;
122 
123  DISALLOW_COPY_AND_ASSIGN(TimeTableEdgeFinding);
124 };
125 
126 } // namespace sat
127 } // namespace operations_research
128 
129 #endif // OR_TOOLS_SAT_TIMETABLE_EDGEFINDING_H_
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
sat_base.h
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
int_type.h
intervals.h
operations_research::sat::TimeTableEdgeFinding::TimeTableEdgeFinding
TimeTableEdgeFinding(const std::vector< AffineExpression > &demands, AffineExpression capacity, SchedulingConstraintHelper *helper, IntegerTrail *integer_trail)
Definition: timetable_edgefinding.cc:30
operations_research::sat::TimeTableEdgeFinding::RegisterWith
void RegisterWith(GenericLiteralWatcher *watcher)
Definition: timetable_edgefinding.cc:47
operations_research::sat::TimeTableEdgeFinding::Propagate
bool Propagate() final
Definition: timetable_edgefinding.cc:56
operations_research::sat::TimeTableEdgeFinding
Definition: timetable_edgefinding.h:61
capacity
int64 capacity
Definition: routing_flow.cc:129
operations_research::sat::IntegerTrail::LowerBound
IntegerValue LowerBound(IntegerVariable i) const
Definition: integer.h:1283
integer.h