piecewise_linear_function.h

Go to the documentation of this file.

// Copyright 2010-2025 Google LLC
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
 
// This file implements piecewise linear functions over int64_t. It is built
// by inserting segments.
//
// This class maintains a minimal internal representation and checks for
// overflow.
 
#ifndef OR_TOOLS_UTIL_PIECEWISE_LINEAR_FUNCTION_H_
#define OR_TOOLS_UTIL_PIECEWISE_LINEAR_FUNCTION_H_
 
#include <cstdint>
#include <functional>
#include <iterator>
#include <string>
#include <utility>
#include <vector>
 
#include "absl/algorithm/container.h"
#include "absl/container/inlined_vector.h"
#include "absl/log/check.h"
#include "absl/strings/string_view.h"
 
namespace operations_research {
// This structure stores one straight line. It contains the start point, the
// end point and the slope.
// It is defined for x values between start_x and end_x.
class PiecewiseSegment {
 public:
  PiecewiseSegment(int64_t point_x, int64_t point_y, int64_t slope,
                   int64_t other_point_x);
 
  // Returns the value of the segment at point x.
  int64_t Value(int64_t x) const;
  // Returns the start of the segment's domain.
  int64_t start_x() const { return start_x_; }
  // Returns the end of the segment's domain.
  int64_t end_x() const { return end_x_; }
  // Returns the value at the start of the segment's domain.
  int64_t start_y() const { return Value(start_x_); }
  // Returns the value at the end of the segment's domain.
  int64_t end_y() const { return Value(end_x_); }
  // Returns the segment's slope.
  int64_t slope() const { return slope_; }
  // Returns the intersection of the segment's extension with the y axis.
  int64_t intersection_y() const { return intersection_y_; }
 
  // Comparison method useful for sorting a sequence of segments.
  static bool SortComparator(const PiecewiseSegment& segment1,
                             const PiecewiseSegment& segment2);
  // Comparison method useful for finding in which segment a point belongs.
  static bool FindComparator(int64_t point, const PiecewiseSegment& segment);
 
  // Expands segment to the specified endpoint, if it is further
  // than the current endpoint. The reference point of the segment
  // doesn't change for overflow reasons.
  void ExpandEnd(int64_t end_x);
  // Adds 'constant' to the 'x' the segments.
  void AddConstantToX(int64_t constant);
  // Adds 'constant' to the 'y' the segments.
  void AddConstantToY(int64_t constant);
 
  std::string DebugString() const;
 
 private:
  // Computes the value of the segment at point x, taking care of possible
  // overflows when the value x follow the x coordinate of the segment's
  // reference point.
  int64_t SafeValuePostReference(int64_t x) const;
  // Computes the value of the segment at point x, taking care of possible
  // overflows when the value x follow the x coordinate of the segment's
  // reference point.
  int64_t SafeValuePreReference(int64_t x) const;
 
  // The x coordinate of the segment's left endpoint.
  int64_t start_x_;
  // The x coordinate of the segment's right endpoint.
  int64_t end_x_;
  // The segment's slope.
  int64_t slope_;
  // The x coordinate of the segment's finite reference point.
  int64_t reference_x_;
  // The y coordinate of the segment's finite reference point.
  int64_t reference_y_;
  // The intersection of the segment's extension with the y axis.
  int64_t intersection_y_;
};
 
// In mathematics, a piecewise linear function is a function composed
// of straight-line, non overlapping sections.
class PiecewiseLinearFunction {
 public:
  static const int kNotFound;
 
  // This API provides a factory for creating different families of Piecewise
  // Linear Functions based on specific properties of each family. The
  // PiecewiseLinearFunction is composed by a set of PiecwiseSegments and upon
  // creation is not modifiable but with the provided function operations.
  // The object returned by any of these builders in the factory is owned by
  // the client code.
 
  // Builds the most generic form of multiple-segment piecewise linear function
  // supporting domain holes. For a fixed index i the elements in points_x[i]
  // points_y[i], slopes[i], other_points_x[i] represent a segment.
  // The point (points_x[i], points_y[i]) represents one of the endpoints of
  // the segment and the other_points_x[i] represents the x coordinate of the
  // other endpoint which may precede, follow or coincide with points_x[i].
  // The segments represented by these vectors should not be overlapping.
  // Common endpoints are allowed.
  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);
 
  // Builds a multiple-segment step function with continuous or non continuous
  // domain. The arguments have the same semantics with the generic builder of
  // the piecewise linear function. In the step function all the slopes are 0.
  static PiecewiseLinearFunction* CreateStepFunction(
      std::vector<int64_t> points_x, std::vector<int64_t> points_y,
      std::vector<int64_t> other_points_x);
 
  // Builds a multiple-segment piecewise linear function with domain from
  // from kint64min to kint64max with n points and n+1 slopes. Each slope
  // stops at the point with the corresponding index apart from the last one
  // which stops at kint64max. The first slope stops at the first point at
  // the level specified.
  static PiecewiseLinearFunction* CreateFullDomainFunction(
      int64_t initial_level, std::vector<int64_t> points_x,
      std::vector<int64_t> slopes);
 
  // Builds a function consisting of one segment.
  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 ray starting at the specified
  // x and y coordinates with the specified slope.
  static PiecewiseLinearFunction* CreateRightRayFunction(int64_t point_x,
                                                         int64_t point_y,
                                                         int64_t slope);
 
  // Builds a function consisting of one ray starting at the specified
  // x and y coordinates with the specified slope.
  static PiecewiseLinearFunction* CreateLeftRayFunction(int64_t point_x,
                                                        int64_t point_y,
                                                        int64_t slope);
 
  // Builds a two-segment fixed charge piecewise linear cost function. For
  // values less than zero, the cost is zero. For values greater than zero,
  // cost follows the line specified by the slope and the value given as
  // arguments. The slope and value are positive.
  static PiecewiseLinearFunction* CreateFixedChargeFunction(int64_t slope,
                                                            int64_t value);
 
  // Builds an earliness-tardiness two-segment piecewise linear cost function.
  // The reference specifies the point where the cost is zero. Before the
  // reference, the cost increases with the earliness slope and after the
  // reference, it increases with the tardiness slope. The absolute values of
  // the slopes are given.
  static PiecewiseLinearFunction* CreateEarlyTardyFunction(
      int64_t reference, int64_t earliness_slope, int64_t tardiness_slope);
 
  // Builds an earliness-tardiness three-segment piecewise linear cost function
  // with a slack period around the due date. The early slack is the point
  // before which the cost increases with the ealiness slope specified. The
  // late slack is the point after which the cost increases with the late slope
  // specified. Between the early and the late slack point, the cost is zero.
  // The absolute values of the slopes are given.
  static PiecewiseLinearFunction* CreateEarlyTardyFunctionWithSlack(
      int64_t early_slack, int64_t late_slack, int64_t earliness_slope,
      int64_t tardiness_slope);
 
  // Returns if x is in the domain of the function.
  bool InDomain(int64_t x) const;
  // Determines whether the piecewise linear function is convex or non-convex
  // and returns true when the function is convex.
  bool IsConvex() const;
  // Returns true if the piecewise linear function is non-decreasing.
  bool IsNonDecreasing() const;
  // Returns true if the piecewise linear function is non-increasing.
  bool IsNonIncreasing() const;
  // Returns the value of the piecewise linear function for x.
  int64_t Value(int64_t x) const;
  // Returns the maximum value of all the segments in the function.
  int64_t GetMaximum() const;
  // Returns the minimum value of all the segments in the function.
  int64_t GetMinimum() const;
  // Returns the maximum endpoint value of the segments in the specified
  // range. If the range is disjoint from the segments in the function, it
  // returns kint64max.
  int64_t GetMaximum(int64_t range_start, int64_t range_end) const;
  // Returns the minimum endpoint value of the segments in the specified
  // range. If the range is disjoint from the segments in the function, it
  // returns kint64max.
  int64_t GetMinimum(int64_t range_start, int64_t range_end) const;
  // Returns the smallest range within a given range containing all values
  // greater than a given value.
  std::pair<int64_t, int64_t> GetSmallestRangeGreaterThanValue(
      int64_t range_start, int64_t range_end, int64_t value) const;
  // Returns the smallest range within a given range containing all values
  // less than a given value.
  std::pair<int64_t, int64_t> GetSmallestRangeLessThanValue(
      int64_t range_start, int64_t range_end, int64_t value) const;
  // Returns the smallest range within a given range containing all values
  // greater than value_min and less than value_max.
  std::pair<int64_t, int64_t> GetSmallestRangeInValueRange(
      int64_t range_start, int64_t range_end, int64_t value_min,
      int64_t value_max) const;
 
  // Adds 'constant' to the 'x' of all segments. If the argument is positive,
  // the translation is to the right and when it's negative, to the left. The
  // overflows and the underflows are sticky.
  void AddConstantToX(int64_t constant);
  // Adds 'constant' to the 'y' of all segments. If the argument is positive,
  // the translation is up and when it's negative, down. The overflows and the
  // underflows are sticky.
  void AddConstantToY(int64_t constant);
  // Adds the function to the existing one. The domain of the resulting
  // function is the intersection of the two domains. The overflows and
  // the underflows are sticky.
  void Add(const PiecewiseLinearFunction& other);
  // Subtracts the function to the existing one. The domain of the
  // resulting function is the intersection of the two domains. The
  // overflows and the underflows are sticky.
  void Subtract(const PiecewiseLinearFunction& other);
  // Decomposes the piecewise linear function in a set of convex piecewise
  // linear functions. The objects in the vector are owned by the client code.
  std::vector<PiecewiseLinearFunction*> DecomposeToConvexFunctions() const;
 
  const std::vector<PiecewiseSegment>& segments() const { return segments_; }
 
  std::string DebugString() const;
 
 private:
  // Takes the sequence of segments, sorts them on increasing start and inserts
  // them in the piecewise linear function.
  explicit PiecewiseLinearFunction(std::vector<PiecewiseSegment> segments);
  // Inserts a segment in the function.
  void InsertSegment(const PiecewiseSegment& segment);
  // Operation between two functions. In any operation between two functions the
  // final domain is the intersection between the two domains.
  void Operation(const PiecewiseLinearFunction& other,
                 const std::function<int64_t(int64_t, int64_t)>& operation);
  // Finds start and end segment indices from a range; returns false if the
  // range is outside the domain of the function.
  bool FindSegmentIndicesFromRange(int64_t range_start, int64_t range_end,
                                   int* start_segment, int* end_segment) const;
  void UpdateStatus() {
    if (is_modified_) {
      is_convex_ = IsConvexInternal();
      is_non_decreasing_ = IsNonDecreasingInternal();
      is_non_increasing_ = IsNonIncreasingInternal();
      is_modified_ = false;
    }
  }
  bool IsConvexInternal() const;
  bool IsNonDecreasingInternal() const;
  bool IsNonIncreasingInternal() const;
 
  // The vector of segments in the function, sorted in ascending order of start
  // points.
  std::vector<PiecewiseSegment> segments_;
  bool is_modified_;
  bool is_convex_;
  bool is_non_decreasing_;
  bool is_non_increasing_;
};
 
// The following class defines a piecewise linear formulation with potential
// double values for the slope of each linear function.
// This formulation is meant to be used with a small number of segments (see
// InlinedVector sizes below).
// These segments are determined by int64_t values for the "anchor" x and y
// values, such that (x_anchors_[i], y_anchors_[i]) and
// (x_anchors_[i+1], y_anchors_[i+1]) are respectively the start and end point
// of the i-th segment.
// TODO(user): Adjust the inlined vector sizes based on experiments.
class FloatSlopePiecewiseLinearFunction {
 public:
  static const int kNoValue;
 
  FloatSlopePiecewiseLinearFunction() = default;
  FloatSlopePiecewiseLinearFunction(absl::InlinedVector<int64_t, 8> x_anchors,
                                    absl::InlinedVector<int64_t, 8> y_anchors);
  FloatSlopePiecewiseLinearFunction(
      FloatSlopePiecewiseLinearFunction&& other) noexcept {
    *this = std::move(other);
  }
 
  FloatSlopePiecewiseLinearFunction& operator=(
      FloatSlopePiecewiseLinearFunction&& other) noexcept {
    x_anchors_ = std::move(other.x_anchors_);
    y_anchors_ = std::move(other.y_anchors_);
    return *this;
  }
 
  std::string DebugString(absl::string_view line_prefix = {}) const;
 
  const absl::InlinedVector<int64_t, 8>& x_anchors() const {
    return x_anchors_;
  }
  const absl::InlinedVector<int64_t, 8>& y_anchors() const {
    return y_anchors_;
  }
 
  // Computes the y value associated to 'x'. Returns kNoValue if 'x' is out of
  // bounds, i.e. lower than the first x_anchor and largest than the last.
  int64_t ComputeInBoundsValue(int64_t x) const;
 
  // Computes the y value associated to 'x'. Unlike ComputeInBoundsValue(), if
  // 'x' is outside the bounds of the function, the function will still be
  // defined by its outer segments.
  int64_t ComputeConvexValue(int64_t x) const;
 
 private:
  // Returns the index of the segment x belongs to, i.e. the index i such that
  // x_anchors_[i] ≤ x < x_anchors_[i+1]. For x = x_anchors_.back(), also
  // returns the last segment (i.e. x_anchors_.size() - 2).
  // Returns kNoValue if x is out of bounds for the function.
  int GetSegmentIndex(int64_t x) const {
    if (x_anchors_.empty() || x < x_anchors_[0] || x > x_anchors_.back()) {
      return kNoValue;
    }
    if (x == x_anchors_.back()) return x_anchors_.size() - 2;
 
    // Search for first element xi such that xi > x.
    const auto upper_segment = absl::c_upper_bound(x_anchors_, x);
    const int segment_index =
        std::distance(x_anchors_.begin(), upper_segment) - 1;
    DCHECK_GE(segment_index, 0);
    DCHECK_LE(segment_index, x_anchors_.size() - 2);
    return segment_index;
  }
 
  // Returns the value of 'x' on the linear segment determined by
  // x_anchors_[segment_index] and x_anchors_[segment_index + 1].
  int64_t GetValueOnSegment(int64_t x, int segment_index) const;
 
  // The set of *increasing* anchor cumul values for the interpolation.
  absl::InlinedVector<int64_t, 8> x_anchors_;
  // The y values used for the interpolation:
  // For any x anchor value, let i be an index such that
  // x_anchors[i] ≤ x < x_anchors[i+1], then the y value for x is
  // y_anchors[i] * (1-λ) + y_anchors[i+1] * λ, with
  // λ = (x - x_anchors[i]) / (x_anchors[i+1] - x_anchors[i]).
  absl::InlinedVector<int64_t, 8> y_anchors_;
};
 
}  // namespace operations_research
#endif  // OR_TOOLS_UTIL_PIECEWISE_LINEAR_FUNCTION_H_