Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
piecewise_linear_function.h
Go to the documentation of this file.
1// Copyright 2010-2025 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_t. 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 <cstdint>
24#include <functional>
25#include <iterator>
26#include <string>
27#include <utility>
28#include <vector>
29
30#include "absl/algorithm/container.h"
31#include "absl/container/inlined_vector.h"
32#include "absl/log/check.h"
33#include "absl/strings/string_view.h"
34
35namespace operations_research {
36// This structure stores one straight line. It contains the start point, the
37// end point and the slope.
38// It is defined for x values between start_x and end_x.
40 public:
41 PiecewiseSegment(int64_t point_x, int64_t point_y, int64_t slope,
42 int64_t other_point_x);
43
44 // Returns the value of the segment at point x.
45 int64_t Value(int64_t x) const;
46 // Returns the start of the segment's domain.
47 int64_t start_x() const { return start_x_; }
48 // Returns the end of the segment's domain.
49 int64_t end_x() const { return end_x_; }
50 // Returns the value at the start of the segment's domain.
51 int64_t start_y() const { return Value(start_x_); }
52 // Returns the value at the end of the segment's domain.
53 int64_t end_y() const { return Value(end_x_); }
54 // Returns the segment's slope.
55 int64_t slope() const { return slope_; }
56 // Returns the intersection of the segment's extension with the y axis.
57 int64_t intersection_y() const { return intersection_y_; }
58
59 // Comparison method useful for sorting a sequence of segments.
60 static bool SortComparator(const PiecewiseSegment& segment1,
61 const PiecewiseSegment& segment2);
62 // Comparison method useful for finding in which segment a point belongs.
63 static bool FindComparator(int64_t point, const PiecewiseSegment& segment);
64
65 // Expands segment to the specified endpoint, if it is further
66 // than the current endpoint. The reference point of the segment
67 // doesn't change for overflow reasons.
68 void ExpandEnd(int64_t end_x);
69 // Adds 'constant' to the 'x' the segments.
70 void AddConstantToX(int64_t constant);
71 // Adds 'constant' to the 'y' the segments.
72 void AddConstantToY(int64_t constant);
73
74 std::string DebugString() const;
75
76 private:
77 // Computes the value of the segment at point x, taking care of possible
78 // overflows when the value x follow the x coordinate of the segment's
79 // reference point.
80 int64_t SafeValuePostReference(int64_t x) const;
81 // Computes the value of the segment at point x, taking care of possible
82 // overflows when the value x follow the x coordinate of the segment's
83 // reference point.
84 int64_t SafeValuePreReference(int64_t x) const;
85
86 // The x coordinate of the segment's left endpoint.
87 int64_t start_x_;
88 // The x coordinate of the segment's right endpoint.
89 int64_t end_x_;
90 // The segment's slope.
91 int64_t slope_;
92 // The x coordinate of the segment's finite reference point.
93 int64_t reference_x_;
94 // The y coordinate of the segment's finite reference point.
95 int64_t reference_y_;
96 // The intersection of the segment's extension with the y axis.
97 int64_t intersection_y_;
98};
99
100// In mathematics, a piecewise linear function is a function composed
101// of straight-line, non overlapping sections.
102class PiecewiseLinearFunction {
103 public:
104 static const int kNotFound;
105
106 // This API provides a factory for creating different families of Piecewise
107 // Linear Functions based on specific properties of each family. The
108 // PiecewiseLinearFunction is composed by a set of PiecwiseSegments and upon
109 // creation is not modifiable but with the provided function operations.
110 // The object returned by any of these builders in the factory is owned by
111 // the client code.
112
113 // Builds the most generic form of multiple-segment piecewise linear function
114 // supporting domain holes. For a fixed index i the elements in points_x[i]
115 // points_y[i], slopes[i], other_points_x[i] represent a segment.
116 // The point (points_x[i], points_y[i]) represents one of the endpoints of
117 // the segment and the other_points_x[i] represents the x coordinate of the
118 // other endpoint which may precede, follow or coincide with points_x[i].
119 // The segments represented by these vectors should not be overlapping.
120 // Common endpoints are allowed.
121 static PiecewiseLinearFunction* CreatePiecewiseLinearFunction(
122 std::vector<int64_t> points_x, std::vector<int64_t> points_y,
123 std::vector<int64_t> slopes, std::vector<int64_t> other_points_x);
124
125 // Builds a multiple-segment step function with continuous or non continuous
126 // domain. The arguments have the same semantics with the generic builder of
127 // the piecewise linear function. In the step function all the slopes are 0.
128 static PiecewiseLinearFunction* CreateStepFunction(
129 std::vector<int64_t> points_x, std::vector<int64_t> points_y,
130 std::vector<int64_t> other_points_x);
131
132 // Builds a multiple-segment piecewise linear function with domain from
133 // from kint64min to kint64max with n points and n+1 slopes. Each slope
134 // stops at the point with the corresponding index apart from the last one
135 // which stops at kint64max. The first slope stops at the first point at
136 // the level specified.
137 static PiecewiseLinearFunction* CreateFullDomainFunction(
138 int64_t initial_level, std::vector<int64_t> points_x,
139 std::vector<int64_t> slopes);
140
141 // Builds a function consisting of one segment.
142 static PiecewiseLinearFunction* CreateOneSegmentFunction(
143 int64_t point_x, int64_t point_y, int64_t slope, int64_t other_point_x);
144
145 // Builds a function consisting of one ray starting at the specified
146 // x and y coordinates with the specified slope.
147 static PiecewiseLinearFunction* CreateRightRayFunction(int64_t point_x,
148 int64_t point_y,
149 int64_t slope);
150
151 // Builds a function consisting of one ray starting at the specified
152 // x and y coordinates with the specified slope.
153 static PiecewiseLinearFunction* CreateLeftRayFunction(int64_t point_x,
154 int64_t point_y,
155 int64_t slope);
156
157 // Builds a two-segment fixed charge piecewise linear cost function. For
158 // values less than zero, the cost is zero. For values greater than zero,
159 // cost follows the line specified by the slope and the value given as
160 // arguments. The slope and value are positive.
161 static PiecewiseLinearFunction* CreateFixedChargeFunction(int64_t slope,
162 int64_t value);
163
164 // Builds an earliness-tardiness two-segment piecewise linear cost function.
165 // The reference specifies the point where the cost is zero. Before the
166 // reference, the cost increases with the earliness slope and after the
167 // reference, it increases with the tardiness slope. The absolute values of
168 // the slopes are given.
169 static PiecewiseLinearFunction* CreateEarlyTardyFunction(
170 int64_t reference, int64_t earliness_slope, int64_t tardiness_slope);
171
172 // Builds an earliness-tardiness three-segment piecewise linear cost function
173 // with a slack period around the due date. The early slack is the point
174 // before which the cost increases with the ealiness slope specified. The
175 // late slack is the point after which the cost increases with the late slope
176 // specified. Between the early and the late slack point, the cost is zero.
177 // The absolute values of the slopes are given.
178 static PiecewiseLinearFunction* CreateEarlyTardyFunctionWithSlack(
179 int64_t early_slack, int64_t late_slack, int64_t earliness_slope,
180 int64_t tardiness_slope);
181
182 // Returns if x is in the domain of the function.
183 bool InDomain(int64_t x) const;
184 // Determines whether the piecewise linear function is convex or non-convex
185 // and returns true when the function is convex.
186 bool IsConvex() const;
187 // Returns true if the piecewise linear function is non-decreasing.
188 bool IsNonDecreasing() const;
189 // Returns true if the piecewise linear function is non-increasing.
190 bool IsNonIncreasing() const;
191 // Returns the value of the piecewise linear function for x.
192 int64_t Value(int64_t x) const;
193 // Returns the maximum value of all the segments in the function.
194 int64_t GetMaximum() const;
195 // Returns the minimum value of all the segments in the function.
196 int64_t GetMinimum() const;
197 // Returns the maximum endpoint value of the segments in the specified
198 // range. If the range is disjoint from the segments in the function, it
199 // returns kint64max.
200 int64_t GetMaximum(int64_t range_start, int64_t range_end) const;
201 // Returns the minimum endpoint value of the segments in the specified
202 // range. If the range is disjoint from the segments in the function, it
203 // returns kint64max.
204 int64_t GetMinimum(int64_t range_start, int64_t range_end) const;
205 // Returns the smallest range within a given range containing all values
206 // greater than a given value.
207 std::pair<int64_t, int64_t> GetSmallestRangeGreaterThanValue(
208 int64_t range_start, int64_t range_end, int64_t value) const;
209 // Returns the smallest range within a given range containing all values
210 // less than a given value.
211 std::pair<int64_t, int64_t> GetSmallestRangeLessThanValue(
212 int64_t range_start, int64_t range_end, int64_t value) const;
213 // Returns the smallest range within a given range containing all values
214 // greater than value_min and less than value_max.
215 std::pair<int64_t, int64_t> GetSmallestRangeInValueRange(
216 int64_t range_start, int64_t range_end, int64_t value_min,
217 int64_t value_max) const;
218
219 // Adds 'constant' to the 'x' of all segments. If the argument is positive,
220 // the translation is to the right and when it's negative, to the left. The
221 // overflows and the underflows are sticky.
222 void AddConstantToX(int64_t constant);
223 // Adds 'constant' to the 'y' of all segments. If the argument is positive,
224 // the translation is up and when it's negative, down. The overflows and the
225 // underflows are sticky.
226 void AddConstantToY(int64_t constant);
227 // Adds the function to the existing one. The domain of the resulting
228 // function is the intersection of the two domains. The overflows and
229 // the underflows are sticky.
230 void Add(const PiecewiseLinearFunction& other);
231 // Subtracts the function to the existing one. The domain of the
232 // resulting function is the intersection of the two domains. The
233 // overflows and the underflows are sticky.
234 void Subtract(const PiecewiseLinearFunction& other);
235 // Decomposes the piecewise linear function in a set of convex piecewise
236 // linear functions. The objects in the vector are owned by the client code.
237 std::vector<PiecewiseLinearFunction*> DecomposeToConvexFunctions() const;
238
239 const std::vector<PiecewiseSegment>& segments() const { return segments_; }
240
241 std::string DebugString() const;
242
243 private:
244 // Takes the sequence of segments, sorts them on increasing start and inserts
245 // them in the piecewise linear function.
246 explicit PiecewiseLinearFunction(std::vector<PiecewiseSegment> segments);
247 // Inserts a segment in the function.
248 void InsertSegment(const PiecewiseSegment& segment);
249 // Operation between two functions. In any operation between two functions the
250 // final domain is the intersection between the two domains.
251 void Operation(const PiecewiseLinearFunction& other,
252 const std::function<int64_t(int64_t, int64_t)>& operation);
253 // Finds start and end segment indices from a range; returns false if the
254 // range is outside the domain of the function.
255 bool FindSegmentIndicesFromRange(int64_t range_start, int64_t range_end,
256 int* start_segment, int* end_segment) const;
257 void UpdateStatus() {
258 if (is_modified_) {
259 is_convex_ = IsConvexInternal();
260 is_non_decreasing_ = IsNonDecreasingInternal();
261 is_non_increasing_ = IsNonIncreasingInternal();
262 is_modified_ = false;
263 }
264 }
265 bool IsConvexInternal() const;
266 bool IsNonDecreasingInternal() const;
267 bool IsNonIncreasingInternal() const;
268
269 // The vector of segments in the function, sorted in ascending order of start
270 // points.
271 std::vector<PiecewiseSegment> segments_;
272 bool is_modified_;
273 bool is_convex_;
274 bool is_non_decreasing_;
275 bool is_non_increasing_;
276};
277
278// The following class defines a piecewise linear formulation with potential
279// double values for the slope of each linear function.
280// This formulation is meant to be used with a small number of segments (see
281// InlinedVector sizes below).
282// These segments are determined by int64_t values for the "anchor" x and y
283// values, such that (x_anchors_[i], y_anchors_[i]) and
284// (x_anchors_[i+1], y_anchors_[i+1]) are respectively the start and end point
285// of the i-th segment.
286// TODO(user): Adjust the inlined vector sizes based on experiments.
288 public:
289 static const int kNoValue;
290
292 FloatSlopePiecewiseLinearFunction(absl::InlinedVector<int64_t, 8> x_anchors,
293 absl::InlinedVector<int64_t, 8> y_anchors);
295 FloatSlopePiecewiseLinearFunction&& other) noexcept {
296 *this = std::move(other);
297 }
298
300 FloatSlopePiecewiseLinearFunction&& other) noexcept {
301 x_anchors_ = std::move(other.x_anchors_);
302 y_anchors_ = std::move(other.y_anchors_);
303 return *this;
304 }
305
306 std::string DebugString(absl::string_view line_prefix = {}) const;
307
308 const absl::InlinedVector<int64_t, 8>& x_anchors() const {
309 return x_anchors_;
310 }
311 const absl::InlinedVector<int64_t, 8>& y_anchors() const {
312 return y_anchors_;
313 }
314
315 // Computes the y value associated to 'x'. Returns kNoValue if 'x' is out of
316 // bounds, i.e. lower than the first x_anchor and largest than the last.
317 int64_t ComputeInBoundsValue(int64_t x) const;
318
319 // Computes the y value associated to 'x'. Unlike ComputeInBoundsValue(), if
320 // 'x' is outside the bounds of the function, the function will still be
321 // defined by its outer segments.
322 int64_t ComputeConvexValue(int64_t x) const;
323
324 private:
325 // Returns the index of the segment x belongs to, i.e. the index i such that
326 // x_anchors_[i] ≤ x < x_anchors_[i+1]. For x = x_anchors_.back(), also
327 // returns the last segment (i.e. x_anchors_.size() - 2).
328 // Returns kNoValue if x is out of bounds for the function.
329 int GetSegmentIndex(int64_t x) const {
330 if (x_anchors_.empty() || x < x_anchors_[0] || x > x_anchors_.back()) {
331 return kNoValue;
332 }
333 if (x == x_anchors_.back()) return x_anchors_.size() - 2;
334
335 // Search for first element xi such that xi > x.
336 const auto upper_segment = absl::c_upper_bound(x_anchors_, x);
337 const int segment_index =
338 std::distance(x_anchors_.begin(), upper_segment) - 1;
339 DCHECK_GE(segment_index, 0);
340 DCHECK_LE(segment_index, x_anchors_.size() - 2);
341 return segment_index;
342 }
343
344 // Returns the value of 'x' on the linear segment determined by
345 // x_anchors_[segment_index] and x_anchors_[segment_index + 1].
346 int64_t GetValueOnSegment(int64_t x, int segment_index) const;
347
348 // The set of *increasing* anchor cumul values for the interpolation.
349 absl::InlinedVector<int64_t, 8> x_anchors_;
350 // The y values used for the interpolation:
351 // For any x anchor value, let i be an index such that
352 // x_anchors[i] ≤ x < x_anchors[i+1], then the y value for x is
353 // y_anchors[i] * (1-λ) + y_anchors[i+1] * λ, with
354 // λ = (x - x_anchors[i]) / (x_anchors[i+1] - x_anchors[i]).
355 absl::InlinedVector<int64_t, 8> y_anchors_;
356};
357
358} // namespace operations_research
359#endif // OR_TOOLS_UTIL_PIECEWISE_LINEAR_FUNCTION_H_
FloatSlopePiecewiseLinearFunction(FloatSlopePiecewiseLinearFunction &&other) noexcept
std::string DebugString(absl::string_view line_prefix={}) const
const absl::InlinedVector< int64_t, 8 > & x_anchors() const
const absl::InlinedVector< int64_t, 8 > & y_anchors() const
static const int kNoValue
FloatSlopePiecewiseLinearFunction.
FloatSlopePiecewiseLinearFunction & operator=(FloatSlopePiecewiseLinearFunction &&other) noexcept
int64_t GetMaximum() const
Returns the maximum value of all the segments in the function.
std::vector< PiecewiseLinearFunction * > DecomposeToConvexFunctions() const
static PiecewiseLinearFunction * CreateFullDomainFunction(int64_t initial_level, std::vector< int64_t > points_x, std::vector< int64_t > slopes)
static PiecewiseLinearFunction * CreateRightRayFunction(int64_t point_x, int64_t point_y, int64_t slope)
bool IsNonIncreasing() const
Returns true if the piecewise linear function is non-increasing.
std::pair< int64_t, int64_t > GetSmallestRangeLessThanValue(int64_t range_start, int64_t range_end, int64_t value) const
static const int kNotFound
PiecewiseLinearFunction.
static PiecewiseLinearFunction * CreateFixedChargeFunction(int64_t slope, int64_t value)
void Add(const PiecewiseLinearFunction &other)
static PiecewiseLinearFunction * CreateStepFunction(std::vector< int64_t > points_x, std::vector< int64_t > points_y, std::vector< int64_t > other_points_x)
int64_t GetMinimum() const
Returns the minimum value of all the segments in the function.
const std::vector< PiecewiseSegment > & segments() const
static PiecewiseLinearFunction * CreateOneSegmentFunction(int64_t point_x, int64_t point_y, int64_t slope, int64_t other_point_x)
Builds a function consisting of one segment.
std::pair< int64_t, int64_t > GetSmallestRangeInValueRange(int64_t range_start, int64_t range_end, int64_t value_min, int64_t value_max) const
static PiecewiseLinearFunction * CreateLeftRayFunction(int64_t point_x, int64_t point_y, int64_t slope)
bool IsNonDecreasing() const
Returns true if the piecewise linear function is non-decreasing.
static PiecewiseLinearFunction * CreateEarlyTardyFunction(int64_t reference, int64_t earliness_slope, int64_t tardiness_slope)
static PiecewiseLinearFunction * CreatePiecewiseLinearFunction(std::vector< int64_t > points_x, std::vector< int64_t > points_y, std::vector< int64_t > slopes, std::vector< int64_t > other_points_x)
static PiecewiseLinearFunction * CreateEarlyTardyFunctionWithSlack(int64_t early_slack, int64_t late_slack, int64_t earliness_slope, int64_t tardiness_slope)
int64_t Value(int64_t x) const
Returns the value of the piecewise linear function for x.
std::pair< int64_t, int64_t > GetSmallestRangeGreaterThanValue(int64_t range_start, int64_t range_end, int64_t value) const
bool InDomain(int64_t x) const
Returns if x is in the domain of the function.
void Subtract(const PiecewiseLinearFunction &other)
int64_t end_x() const
Returns the end of the segment's domain.
int64_t start_y() const
Returns the value at the start of the segment's domain.
static bool FindComparator(int64_t point, const PiecewiseSegment &segment)
Comparison method useful for finding in which segment a point belongs.
static bool SortComparator(const PiecewiseSegment &segment1, const PiecewiseSegment &segment2)
Comparison method useful for sorting a sequence of segments.
void AddConstantToY(int64_t constant)
Adds 'constant' to the 'y' the segments.
int64_t intersection_y() const
Returns the intersection of the segment's extension with the y axis.
int64_t slope() const
Returns the segment's slope.
int64_t start_x() const
Returns the start of the segment's domain.
void AddConstantToX(int64_t constant)
Adds 'constant' to the 'x' the segments.
PiecewiseSegment(int64_t point_x, int64_t point_y, int64_t slope, int64_t other_point_x)
PiecewiseSegment.
int64_t Value(int64_t x) const
Returns the value of the segment at point x.
int64_t end_y() const
Returns the value at the end of the segment's domain.
In SWIG mode, we don't want anything besides these top-level includes.