OR-Tools  8.2
piecewise_linear_function.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// This file implements piecewise linear functions over int64. It is built
15// by inserting segments.
16//
17// This class maintains a minimal internal representation and checks for
18// overflow.
19
20#ifndef OR_TOOLS_UTIL_PIECEWISE_LINEAR_FUNCTION_H_
21#define OR_TOOLS_UTIL_PIECEWISE_LINEAR_FUNCTION_H_
22
23#include <algorithm>
24#include <functional>
25#include <memory>
26#include <string>
27#include <vector>
28
31#include "ortools/base/macros.h"
33
34namespace operations_research {
35// This structure stores one straight line. It contains the start point, the
36// end point and the slope.
37// It is defined for x values between start_x and end_x.
39 public:
40 PiecewiseSegment(int64 point_x, int64 point_y, int64 slope,
41 int64 other_point_x);
42
43 // Returns the value of the segment at point x.
44 int64 Value(int64 x) const;
45 // Returns the start of the segment's domain.
46 int64 start_x() const { return start_x_; }
47 // Returns the end of the segment's domain.
48 int64 end_x() const { return end_x_; }
49 // Returns the value at the start of the segment's domain.
50 int64 start_y() const { return Value(start_x_); }
51 // Returns the value at the end of the segment's domain.
52 int64 end_y() const { return Value(end_x_); }
53 // Returns the segment's slope.
54 int64 slope() const { return slope_; }
55 // Returns the intersection of the segment's extension with the y axis.
56 int64 intersection_y() const { return intersection_y_; }
57
58 // Comparison method useful for sorting a sequence of segments.
59 static bool SortComparator(const PiecewiseSegment& segment1,
60 const PiecewiseSegment& segment2);
61 // Comparison method useful for finding in which segment a point belongs.
62 static bool FindComparator(int64 point, const PiecewiseSegment& segment);
63
64 // Expands segment to the specified endpoint, if it is further
65 // than the current endpoint. The reference point of the segment
66 // doesn't change for overflow reasons.
67 void ExpandEnd(int64 end_x);
68 // Adds 'constant' to the 'x' the segments.
69 void AddConstantToX(int64 constant);
70 // Adds 'constant' to the 'y' the segments.
71 void AddConstantToY(int64 constant);
72
73 std::string DebugString() const;
74
75 private:
76 // Computes the value of the segment at point x, taking care of possible
77 // overflows when the value x follow the x coordinate of the segment's
78 // reference point.
79 int64 SafeValuePostReference(int64 x) const;
80 // Computes the value of the segment at point x, taking care of possible
81 // overflows when the value x follow the x coordinate of the segment's
82 // reference point.
83 int64 SafeValuePreReference(int64 x) const;
84
85 // The x coordinate of the segment's left endpoint.
86 int64 start_x_;
87 // The x coordinate of the segment's right endpoint.
88 int64 end_x_;
89 // The segment's slope.
90 int64 slope_;
91 // The x coordinate of the segment's finite reference point.
92 int64 reference_x_;
93 // The y coordinate of the segment's finite reference point.
94 int64 reference_y_;
95 // The intersection of the segment's extension with the y axis.
96 int64 intersection_y_;
97};
98
99// In mathematics, a piecewise linear function is a function composed
100// of straight-line, non overlapping sections.
102 public:
103 static const int kNotFound;
104
105 // This API provides a factory for creating different families of Piecewise
106 // Linear Functions based on specific properties of each family. The
107 // PiecewiseLinearFunction is composed by a set of PiecwiseSegments and upon
108 // creation is not modifiable but with the provided function operations.
109 // The object returned by any of these builders in the factory is owned by
110 // the client code.
111
112 // Builds the most generic form of multiple-segment piecewise linear function
113 // supporting domain holes. For a fixed index i the elements in points_x[i]
114 // points_y[i], slopes[i], other_points_x[i] represent a segment.
115 // The point (points_x[i], points_y[i]) represents one of the endpoints of
116 // the segment and the other_points_x[i] represents the x coordinate of the
117 // other endpoint which may precede, follow or coincide with points_x[i].
118 // The segments represented by these vectors should not be overlapping.
119 // Common endpoints are allowed.
121 std::vector<int64> points_x, std::vector<int64> points_y,
122 std::vector<int64> slopes, std::vector<int64> other_points_x);
123
124 // Builds a multiple-segment step function with continuous or non continuous
125 // domain. The arguments have the same semantics with the generic builder of
126 // the piecewise linear function. In the step function all the slopes are 0.
128 std::vector<int64> points_x, std::vector<int64> points_y,
129 std::vector<int64> other_points_x);
130
131 // Builds a multiple-segment piecewise linear function with domain from
132 // from kint64min to kint64max with n points and n+1 slopes. Each slope
133 // stops at the point with the corresponding index apart from the last one
134 // which stops at kint64max. The first slope stops at the first point at
135 // the level specified.
137 int64 initial_level, std::vector<int64> points_x,
138 std::vector<int64> slopes);
139
140 // Builds a function consisting of one segment.
142 int64 point_y,
143 int64 slope,
144 int64 other_point_x);
145
146 // Builds a function consisting of one ray starting at the specified
147 // x and y coordinates with the specified slope.
149 int64 point_y,
150 int64 slope);
151
152 // Builds a function consisting of one ray starting at the specified
153 // x and y coordinates with the specified slope.
155 int64 point_y,
156 int64 slope);
157
158 // Builds a two-segment fixed charge piecewise linear cost function. For
159 // values less than zero, the cost is zero. For values greater than zero,
160 // cost follows the line specified by the slope and the value given as
161 // arguments. The slope and value are positive.
163 int64 value);
164
165 // Builds an earliness-tardiness two-segment piecewise linear cost function.
166 // The reference specifies the point where the cost is zero. Before the
167 // reference, the cost increases with the earliness slope and after the
168 // referece, it increases with the tardiness slope. The absolute values of
169 // the slopes are given.
171 int64 reference, int64 earliness_slope, int64 tardiness_slope);
172
173 // Builds an earliness-tardiness three-segment piecewise linear cost function
174 // with a slack period around the due date. The early slack is the point
175 // before which the cost increases with the ealiness slope specified. The
176 // late slack is the point after which the cost increases with the late slope
177 // specified. Between the early and the late slack point, the cost is zero.
178 // The absolute values of the slopes are given.
180 int64 early_slack, int64 late_slack, int64 earliness_slope,
181 int64 tardiness_slope);
182
183 // Returns if x is in the domain of the function.
184 bool InDomain(int64 x) const;
185 // Determines whether the piecewise linear function is convex or non-convex
186 // and returns true when the function is convex.
187 bool IsConvex() const;
188 // Returns true if the piecewise linear function is non-decreasing.
189 bool IsNonDecreasing() const;
190 // Returns true if the piecewise linear function is non-increasing.
191 bool IsNonIncreasing() const;
192 // Returns the value of the piecewise linear function for x.
193 int64 Value(int64 x) const;
194 // Returns the maximum value of all the segments in the function.
195 int64 GetMaximum() const;
196 // Returns the minimum value of all the segments in the function.
197 int64 GetMinimum() const;
198 // Returns the maximum endpoint value of the segments in the specified
199 // range. If the range is disjoint from the segments in the function, it
200 // returns kint64max.
201 int64 GetMaximum(int64 range_start, int64 range_end) const;
202 // Returns the minimum endpoint value of the segments in the specified
203 // range. If the range is disjoint from the segments in the function, it
204 // returns kint64max.
205 int64 GetMinimum(int64 range_start, int64 range_end) const;
206 // Returns the smallest range within a given range containing all values
207 // greater than a given value.
208 std::pair<int64, int64> GetSmallestRangeGreaterThanValue(int64 range_start,
209 int64 range_end,
210 int64 value) const;
211 // Returns the smallest range within a given range containing all values
212 // less than a given value.
213 std::pair<int64, int64> GetSmallestRangeLessThanValue(int64 range_start,
214 int64 range_end,
215 int64 value) const;
216 // Returns the smallest range within a given range containing all values
217 // greater than value_min and less than value_max.
218 std::pair<int64, int64> GetSmallestRangeInValueRange(int64 range_start,
219 int64 range_end,
220 int64 value_min,
221 int64 value_max) const;
222
223 // Adds 'constant' to the 'x' of all segments. If the argument is positive,
224 // the translation is to the right and when it's negative, to the left. The
225 // overflows and the underflows are sticky.
226 void AddConstantToX(int64 constant);
227 // Adds 'constant' to the 'y' of all segments. If the argument is positive,
228 // the translation is up and when it's negative, down. The overflows and the
229 // underflows are sticky.
230 void AddConstantToY(int64 constant);
231 // Adds the function to the existing one. The domain of the resulting
232 // function is the intersection of the two domains. The overflows and
233 // the underflows are sticky.
234 void Add(const PiecewiseLinearFunction& other);
235 // Subtracts the function to the existing one. The domain of the
236 // resulting function is the intersection of the two domains. The
237 // overflows and the underflows are sticky.
238 void Subtract(const PiecewiseLinearFunction& other);
239 // Decomposes the piecewise linear function in a set of convex piecewise
240 // linear functions. The objects in the vector are owned by the client code.
241 std::vector<PiecewiseLinearFunction*> DecomposeToConvexFunctions() const;
242
243 const std::vector<PiecewiseSegment>& segments() const { return segments_; }
244
245 std::string DebugString() const;
246
247 private:
248 // Takes the sequence of segments, sorts them on increasing start and inserts
249 // them in the piecewise linear function.
250 explicit PiecewiseLinearFunction(std::vector<PiecewiseSegment> segments);
251 // Inserts a segment in the function.
252 void InsertSegment(const PiecewiseSegment& segment);
253 // Operation between two functions. In any operation between two functions the
254 // final domain is the intersection between the two domains.
255 void Operation(const PiecewiseLinearFunction& other,
256 const std::function<int64(int64, int64)>& operation);
257 // Finds start and end segment indices from a range; returns false if the
258 // range is outside the domain of the function.
259 bool FindSegmentIndicesFromRange(int64 range_start, int64 range_end,
260 int* start_segment, int* end_segment) const;
261 void UpdateStatus() {
262 if (is_modified_) {
263 is_convex_ = IsConvexInternal();
264 is_non_decreasing_ = IsNonDecreasingInternal();
265 is_non_increasing_ = IsNonIncreasingInternal();
266 is_modified_ = false;
267 }
268 }
269 bool IsConvexInternal() const;
270 bool IsNonDecreasingInternal() const;
271 bool IsNonIncreasingInternal() const;
272
273 // The vector of segments in the function, sorted in ascending order of start
274 // points.
275 std::vector<PiecewiseSegment> segments_;
276 bool is_modified_;
277 bool is_convex_;
278 bool is_non_decreasing_;
279 bool is_non_increasing_;
280};
281} // namespace operations_research
282#endif // OR_TOOLS_UTIL_PIECEWISE_LINEAR_FUNCTION_H_
std::pair< int64, int64 > GetSmallestRangeInValueRange(int64 range_start, int64 range_end, int64 value_min, int64 value_max) const
static PiecewiseLinearFunction * CreateEarlyTardyFunction(int64 reference, int64 earliness_slope, int64 tardiness_slope)
static PiecewiseLinearFunction * CreateFullDomainFunction(int64 initial_level, std::vector< int64 > points_x, std::vector< int64 > slopes)
static PiecewiseLinearFunction * CreatePiecewiseLinearFunction(std::vector< int64 > points_x, std::vector< int64 > points_y, std::vector< int64 > slopes, std::vector< int64 > other_points_x)
static PiecewiseLinearFunction * CreateStepFunction(std::vector< int64 > points_x, std::vector< int64 > points_y, std::vector< int64 > other_points_x)
std::vector< PiecewiseLinearFunction * > DecomposeToConvexFunctions() const
void Add(const PiecewiseLinearFunction &other)
static PiecewiseLinearFunction * CreateFixedChargeFunction(int64 slope, int64 value)
void Subtract(const PiecewiseLinearFunction &other)
std::pair< int64, int64 > GetSmallestRangeGreaterThanValue(int64 range_start, int64 range_end, int64 value) const
std::pair< int64, int64 > GetSmallestRangeLessThanValue(int64 range_start, int64 range_end, int64 value) const
static PiecewiseLinearFunction * CreateOneSegmentFunction(int64 point_x, int64 point_y, int64 slope, int64 other_point_x)
const std::vector< PiecewiseSegment > & segments() const
static PiecewiseLinearFunction * CreateEarlyTardyFunctionWithSlack(int64 early_slack, int64 late_slack, int64 earliness_slope, int64 tardiness_slope)
static PiecewiseLinearFunction * CreateRightRayFunction(int64 point_x, int64 point_y, int64 slope)
static PiecewiseLinearFunction * CreateLeftRayFunction(int64 point_x, int64 point_y, int64 slope)
static bool FindComparator(int64 point, const PiecewiseSegment &segment)
PiecewiseSegment(int64 point_x, int64 point_y, int64 slope, int64 other_point_x)
static bool SortComparator(const PiecewiseSegment &segment1, const PiecewiseSegment &segment2)
int64 value
int64_t int64
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...