OR-Tools  8.2
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
20#include "ortools/base/macros.h"
21#include "ortools/sat/integer.h"
24
25namespace operations_research {
26namespace 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
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_
IntegerValue UpperBound(IntegerVariable i) const
Definition: integer.h:1304
IntegerValue LowerBound(IntegerVariable i) const
Definition: integer.h:1300
void RegisterWith(GenericLiteralWatcher *watcher)
TimeTableEdgeFinding(const std::vector< AffineExpression > &demands, AffineExpression capacity, SchedulingConstraintHelper *helper, IntegerTrail *integer_trail)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 capacity