Google OR-Tools: ortools/util/piecewise_linear

Google OR-Tools: ortools/util/piecewise_linear_function.h Source File

20#ifndef ORTOOLS_UTIL_PIECEWISE_LINEAR_FUNCTION_H_

21#define ORTOOLS_UTIL_PIECEWISE_LINEAR_FUNCTION_H_

23#include <cstdint>

24#include <functional>

25#include <iterator>

26#include <string>

27#include <utility>

28#include <vector>

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"

40 public:

42 int64_t other_point_x);

45 int64_t Value(int64_t x) const;

47 int64_t start_x() const { return start_x_; }

49 int64_t end_x() const { return end_x_; }

53 int64_t end_y() const { return Value(end_x_); }

55 int64_t slope() const { return slope_; }

76 private:

80 int64_t SafeValuePostReference(int64_t x) const;

84 int64_t SafeValuePreReference(int64_t x) const;

87 int64_t start_x_;

89 int64_t end_x_;

91 int64_t slope_;

93 int64_t reference_x_;

95 int64_t reference_y_;

97 int64_t intersection_y_;

98};

100

101

102class PiecewiseLinearFunction {

103 public:

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

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

126

127

129 std::vector<int64_t> points_x, std::vector<int64_t> points_y,

130 std::vector<int64_t> other_points_x);

131

132

133

134

135

136

138 int64_t initial_level, std::vector<int64_t> points_x,

139 std::vector<int64_t> slopes);

140

141

143 int64_t point_x, int64_t point_y, int64_t slope, int64_t other_point_x);

144

145

146

148 int64_t point_y,

149 int64_t slope);

150

151

152

154 int64_t point_y,

155 int64_t slope);

156

157

158

159

160

162 int64_t value);

163

164

165

166

167

168

170 int64_t reference, int64_t earliness_slope, int64_t tardiness_slope);

171

172

173

174

175

176

177

179 int64_t early_slack, int64_t late_slack, int64_t earliness_slope,

180 int64_t tardiness_slope);

181

182

183 bool InDomain(int64_t x) const;

184

185

187

189

191

192 int64_t Value(int64_t x) const;

193

195

197

198

199

200 int64_t GetMaximum(int64_t range_start, int64_t range_end) const;

201

202

203

204 int64_t GetMinimum(int64_t range_start, int64_t range_end) const;

205

206

208 int64_t range_start, int64_t range_end, int64_t value) const;

209

210

212 int64_t range_start, int64_t range_end, int64_t value) const;

213

214

216 int64_t range_start, int64_t range_end, int64_t value_min,

217 int64_t value_max) const;

218

219

220

221

223

224

225

227

228

229

230 void Add(const PiecewiseLinearFunction& other);

231

232

233

234 void Subtract(const PiecewiseLinearFunction& other);

235

236

238

239 const std::vector<PiecewiseSegment>& segments() const { return segments_; }

240

242

243 private:

244

245

247

249

250

252 const std::function<int64_t(int64_t, int64_t)>& operation);

253

254

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

270

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

279

280

281

282

283

284

285

286

288 public:

290

293 absl::InlinedVector<int64_t, 8> y_anchors);

296 *this = std::move(other);

297 }

298

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

316

318

319

320

321

323

324 private:

325

326

327

328

329 int GetSegmentIndex(int64_t x) const {

330 if (x_anchors_.empty() || x < x_anchors_[0] || x > x_anchors_.back()) {

332 }

333 if (x == x_anchors_.back()) return x_anchors_.size() - 2;

334

335

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

345

346 int64_t GetValueOnSegment(int64_t x, int segment_index) const;

347

348

349 absl::InlinedVector<int64_t, 8> x_anchors_;

350

351

352

353

354

355 absl::InlinedVector<int64_t, 8> y_anchors_;

356};

357

358}

359#endif

int64_t ComputeConvexValue(int64_t x) const

FloatSlopePiecewiseLinearFunction(FloatSlopePiecewiseLinearFunction &&other) noexcept

Definition piecewise_linear_function.h:294

FloatSlopePiecewiseLinearFunction()=default

int64_t ComputeInBoundsValue(int64_t x) const

std::string DebugString(absl::string_view line_prefix={}) const

const absl::InlinedVector< int64_t, 8 > & x_anchors() const

Definition piecewise_linear_function.h:308

const absl::InlinedVector< int64_t, 8 > & y_anchors() const

Definition piecewise_linear_function.h:311

static const int kNoValue

Definition piecewise_linear_function.h:289

FloatSlopePiecewiseLinearFunction & operator=(FloatSlopePiecewiseLinearFunction &&other) noexcept

Definition piecewise_linear_function.h:299

int64_t GetMaximum() const

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

std::pair< int64_t, int64_t > GetSmallestRangeLessThanValue(int64_t range_start, int64_t range_end, int64_t value) const

static const int kNotFound

Definition piecewise_linear_function.h:104

static PiecewiseLinearFunction * CreateFixedChargeFunction(int64_t slope, int64_t value)

std::string DebugString() const

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

void AddConstantToY(int64_t constant)

const std::vector< PiecewiseSegment > & segments() const

Definition piecewise_linear_function.h:239

static PiecewiseLinearFunction * CreateOneSegmentFunction(int64_t point_x, int64_t point_y, int64_t slope, int64_t other_point_x)

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

static PiecewiseLinearFunction * CreateEarlyTardyFunction(int64_t reference, int64_t earliness_slope, int64_t tardiness_slope)

void AddConstantToX(int64_t constant)

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

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

void Subtract(const PiecewiseLinearFunction &other)

int64_t end_x() const

Definition piecewise_linear_function.h:49

int64_t start_y() const

Definition piecewise_linear_function.h:51

static bool FindComparator(int64_t point, const PiecewiseSegment &segment)

static bool SortComparator(const PiecewiseSegment &segment1, const PiecewiseSegment &segment2)

std::string DebugString() const

void ExpandEnd(int64_t end_x)