OR-Tools  8.2
piecewise_linear_function.cc
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 
15 
16 #include <algorithm>
17 #include <set>
18 #include <string>
19 #include <vector>
20 
21 #include "absl/strings/str_format.h"
22 #include "ortools/base/logging.h"
23 
24 namespace operations_research {
25 namespace {
26 // If the x value is in the function's domain, it returns the index of the
27 // segment it belongs to. The segments are closed to the left and open to
28 // the right, hence if x is a common endpoint of two segments, it returns
29 // the index of the right segment. If the x value is not in the function's
30 // domain, it returns the index of the previous segment or kNotFound if x
31 // is before the first segment's start.
32 int FindSegmentIndex(const std::vector<PiecewiseSegment>& segments, int64 x) {
33  if (segments.empty() || segments.front().start_x() > x) {
35  }
36 
37  // Returns an iterator pointing to the first segment whose the x coordinate
38  // of its start point which compares greater than the x value.
39  std::vector<PiecewiseSegment>::const_iterator position = std::upper_bound(
40  segments.begin(), segments.end(), x, PiecewiseSegment::FindComparator);
41  if (position == segments.end()) {
42  return segments.size() - 1;
43  }
44  position -= position->start_x() > x ? 1 : 0;
45 
46  return position - segments.begin();
47 }
48 
49 inline bool IsAtBounds(int64 value) {
50  return value == kint64min || value == kint64max;
51 }
52 
53 inline bool PointInsideRange(int64 point, int64 range_start, int64 range_end) {
54  return range_start <= point && range_end >= point;
55 }
56 
57 // Checks whether two segments form a convex pair, i.e. they are continuous and
58 // the slope of the right is bigger than the slope of the left.
59 inline bool FormConvexPair(const PiecewiseSegment& left,
60  const PiecewiseSegment& right) {
61  return right.slope() >= left.slope() && right.start_x() == left.end_x() &&
62  right.start_y() == left.end_y();
63 }
64 
65 uint64 UnsignedCapAdd(uint64 left, uint64 right) {
66  return left > kuint64max - right ? kuint64max : left + right;
67 }
68 
69 uint64 UnsignedCapProd(uint64 left, uint64 right) {
70  if (right == 0) return 0;
71  if (left > kuint64max / right) return kuint64max;
72  return left * right;
73 }
74 } // namespace
75 
77  int64 other_point_x)
78  : slope_(slope), reference_x_(point_x), reference_y_(point_y) {
79  start_x_ = std::min(point_x, other_point_x);
80  end_x_ = std::max(point_x, other_point_x);
81  intersection_y_ =
82  reference_x_ < 0 ? SafeValuePostReference(0) : SafeValuePreReference(0);
83 }
84 
86  CHECK_GE(x, start_x_);
87  CHECK_LE(x, end_x_);
88 
89  const int64 span_x = CapSub(x, reference_x_);
90 
91  if (span_x == kint64max) {
92  return SafeValuePostReference(x);
93  }
94  if (span_x == kint64min) {
95  return SafeValuePreReference(x);
96  }
97 
98  const int64 span_y = CapProd(slope_, span_x);
99  if (IsAtBounds(span_y)) {
100  if (span_x >= 0) {
101  return SafeValuePostReference(x);
102  } else {
103  return SafeValuePreReference(x);
104  }
105  }
106 
107  const int64 value = CapAdd(reference_y_, span_y);
108  if (IsAtBounds(value)) {
109  if (span_x >= 0) {
110  return SafeValuePostReference(x);
111  } else {
112  return SafeValuePreReference(x);
113  }
114  } else {
115  return value;
116  }
117 }
118 
119 int64 PiecewiseSegment::SafeValuePostReference(int64 x) const {
120  DCHECK_GE(x, reference_x_);
121  const uint64 span_x = static_cast<uint64>(x) - reference_x_;
122  if (span_x == 0) {
123  return reference_y_;
124  }
125  if (slope_ == 0) {
126  // Zero slope segment.
127  return reference_y_;
128  } else if (slope_ > 0) {
129  // Positive slope segment.
130  const uint64 span_y = UnsignedCapProd(span_x, slope_);
131  if (reference_y_ == 0) {
132  return span_y > kint64max ? kint64max : span_y;
133  } else if (reference_y_ > 0) {
134  const uint64 unsigned_sum = UnsignedCapAdd(reference_y_, span_y);
135  return unsigned_sum > kint64max ? kint64max
136  : static_cast<int64>(unsigned_sum);
137  } else {
138  const uint64 opp_reference_y = -static_cast<uint64>(reference_y_);
139  if (span_y >= opp_reference_y) {
140  return span_y - opp_reference_y > kint64max
141  ? kint64max
142  : static_cast<int64>(span_y - opp_reference_y);
143  } else {
144  return opp_reference_y - span_y > static_cast<uint64>(kint64max) + 1
145  ? kint64min
146  : -static_cast<int64>(opp_reference_y - span_y);
147  }
148  }
149  } else {
150  // Negative slope segment.
151  const uint64 span_y = UnsignedCapProd(span_x, -slope_);
152  if (reference_y_ == 0) {
153  return span_y > kint64max ? kint64min : -static_cast<int64>(span_y);
154  } else if (reference_y_ < 0) {
155  const uint64 opp_reference_y = -static_cast<uint64>(reference_y_);
156  const uint64 opp_unsigned_sum = UnsignedCapAdd(opp_reference_y, span_y);
157  return opp_unsigned_sum > kint64max
158  ? kint64min
159  : -static_cast<int64>(opp_unsigned_sum);
160  } else {
161  if (reference_y_ >= span_y) {
162  return reference_y_ - span_y > kint64max
163  ? kint64max
164  : static_cast<int64>(reference_y_ - span_y);
165  } else {
166  return span_y - reference_y_ > static_cast<uint64>(kint64max) + 1
167  ? kint64min
168  : -static_cast<int64>(span_y - reference_y_);
169  }
170  }
171  }
172 }
173 
174 int64 PiecewiseSegment::SafeValuePreReference(int64 x) const {
175  DCHECK_LE(x, reference_x_);
176  const uint64 span_x = static_cast<uint64>(reference_x_) - x;
177  if (slope_ == 0) {
178  // Zero slope segment.
179  return reference_y_;
180  } else if (slope_ > 0) {
181  // Positive slope segment.
182  const uint64 span_y = UnsignedCapProd(span_x, slope_);
183  if (reference_y_ == 0) {
184  return span_y > kint64max ? kint64min : -static_cast<int64>(span_y);
185  } else if (reference_y_ > 0) {
186  if (reference_y_ >= span_y) {
187  return reference_y_ - span_y > kint64max
188  ? kint64max
189  : static_cast<int64>(reference_y_ - span_y);
190  } else {
191  return span_y - reference_y_ > static_cast<uint64>(kint64max) + 1
192  ? kint64min
193  : -static_cast<uint64>(span_y - reference_y_);
194  }
195  } else {
196  const uint64 opp_reference_y = -static_cast<uint64>(reference_y_);
197  const uint64 opp_unsigned_sum = UnsignedCapAdd(opp_reference_y, span_y);
198  return opp_unsigned_sum > kint64max
199  ? kint64min
200  : -static_cast<uint64>(opp_unsigned_sum);
201  }
202  } else {
203  // Negative slope segment.
204  const uint64 span_y = UnsignedCapProd(span_x, -slope_);
205  if (reference_y_ == 0) {
206  return span_y > kint64max ? kint64max : span_y;
207  } else if (reference_y_ < 0) {
208  const uint64 opp_reference_y = -static_cast<uint64>(reference_y_);
209  if (span_y >= opp_reference_y) {
210  return span_y - opp_reference_y > kint64max
211  ? kint64max
212  : static_cast<int64>(span_y - opp_reference_y);
213  } else {
214  return opp_reference_y - span_y > static_cast<uint64>(kint64max) + 1
215  ? kint64min
216  : -static_cast<uint64>(opp_reference_y - span_y);
217  }
218  } else {
219  const uint64 unsigned_sum = UnsignedCapAdd(reference_y_, span_y);
220  return unsigned_sum > kint64max ? kint64max
221  : static_cast<int64>(unsigned_sum);
222  }
223  }
224 }
225 
227  const PiecewiseSegment& segment2) {
228  return segment1.start_x_ < segment2.start_x_;
229 }
230 
232  const PiecewiseSegment& segment) {
233  return point == kint64min || point < segment.start_x();
234 }
235 
237  end_x_ = std::max(end_x_, end_x);
238 }
239 
241  if (IsAtBounds(CapAdd(reference_x_, constant))) {
242  LOG(ERROR) << "Segment Overflow: " << DebugString();
243  return;
244  }
245  start_x_ = CapAdd(start_x_, constant);
246  end_x_ = CapAdd(end_x_, constant);
247  reference_x_ = CapAdd(reference_x_, constant);
248 }
249 
251  if (IsAtBounds(CapAdd(reference_y_, constant))) {
252  LOG(ERROR) << "Segment Overflow: " << DebugString();
253  return;
254  }
255  reference_y_ = CapAdd(reference_y_, constant);
256 }
257 
258 std::string PiecewiseSegment::DebugString() const {
259  std::string result = absl::StrFormat(
260  "PiecewiseSegment(<start: (%d, %d), end: (%d, %d), "
261  "reference: (%d, %d), slope = %d>)",
262  start_x_, Value(start_x_), end_x_, Value(end_x_), reference_x_,
263  reference_y_, slope_);
264  return result;
265 }
266 
268 
269 PiecewiseLinearFunction::PiecewiseLinearFunction(
270  std::vector<PiecewiseSegment> segments)
271  : is_modified_(true),
272  is_convex_(false),
273  is_non_decreasing_(false),
274  is_non_increasing_(false) {
275  // Sort the segments in ascending order of start.
276  std::sort(segments.begin(), segments.end(), PiecewiseSegment::SortComparator);
277  // Check for overlapping segments.
278  for (int i = 0; i < segments.size() - 1; ++i) {
279  if (segments[i].end_x() > segments[i + 1].start_x()) {
280  LOG(FATAL) << "Overlapping segments: " << segments[i].DebugString()
281  << " & " << segments[i + 1].DebugString();
282  }
283  }
284  // Construct the piecewise linear function.
285  for (const auto& segment : segments) {
286  InsertSegment(segment);
287  }
288 }
289 
291  std::vector<int64> points_x, std::vector<int64> points_y,
292  std::vector<int64> slopes, std::vector<int64> other_points_x) {
293  CHECK_EQ(points_x.size(), points_y.size());
294  CHECK_EQ(points_x.size(), other_points_x.size());
295  CHECK_EQ(points_x.size(), slopes.size());
296  CHECK_GT(points_x.size(), 0);
297 
298  std::vector<PiecewiseSegment> segments;
299  for (int i = 0; i < points_x.size(); ++i) {
300  segments.push_back(PiecewiseSegment(points_x[i], points_y[i], slopes[i],
301  other_points_x[i]));
302  }
303 
304  return new PiecewiseLinearFunction(std::move(segments));
305 }
306 
308  std::vector<int64> points_x, std::vector<int64> points_y,
309  std::vector<int64> other_points_x) {
310  CHECK_EQ(points_x.size(), points_y.size());
311  CHECK_EQ(points_x.size(), other_points_x.size());
312  CHECK_GT(points_x.size(), 0);
313 
314  std::vector<PiecewiseSegment> segments;
315  for (int i = 0; i < points_x.size(); ++i) {
316  segments.push_back(
317  PiecewiseSegment(points_x[i], points_y[i], 0, other_points_x[i]));
318  }
319 
320  return new PiecewiseLinearFunction(std::move(segments));
321 }
322 
324  int64 initial_level, std::vector<int64> points_x,
325  std::vector<int64> slopes) {
326  CHECK_EQ(points_x.size(), slopes.size() - 1);
327  CHECK_GT(points_x.size(), 0);
328 
329  int64 level = initial_level;
330  std::vector<PiecewiseSegment> segments;
331  PiecewiseSegment segment =
332  PiecewiseSegment(points_x[0], level, slopes[0], kint64min);
333  segments.push_back(segment);
334  level = segment.Value(points_x[0]);
335  for (int i = 1; i < points_x.size(); ++i) {
336  PiecewiseSegment segment =
337  PiecewiseSegment(points_x[i - 1], level, slopes[i], points_x[i]);
338  segments.push_back(segment);
339  level = segment.Value(points_x[i]);
340  }
341  segments.push_back(
342  PiecewiseSegment(points_x.back(), level, slopes.back(), kint64max));
343 
344  return new PiecewiseLinearFunction(std::move(segments));
345 }
346 
348  int64 point_x, int64 point_y, int64 slope, int64 other_point_x) {
349  // Visual studio 2013: We cannot inline the vector in the
350  // PiecewiseLinearFunction ctor.
351  std::vector<PiecewiseSegment> segments = {
352  PiecewiseSegment(point_x, point_y, slope, other_point_x)};
353  return new PiecewiseLinearFunction(std::move(segments));
354 }
355 
357  int64 point_x, int64 point_y, int64 slope) {
358  std::vector<PiecewiseSegment> segments = {
359  PiecewiseSegment(point_x, point_y, slope, kint64max)};
360  return new PiecewiseLinearFunction(std::move(segments));
361 }
362 
364  int64 point_x, int64 point_y, int64 slope) {
365  std::vector<PiecewiseSegment> segments = {
366  PiecewiseSegment(point_x, point_y, slope, kint64min)};
367  return new PiecewiseLinearFunction(std::move(segments));
368 }
369 
371  int64 slope, int64 value) {
372  std::vector<PiecewiseSegment> segments = {
373  PiecewiseSegment(0, 0, 0, kint64min),
374  PiecewiseSegment(0, value, slope, kint64max)};
375  CHECK_GE(slope, 0);
376  CHECK_GE(value, 0);
377  return new PiecewiseLinearFunction(std::move(segments));
378 }
379 
381  int64 reference, int64 earliness_slope, int64 tardiness_slope) {
382  std::vector<PiecewiseSegment> segments = {
383  PiecewiseSegment(reference, 0, -earliness_slope, kint64min),
384  PiecewiseSegment(reference, 0, tardiness_slope, kint64max)};
385  CHECK_GE(earliness_slope, 0);
386  CHECK_GE(tardiness_slope, 0);
387  return new PiecewiseLinearFunction(std::move(segments));
388 }
389 
392  int64 early_slack, int64 late_slack, int64 earliness_slope,
393  int64 tardiness_slope) {
394  std::vector<PiecewiseSegment> segments = {
395  PiecewiseSegment(early_slack, 0, -earliness_slope, kint64min),
396  PiecewiseSegment(early_slack, 0, 0, late_slack),
397  PiecewiseSegment(late_slack, 0, tardiness_slope, kint64max)};
398 
399  CHECK_GE(earliness_slope, 0);
400  CHECK_GE(tardiness_slope, 0);
401  return new PiecewiseLinearFunction(std::move(segments));
402 }
403 
405  int index = FindSegmentIndex(segments_, x);
406  if (index == kNotFound) {
407  return false;
408  }
409  if (segments_[index].end_x() < x) {
410  return false;
411  }
412  return true;
413 }
414 
416  const_cast<PiecewiseLinearFunction*>(this)->UpdateStatus();
417  return is_convex_;
418 }
419 
421  const_cast<PiecewiseLinearFunction*>(this)->UpdateStatus();
422  return is_non_decreasing_;
423 }
424 
426  const_cast<PiecewiseLinearFunction*>(this)->UpdateStatus();
427  return is_non_increasing_;
428 }
429 
431  if (!InDomain(x)) {
432  // TODO(user): Allow the user to specify the
433  // undefined value and use kint64max as the default.
434  return kint64max;
435  }
436  const int index = FindSegmentIndex(segments_, x);
437  return segments_[index].Value(x);
438 }
439 
441  int64 range_end) const {
442  if (IsNonDecreasing() && InDomain(range_end)) {
443  return Value(range_end);
444  } else if (IsNonIncreasing() && InDomain(range_start)) {
445  return Value(range_start);
446  }
447  int start_segment = -1;
448  int end_segment = -1;
449  if (!FindSegmentIndicesFromRange(range_start, range_end, &start_segment,
450  &end_segment)) {
451  return kint64max;
452  }
453  CHECK_GE(end_segment, start_segment);
454 
455  int64 range_maximum = kint64min;
456  if (InDomain(range_start)) {
457  range_maximum = std::max(Value(range_start), range_maximum);
458  }
459  if (InDomain(range_end)) {
460  range_maximum = std::max(Value(range_end), range_maximum);
461  }
462 
463  for (int i = std::max(0, start_segment); i <= end_segment; ++i) {
464  if (PointInsideRange(segments_[i].start_x(), range_start, range_end)) {
465  range_maximum = std::max(range_maximum, segments_[i].start_y());
466  }
467  if (PointInsideRange(segments_[i].end_x(), range_start, range_end)) {
468  range_maximum = std::max(range_maximum, segments_[i].end_y());
469  }
470  }
471  return range_maximum;
472 }
473 
475  int64 range_end) const {
476  if (IsNonDecreasing() && InDomain(range_start)) {
477  return Value(range_start);
478  } else if (IsNonIncreasing() && InDomain(range_end)) {
479  return Value(range_end);
480  }
481  int start_segment = -1;
482  int end_segment = -1;
483  if (!FindSegmentIndicesFromRange(range_start, range_end, &start_segment,
484  &end_segment)) {
485  return kint64max;
486  }
487  CHECK_GE(end_segment, start_segment);
488 
489  int64 range_minimum = kint64max;
490  if (InDomain(range_start)) {
491  range_minimum = std::min(Value(range_start), range_minimum);
492  }
493  if (InDomain(range_end)) {
494  range_minimum = std::min(Value(range_end), range_minimum);
495  }
496 
497  for (int i = std::max(0, start_segment); i <= end_segment; ++i) {
498  if (PointInsideRange(segments_[i].start_x(), range_start, range_end)) {
499  range_minimum = std::min(range_minimum, segments_[i].start_y());
500  }
501  if (PointInsideRange(segments_[i].end_x(), range_start, range_end)) {
502  range_minimum = std::min(range_minimum, segments_[i].end_y());
503  }
504  }
505  return range_minimum;
506 }
507 
509  return GetMaximum(segments_.front().start_x(), segments_.back().end_x());
510 }
511 
513  return GetMinimum(segments_.front().start_x(), segments_.back().end_x());
514 }
515 
516 std::pair<int64, int64>
518  int64 range_end,
519  int64 value) const {
520  return GetSmallestRangeInValueRange(range_start, range_end, value, kint64max);
521 }
522 
524  int64 range_start, int64 range_end, int64 value) const {
525  return GetSmallestRangeInValueRange(range_start, range_end, kint64min, value);
526 }
527 
528 namespace {
529 std::pair<int64, int64> ComputeXFromY(int64 start_x, int64 start_y, int64 slope,
530  int64 y) {
531  DCHECK_NE(slope, 0);
532  const int64 delta_y = CapSub(y, start_y);
533  const int64 delta_x = delta_y / slope;
534  if ((delta_y >= 0 && slope >= 0) || (delta_y <= 0 && slope <= 0)) {
535  const int64 delta_x_down = delta_x;
536  const int64 delta_x_up = delta_y % slope == 0 ? delta_x : delta_x + 1;
537  return {delta_x_down + start_x, delta_x_up + start_x};
538  } else {
539  const int64 delta_x_down = delta_y % slope == 0 ? delta_x : delta_x - 1;
540  const int64 delta_x_up = -(-delta_y / slope);
541  return {delta_x_down + start_x, delta_x_up + start_x};
542  }
543 }
544 
545 std::pair<int64, int64> GetRangeInValueRange(int64 start_x, int64 end_x,
546  int64 start_y, int64 end_y,
547  int64 slope, int64 value_min,
548  int64 value_max) {
549  if ((start_y > value_max && end_y > value_max) ||
550  (start_y < value_min && end_y < value_min)) {
551  return {kint64max, kint64min};
552  }
553  std::pair<int64, int64> x_range_max = {kint64max, kint64min};
554  if (start_y <= value_max && end_y <= value_max) {
555  x_range_max = {start_x, end_x};
556  } else if (start_y <= value_max || end_y <= value_max) {
557  const auto x = start_x == kint64min
558  ? ComputeXFromY(end_x, end_y, slope, value_max)
559  : ComputeXFromY(start_x, start_y, slope, value_max);
560  if (end_y <= value_max) {
561  x_range_max = {x.second, end_x};
562  } else {
563  x_range_max = {start_x, x.first};
564  }
565  }
566  std::pair<int64, int64> x_range_min = {kint64max, kint64min};
567  if (start_y >= value_min && end_y >= value_min) {
568  x_range_min = {start_x, end_x};
569  } else if (start_y >= value_min || end_y >= value_min) {
570  const auto x = start_x == kint64min
571  ? ComputeXFromY(end_x, end_y, slope, value_min)
572  : ComputeXFromY(start_x, start_y, slope, value_min);
573  if (end_y >= value_min) {
574  x_range_min = {x.second, end_x};
575  } else {
576  x_range_min = {start_x, x.first};
577  }
578  }
579  if (x_range_min.first > x_range_max.second ||
580  x_range_max.first > x_range_min.second) {
581  return {kint64max, kint64min};
582  }
583  return {std::max(x_range_min.first, x_range_max.first),
584  std::min(x_range_min.second, x_range_max.second)};
585 }
586 } // namespace
587 
589  int64 range_start, int64 range_end, int64 value_min,
590  int64 value_max) const {
591  int64 reduced_range_start = kint64max;
592  int64 reduced_range_end = kint64min;
593  int start_segment = -1;
594  int end_segment = -1;
595  if (!FindSegmentIndicesFromRange(range_start, range_end, &start_segment,
596  &end_segment)) {
597  return {reduced_range_start, reduced_range_end};
598  }
599  for (int i = std::max(0, start_segment); i <= end_segment; ++i) {
600  const auto& segment = segments_[i];
601  const int64 start_x = std::max(range_start, segment.start_x());
602  const int64 end_x = std::min(range_end, segment.end_x());
603  const int64 start_y = segment.Value(start_x);
604  const int64 end_y = segment.Value(end_x);
605  const std::pair<int64, int64> range = GetRangeInValueRange(
606  start_x, end_x, start_y, end_y, segment.slope(), value_min, value_max);
607  reduced_range_start = std::min(reduced_range_start, range.first);
608  reduced_range_end = std::max(reduced_range_end, range.second);
609  }
610  return {reduced_range_start, reduced_range_end};
611 }
612 
614  is_modified_ = true;
615  for (int i = 0; i < segments_.size(); ++i) {
616  segments_[i].AddConstantToX(constant);
617  }
618 }
619 
621  is_modified_ = true;
622  for (int i = 0; i < segments_.size(); ++i) {
623  segments_[i].AddConstantToY(constant);
624  }
625 }
626 
628  Operation(other, [](int64 a, int64 b) { return CapAdd(a, b); });
629 }
630 
632  Operation(other, [](int64 a, int64 b) { return CapSub(a, b); });
633 }
634 
635 std::vector<PiecewiseLinearFunction*>
637  CHECK_GE(segments_.size(), 1);
638  if (IsConvex()) {
639  return {new PiecewiseLinearFunction(segments_)};
640  }
641 
642  std::vector<PiecewiseLinearFunction*> convex_functions;
643  std::vector<PiecewiseSegment> convex_segments;
644 
645  for (const PiecewiseSegment& segment : segments_) {
646  if (convex_segments.empty()) {
647  convex_segments.push_back(segment);
648  continue;
649  }
650 
651  const PiecewiseSegment& last = convex_segments.back();
652  if (FormConvexPair(last, segment)) {
653  // The segment belongs to the convex sub-function formulated up to now.
654  convex_segments.push_back(segment);
655  } else {
656  convex_functions.push_back(new PiecewiseLinearFunction(convex_segments));
657  convex_segments.clear();
658  convex_segments.push_back(segment);
659  }
660  }
661 
662  if (!convex_segments.empty()) {
663  convex_functions.push_back(
664  new PiecewiseLinearFunction(std::move(convex_segments)));
665  }
666  return convex_functions;
667 }
668 
670  std::string result = "PiecewiseLinearFunction(";
671  for (int i = 0; i < segments_.size(); ++i) {
672  result.append(segments_[i].DebugString());
673  result.append(" ");
674  }
675  return result;
676 }
677 
678 void PiecewiseLinearFunction::InsertSegment(const PiecewiseSegment& segment) {
679  is_modified_ = true;
680  // No intersection.
681  if (segments_.empty() || segments_.back().end_x() < segment.start_x()) {
682  segments_.push_back(segment);
683  return;
684  }
685 
686  // Common endpoint.
687  if (segments_.back().end_x() == segment.start_x()) {
688  if (segments_.back().end_y() == segment.start_y() &&
689  segments_.back().slope() == segment.slope()) {
690  segments_.back().ExpandEnd(segment.end_x());
691  return;
692  }
693  segments_.push_back(segment);
694  }
695 }
696 
697 void PiecewiseLinearFunction::Operation(
698  const PiecewiseLinearFunction& other,
699  const std::function<int64(int64, int64)>& operation) {
700  is_modified_ = true;
701  std::vector<PiecewiseSegment> own_segments;
702  const std::vector<PiecewiseSegment>& other_segments = other.segments();
703  own_segments.swap(segments_);
704 
705  std::set<int64> start_x_points;
706  for (int i = 0; i < own_segments.size(); ++i) {
707  start_x_points.insert(own_segments[i].start_x());
708  }
709  for (int i = 0; i < other_segments.size(); ++i) {
710  start_x_points.insert(other_segments[i].start_x());
711  }
712 
713  for (int64 start_x : start_x_points) {
714  const int own_index = FindSegmentIndex(own_segments, start_x);
715  const int other_index = FindSegmentIndex(other_segments, start_x);
716  if (own_index >= 0 && other_index >= 0) {
717  const PiecewiseSegment& own_segment = own_segments[own_index];
718  const PiecewiseSegment& other_segment = other_segments[other_index];
719 
720  const int64 end_x = std::min(own_segment.end_x(), other_segment.end_x());
721  const int64 start_y =
722  operation(own_segment.Value(start_x), other_segment.Value(start_x));
723  const int64 end_y =
724  operation(own_segment.Value(end_x), other_segment.Value(end_x));
725  const int64 slope = operation(own_segment.slope(), other_segment.slope());
726 
727  int64 point_x, point_y, other_point_x;
728  if (IsAtBounds(start_y)) {
729  point_x = end_x;
730  point_y = end_y;
731  other_point_x = start_x;
732  } else {
733  point_x = start_x;
734  point_y = start_y;
735  other_point_x = end_x;
736  }
737  InsertSegment(PiecewiseSegment(point_x, point_y, slope, other_point_x));
738  }
739  }
740 }
741 
742 bool PiecewiseLinearFunction::FindSegmentIndicesFromRange(
743  int64 range_start, int64 range_end, int* start_segment,
744  int* end_segment) const {
745  *start_segment = FindSegmentIndex(segments_, range_start);
746  *end_segment = FindSegmentIndex(segments_, range_end);
747  if (*start_segment == *end_segment) {
748  if (*start_segment < 0) {
749  // Given range before function's domain start.
750  return false;
751  }
752  if (segments_[*start_segment].end_x() < range_start) {
753  // Given range in a hole of the function's domain.
754  return false;
755  }
756  }
757  return true;
758 }
759 
760 bool PiecewiseLinearFunction::IsConvexInternal() const {
761  for (int i = 1; i < segments_.size(); ++i) {
762  if (!FormConvexPair(segments_[i - 1], segments_[i])) {
763  return false;
764  }
765  }
766  return true;
767 }
768 
769 bool PiecewiseLinearFunction::IsNonDecreasingInternal() const {
771  for (const auto& segment : segments_) {
772  const int64 start_y = segment.start_y();
773  const int64 end_y = segment.end_y();
774  if (end_y < start_y || start_y < value) return false;
775  value = end_y;
776  }
777  return true;
778 }
779 
780 bool PiecewiseLinearFunction::IsNonIncreasingInternal() const {
782  for (const auto& segment : segments_) {
783  const int64 start_y = segment.start_y();
784  const int64 end_y = segment.end_y();
785  if (end_y > start_y || start_y > value) return false;
786  value = end_y;
787  }
788  return true;
789 }
790 
791 } // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define LOG(severity)
Definition: base/logging.h:420
#define CHECK_LE(val1, val2)
Definition: base/logging.h:699
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
static const int64 kint64max
int64_t int64
static const uint64 kuint64max
uint64_t uint64
static const int64 kint64min
const int ERROR
Definition: log_severity.h:32
const int FATAL
Definition: log_severity.h:32
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 CapSub(int64 x, int64 y)
int64 CapAdd(int64 x, int64 y)
int64 CapProd(int64 x, int64 y)
int index
Definition: pack.cc:508