Google OR-Tools: ortools/constraint_solver/routing_lp

Google OR-Tools: ortools/constraint_solver/routing_lp_scheduling.h Source File

14#ifndef ORTOOLS_CONSTRAINT_SOLVER_ROUTING_LP_SCHEDULING_H_

15#define ORTOOLS_CONSTRAINT_SOLVER_ROUTING_LP_SCHEDULING_H_

17#include <algorithm>

18#include <cstdint>

19#include <deque>

20#include <functional>

21#include <limits>

22#include <memory>

23#include <ostream>

24#include <string>

25#include <utility>

26#include <vector>

28#include "absl/container/flat_hash_map.h"

29#include "absl/container/flat_hash_set.h"

30#include "absl/log/check.h"

31#include "absl/strings/str_format.h"

32#include "absl/strings/string_view.h"

33#include "absl/time/time.h"

34#include "absl/types/span.h"

59 public:

69 const std::function<int64_t(int64_t)>& next_accessor,

70 int64_t cumul_offset,

71 const std::vector<RoutingModel::RouteDimensionTravelInfo>*

72 dimension_travel_info_per_route = nullptr);

75 return propagated_bounds_[PositiveNode(index)];

76 }

79 const int64_t negated_upper_bound = propagated_bounds_[NegativeNode(index)];

80 return negated_upper_bound == std::numeric_limits<int64_t>::min()

81 ? std::numeric_limits<int64_t>::max()

82 : -negated_upper_bound;

83 }

87 private:

91 struct ArcInfo {

92 int head;

93 int64_t offset;

94 };

95 static const int kNoParent;

96 static const int kParentToBePropagated;

100 int PositiveNode(int index) const { return 2 * index; }

101 int NegativeNode(int index) const { return 2 * index + 1; }

102

103 void AddNodeToQueue(int node) {

104 if (!node_in_queue_[node]) {

105 bf_queue_.push_back(node);

106 node_in_queue_[node] = true;

107 }

108 }

109

110

111

112

113 void AddArcs(int first_index, int second_index, int64_t offset);

114

115 bool InitializeArcsAndBounds(

116 const std::function<int64_t(int64_t)>& next_accessor,

117 int64_t cumul_offset,

118 const std::vector<RoutingModel::RouteDimensionTravelInfo>*

119 dimension_travel_info_per_route = nullptr);

120

121 bool UpdateCurrentLowerBoundOfNode(int node, int64_t new_lb, int64_t offset);

122

123 bool DisassembleSubtree(int source, int target);

124

125 bool CleanupAndReturnFalse() {

126

127 for (int node_to_cleanup : bf_queue_) {

128 node_in_queue_[node_to_cleanup] = false;

129 }

130 bf_queue_.clear();

131 return false;

132 }

133

134 const RoutingDimension& dimension_;

135 const int64_t num_nodes_;

136

137

138

139

140 std::vector<std::vector<ArcInfo>> outgoing_arcs_;

141

142 std::deque<int> bf_queue_;

143 std::vector<bool> node_in_queue_;

144 std::vector<int> tree_parent_node_of_;

145

146

147

148 std::vector<int64_t> propagated_bounds_;

149

150

151 std::vector<int> tmp_dfs_stack_;

152

153

154 std::vector<std::pair<int64_t, int64_t>>

155 visited_pickup_delivery_indices_for_pair_;

156};

157

159

161

162

164

166

168};

169

171 public:

173

181 int64_t upper_bound) = 0;

183 const std::vector<int64_t>& starts,

184 const std::vector<int64_t>& ends) = 0;

192 virtual void SetCoefficient(int ct, int index, double coefficient) = 0;

202

203

204 virtual void SetParameters(const std::string& parameters) = 0;

205

206

207

208

209

210 virtual void AddRoute(absl::Span<const int64_t> nodes,

211 absl::Span<const int> schedule_variables) = 0;

212

213

215

216

218

219

220 int AddVariable(int64_t lower_bound, int64_t upper_bound) {

221 CHECK_LE(lower_bound, upper_bound);

224 return variable;

225 }

226

227

228

230 int64_t lower_bound, int64_t upper_bound,

231 absl::Span<const std::pair<int, double>> variable_coeffs) {

232 CHECK_LE(lower_bound, upper_bound);

234 for (const auto& variable_coeff : variable_coeffs) {

235 SetCoefficient(ct, variable_coeff.first, variable_coeff.second);

236 }

237 return ct;

238 }

239

240

241

243 int64_t lower_bound, int64_t upper_bound,

244 absl::Span<const std::pair<int, double>> weighted_variables) {

246 if (std::numeric_limits<int64_t>::min() < lower_bound) {

247 const int under_lower_bound = AddVariable(0, 1);

248#ifndef NDEBUG

250#endif

251 SetCoefficient(reification_ct, under_lower_bound, 1);

252 const int under_lower_bound_ct =

254 lower_bound - 1, weighted_variables);

256 }

257 if (upper_bound < std::numeric_limits<int64_t>::max()) {

258 const int above_upper_bound = AddVariable(0, 1);

259#ifndef NDEBUG

261#endif

262 SetCoefficient(reification_ct, above_upper_bound, 1);

264 upper_bound + 1, std::numeric_limits<int64_t>::max(),

265 weighted_variables);

267 }

268 const int within_bounds = AddVariable(0, 1);

269#ifndef NDEBUG

271#endif

273 const int within_bounds_ct =

276 return within_bounds;

277 }

278

279 protected:

281};

282

284 public:

288 is_relaxation_(is_relaxation) {

289 lp_solver_.SetParameters(parameters);

290 linear_program_.SetMaximizationProblem(false);

291 }

293 linear_program_.Clear();

294 linear_program_.SetMaximizationProblem(false);

295 allowed_intervals_.clear();

296 }

298 return linear_program_.CreateNewVariable().value();

299 }

301 linear_program_.SetVariableName(glop::ColIndex(index), name);

302 }

304 int64_t upper_bound) override {

305 DCHECK_GE(lower_bound, 0);

306

307

308

309 const int64_t kMaxValue = 1e10;

310 const double lp_min = lower_bound;

311 const double lp_max =

312 (upper_bound > kMaxValue) ? glop::kInfinity : upper_bound;

313 if (lp_min <= lp_max) {

314 linear_program_.SetVariableBounds(glop::ColIndex(index), lp_min, lp_max);

315 return true;

316 }

317

318

319 return false;

320 }

322 const std::vector<int64_t>& ends) override {

323

324

325

326

327 allowed_intervals_[index] =

328 std::make_unique<SortedDisjointIntervalList>(starts, ends);

329 }

331 return linear_program_.variable_lower_bounds()[glop::ColIndex(index)];

332 }

334 const double upper_bound =

335 linear_program_.variable_upper_bounds()[glop::ColIndex(index)];

336 DCHECK_GE(upper_bound, 0);

337 return upper_bound == glop::kInfinity ? std::numeric_limits<int64_t>::max()

338 : static_cast<int64_t>(upper_bound);

339 }

341 linear_program_.SetObjectiveCoefficient(glop::ColIndex(index), coefficient);

342 }

344 return linear_program_.objective_coefficients()[glop::ColIndex(index)];

345 }

347 for (glop::ColIndex i(0); i < linear_program_.num_variables(); ++i) {

348 linear_program_.SetObjectiveCoefficient(i, 0);

349 }

350 }

352 return linear_program_.num_variables().value();

353 }

355 const glop::RowIndex ct = linear_program_.CreateNewConstraint();

356 linear_program_.SetConstraintBounds(

357 ct,

358 (lower_bound == std::numeric_limits<int64_t>::min()) ? -glop::kInfinity

359 : lower_bound,

360 (upper_bound == std::numeric_limits<int64_t>::max()) ? glop::kInfinity

361 : upper_bound);

362 return ct.value();

363 }

364 void SetCoefficient(int ct, int index, double coefficient) override {

365

366

367 if (coefficient == 0.0) return;

368 linear_program_.SetCoefficient(glop::RowIndex(ct), glop::ColIndex(index),

369 coefficient);

370 }

373 double max_coefficient = 0;

374 for (int variable = 0; variable < NumVariables(); variable++) {

376 max_coefficient = std::max(MathUtil::Abs(coefficient), max_coefficient);

377 }

378 DCHECK_GE(max_coefficient, 0);

379 if (max_coefficient == 0) {

380

381 return;

382 }

383 const glop::RowIndex ct = linear_program_.CreateNewConstraint();

384 double normalized_objective_value = 0;

385 for (int variable = 0; variable < NumVariables(); variable++) {

387 if (coefficient != 0) {

388 const double normalized_coeff = coefficient / max_coefficient;

389 SetCoefficient(ct.value(), variable, normalized_coeff);

390 normalized_objective_value +=

391 normalized_coeff * GetValueDouble(glop::ColIndex(variable));

392 }

393 }

394 normalized_objective_value = std::max(

395 normalized_objective_value, GetObjectiveValue() / max_coefficient);

396 linear_program_.SetConstraintBounds(ct, -glop::kInfinity,

397 normalized_objective_value);

398 }

400 std::vector<int> ) override {}

402 std::vector<int> ) override {}

404 void AddRoute(absl::Span<const int64_t>, absl::Span<const int>) override{};

406 lp_solver_.GetMutableParameters()->set_max_time_in_seconds(

407 absl::ToDoubleSeconds(duration_limit));

408

409

410

411

412

413

414 linear_program_.NotifyThatColumnsAreClean();

415 VLOG(2) << linear_program_.Dump();

422 }

423 if (is_relaxation_) {

425 }

426 for (const auto& allowed_interval : allowed_intervals_) {

427 const int64_t value = GetVariableValue(allowed_interval.first);

429 allowed_interval.second.get();

431 if (it == interval_list->end() || value < it->start) {

433 }

434 }

435 if (feasible_only && !linear_program_.objective_coefficients().empty()) {

437 }

439 }

444 const double value_double = GetValueDouble(glop::ColIndex(index));

445 return (value_double >= std::numeric_limits<int64_t>::max())

446 ? std::numeric_limits<int64_t>::max()

448 }

450 return linear_program_.SolutionIsInteger(lp_solver_.variable_values(),

451 1e-3);

452 }

453

456 const bool status = params.ParseFromString(parameters);

457 DCHECK(status);

458 lp_solver_.SetParameters(params);

459 }

460

461

462

463 std::string PrintModel() const override { return linear_program_.Dump(); }

464

465 private:

466 double GetValueDouble(glop::ColIndex index) const {

468 }

469

470 const bool is_relaxation_;

471 glop::LinearProgram linear_program_;

472 glop::LPSolver lp_solver_;

473 absl::flat_hash_map<int, std::unique_ptr<SortedDisjointIntervalList>>

474 allowed_intervals_;

475};

476

478 public:

481 parameters_.set_num_workers(1);

482

483

484 parameters_.set_cp_model_presolve(true);

485 parameters_.set_max_presolve_iterations(1);

486 parameters_.set_cp_model_probing_level(0);

487 parameters_.set_use_sat_inprocessing(false);

488 parameters_.set_symmetry_level(0);

489 parameters_.set_catch_sigint_signal(false);

490 parameters_.set_mip_max_bound(1e8);

492 parameters_.set_linearization_level(2);

493 parameters_.set_cut_level(0);

494 parameters_.set_add_lp_constraints_lazily(false);

495 parameters_.set_use_absl_random(false);

496 parameters_.set_alternative_pool_size(0);

497 parameters_.set_transitive_precedences_work_limit(0);

498 }

501 model_.Clear();

502 response_.Clear();

503 objective_coefficients_.clear();

504 schedule_variables_.clear();

505 }

507 const int index = model_.variables_size();

510 variable->add_domain(static_cast<int64_t>(parameters_.mip_max_bound()));

511 return index;

512 }

514 model_.mutable_variables(index)->set_name(name.data());

515 }

517 int64_t upper_bound) override {

518 DCHECK_GE(lower_bound, 0);

519 const int64_t capped_upper_bound =

520 std::min<int64_t>(upper_bound, parameters_.mip_max_bound());

521 if (lower_bound > capped_upper_bound) return false;

523 variable->set_domain(0, lower_bound);

524 variable->set_domain(1, capped_upper_bound);

525 return true;

526 }

528 const std::vector<int64_t>& ends) override {

529 DCHECK_EQ(starts.size(), ends.size());

531 for (int i = 0; i < starts.size(); ++i) {

533#ifndef NDEBUG

535 absl::StrFormat("disjoint(%ld, %ld)", index, i));

536#endif

541 model_.mutable_constraints(window_ct)->add_enforcement_literal(variable);

542 }

543 }

545 return model_.variables(index).domain(0);

546 }

548 const auto& domain = model_.variables(index).domain();

549 return domain[domain.size() - 1];

550 }

552 if (index >= objective_coefficients_.size()) {

553 objective_coefficients_.resize(index + 1, 0);

554 }

555 objective_coefficients_[index] = coefficient;

557 model_.mutable_floating_point_objective();

560 }

562 return (index < objective_coefficients_.size())

563 ? objective_coefficients_[index]

564 : 0;

565 }

567 model_.mutable_floating_point_objective()->Clear();

568 }

569 int NumVariables() const override { return model_.variables_size(); }

572 model_.add_constraints()->mutable_linear();

575 return model_.constraints_size() - 1;

576 }

577 void SetCoefficient(int ct_index, int index, double coefficient) override {

579 model_.mutable_constraints(ct_index)->mutable_linear();

581 const int64_t integer_coefficient = coefficient;

583 }

587 int64_t activity = 0;

588 for (int i = 0; i < objective.vars_size(); ++i) {

589 activity += response_.solution(objective.vars(i)) * objective.coeffs(i);

590 }

591 const int ct =

593 for (int i = 0; i < objective.vars_size(); ++i) {

595 }

596 model_.clear_objective();

597 }

600 model_.add_constraints()->mutable_lin_max();

603 for (const int var : vars) {

607 }

608 }

611 model_.add_constraints()->mutable_int_prod();

614 for (const int var : vars) {

618 }

619 }

621 DCHECK_LT(ct, model_.constraints_size());

622 model_.mutable_constraints(ct)->add_enforcement_literal(condition);

623 }

624 void AddRoute(absl::Span<const int64_t> nodes,

625 absl::Span<const int> schedule_variables) override {

626 DCHECK_EQ(nodes.size(), schedule_variables.size());

627 for (const int64_t node : nodes) {

628 if (node >= schedule_hint_.size()) schedule_hint_.resize(node + 1, 0);

629 }

630 for (int n = 0; n < nodes.size(); ++n) {

631 schedule_variables_.push_back(

632 {.node = nodes[n], .cumul = schedule_variables[n]});

633 }

634 }

636 const double max_time = absl::ToDoubleSeconds(duration_limit);

638 parameters_.set_max_time_in_seconds(max_time);

640 auto record_hint = [this]() {

641 hint_.Clear();

642 for (int i = 0; i < response_.solution_size(); ++i) {

643 hint_.add_vars(i);

644 hint_.add_values(response_.solution(i));

645 }

646 for (const auto& [node, cumul] : schedule_variables_) {

647 schedule_hint_[node] = response_.solution(cumul);

648 }

649 };

650 model_.clear_solution_hint();

651 auto* hint = model_.mutable_solution_hint();

652 if (hint_.vars_size() == model_.variables_size()) {

653 *hint = hint_;

654 } else {

655 for (const auto& [node, cumul] : schedule_variables_) {

656 if (schedule_hint_[node] == 0) continue;

657 hint->add_vars(cumul);

658 hint->add_values(schedule_hint_[node]);

659 }

660 }

665 VLOG(2) << response_;

669 !model_.has_floating_point_objective())) {

670 record_hint();

673

674

676 }

678 }

683 return response_.solution(index);

684 }

686

687

691

692 bool ModelIsEmpty() const override { return model_.ByteSizeLong() == 0; }

693

694

695 std::string PrintModel() const override;

696

697 private:

701 std::vector<double> objective_coefficients_;

703 struct NodeAndCumul {

704 int64_t node;

705 int cumul;

706 };

707

708 std::vector<NodeAndCumul> schedule_variables_;

709

710 std::vector<int64_t> schedule_hint_;

711};

712

713

714

718

719 public:

721 bool use_precedence_propagator);

722

723

724

726 int vehicle, double solve_duration_ratio,

727 const std::function<int64_t(int64_t)>& next_accessor,

728 const RouteDimensionTravelInfo* dimension_travel_info,

729 const Resource* resource, bool optimize_vehicle_costs,

731 std::vector<int64_t>* break_values, int64_t* cost_without_transit,

732 int64_t* transit_cost, bool clear_lp = true);

733

734

735

736

738 int vehicle, double solve_duration_ratio,

739 const std::function<int64_t(int64_t)>& next_accessor,

740 const RouteDimensionTravelInfo* dimension_travel_info,

742 absl::Span<const int64_t> solution_cumul_values,

743 absl::Span<const int64_t> solution_break_values,

744 int64_t* cost_without_transits, int64_t* cost_offset = nullptr,

745 bool reuse_previous_model_if_possible = true, bool clear_lp = false,

746 bool clear_solution_constraints = true,

747 absl::Duration* solve_duration = nullptr);

748

749

750

751

752

754 int vehicle, double solve_duration_ratio,

755 const std::function<int64_t(int64_t)>& next_accessor,

756 const std::function<int64_t(int64_t, int64_t)>& transit_accessor,

757 const RouteDimensionTravelInfo* dimension_travel_info,

758 absl::Span<const Resource> resources,

759 absl::Span<const int> resource_indices, bool optimize_vehicle_costs,

761 std::vector<std::vector<int64_t>>* cumul_values,

762 std::vector<std::vector<int64_t>>* break_values,

763 std::vector<int64_t>* costs_without_transits, int64_t* transit_cost,

764 bool clear_lp = true);

765

766

767

768

769

770

772 const std::function<int64_t(int64_t)>& next_accessor,

773 const std::vector<RouteDimensionTravelInfo>&

774 dimension_travel_info_per_route,

776 std::vector<int64_t>* break_values,

777 std::vector<std::vector<int>>* resource_indices_per_group,

778 int64_t* cost_without_transits, int64_t* transit_cost,

779 bool clear_lp = true, bool optimize_resource_assignment = true);

780

782 const std::function<int64_t(int64_t)>& next_accessor,

783 const std::vector<RouteDimensionTravelInfo>&

784 dimension_travel_info_per_route,

786 std::vector<int64_t>* break_values);

787

789 int vehicle, double solve_duration_ratio,

790 const std::function<int64_t(int64_t)>& next_accessor,

791 const RouteDimensionTravelInfo* dimension_travel_info,

793 std::vector<int64_t>* cumul_values, std::vector<int64_t>* break_values);

794

801 int vehicle, double solve_duration_ratio,

802 const std::function<int64_t(int64_t)>& next_accessor,

803 absl::Span<const int64_t> transit_targets,

805 std::vector<int64_t>* optimal_transits,

806 std::vector<int64_t>* optimal_cumuls,

807 std::vector<int64_t>* optimal_breaks);

808

810

811 private:

812

813

815

816

817

818 bool ExtractRouteCumulBounds(absl::Span<const int64_t> route,

819 int64_t cumul_offset);

820

821

822

823

824 bool TightenRouteCumulBounds(absl::Span<const int64_t> route,

825 absl::Span<const int64_t> min_transits,

826 int64_t cumul_offset);

827

828

829

830

831

832 bool SetRouteCumulConstraints(

833 int vehicle, const std::function<int64_t(int64_t)>& next_accessor,

834 const std::function<int64_t(int64_t, int64_t)>& transit_accessor,

835 absl::Span<const int64_t> transit_targets,

836 const RouteDimensionTravelInfo* dimension_travel_info,

837 int64_t cumul_offset, bool optimize_costs,

839 int64_t* route_cost_offset);

840

841

842

843

844

845 void SetRouteCumulCosts(int vehicle, int64_t cumul_offset,

846 int64_t total_fixed_transit,

848 int64_t* route_transit_cost,

849 int64_t* route_cost_offset);

850

851

852

853

854 bool SetRouteTravelConstraints(

855 const RouteDimensionTravelInfo* dimension_travel_info,

856 absl::Span<const int> lp_slacks, absl::Span<const int64_t> fixed_transits,

857 absl::Span<const int64_t> transit_targets,

859

860

861

862

863

864

865

866

867 bool SetGlobalConstraints(

868 const std::function<int64_t(int64_t)>& next_accessor,

869 int64_t cumul_offset, bool optimize_costs,

871

872 bool SetGlobalConstraintsForResourceAssignment(

873 const std::function<int64_t(int64_t)>& next_accessor,

875

876 void SetValuesFromLP(absl::Span<const int> lp_variables, int64_t offset,

877 int64_t default_value,

879 std::vector<int64_t>* lp_values) const;

880

881 void SetResourceIndices(

883 std::vector<std::vector<int>>* resource_indices_per_group) const;

884

885

886

887

888

889

890

892 std::vector<int> vehicles, double solve_duration_ratio,

895

896 std::unique_ptr<CumulBoundsPropagator> propagator_;

897 std::vector<int64_t> current_route_min_cumuls_;

898 std::vector<int64_t> current_route_max_cumuls_;

899

900 std::vector<int64_t> current_route_nodes_;

902

903 std::vector<int> current_route_cumul_variables_;

904 std::vector<int> index_to_cumul_variable_;

905

906 std::vector<int> current_route_variable_transit_variables_;

907

908

909

910

911 std::vector<int> current_route_break_variables_;

912

913

914

915 std::vector<int> all_break_variables_;

916

917

918

919 std::vector<int> vehicle_to_all_break_variables_offset_;

920

921

922

923

924 std::vector<std::vector<int>>

925 resource_class_to_vehicle_assignment_variables_per_group_;

926

927

928 std::vector<std::vector<absl::flat_hash_set<int>>>

929 resource_class_ignored_resources_per_group_;

930

931 int max_end_cumul_;

932 int min_start_cumul_;

933 std::vector<std::pair<int64_t, int64_t>>

934 visited_pickup_delivery_indices_for_pair_;

935};

936

937

938

939

940

941

943 public:

948

949

950

951

952

954 int vehicle, double solve_duration_ratio,

955 const std::function<int64_t(int64_t)>& next_accessor,

956 int64_t* optimal_cost);

957

958

959

961 int vehicle, double solve_duration_ratio,

962 const std::function<int64_t(int64_t)>& next_accessor,

964 int64_t* optimal_cost_without_transits);

965

966 std::vector<DimensionSchedulingStatus>

968 int vehicle, double solve_duration_ratio,

969 const std::function<int64_t(int64_t)>& next_accessor,

970 const std::function<int64_t(int64_t, int64_t)>& transit_accessor,

971 absl::Span<const RoutingModel::ResourceGroup::Resource> resources,

972 absl::Span<const int> resource_indices, bool optimize_vehicle_costs,

973 std::vector<int64_t>* optimal_costs_without_transits,

974 std::vector<std::vector<int64_t>>* optimal_cumuls,

975 std::vector<std::vector<int64_t>>* optimal_breaks);

976

977

978

979

980

981

983 int vehicle, double solve_duration_ratio,

984 const std::function<int64_t(int64_t)>& next_accessor,

987 std::vector<int64_t>* optimal_cumuls,

988 std::vector<int64_t>* optimal_breaks);

989

990

991

993 int vehicle, double solve_duration_ratio,

994 const std::function<int64_t(int64_t)>& next_accessor,

996 std::vector<int64_t>* optimal_cumuls,

997 std::vector<int64_t>* optimal_breaks,

998 int64_t* optimal_cost_without_transits);

999

1000

1001

1003 int vehicle, double solve_duration_ratio,

1004 const std::function<int64_t(int64_t)>& next_accessor,

1006 absl::Span<const int64_t> solution_cumul_values,

1007 absl::Span<const int64_t> solution_break_values, int64_t* solution_cost,

1008 int64_t* cost_offset = nullptr,

1009 bool reuse_previous_model_if_possible = false, bool clear_lp = true,

1010 absl::Duration* solve_duration = nullptr);

1011

1012

1013

1014

1015

1016

1018 int vehicle, double solve_duration_ratio,

1019 const std::function<int64_t(int64_t)>& next_accessor,

1022 std::vector<int64_t>* packed_cumuls, std::vector<int64_t>* packed_breaks);

1023

1024

1025

1026

1028 int vehicle, double solve_duration_ratio,

1029 const std::function<int64_t(int64_t)>& next_accessor,

1030 absl::Span<const int64_t> transit_targets,

1032 std::vector<int64_t>* optimal_transits,

1033 std::vector<int64_t>* optimal_cumuls,

1034 std::vector<int64_t>* optimal_breaks);

1035

1037 return optimizer_core_.dimension();

1038 }

1039

1040 private:

1041 std::vector<std::unique_ptr<RoutingLinearSolverWrapper>> solver_;

1043};

1044

1046 public:

1051

1052

1053

1054

1055

1057 const std::function<int64_t(int64_t)>& next_accessor,

1058 int64_t* optimal_cost_without_transits);

1059

1060

1061

1062

1063

1065 const std::function<int64_t(int64_t)>& next_accessor,

1066 const std::vector<RoutingModel::RouteDimensionTravelInfo>&

1067 dimension_travel_info_per_route,

1068 std::vector<int64_t>* optimal_cumuls,

1069 std::vector<int64_t>* optimal_breaks,

1070 std::vector<std::vector<int>>* optimal_resource_indices_per_group);

1071

1072

1073

1074

1075

1076

1077

1079 const std::function<int64_t(int64_t)>& next_accessor,

1080 const std::vector<RoutingModel::RouteDimensionTravelInfo>&

1081 dimension_travel_info_per_route,

1082 std::vector<int64_t>* packed_cumuls, std::vector<int64_t>* packed_breaks);

1083

1085 return optimizer_core_.dimension();

1086 }

1087

1088 private:

1089 std::unique_ptr<RoutingLinearSolverWrapper> solver_;

1091};

1092

1093

1094

1095

1096

1097

1098

1099

1100

1101

1102

1103

1104

1105

1106

1107

1108

1109

1110

1112 absl::Span<const int> vehicles,

1114 std::vector<int>>&

1115 resource_indices_per_class,

1117 absl::flat_hash_set<int>>&

1118 ignored_resources_per_class,

1119 std::function<const std::vector<int64_t>*(int)>

1120 vehicle_to_resource_class_assignment_costs,

1121 std::vector<int>* resource_indices);

1122

1123

1124

1125

1126

1127

1128

1129

1130

1131

1133 int v, double solve_duration_ratio,

1134 const RoutingModel::ResourceGroup& resource_group,

1136 absl::flat_hash_set<int>>&

1137 ignored_resources_per_class,

1138 const std::function<int64_t(int64_t)>& next_accessor,

1139 const std::function<int64_t(int64_t, int64_t)>& transit_accessor,

1140 bool optimize_vehicle_costs, LocalDimensionCumulOptimizer* lp_optimizer,

1141 LocalDimensionCumulOptimizer* mp_optimizer,

1142 std::vector<int64_t>* assignment_costs,

1143 std::vector<std::vector<int64_t>>* cumul_values,

1144 std::vector<std::vector<int64_t>>* break_values);

1145

1146

1147

1157

1158

1159

1160

1161

1162

1163

1165 const FloatSlopePiecewiseLinearFunction& pwl_function, int index_start = 0,

1166 int index_end = -1);

1167

1168

1169

1170

1171

1172

1173

1175 absl::Span<const SlopeAndYIntercept> slope_and_y_intercept);

1176

1177}

1178

1179#endif

CumulBoundsPropagator(const RoutingDimension *dimension)

bool PropagateCumulBounds(const std::function< int64_t(int64_t)> &next_accessor, int64_t cumul_offset, const std::vector< RoutingModel::RouteDimensionTravelInfo > *dimension_travel_info_per_route=nullptr)

int64_t CumulMax(int index) const

Definition routing_lp_scheduling.h:78

int64_t CumulMin(int index) const

Definition routing_lp_scheduling.h:74

const RoutingDimension & dimension() const

Definition routing_lp_scheduling.h:85

DimensionSchedulingStatus Optimize(const std::function< int64_t(int64_t)> &next_accessor, const std::vector< RouteDimensionTravelInfo > &dimension_travel_info_per_route, RoutingLinearSolverWrapper *solver, std::vector< int64_t > *cumul_values, std::vector< int64_t > *break_values, std::vector< std::vector< int > > *resource_indices_per_group, int64_t *cost_without_transits, int64_t *transit_cost, bool clear_lp=true, bool optimize_resource_assignment=true)

DimensionSchedulingStatus ComputeSingleRouteSolutionCostWithoutFixedTransits(int vehicle, double solve_duration_ratio, const std::function< int64_t(int64_t)> &next_accessor, const RouteDimensionTravelInfo *dimension_travel_info, RoutingLinearSolverWrapper *solver, absl::Span< const int64_t > solution_cumul_values, absl::Span< const int64_t > solution_break_values, int64_t *cost_without_transits, int64_t *cost_offset=nullptr, bool reuse_previous_model_if_possible=true, bool clear_lp=false, bool clear_solution_constraints=true, absl::Duration *solve_duration=nullptr)

const RoutingDimension * dimension() const

Definition routing_lp_scheduling.h:809

DimensionSchedulingStatus OptimizeAndPack(const std::function< int64_t(int64_t)> &next_accessor, const std::vector< RouteDimensionTravelInfo > &dimension_travel_info_per_route, RoutingLinearSolverWrapper *solver, std::vector< int64_t > *cumul_values, std::vector< int64_t > *break_values)

DimensionSchedulingStatus OptimizeSingleRouteWithTransitTargets(int vehicle, double solve_duration_ratio, const std::function< int64_t(int64_t)> &next_accessor, absl::Span< const int64_t > transit_targets, TransitTargetCost transit_target_cost, RoutingLinearSolverWrapper *solver, std::vector< int64_t > *optimal_transits, std::vector< int64_t > *optimal_cumuls, std::vector< int64_t > *optimal_breaks)

DimensionCumulOptimizerCore(const RoutingDimension *dimension, bool use_precedence_propagator)

DimensionSchedulingStatus OptimizeSingleRouteWithResource(int vehicle, double solve_duration_ratio, const std::function< int64_t(int64_t)> &next_accessor, const RouteDimensionTravelInfo *dimension_travel_info, const Resource *resource, bool optimize_vehicle_costs, RoutingLinearSolverWrapper *solver, std::vector< int64_t > *cumul_values, std::vector< int64_t > *break_values, int64_t *cost_without_transit, int64_t *transit_cost, bool clear_lp=true)

DimensionSchedulingStatus OptimizeAndPackSingleRoute(int vehicle, double solve_duration_ratio, const std::function< int64_t(int64_t)> &next_accessor, const RouteDimensionTravelInfo *dimension_travel_info, const Resource *resource, RoutingLinearSolverWrapper *solver, std::vector< int64_t > *cumul_values, std::vector< int64_t > *break_values)

std::vector< DimensionSchedulingStatus > OptimizeSingleRouteWithResources(int vehicle, double solve_duration_ratio, const std::function< int64_t(int64_t)> &next_accessor, const std::function< int64_t(int64_t, int64_t)> &transit_accessor, const RouteDimensionTravelInfo *dimension_travel_info, absl::Span< const Resource > resources, absl::Span< const int > resource_indices, bool optimize_vehicle_costs, RoutingLinearSolverWrapper *solver, std::vector< std::vector< int64_t > > *cumul_values, std::vector< std::vector< int64_t > > *break_values, std::vector< int64_t > *costs_without_transits, int64_t *transit_cost, bool clear_lp=true)

DimensionSchedulingStatus ComputeCumulCostWithoutFixedTransits(const std::function< int64_t(int64_t)> &next_accessor, int64_t *optimal_cost_without_transits)

GlobalDimensionCumulOptimizer(const RoutingDimension *dimension, RoutingSearchParameters::SchedulingSolver solver_type, RoutingSearchStats *search_stats)

const RoutingDimension * dimension() const

Definition routing_lp_scheduling.h:1084

DimensionSchedulingStatus ComputeCumuls(const std::function< int64_t(int64_t)> &next_accessor, const std::vector< RoutingModel::RouteDimensionTravelInfo > &dimension_travel_info_per_route, std::vector< int64_t > *optimal_cumuls, std::vector< int64_t > *optimal_breaks, std::vector< std::vector< int > > *optimal_resource_indices_per_group)

DimensionSchedulingStatus ComputePackedCumuls(const std::function< int64_t(int64_t)> &next_accessor, const std::vector< RoutingModel::RouteDimensionTravelInfo > &dimension_travel_info_per_route, std::vector< int64_t > *packed_cumuls, std::vector< int64_t > *packed_breaks)

const RoutingDimension * dimension() const

Definition routing_lp_scheduling.h:1036

DimensionSchedulingStatus ComputeRouteSolutionCostWithoutFixedTransits(int vehicle, double solve_duration_ratio, const std::function< int64_t(int64_t)> &next_accessor, const RoutingModel::RouteDimensionTravelInfo *dimension_travel_info, absl::Span< const int64_t > solution_cumul_values, absl::Span< const int64_t > solution_break_values, int64_t *solution_cost, int64_t *cost_offset=nullptr, bool reuse_previous_model_if_possible=false, bool clear_lp=true, absl::Duration *solve_duration=nullptr)

DimensionSchedulingStatus ComputePackedRouteCumuls(int vehicle, double solve_duration_ratio, const std::function< int64_t(int64_t)> &next_accessor, const RoutingModel::RouteDimensionTravelInfo *dimension_travel_info, const RoutingModel::ResourceGroup::Resource *resource, std::vector< int64_t > *packed_cumuls, std::vector< int64_t > *packed_breaks)

LocalDimensionCumulOptimizer(const RoutingDimension *dimension, RoutingSearchParameters::SchedulingSolver solver_type, RoutingSearchStats *search_stats)

DimensionSchedulingStatus ComputeRouteCumuls(int vehicle, double solve_duration_ratio, const std::function< int64_t(int64_t)> &next_accessor, const RoutingModel::RouteDimensionTravelInfo *dimension_travel_info, const RoutingModel::ResourceGroup::Resource *resource, std::vector< int64_t > *optimal_cumuls, std::vector< int64_t > *optimal_breaks)

DimensionSchedulingStatus ComputeRouteCumulCostWithoutFixedTransits(int vehicle, double solve_duration_ratio, const std::function< int64_t(int64_t)> &next_accessor, const RoutingModel::ResourceGroup::Resource *resource, int64_t *optimal_cost_without_transits)

DimensionSchedulingStatus ComputeRouteCumulsAndCostWithoutFixedTransits(int vehicle, double solve_duration_ratio, const std::function< int64_t(int64_t)> &next_accessor, const RoutingModel::RouteDimensionTravelInfo *dimension_travel_info, std::vector< int64_t > *optimal_cumuls, std::vector< int64_t > *optimal_breaks, int64_t *optimal_cost_without_transits)

Merge with the packing method DimensionSchedulingStatus ComputeRouteCumulsWithTransitTargets(int vehicle, double solve_duration_ratio, const std::function< int64_t(int64_t)> &next_accessor, absl::Span< const int64_t > transit_targets, DimensionCumulOptimizerCore::TransitTargetCost transit_target_cost, std::vector< int64_t > *optimal_transits, std::vector< int64_t > *optimal_cumuls, std::vector< int64_t > *optimal_breaks)

std::vector< DimensionSchedulingStatus > ComputeRouteCumulCostsForResourcesWithoutFixedTransits(int vehicle, double solve_duration_ratio, const std::function< int64_t(int64_t)> &next_accessor, const std::function< int64_t(int64_t, int64_t)> &transit_accessor, absl::Span< const RoutingModel::ResourceGroup::Resource > resources, absl::Span< const int > resource_indices, bool optimize_vehicle_costs, std::vector< int64_t > *optimal_costs_without_transits, std::vector< std::vector< int64_t > > *optimal_cumuls, std::vector< std::vector< int64_t > > *optimal_breaks)

DimensionSchedulingStatus ComputeRouteCumulCost(int vehicle, double solve_duration_ratio, const std::function< int64_t(int64_t)> &next_accessor, int64_t *optimal_cost)

static IntOut Round(FloatIn x)

void AddMaximumConstraint(int max_var, std::vector< int > vars) override

Definition routing_lp_scheduling.h:598

void AddObjectiveConstraint() override

Definition routing_lp_scheduling.h:585

void SetParameters(const std::string &) override

Definition routing_lp_scheduling.h:688

void SetVariableDisjointBounds(int index, const std::vector< int64_t > &starts, const std::vector< int64_t > &ends) override

Definition routing_lp_scheduling.h:527

int NumVariables() const override

Definition routing_lp_scheduling.h:569

bool IsCPSATSolver() override

Definition routing_lp_scheduling.h:584

int CreateNewConstraint(int64_t lower_bound, int64_t upper_bound) override

Definition routing_lp_scheduling.h:570

int CreateNewPositiveVariable() override

Definition routing_lp_scheduling.h:506

DimensionSchedulingStatus Solve(absl::Duration duration_limit) override

Definition routing_lp_scheduling.h:635

void SetCoefficient(int ct_index, int index, double coefficient) override

Definition routing_lp_scheduling.h:577

void SetVariableName(int index, absl::string_view name) override

Definition routing_lp_scheduling.h:513

bool SetVariableBounds(int index, int64_t lower_bound, int64_t upper_bound) override

Definition routing_lp_scheduling.h:516

void SetObjectiveCoefficient(int index, double coefficient) override

Definition routing_lp_scheduling.h:551

double GetObjectiveCoefficient(int index) const override

Definition routing_lp_scheduling.h:561

std::string PrintModel() const override

int64_t GetVariableUpperBound(int index) const override

Definition routing_lp_scheduling.h:547

void SetEnforcementLiteral(int ct, int condition) override

Definition routing_lp_scheduling.h:620

void ClearObjective() override

Definition routing_lp_scheduling.h:566

int64_t GetObjectiveValue() const override

Definition routing_lp_scheduling.h:679

void AddRoute(absl::Span< const int64_t > nodes, absl::Span< const int > schedule_variables) override

Definition routing_lp_scheduling.h:624

RoutingCPSatWrapper(RoutingSearchStats *const search_stats)

Definition routing_lp_scheduling.h:479

int64_t GetVariableLowerBound(int index) const override

Definition routing_lp_scheduling.h:544

int64_t GetVariableValue(int index) const override

Definition routing_lp_scheduling.h:682

bool ModelIsEmpty() const override

Definition routing_lp_scheduling.h:692

void AddProductConstraint(int product_var, std::vector< int > vars) override

Definition routing_lp_scheduling.h:609

~RoutingCPSatWrapper() override

Definition routing_lp_scheduling.h:499

bool SolutionIsInteger() const override

Definition routing_lp_scheduling.h:685

void Clear() override

Definition routing_lp_scheduling.h:500

int64_t GetVariableLowerBound(int index) const override

Definition routing_lp_scheduling.h:330

int NumVariables() const override

Definition routing_lp_scheduling.h:351

void ClearObjective() override

Definition routing_lp_scheduling.h:346

bool SetVariableBounds(int index, int64_t lower_bound, int64_t upper_bound) override

Definition routing_lp_scheduling.h:303

int64_t GetVariableValue(int index) const override

Definition routing_lp_scheduling.h:443

double GetObjectiveCoefficient(int index) const override

Definition routing_lp_scheduling.h:343

int CreateNewPositiveVariable() override

Definition routing_lp_scheduling.h:297

RoutingGlopWrapper(bool is_relaxation, const glop::GlopParameters &parameters, RoutingSearchStats *search_stats)

Definition routing_lp_scheduling.h:285

void AddRoute(absl::Span< const int64_t >, absl::Span< const int >) override

Definition routing_lp_scheduling.h:404

std::string PrintModel() const override

Definition routing_lp_scheduling.h:463

void SetObjectiveCoefficient(int index, double coefficient) override

Definition routing_lp_scheduling.h:340

void AddMaximumConstraint(int, std::vector< int >) override

Definition routing_lp_scheduling.h:399

void AddObjectiveConstraint() override

Definition routing_lp_scheduling.h:372

void SetEnforcementLiteral(int, int) override

Definition routing_lp_scheduling.h:403

void Clear() override

Definition routing_lp_scheduling.h:292

DimensionSchedulingStatus Solve(absl::Duration duration_limit) override

Definition routing_lp_scheduling.h:405

int64_t GetObjectiveValue() const override

Definition routing_lp_scheduling.h:440

int64_t GetVariableUpperBound(int index) const override

Definition routing_lp_scheduling.h:333

bool IsCPSATSolver() override

Definition routing_lp_scheduling.h:371

bool SolutionIsInteger() const override

Definition routing_lp_scheduling.h:449

void SetVariableDisjointBounds(int index, const std::vector< int64_t > &starts, const std::vector< int64_t > &ends) override

Definition routing_lp_scheduling.h:321

void SetCoefficient(int ct, int index, double coefficient) override

Definition routing_lp_scheduling.h:364

void SetVariableName(int index, absl::string_view name) override

Definition routing_lp_scheduling.h:300

int CreateNewConstraint(int64_t lower_bound, int64_t upper_bound) override

Definition routing_lp_scheduling.h:354

void AddProductConstraint(int, std::vector< int >) override

Definition routing_lp_scheduling.h:401

void SetParameters(const std::string &parameters) override

Definition routing_lp_scheduling.h:454

virtual int NumVariables() const =0

virtual int64_t GetObjectiveValue() const =0

virtual DimensionSchedulingStatus Solve(absl::Duration duration_limit)=0

virtual void SetCoefficient(int ct, int index, double coefficient)=0

virtual int64_t GetVariableUpperBound(int index) const =0

RoutingSearchStats *const search_stats_

Definition routing_lp_scheduling.h:280

virtual ~RoutingLinearSolverWrapper()=default

int AddLinearConstraint(int64_t lower_bound, int64_t upper_bound, absl::Span< const std::pair< int, double > > variable_coeffs)

Definition routing_lp_scheduling.h:229

virtual bool SolutionIsInteger() const =0

virtual int CreateNewConstraint(int64_t lower_bound, int64_t upper_bound)=0

virtual void SetEnforcementLiteral(int ct, int condition)=0

virtual void AddProductConstraint(int product_var, std::vector< int > vars)=0

virtual std::string PrintModel() const =0

virtual int64_t GetVariableValue(int index) const =0

virtual void SetVariableDisjointBounds(int index, const std::vector< int64_t > &starts, const std::vector< int64_t > &ends)=0

int AddReifiedLinearConstraint(int64_t lower_bound, int64_t upper_bound, absl::Span< const std::pair< int, double > > weighted_variables)

Definition routing_lp_scheduling.h:242

virtual void AddRoute(absl::Span< const int64_t > nodes, absl::Span< const int > schedule_variables)=0

virtual void SetObjectiveCoefficient(int index, double coefficient)=0

static const int kNoConstraint

Definition routing_lp_scheduling.h:172

virtual void ClearObjective()=0

virtual int CreateNewPositiveVariable()=0

virtual bool SetVariableBounds(int index, int64_t lower_bound, int64_t upper_bound)=0

virtual void SetParameters(const std::string &parameters)=0

virtual void AddMaximumConstraint(int max_var, std::vector< int > vars)=0

virtual void SetVariableName(int index, absl::string_view name)=0

virtual void AddObjectiveConstraint()=0

virtual bool ModelIsEmpty() const

Definition routing_lp_scheduling.h:214

virtual int64_t GetVariableLowerBound(int index) const =0

virtual bool IsCPSATSolver()=0

RoutingLinearSolverWrapper(RoutingSearchStats *search_stats)

Definition routing_lp_scheduling.h:174

virtual double GetObjectiveCoefficient(int index) const =0

int AddVariable(int64_t lower_bound, int64_t upper_bound)

Definition routing_lp_scheduling.h:220

A Resource sets attributes (costs/constraints) for a set of dimensions.

RoutingResourceClassIndex ResourceClassIndex

RoutingSearchParameters_SchedulingSolver SchedulingSolver

Iterator FirstIntervalGreaterOrEqual(int64_t value) const

ConstIterator end() const

const DenseRow & variable_values() const

::int32_t vars(int index) const

::int64_t coeffs(int index) const

void add_coeffs(double value)

void add_vars(::int32_t value)

void add_domain(::int64_t value)

void set_domain(int index, ::int64_t value)

::operations_research::sat::LinearExpressionProto *PROTOBUF_NONNULL mutable_target()

::operations_research::sat::LinearExpressionProto *PROTOBUF_NONNULL add_exprs()

void add_vars(::int32_t value)

void add_domain(::int64_t value)

void add_coeffs(::int64_t value)

void add_vars(::int32_t value)

T Add(std::function< T(Model *)> f)

static constexpr SearchBranching PORTFOLIO_SEARCH

constexpr Fractional kInfinity

std::function< SatParameters(Model *)> NewSatParameters(absl::string_view params)

CpSolverResponse SolveCpModel(const CpModelProto &model_proto, Model *model)

int64_t ComputeBestVehicleToResourceAssignment(absl::Span< const int > vehicles, const util_intops::StrongVector< RoutingModel::ResourceClassIndex, std::vector< int > > &resource_indices_per_class, const util_intops::StrongVector< RoutingModel::ResourceClassIndex, absl::flat_hash_set< int > > &ignored_resources_per_class, std::function< const std::vector< int64_t > *(int)> vehicle_to_resource_class_assignment_costs, std::vector< int > *resource_indices)

DimensionSchedulingStatus

Definition routing_lp_scheduling.h:158

@ INFEASIBLE

Definition routing_lp_scheduling.h:167

@ FEASIBLE

Definition routing_lp_scheduling.h:165

@ OPTIMAL

Definition routing_lp_scheduling.h:160

@ RELAXED_OPTIMAL_ONLY

Definition routing_lp_scheduling.h:163

std::vector< bool > SlopeAndYInterceptToConvexityRegions(absl::Span< const SlopeAndYIntercept > slope_and_y_intercept)

bool ComputeVehicleToResourceClassAssignmentCosts(int v, double solve_duration_ratio, const RoutingModel::ResourceGroup &resource_group, const util_intops::StrongVector< RoutingModel::ResourceClassIndex, absl::flat_hash_set< int > > &ignored_resources_per_class, const std::function< int64_t(int64_t)> &next_accessor, const std::function< int64_t(int64_t, int64_t)> &transit_accessor, bool optimize_vehicle_costs, LocalDimensionCumulOptimizer *lp_optimizer, LocalDimensionCumulOptimizer *mp_optimizer, std::vector< int64_t > *assignment_costs, std::vector< std::vector< int64_t > > *cumul_values, std::vector< std::vector< int64_t > > *break_values)

std::string ProtobufDebugString(const P &message)

std::vector< SlopeAndYIntercept > PiecewiseLinearFunctionToSlopeAndYIntercept(const FloatSlopePiecewiseLinearFunction &pwl_function, int index_start, int index_end)

The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...

double threshold_ratio

Definition routing_lp_scheduling.h:796

int64_t cost_coefficient_above_threshold

Definition routing_lp_scheduling.h:798

int64_t cost_coefficient_below_threshold

Definition routing_lp_scheduling.h:797

double slope

Definition routing_lp_scheduling.h:1149

friend::std::ostream & operator<<(::std::ostream &os, const SlopeAndYIntercept &it)

Definition routing_lp_scheduling.h:1152

double y_intercept

Definition routing_lp_scheduling.h:1150