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 
34 namespace 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
const std::vector< PiecewiseSegment > & segments() 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)
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...