1

2

3

4

5

6

7

8

9

10

11

12

13

15

16#include <algorithm>

17#include <cmath>

18#include <cstdint>

19#include <cstdlib>

20#include <functional>

21#include <limits>

22#include <memory>

23#include <numeric>

24#include <optional>

25#include <string>

26#include <utility>

27#include <vector>

28

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

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

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

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

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

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

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

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

54

56

57namespace {

58

59constexpr int64_t kint64min = std::numeric_limits<int64_t>::min();

60constexpr int64_t kint64max = std::numeric_limits<int64_t>::max();

61

62

63

67 parameters.set_use_preprocessing(false);

68 return parameters;

69}

70

74 return parameters;

75}

76

77bool GetCumulBoundsWithOffset(const RoutingDimension& dimension,

78 int64_t node_index, int64_t cumul_offset,

79 int64_t* lower_bound, int64_t* upper_bound) {

80 DCHECK(lower_bound != nullptr);

81 DCHECK(upper_bound != nullptr);

82

83 const IntVar& cumul_var = *dimension.CumulVar(node_index);

84 *upper_bound = cumul_var.Max();

85 if (*upper_bound < cumul_offset) {

86 return false;

87 }

88

89 const int64_t first_after_offset =

90 std::max(dimension.GetFirstPossibleGreaterOrEqualValueForNode(

91 node_index, cumul_offset),

92 cumul_var.Min());

93 DCHECK_LT(first_after_offset, kint64max);

94 *lower_bound = CapSub(first_after_offset, cumul_offset);

95 DCHECK_GE(*lower_bound, 0);

96

98 return true;

99 }

100 *upper_bound = CapSub(*upper_bound, cumul_offset);

101 DCHECK_GE(*upper_bound, *lower_bound);

102 return true;

103}

104

105int64_t GetFirstPossibleValueForCumulWithOffset(

107 int64_t lower_bound_without_offset, int64_t cumul_offset) {

109 dimension.GetFirstPossibleGreaterOrEqualValueForNode(

110 node_index, CapAdd(lower_bound_without_offset, cumul_offset)),

111 cumul_offset);

112}

113

114int64_t GetLastPossibleValueForCumulWithOffset(

116 int64_t upper_bound_without_offset, int64_t cumul_offset) {

118 dimension.GetLastPossibleLessOrEqualValueForNode(

119 node_index, CapAdd(upper_bound_without_offset, cumul_offset)),

120 cumul_offset);

121}

122

124

125

126

127

128

129void StoreVisitedPickupDeliveryPairsOnRoute(

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

132 std::vector<int>* visited_pairs,

133 std::vector<std::pair<int64_t, int64_t>>*

134 visited_pickup_delivery_indices_for_pair) {

135

136 DCHECK_EQ(visited_pickup_delivery_indices_for_pair->size(),

137 dimension.model()->GetPickupAndDeliveryPairs().size());

138 DCHECK(std::all_of(visited_pickup_delivery_indices_for_pair->begin(),

139 visited_pickup_delivery_indices_for_pair->end(),

140 [](std::pair<int64_t, int64_t> p) {

141 return p.first == -1 && p.second == -1;

142 }));

143 visited_pairs->clear();

144 if (!dimension.HasPickupToDeliveryLimits()) {

145 return;

146 }

147 const RoutingModel& model = *dimension.model();

148

149 int64_t node_index = model.Start(vehicle);

150 while (!model.IsEnd(node_index)) {

151 if (model.IsPickup(node_index)) {

152

153 const std::optional<PDPosition> pickup_position =

154 model.GetPickupPosition(node_index);

155 DCHECK(pickup_position.has_value());

156 const int pair_index = pickup_position->pd_pair_index;

157 (*visited_pickup_delivery_indices_for_pair)[pair_index].first =

158 node_index;

159 visited_pairs->push_back(pair_index);

160 } else if (model.IsDelivery(node_index)) {

161

162

163 const std::optional<PDPosition> delivery_position =

164 model.GetDeliveryPosition(node_index);

165 DCHECK(delivery_position.has_value());

166 const int pair_index = delivery_position->pd_pair_index;

167 std::pair<int64_t, int64_t>& pickup_delivery_index =

168 (*visited_pickup_delivery_indices_for_pair)[pair_index];

169 if (pickup_delivery_index.first < 0) {

170

171

172 node_index = next_accessor(node_index);

173 continue;

174 }

175 pickup_delivery_index.second = node_index;

176 }

177 node_index = next_accessor(node_index);

178 }

179}

180

181}

182

183

184

215

238

254

273

289

304

323

337

354

355const int CumulBoundsPropagator::kNoParent = -2;

356const int CumulBoundsPropagator::kParentToBePropagated = -1;

357

367

368void CumulBoundsPropagator::AddArcs(int first_index, int second_index,

369 int64_t offset) {

370

371 outgoing_arcs_[PositiveNode(first_index)].push_back(

372 {PositiveNode(second_index), offset});

373 AddNodeToQueue(PositiveNode(first_index));

374

375 outgoing_arcs_[NegativeNode(second_index)].push_back(

376 {NegativeNode(first_index), offset});

377 AddNodeToQueue(NegativeNode(second_index));

378}

379

380bool CumulBoundsPropagator::InitializeArcsAndBounds(

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

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

383 dimension_travel_info_per_route) {

384 propagated_bounds_.assign(num_nodes_, kint64min);

385

386 for (std::vector<ArcInfo>& arcs : outgoing_arcs_) {

387 arcs.clear();

388 }

389

390 RoutingModel* const model = dimension_.model();

391 std::vector<int64_t>& lower_bounds = propagated_bounds_;

392

393 for (int vehicle = 0; vehicle < model->vehicles(); vehicle++) {

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

395 dimension_.transit_evaluator(vehicle);

396

397 int node = model->Start(vehicle);

398 int index_on_route = 0;

399 while (true) {

400 int64_t cumul_lb, cumul_ub;

401 if (!GetCumulBoundsWithOffset(dimension_, node, cumul_offset, &cumul_lb,

402 &cumul_ub)) {

403 return false;

404 }

405 lower_bounds[PositiveNode(node)] = cumul_lb;

407 lower_bounds[NegativeNode(node)] = -cumul_ub;

408 }

409

410 if (model->IsEnd(node)) {

411 break;

412 }

413

414 const int next = next_accessor(node);

415 int64_t transit = transit_accessor(node, next);

416 if (dimension_travel_info_per_route != nullptr &&

417 !dimension_travel_info_per_route->empty()) {

418 const RoutingModel::RouteDimensionTravelInfo::TransitionInfo&

419 transition_info = (*dimension_travel_info_per_route)[vehicle]

420 .transition_info[index_on_route];

421 transit = transition_info.compressed_travel_value_lower_bound +

422 transition_info.pre_travel_transit_value +

423 transition_info.post_travel_transit_value;

424 ++index_on_route;

425 }

426 const IntVar& slack_var = *dimension_.SlackVar(node);

427

428

429 AddArcs(node, next, CapAdd(transit, slack_var.Min()));

430 if (slack_var.Max() < kint64max) {

431

432 AddArcs(next, node, CapSub(-slack_var.Max(), transit));

433 }

434

435 node = next;

436 }

437

438

439 const int64_t span_ub = dimension_.GetSpanUpperBoundForVehicle(vehicle);

441 AddArcs(model->End(vehicle), model->Start(vehicle), -span_ub);

442 }

443

444

445 std::vector<int> visited_pairs;

446 StoreVisitedPickupDeliveryPairsOnRoute(

447 dimension_, vehicle, next_accessor, &visited_pairs,

448 &visited_pickup_delivery_indices_for_pair_);

449 for (int pair_index : visited_pairs) {

450 const int64_t pickup_index =

451 visited_pickup_delivery_indices_for_pair_[pair_index].first;

452 const int64_t delivery_index =

453 visited_pickup_delivery_indices_for_pair_[pair_index].second;

454 visited_pickup_delivery_indices_for_pair_[pair_index] = {-1, -1};

455

456 DCHECK_GE(pickup_index, 0);

457 if (delivery_index < 0) {

458

459 continue;

460 }

461

462 const int64_t limit = dimension_.GetPickupToDeliveryLimitForPair(

463 pair_index, model->GetPickupPosition(pickup_index)->alternative_index,

464 model->GetDeliveryPosition(delivery_index)->alternative_index);

466

467 AddArcs(delivery_index, pickup_index, -limit);

468 }

469 }

470 }

471

472 for (const auto [first_node, second_node, offset, performed_constraint] :

473 dimension_.GetNodePrecedences()) {

474 if (next_accessor(first_node) == -1 || next_accessor(second_node) == -1) {

475 continue;

476 }

477 const bool first_node_unperformed =

478 lower_bounds[PositiveNode(first_node)] == kint64min;

479 const bool second_node_unperformed =

480 lower_bounds[PositiveNode(second_node)] == kint64min;

482 second_node_unperformed,

483 performed_constraint)) {

485 break;

487 continue;

489 return false;

490 }

491 AddArcs(first_node, second_node, offset);

492 }

493

494 return true;

495}

496

497bool CumulBoundsPropagator::UpdateCurrentLowerBoundOfNode(int node,

498 int64_t new_lb,

499 int64_t offset) {

500 const int cumul_var_index = node / 2;

501

502 if (node == PositiveNode(cumul_var_index)) {

503

504 propagated_bounds_[node] = GetFirstPossibleValueForCumulWithOffset(

505 dimension_, cumul_var_index, new_lb, offset);

506 } else {

507

508 const int64_t new_ub = CapSub(0, new_lb);

509 propagated_bounds_[node] =

510 CapSub(0, GetLastPossibleValueForCumulWithOffset(

511 dimension_, cumul_var_index, new_ub, offset));

512 }

513

514

515 const int64_t cumul_lower_bound =

516 propagated_bounds_[PositiveNode(cumul_var_index)];

517

518 const int64_t negated_cumul_upper_bound =

519 propagated_bounds_[NegativeNode(cumul_var_index)];

520

521 return CapAdd(negated_cumul_upper_bound, cumul_lower_bound) <= 0;

522}

523

524bool CumulBoundsPropagator::DisassembleSubtree(int source, int target) {

525 tmp_dfs_stack_.clear();

526 tmp_dfs_stack_.push_back(source);

527 while (!tmp_dfs_stack_.empty()) {

528 const int tail = tmp_dfs_stack_.back();

529 tmp_dfs_stack_.pop_back();

530 for (const ArcInfo& arc : outgoing_arcs_[tail]) {

531 const int child_node = arc.head;

532 if (tree_parent_node_of_[child_node] != tail) continue;

533 if (child_node == target) return false;

534 tree_parent_node_of_[child_node] = kParentToBePropagated;

535 tmp_dfs_stack_.push_back(child_node);

536 }

537 }

538 return true;

539}

540

596

627

730

731namespace {

732template <typename T>

733void ClearIfNonNull(std::vector<T>* v) {

734 if (v != nullptr) {

735 v->clear();

736 }

737}

738}

739

787

788namespace {

789

791

792bool GetDomainOffsetBounds(const Domain& domain, int64_t offset,

794 const int64_t lower_bound =

795 std::max<int64_t>(CapSub(domain.Min(), offset), 0);

796 const int64_t upper_bound =

798 if (lower_bound > upper_bound) return false;

799

800 *interval = ClosedInterval(lower_bound, upper_bound);

801 return true;

802}

803

804bool GetIntervalIntersectionWithOffsetDomain(const ClosedInterval& interval,

805 const Domain& domain,

806 int64_t offset,

807 ClosedInterval* intersection) {

809 *intersection = interval;

810 return true;

811 }

813 if (!GetDomainOffsetBounds(domain, offset, &offset_domain)) {

814 return false;

815 }

816 const int64_t intersection_lb = std::max(interval.start, offset_domain.start);

817 const int64_t intersection_ub = std::min(interval.end, offset_domain.end);

818 if (intersection_lb > intersection_ub) return false;

819

820 *intersection = ClosedInterval(intersection_lb, intersection_ub);

821 return true;

822}

823

826 return ClosedInterval(solver.GetVariableLowerBound(index),

827 solver.GetVariableUpperBound(index));

828}

829

830bool TightenStartEndVariableBoundsWithResource(

831 const RoutingDimension& dimension, const ResourceGroup::Resource& resource,

833 const ClosedInterval& end_bounds, int end_index, int64_t offset,

835 const ResourceGroup::Attributes& attributes =

836 resource.GetDimensionAttributes(dimension.index());

839 return GetIntervalIntersectionWithOffsetDomain(start_bounds,

840 attributes.start_domain(),

841 offset, &new_start_bounds) &&

842 solver->SetVariableBounds(start_index, new_start_bounds.start,

843 new_start_bounds.end) &&

844 GetIntervalIntersectionWithOffsetDomain(

845 end_bounds, attributes.end_domain(), offset, &new_end_bounds) &&

846 solver->SetVariableBounds(end_index, new_end_bounds.start,

847 new_end_bounds.end);

848}

849

850bool TightenStartEndVariableBoundsWithAssignedResources(

851 const RoutingDimension& dimension, int v, int start_index, int end_index,

853 const RoutingModel* model = dimension.model();

854 for (int rg_index : model->GetDimensionResourceGroupIndices(&dimension)) {

855 const IntVar* res_var = model->ResourceVars(rg_index)[v];

856 DCHECK(res_var->Bound());

857 const int res_index = res_var->Value();

858 if (res_index < 0) {

859

860 DCHECK(!model->GetResourceGroup(rg_index)->VehicleRequiresAResource(v));

861 continue;

862 }

863 const ResourceGroup::Resource& resource =

864 model->GetResourceGroup(rg_index)->GetResource(res_index);

865 if (!TightenStartEndVariableBoundsWithResource(

866 dimension, resource, GetVariableBounds(start_index, *solver),

867 start_index, GetVariableBounds(end_index, *solver), end_index,

868 offset, solver)) {

869 return false;

870 }

871 }

872 return true;

873}

874

875}

876

877std::vector<DimensionSchedulingStatus>

983

1080

1128

1176

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

1182

1183

1184

1185

1186

1187

1188

1189

1190

1191

1193

1194

1197 for (int vehicle : vehicles) {

1199 index_to_cumul_variable_[model->End(vehicle)], 1);

1200 }

1201

1202 glop::GlopParameters current_params;

1203 const auto retry_solving = [&current_params, model, solver,

1204 solve_duration_ratio]() {

1205

1206

1207

1208 current_params.set_use_dual_simplex(!current_params.use_dual_simplex());

1209 solver->SetParameters(current_params.SerializeAsString());

1210 return solver->Solve(model->RemainingTime() * solve_duration_ratio);

1211 };

1212 if (solver->Solve(model->RemainingTime() * solve_duration_ratio) ==

1214 if (solver->IsCPSATSolver()) {

1216 }

1217

1218 current_params = packing_parameters;

1221 }

1222 }

1223

1224

1225

1226 solver->ClearObjective();

1227 for (int vehicle : vehicles) {

1228 const int end_cumul_var = index_to_cumul_variable_[model->End(vehicle)];

1229

1230 solver->SetVariableBounds(end_cumul_var,

1231 solver->GetVariableLowerBound(end_cumul_var),

1232 solver->GetVariableValue(end_cumul_var));

1233

1234

1235 solver->SetObjectiveCoefficient(

1236 index_to_cumul_variable_[model->Start(vehicle)], -1);

1237 }

1238

1240 solver->Solve(model->RemainingTime() * solve_duration_ratio);

1241 if (!solver->IsCPSATSolver() &&

1243 status = retry_solving();

1244 }

1245 return status;

1246}

1247

1410

1417

1418void DimensionCumulOptimizerCore::InitOptimizer(

1419 RoutingLinearSolverWrapper* solver) {

1420 solver->Clear();

1421 index_to_cumul_variable_.assign(dimension_->cumuls().size(), -1);

1422 max_end_cumul_ = solver->CreateNewPositiveVariable();

1424 min_start_cumul_ = solver->CreateNewPositiveVariable();

1426}

1427

1428bool DimensionCumulOptimizerCore::ExtractRouteCumulBounds(

1429 absl::Span<const int64_t> route, int64_t cumul_offset) {

1430 const int route_size = route.size();

1431 current_route_min_cumuls_.resize(route_size);

1432 current_route_max_cumuls_.resize(route_size);

1433

1434

1435 for (int pos = 0; pos < route_size; ++pos) {

1436 if (!GetCumulBoundsWithOffset(*dimension_, route[pos], cumul_offset,

1437 &current_route_min_cumuls_[pos],

1438 &current_route_max_cumuls_[pos])) {

1439 return false;

1440 }

1441 }

1442 return true;

1443}

1444

1445bool DimensionCumulOptimizerCore::TightenRouteCumulBounds(

1446 absl::Span<const int64_t> route, absl::Span<const int64_t> min_transits,

1447 int64_t cumul_offset) {

1448 const int route_size = route.size();

1449 if (propagator_ != nullptr) {

1450 for (int pos = 0; pos < route_size; pos++) {

1451 const int64_t node = route[pos];

1452 current_route_min_cumuls_[pos] = propagator_->CumulMin(node);

1453 DCHECK_GE(current_route_min_cumuls_[pos], 0);

1454 current_route_max_cumuls_[pos] = propagator_->CumulMax(node);

1455 DCHECK_GE(current_route_max_cumuls_[pos], current_route_min_cumuls_[pos]);

1456 }

1457 return true;

1458 }

1459

1460

1461

1462 for (int pos = 1; pos < route_size; ++pos) {

1463 const int64_t slack_min = dimension_->SlackVar(route[pos - 1])->Min();

1464 current_route_min_cumuls_[pos] = std::max(

1465 current_route_min_cumuls_[pos],

1467 CapAdd(current_route_min_cumuls_[pos - 1], min_transits[pos - 1]),

1468 slack_min));

1469 current_route_min_cumuls_[pos] = GetFirstPossibleValueForCumulWithOffset(

1470 *dimension_, route[pos], current_route_min_cumuls_[pos], cumul_offset);

1471 if (current_route_min_cumuls_[pos] > current_route_max_cumuls_[pos]) {

1472 return false;

1473 }

1474 }

1475

1476 for (int pos = route_size - 2; pos >= 0; --pos) {

1477

1478

1479 if (current_route_max_cumuls_[pos + 1] < kint64max) {

1480 const int64_t slack_min = dimension_->SlackVar(route[pos])->Min();

1481 current_route_max_cumuls_[pos] = std::min(

1482 current_route_max_cumuls_[pos],

1483 CapSub(CapSub(current_route_max_cumuls_[pos + 1], min_transits[pos]),

1484 slack_min));

1485 current_route_max_cumuls_[pos] = GetLastPossibleValueForCumulWithOffset(

1486 *dimension_, route[pos], current_route_max_cumuls_[pos],

1487 cumul_offset);

1488 if (current_route_max_cumuls_[pos] < current_route_min_cumuls_[pos]) {

1489 return false;

1490 }

1491 }

1492 }

1493 return true;

1494}

1495

1513

1528

1529namespace {

1530

1531

1532double FindBestScaling(absl::Span<const double> coefficients,

1533 absl::Span<const double> lower_bounds,

1534 absl::Span<const double> upper_bounds,

1535 int64_t max_absolute_activity,

1536 double wanted_absolute_activity_precision) {

1537 double unused_relative_coeff_error = 0;

1538 double unused_scaled_sum_error = 0;

1540 coefficients, lower_bounds, upper_bounds, max_absolute_activity,

1541 wanted_absolute_activity_precision, &unused_relative_coeff_error,

1542 &unused_scaled_sum_error);

1543}

1544}

1545

1546bool DimensionCumulOptimizerCore::SetRouteTravelConstraints(

1547 const RouteDimensionTravelInfo* dimension_travel_info,

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

1549 absl::Span<const int64_t> transit_targets,

1551 const std::vector<int>& lp_cumuls = current_route_cumul_variables_;

1552 const int path_size = lp_cumuls.size();

1553 std::vector<int>& variable_transits =

1554 current_route_variable_transit_variables_;

1555

1556 if (dimension_travel_info == nullptr ||

1557 dimension_travel_info->transition_info.empty()) {

1558 variable_transits.assign(path_size - 1, -1);

1559

1560

1561

1562

1563

1564 for (int pos = 0; pos < path_size - 1; ++pos) {

1565 const int64_t fixed_transit = fixed_transits[pos];

1566 const int ct = solver->CreateNewConstraint(fixed_transit, fixed_transit);

1567 solver->SetCoefficient(ct, lp_cumuls[pos + 1], 1);

1568 solver->SetCoefficient(ct, lp_cumuls[pos], -1);

1569 solver->SetCoefficient(ct, lp_slacks[pos], -1);

1570 if (!transit_targets.empty()) {

1571 const int64_t max_variable_transit =

1572 CapSub(transit_targets[pos], fixed_transit);

1573 if (max_variable_transit > 0) {

1574 variable_transits[pos] = solver->AddVariable(0, max_variable_transit);

1575 solver->SetCoefficient(ct, variable_transits[pos], -1);

1576 }

1577 }

1578 }

1579 return true;

1580 }

1581

1582

1583

1584 for (int pos = 0; pos < path_size - 1; ++pos) {

1585

1586

1587

1588 const int compression_cost = solver->CreateNewPositiveVariable();

1590 absl::StrFormat("compression_cost(%ld)", pos));

1591

1592

1593

1594

1595

1596

1597 const int relative_compression_cost = solver->CreateNewPositiveVariable();

1599 solver, relative_compression_cost,

1600 absl::StrFormat("relative_compression_cost(%ld)", pos));

1601

1602 const RoutingModel::RouteDimensionTravelInfo::TransitionInfo&

1603 transition_info = dimension_travel_info->transition_info[pos];

1604 const FloatSlopePiecewiseLinearFunction& travel_function =

1605 transition_info.travel_start_dependent_travel;

1606 const auto& travel_x_anchors = travel_function.x_anchors();

1607

1608

1609

1610 const int64_t pre_travel_transit = transition_info.pre_travel_transit_value;

1611 const int64_t post_travel_transit =

1612 transition_info.post_travel_transit_value;

1613 const int64_t compressed_travel_value_lower_bound =

1614 transition_info.compressed_travel_value_lower_bound;

1615 const int64_t travel_value_upper_bound =

1616 transition_info.travel_value_upper_bound;

1617

1618

1619

1620

1621

1622 const int travel_value = solver->AddVariable(

1623 compressed_travel_value_lower_bound, travel_value_upper_bound);

1625 absl::StrFormat("travel_value(%ld)", pos));

1626 const int travel_start = solver->AddVariable(

1627 current_route_min_cumuls_[pos] + pre_travel_transit,

1628 current_route_max_cumuls_[pos + 1] - post_travel_transit -

1629 compressed_travel_value_lower_bound);

1631 absl::StrFormat("travel_start(%ld)", pos));

1632

1633

1634 solver->AddLinearConstraint(pre_travel_transit, pre_travel_transit,

1635 {{travel_start, 1}, {lp_cumuls[pos], -1}});

1636

1637

1638

1639

1640 const int num_pwl_anchors = travel_x_anchors.size();

1641 int index_anchor_start = 0;

1642 while (index_anchor_start < num_pwl_anchors - 1 &&

1643 travel_x_anchors[index_anchor_start + 1] <=

1644 current_route_min_cumuls_[pos] + pre_travel_transit) {

1645 ++index_anchor_start;

1646 }

1647 int index_anchor_end = num_pwl_anchors - 1;

1648 while (index_anchor_end > 0 &&

1649 travel_x_anchors[index_anchor_end - 1] >=

1650 current_route_max_cumuls_[pos] + pre_travel_transit) {

1651 --index_anchor_end;

1652 }

1653

1654 if (index_anchor_start >= index_anchor_end) return false;

1655

1656

1657

1658

1659 const std::vector<SlopeAndYIntercept> slope_and_y_intercept =

1661 travel_function, index_anchor_start, index_anchor_end);

1662

1663

1664 const std::vector<bool> convexities =

1666

1667 int nb_bin_variables = 0;

1668 for (const bool convexity : convexities) {

1669 if (convexity) {

1670 ++nb_bin_variables;

1671 if (nb_bin_variables >= 2) break;

1672 }

1673 }

1674 const bool need_bins = (nb_bin_variables > 1);

1675

1676 const int travel_start_in_one_segment_ct =

1677 need_bins ? solver->CreateNewConstraint(1, 1)

1678 : -1;

1679

1680 int belongs_to_this_segment_var;

1681 for (int seg = 0; seg < convexities.size(); ++seg) {

1682 if (need_bins && convexities[seg]) {

1683 belongs_to_this_segment_var = solver->AddVariable(0, 1);

1685 solver, belongs_to_this_segment_var,

1686 absl::StrFormat("travel_start(%ld)belongs_to_seg(%ld)", pos, seg));

1687 solver->SetCoefficient(travel_start_in_one_segment_ct,

1688 belongs_to_this_segment_var, 1);

1689

1690

1691

1692

1693 const int64_t lower_bound_interval =

1694 seg > 0 ? travel_x_anchors[index_anchor_start + seg]

1695 : current_route_min_cumuls_[pos] + pre_travel_transit;

1696 int64_t end_of_seg = seg + 1;

1697 const int num_convexities = convexities.size();

1698 while (end_of_seg < num_convexities && !convexities[end_of_seg]) {

1699 ++end_of_seg;

1700 }

1701 const int64_t higher_bound_interval =

1702 end_of_seg < num_pwl_anchors - 1

1703 ? travel_x_anchors[index_anchor_start + end_of_seg]

1704 : current_route_max_cumuls_[pos] + pre_travel_transit;

1705 const int travel_start_in_segment_ct = solver->AddLinearConstraint(

1706 lower_bound_interval, higher_bound_interval, {{travel_start, 1}});

1707 solver->SetEnforcementLiteral(travel_start_in_segment_ct,

1708 belongs_to_this_segment_var);

1709 }

1710

1711

1712

1713 const auto [slope, y_intercept] = slope_and_y_intercept[seg];

1714

1715 DCHECK_GE(slope, -1.0) << "Travel value PWL should have a slope >= -1";

1716

1717

1718

1719

1720

1721

1722

1723

1724

1725 const double upper_bound = current_route_max_cumuls_[pos];

1726 const double factor = FindBestScaling(

1727 {1.0, -slope, y_intercept - 0.5},

1728 {static_cast<double>(compressed_travel_value_lower_bound), 0, 1},

1729

1730 {static_cast<double>(travel_value_upper_bound), upper_bound, 1},

1731 (int64_t{1} << 62),

1732 1e-3);

1733

1734

1735

1736 if (factor <= 0) return false;

1737

1738 const int linearization_ct = solver->AddLinearConstraint(

1742 if (need_bins) {

1743 solver->SetEnforcementLiteral(linearization_ct,

1744 belongs_to_this_segment_var);

1745 }

1746

1747

1748

1749

1750

1751

1752

1753

1754

1755

1756

1757

1758

1759 }

1760

1761

1762

1763

1764

1765

1766

1767

1768

1769

1770 const int compressed_travel_value = solver->AddVariable(

1771 compressed_travel_value_lower_bound, travel_value_upper_bound);

1773 solver, compressed_travel_value,

1774 absl::StrFormat("compressed_travel_value(%ld)", pos));

1775 solver->AddLinearConstraint(post_travel_transit + pre_travel_transit,

1776 post_travel_transit + pre_travel_transit,

1777 {{compressed_travel_value, -1},

1778 {lp_cumuls[pos + 1], 1},

1779 {lp_cumuls[pos], -1},

1780 {lp_slacks[pos], -1}});

1781

1782

1783

1784

1785

1786

1787 const int travel_compression_absolute = solver->AddVariable(

1788 0, travel_value_upper_bound - compressed_travel_value_lower_bound);

1790 solver, travel_compression_absolute,

1791 absl::StrFormat("travel_compression_absolute(%ld)", pos));

1792

1793 solver->AddLinearConstraint(0, 0,

1794 {{travel_compression_absolute, 1},

1795 {travel_value, -1},

1796 {compressed_travel_value, 1}});

1797

1798

1799

1800

1801

1802 solver->SetObjectiveCoefficient(

1803 travel_value, dimension_travel_info->travel_cost_coefficient);

1804

1805

1806

1807 const FloatSlopePiecewiseLinearFunction& cost_function =

1808 transition_info.travel_compression_cost;

1809 const auto& cost_x_anchors = cost_function.x_anchors();

1810

1811 const std::vector<SlopeAndYIntercept> cost_slope_and_y_intercept =

1813 const double cost_max = cost_function.ComputeConvexValue(

1814 travel_value_upper_bound - compressed_travel_value_lower_bound);

1815 double previous_slope = 0;

1816 for (int seg = 0; seg < cost_x_anchors.size() - 1; ++seg) {

1817 const auto [slope, y_intercept] = cost_slope_and_y_intercept[seg];

1818

1819 DCHECK_GE(slope, previous_slope)

1820 << "Compression error is not convex. Segment " << (1 + seg)

1821 << " out of " << (cost_x_anchors.size() - 1);

1822 previous_slope = slope;

1823 const double factor = FindBestScaling(

1824 {1.0, -slope, y_intercept},

1825 {0, static_cast<double>(compressed_travel_value_lower_bound), 1},

1826

1827 {cost_max, static_cast<double>(travel_value_upper_bound), 1},

1828 (static_cast<int64_t>(1) << 62),

1829 1e-3);

1830

1831

1832

1833 if (factor <= 0) return false;

1834

1835 solver->AddLinearConstraint(

1837 {{compression_cost, std::round(factor)},

1838 {travel_compression_absolute,

1840 }

1841

1842

1843

1844

1845

1846

1847

1848

1849

1850

1851

1852

1853

1854

1855

1856

1857 solver->AddLinearConstraint(

1858 0, kint64max, {{relative_compression_cost, 1}, {compression_cost, -1}});

1859

1860 solver->SetObjectiveCoefficient(relative_compression_cost, 1.0);

1861 }

1862 return true;

1863}

1864

1865namespace {

1866bool RouteIsValid(const RoutingModel& model, int vehicle,

1867 const std::function<int64_t(int64_t)>& next_accessor) {

1868 absl::flat_hash_set<int64_t> visited;

1869 int node = model.Start(vehicle);

1870 visited.insert(node);

1871 while (!model.IsEnd(node)) {

1872 node = next_accessor(node);

1873 if (visited.contains(node)) return false;

1874 visited.insert(node);

1875 }

1876 return visited.size() >= 2;

1877}

1878}

1879

1880bool DimensionCumulOptimizerCore::SetRouteCumulConstraints(

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

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

1883 absl::Span<const int64_t> transit_targets,

1884 const RouteDimensionTravelInfo* dimension_travel_info, int64_t cumul_offset,

1886 int64_t* route_transit_cost, int64_t* route_cost_offset) {

1887 RoutingModel* const model = dimension_->model();

1888

1889 std::vector<int64_t>& path = current_route_nodes_;

1890 path.clear();

1891 {

1892 DCHECK(RouteIsValid(*model, vehicle, next_accessor));

1893 int node = model->Start(vehicle);

1894 path.push_back(node);

1895 while (!model->IsEnd(node)) {

1896 node = next_accessor(node);

1897 path.push_back(node);

1898 }

1899 DCHECK_GE(path.size(), 2);

1900 }

1901 const int path_size = path.size();

1902

1903 std::vector<int64_t> fixed_transit(path_size - 1);

1904 int64_t total_fixed_transit = 0;

1905 {

1906 for (int pos = 1; pos < path_size; ++pos) {

1907 int64_t& transit = fixed_transit[pos - 1];

1908 transit = transit_accessor(path[pos - 1], path[pos]);

1909 if (!transit_targets.empty()) {

1910

1911

1912

1913

1914 DCHECK_GE(transit_targets[pos - 1], transit);

1915 }

1916 total_fixed_transit = CapAdd(total_fixed_transit, transit);

1917 }

1918 }

1919 if (!ExtractRouteCumulBounds(path, cumul_offset)) {

1920 return false;

1921 }

1922 if (dimension_travel_info == nullptr ||

1923 dimension_travel_info->transition_info.empty()) {

1924 if (!TightenRouteCumulBounds(path, fixed_transit, cumul_offset)) {

1925 return false;

1926 }

1927 } else {

1928

1929 std::vector<int64_t> min_transit(path_size - 1);

1930 for (int pos = 0; pos < path_size - 1; ++pos) {

1932 dimension_travel_info->transition_info[pos];

1934 transition.compressed_travel_value_lower_bound +

1935 transition.post_travel_transit_value;

1936 }

1937 if (!TightenRouteCumulBounds(path, min_transit, cumul_offset)) {

1938 return false;

1939 }

1940 }

1941

1942

1943

1944 std::vector<int>& lp_cumuls = current_route_cumul_variables_;

1945 lp_cumuls.assign(path_size, -1);

1946 for (int pos = 0; pos < path_size; ++pos) {

1947 const int lp_cumul = solver->CreateNewPositiveVariable();

1949 absl::StrFormat("lp_cumul(%ld)", pos));

1950 index_to_cumul_variable_[path[pos]] = lp_cumul;

1951 lp_cumuls[pos] = lp_cumul;

1952 if (!solver->SetVariableBounds(lp_cumul, current_route_min_cumuls_[pos],

1953 current_route_max_cumuls_[pos])) {

1954 return false;

1955 }

1956 const SortedDisjointIntervalList& forbidden =

1957 dimension_->forbidden_intervals()[path[pos]];

1958 if (forbidden.NumIntervals() > 0) {

1959 std::vector<int64_t> starts;

1960 std::vector<int64_t> ends;

1961 for (const ClosedInterval interval :

1962 dimension_->GetAllowedIntervalsInRange(

1963 path[pos], CapAdd(current_route_min_cumuls_[pos], cumul_offset),

1964 CapAdd(current_route_max_cumuls_[pos], cumul_offset))) {

1965 starts.push_back(CapSub(interval.start, cumul_offset));

1966 ends.push_back(CapSub(interval.end, cumul_offset));

1967 }

1968 solver->SetVariableDisjointBounds(lp_cumul, starts, ends);

1969 }

1970 }

1971 solver->AddRoute(path, lp_cumuls);

1972

1973 std::vector<int> lp_slacks(path_size - 1, -1);

1974 for (int pos = 0; pos < path_size - 1; ++pos) {

1975 const IntVar* cp_slack = dimension_->SlackVar(path[pos]);

1976 lp_slacks[pos] = solver->CreateNewPositiveVariable();

1978 absl::StrFormat("lp_slacks(%ld)", pos));

1979 if (!solver->SetVariableBounds(lp_slacks[pos], cp_slack->Min(),

1980 cp_slack->Max())) {

1981 return false;

1982 }

1983 }

1984

1985 if (!SetRouteTravelConstraints(dimension_travel_info, lp_slacks,

1986 fixed_transit, transit_targets, solver)) {

1987 return false;

1988 }

1989

1990 if (route_cost_offset != nullptr) *route_cost_offset = 0;

1991

1992 std::vector<int> visited_pairs;

1993 StoreVisitedPickupDeliveryPairsOnRoute(

1994 *dimension_, vehicle, next_accessor, &visited_pairs,

1995 &visited_pickup_delivery_indices_for_pair_);

1996 for (int pair_index : visited_pairs) {

1997 const int64_t pickup_index =

1998 visited_pickup_delivery_indices_for_pair_[pair_index].first;

1999 const int64_t delivery_index =

2000 visited_pickup_delivery_indices_for_pair_[pair_index].second;

2001 visited_pickup_delivery_indices_for_pair_[pair_index] = {-1, -1};

2002

2003 DCHECK_GE(pickup_index, 0);

2004 if (delivery_index < 0) {

2005

2006 continue;

2007 }

2008

2009 const int64_t limit = dimension_->GetPickupToDeliveryLimitForPair(

2010 pair_index, model->GetPickupPosition(pickup_index)->alternative_index,

2011 model->GetDeliveryPosition(delivery_index)->alternative_index);

2013

2014 const int ct = solver->CreateNewConstraint(kint64min, limit);

2015 solver->SetCoefficient(ct, index_to_cumul_variable_[delivery_index], 1);

2016 solver->SetCoefficient(ct, index_to_cumul_variable_[pickup_index], -1);

2017 }

2018 }

2019

2020

2021 const int64_t span_bound = dimension_->GetSpanUpperBoundForVehicle(vehicle);

2023

2024 const int ct = solver->CreateNewConstraint(kint64min, span_bound);

2025 solver->SetCoefficient(ct, lp_cumuls.back(), 1);

2026 solver->SetCoefficient(ct, lp_cumuls.front(), -1);

2027 }

2028

2029 if (optimize_costs) {

2030 SetRouteCumulCosts(vehicle, cumul_offset, total_fixed_transit, solver,

2031 route_transit_cost, route_cost_offset);

2032 }

2033

2034 current_route_break_variables_.clear();

2035 if (!dimension_->HasBreakConstraints()) return true;

2036

2037

2038

2039

2040

2041

2042 const std::vector<IntervalVar*>& breaks =

2043 dimension_->GetBreakIntervalsOfVehicle(vehicle);

2044 const int num_breaks = breaks.size();

2045

2046

2047

2048 if (num_breaks == 0) {

2049 int64_t maximum_route_span = kint64max;

2050 for (const auto& distance_duration :

2051 dimension_->GetBreakDistanceDurationOfVehicle(vehicle)) {

2052 maximum_route_span =

2053 std::min(maximum_route_span, distance_duration.first);

2054 }

2055 if (maximum_route_span < kint64max) {

2056 const int ct = solver->CreateNewConstraint(kint64min, maximum_route_span);

2057 solver->SetCoefficient(ct, lp_cumuls.back(), 1);

2058 solver->SetCoefficient(ct, lp_cumuls.front(), -1);

2059 }

2060 return true;

2061 }

2062

2063

2064

2065 std::vector<int64_t> pre_travel(path_size - 1, 0);

2066 std::vector<int64_t> post_travel(path_size - 1, 0);

2067 {

2068 const int pre_travel_index =

2069 dimension_->GetPreTravelEvaluatorOfVehicle(vehicle);

2070 if (pre_travel_index != -1) {

2072 &pre_travel);

2073 }

2074 const int post_travel_index =

2075 dimension_->GetPostTravelEvaluatorOfVehicle(vehicle);

2076 if (post_travel_index != -1) {

2078 &post_travel);

2079 }

2080 }

2081

2082

2083

2084

2085 struct LpBreak {

2086 int start;

2087 int end;

2088 int duration;

2089 };

2090 std::vector<LpBreak> lp_breaks;

2091 if (solver->IsCPSATSolver()) {

2092 lp_breaks.resize(num_breaks, {.start = -1, .end = -1, .duration = -1});

2093 }

2094

2095 std::vector<int> slack_exact_lower_bound_ct(path_size - 1, -1);

2096 std::vector<int> slack_linear_lower_bound_ct(path_size - 1, -1);

2097

2098 const int64_t vehicle_start_min = current_route_min_cumuls_.front();

2099 const int64_t vehicle_start_max = current_route_max_cumuls_.front();

2100 const int64_t vehicle_end_min = current_route_min_cumuls_.back();

2101 const int64_t vehicle_end_max = current_route_max_cumuls_.back();

2102 const int all_break_variables_offset =

2103 vehicle_to_all_break_variables_offset_[vehicle];

2104 for (int br = 0; br < num_breaks; ++br) {

2105 const IntervalVar& break_var = *breaks[br];

2106 if (!break_var.MustBePerformed()) continue;

2107 const int64_t break_start_min = CapSub(break_var.StartMin(), cumul_offset);

2108 const int64_t break_start_max = CapSub(break_var.StartMax(), cumul_offset);

2109 const int64_t break_end_min = CapSub(break_var.EndMin(), cumul_offset);

2110 const int64_t break_end_max = CapSub(break_var.EndMax(), cumul_offset);

2111 const int64_t break_duration_min = break_var.DurationMin();

2112 const int64_t break_duration_max = break_var.DurationMax();

2113

2114

2115 if (solver->IsCPSATSolver()) {

2116 if (break_end_max <= vehicle_start_min ||

2117 vehicle_end_max <= break_start_min) {

2118 all_break_variables_[all_break_variables_offset + 2 * br] = -1;

2119 all_break_variables_[all_break_variables_offset + 2 * br + 1] = -1;

2120 current_route_break_variables_.push_back(-1);

2121 current_route_break_variables_.push_back(-1);

2122 continue;

2123 }

2124 lp_breaks[br] = {

2125 .start = solver->AddVariable(break_start_min, break_start_max),

2126 .end = solver->AddVariable(break_end_min, break_end_max),

2127 .duration =

2128 solver->AddVariable(break_duration_min, break_duration_max)};

2129 const auto [break_start, break_end, break_duration] = lp_breaks[br];

2131 absl::StrFormat("lp_break_start(%ld)", br));

2133 absl::StrFormat("lp_break_end(%ld)", br));

2135 absl::StrFormat("lp_break_duration(%ld)", br));

2136

2137 solver->AddLinearConstraint(

2138 0, 0, {{break_end, 1}, {break_start, -1}, {break_duration, -1}});

2139

2140 all_break_variables_[all_break_variables_offset + 2 * br] = break_start;

2141 all_break_variables_[all_break_variables_offset + 2 * br + 1] = break_end;

2142 current_route_break_variables_.push_back(break_start);

2143 current_route_break_variables_.push_back(break_end);

2144 } else {

2145 if (break_end_min <= vehicle_start_max ||

2146 vehicle_end_min <= break_start_max) {

2147 all_break_variables_[all_break_variables_offset + 2 * br] = -1;

2148 all_break_variables_[all_break_variables_offset + 2 * br + 1] = -1;

2149 current_route_break_variables_.push_back(-1);

2150 current_route_break_variables_.push_back(-1);

2151 continue;

2152 }

2153 }

2154

2155

2156

2157

2158 const int break_in_one_slack_ct = solver->CreateNewConstraint(1, 1);

2159

2160 if (solver->IsCPSATSolver()) {

2161

2162 if (break_end_min <= vehicle_start_max) {

2163 const int ct = solver->AddLinearConstraint(

2164 0, kint64max, {{lp_cumuls.front(), 1}, {lp_breaks[br].end, -1}});

2165 const int break_is_before_route = solver->AddVariable(0, 1);

2167 solver, break_is_before_route,

2168 absl::StrFormat("break_is_before_route(%ld)", br));

2169 solver->SetEnforcementLiteral(ct, break_is_before_route);

2170 solver->SetCoefficient(break_in_one_slack_ct, break_is_before_route, 1);

2171 }

2172

2173 if (vehicle_end_min <= break_start_max) {

2174 const int ct = solver->AddLinearConstraint(

2175 0, kint64max, {{lp_breaks[br].start, 1}, {lp_cumuls.back(), -1}});

2176 const int break_is_after_route = solver->AddVariable(0, 1);

2178 solver, break_is_after_route,

2179 absl::StrFormat("break_is_after_route(%ld)", br));

2180 solver->SetEnforcementLiteral(ct, break_is_after_route);

2181 solver->SetCoefficient(break_in_one_slack_ct, break_is_after_route, 1);

2182 }

2183 }

2184

2185

2186 for (int pos = 0; pos < path_size - 1; ++pos) {

2187

2188

2189 const int64_t slack_start_min =

2190 CapAdd(current_route_min_cumuls_[pos], pre_travel[pos]);

2191 if (slack_start_min > break_start_max) break;

2192 const int64_t slack_end_max =

2193 CapSub(current_route_max_cumuls_[pos + 1], post_travel[pos]);

2194 if (break_end_min > slack_end_max) continue;

2195 const int64_t slack_duration_max =

2196 std::min(CapSub(CapSub(current_route_max_cumuls_[pos + 1],

2197 current_route_min_cumuls_[pos]),

2198 fixed_transit[pos]),

2199 dimension_->SlackVar(path[pos])->Max());

2200 if (slack_duration_max < break_duration_min) continue;

2201

2202

2203

2204

2205

2206

2207 const int break_in_slack = solver->AddVariable(0, 1);

2209 solver, break_in_slack,

2210 absl::StrFormat("break_in_slack(%ld, %ld)", br, pos));

2211 if (slack_linear_lower_bound_ct[pos] == -1) {

2212 slack_linear_lower_bound_ct[pos] =

2213 solver->AddLinearConstraint(kint64min, 0, {{lp_slacks[pos], -1}});

2214 }

2215

2216

2217

2218 if (break_in_one_slack_ct < slack_linear_lower_bound_ct[pos]) {

2219 solver->SetCoefficient(break_in_one_slack_ct, break_in_slack, 1);

2220 solver->SetCoefficient(slack_linear_lower_bound_ct[pos], break_in_slack,

2221 break_duration_min);

2222 } else {

2223 solver->SetCoefficient(slack_linear_lower_bound_ct[pos], break_in_slack,

2224 break_duration_min);

2225 solver->SetCoefficient(break_in_one_slack_ct, break_in_slack, 1);

2226 }

2227

2228 if (solver->IsCPSATSolver()) {

2229

2230

2231

2232

2233 const int break_duration_in_slack =

2234 solver->AddVariable(0, slack_duration_max);

2236 solver, break_duration_in_slack,

2237 absl::StrFormat("break_duration_in_slack(%ld, %ld)", br, pos));

2238 solver->AddProductConstraint(break_duration_in_slack,

2239 {break_in_slack, lp_breaks[br].duration});

2240 if (slack_exact_lower_bound_ct[pos] == -1) {

2241 slack_exact_lower_bound_ct[pos] =

2242 solver->AddLinearConstraint(kint64min, 0, {{lp_slacks[pos], -1}});

2243 }

2244 solver->SetCoefficient(slack_exact_lower_bound_ct[pos],

2245 break_duration_in_slack, 1);

2246

2247

2248 const int break_start_after_current_ct = solver->AddLinearConstraint(

2250 {{lp_breaks[br].start, 1}, {lp_cumuls[pos], -1}});

2251 solver->SetEnforcementLiteral(break_start_after_current_ct,

2252 break_in_slack);

2253

2254 const int break_ends_before_next_ct = solver->AddLinearConstraint(

2256 {{lp_cumuls[pos + 1], 1}, {lp_breaks[br].end, -1}});

2257 solver->SetEnforcementLiteral(break_ends_before_next_ct,

2258 break_in_slack);

2259 }

2260 }

2261 }

2262

2263 for (const auto& distance_duration :

2264 dimension_->GetBreakDistanceDurationOfVehicle(vehicle)) {

2265 const int64_t limit = distance_duration.first;

2266 const int64_t min_break_duration = distance_duration.second;

2267 int64_t min_num_breaks = 0;

2268 if (limit > 0) {

2269 min_num_breaks =

2270 std::max<int64_t>(0, CapSub(total_fixed_transit, 1) / limit);

2271 }

2272 if (CapSub(current_route_min_cumuls_.back(),

2273 current_route_max_cumuls_.front()) > limit) {

2274 min_num_breaks = std::max<int64_t>(min_num_breaks, 1);

2275 }

2276 if (num_breaks < min_num_breaks) return false;

2277 if (min_num_breaks == 0) continue;

2278

2279

2280

2281

2282

2283

2284

2285

2286

2287

2288

2289

2290

2291

2292

2293

2294

2295

2296

2297

2298

2299 std::vector<int64_t> sum_transits(path_size);

2300 {

2301 sum_transits[0] = 0;

2302 for (int pos = 1; pos < path_size; ++pos) {

2303 sum_transits[pos] = sum_transits[pos - 1] + fixed_transit[pos - 1];

2304 }

2305 }

2306

2307

2308

2309

2310 std::vector<int> slack_sum_vars(path_size, -1);

2311

2312

2313

2314

2315 auto trigger = [&](int k, int pl, int pr) -> bool {

2316 const int64_t r_pre_travel = pr < path_size - 1 ? pre_travel[pr] : 0;

2317 const int64_t l_post_travel = pl >= 1 ? post_travel[pl - 1] : 0;

2318 const int64_t extra_travel = CapAdd(r_pre_travel, l_post_travel);

2319 if (k == 1) {

2320 const int64_t span_lb = CapAdd(CapSub(current_route_min_cumuls_[pr],

2321 current_route_max_cumuls_[pl]),

2322 extra_travel);

2323 if (span_lb > limit) return true;

2324 }

2325 return CapAdd(CapSub(sum_transits[pr], sum_transits[pl]), extra_travel) >

2327 };

2328 int min_sum_var_index = path_size;

2329 int max_sum_var_index = -1;

2330 for (int k = 1; k <= min_num_breaks; ++k) {

2331 int pr = 0;

2332 for (int pl = 0; pl < path_size - 1; ++pl) {

2333 pr = std::max(pr, pl + 1);

2334

2335 while (pr < path_size && !trigger(k, pl, pr)) ++pr;

2336 if (pr == path_size) break;

2337

2338 while (pl < pr && trigger(k, pl + 1, pr)) ++pl;

2339

2340

2341 if (pl == pr) return false;

2342

2343

2344

2345

2346 if (k < min_num_breaks && trigger(k + 1, pl, pr)) continue;

2347

2348

2349

2350 if (solver->IsCPSATSolver()) {

2351

2352

2353 solver->AddLinearConstraint(

2354 CapAdd(CapSub(sum_transits[pr], sum_transits[pl]),

2355 CapProd(k, min_break_duration)),

2356 kint64max, {{lp_cumuls[pr], 1}, {lp_cumuls[pl], -1}});

2357 } else {

2358 if (slack_sum_vars[pl] == -1) {

2359 slack_sum_vars[pl] = solver->CreateNewPositiveVariable();

2361 absl::StrFormat("slack_sum_vars(%ld)", pl));

2362 min_sum_var_index = std::min(min_sum_var_index, pl);

2363 }

2364 if (slack_sum_vars[pr] == -1) {

2365 slack_sum_vars[pr] = solver->CreateNewPositiveVariable();

2367 absl::StrFormat("slack_sum_vars(%ld)", pr));

2368 max_sum_var_index = std::max(max_sum_var_index, pr);

2369 }

2370

2371 solver->AddLinearConstraint(

2373 {{slack_sum_vars[pr], 1}, {slack_sum_vars[pl], -1}});

2374 }

2375 }

2376 }

2377 if (min_sum_var_index < max_sum_var_index) {

2378 slack_sum_vars[min_sum_var_index] = solver->AddVariable(0, 0);

2379 int prev_index = min_sum_var_index;

2380 for (int pos = min_sum_var_index + 1; pos <= max_sum_var_index; ++pos) {

2381 if (slack_sum_vars[pos] == -1) continue;

2382

2383

2384 const int ct = solver->AddLinearConstraint(

2385 0, 0, {{slack_sum_vars[pos], 1}, {slack_sum_vars[prev_index], -1}});

2386 for (int p = prev_index; p < pos; ++p) {

2387 solver->SetCoefficient(ct, lp_slacks[p], -1);

2388 }

2389 prev_index = pos;

2390 }

2391 }

2392 }

2393 if (!solver->IsCPSATSolver()) return true;

2394 if (!dimension_->GetBreakDistanceDurationOfVehicle(vehicle).empty()) {

2395

2396

2397 for (const IntervalVar* interval :

2398 dimension_->GetBreakIntervalsOfVehicle(vehicle)) {

2399 if (!interval->MustBePerformed()) return true;

2400 }

2401

2402 for (int br = 1; br < num_breaks; ++br) {

2403 if (lp_breaks[br].start == -1 || lp_breaks[br - 1].start == -1) continue;

2404 solver->AddLinearConstraint(

2406 {{lp_breaks[br - 1].end, -1}, {lp_breaks[br].start, 1}});

2407 }

2408 }

2409 for (const auto& distance_duration :

2410 dimension_->GetBreakDistanceDurationOfVehicle(vehicle)) {

2411 const int64_t limit = distance_duration.first;

2412 const int64_t min_break_duration = distance_duration.second;

2413

2414

2415

2416

2417

2418

2419

2420

2421

2422

2423

2424

2425

2426

2427

2428

2429

2430

2431

2432

2433

2434

2435

2436

2437

2438

2439

2440 int previous_cover = solver->AddVariable(CapAdd(vehicle_start_min, limit),

2441 CapAdd(vehicle_start_max, limit));

2443 solver->AddLinearConstraint(limit, limit,

2444 {{previous_cover, 1}, {lp_cumuls.front(), -1}});

2445 for (int br = 0; br < num_breaks; ++br) {

2446 const LpBreak& lp_break = lp_breaks[br];

2447 if (lp_break.start == -1) continue;

2448 const int64_t break_end_min = CapSub(breaks[br]->EndMin(), cumul_offset);

2449 const int64_t break_end_max = CapSub(breaks[br]->EndMax(), cumul_offset);

2450

2451

2452 const int break_is_eligible = solver->AddVariable(0, 1);

2454 absl::StrFormat("break_is_eligible(%ld)", br));

2455 const int break_is_not_eligible = solver->AddVariable(0, 1);

2457 solver, break_is_not_eligible,

2458 absl::StrFormat("break_is_not_eligible(%ld)", br));

2459 {

2460 solver->AddLinearConstraint(

2461 1, 1, {{break_is_eligible, 1}, {break_is_not_eligible, 1}});

2462 const int positive_ct = solver->AddLinearConstraint(

2464 {{lp_break.end, 1}, {lp_break.start, -1}});

2465 solver->SetEnforcementLiteral(positive_ct, break_is_eligible);

2466 const int negative_ct = solver->AddLinearConstraint(

2467 kint64min, min_break_duration - 1,

2468 {{lp_break.end, 1}, {lp_break.start, -1}});

2469 solver->SetEnforcementLiteral(negative_ct, break_is_not_eligible);

2470 }

2471

2472

2473

2474

2475

2476 const int break_cover = solver->AddVariable(

2477 CapAdd(std::min(vehicle_start_min, break_end_min), limit),

2478 CapAdd(std::max(vehicle_start_min, break_end_max), limit));

2480 absl::StrFormat("break_cover(%ld)", br));

2481 const int limit_cover_ct = solver->AddLinearConstraint(

2482 limit, limit, {{break_cover, 1}, {lp_break.end, -1}});

2483 solver->SetEnforcementLiteral(limit_cover_ct, break_is_eligible);

2484 const int empty_cover_ct = solver->AddLinearConstraint(

2485 CapAdd(vehicle_start_min, limit), CapAdd(vehicle_start_min, limit),

2486 {{break_cover, 1}});

2487 solver->SetEnforcementLiteral(empty_cover_ct, break_is_not_eligible);

2488

2489 const int cover =

2490 solver->AddVariable(CapAdd(vehicle_start_min, limit), kint64max);

2492 solver->AddMaximumConstraint(cover, {previous_cover, break_cover});

2493

2494

2495 const int route_end_is_not_covered = solver->AddReifiedLinearConstraint(

2496 1, kint64max, {{lp_cumuls.back(), 1}, {previous_cover, -1}});

2497 const int break_start_cover_ct = solver->AddLinearConstraint(

2498 0, kint64max, {{previous_cover, 1}, {lp_break.start, -1}});

2499 solver->SetEnforcementLiteral(break_start_cover_ct,

2500 route_end_is_not_covered);

2501

2502 previous_cover = cover;

2503 }

2504 solver->AddLinearConstraint(0, kint64max,

2505 {{previous_cover, 1}, {lp_cumuls.back(), -1}});

2506 }

2507

2508 return true;

2509}

2510

2511void DimensionCumulOptimizerCore::SetRouteCumulCosts(

2512 int vehicle, int64_t cumul_offset, int64_t total_fixed_transit,

2514 int64_t* route_cost_offset) {

2515 const std::vector<int>& lp_cumuls = current_route_cumul_variables_;

2516 const std::vector<int64_t>& path = current_route_nodes_;

2517 const int path_size = path.size();

2518

2519 for (int pos = 0; pos < path_size; ++pos) {

2520 const int64_t node = path[pos];

2521 if (!dimension_->HasCumulVarSoftUpperBound(node)) continue;

2522 const int64_t coef = dimension_->GetCumulVarSoftUpperBoundCoefficient(node);

2523 if (coef == 0) continue;

2524 int64_t bound = dimension_->GetCumulVarSoftUpperBound(node);

2525 if (bound < cumul_offset && route_cost_offset != nullptr) {

2526

2527 *route_cost_offset = CapAdd(*route_cost_offset,

2529 }

2530 bound = std::max<int64_t>(0, CapSub(bound, cumul_offset));

2531 if (current_route_max_cumuls_[pos] <= bound) {

2532

2533 continue;

2534 }

2535 const int soft_ub_diff = solver->CreateNewPositiveVariable();

2537 absl::StrFormat("soft_ub_diff(%ld)", pos));

2538 solver->SetObjectiveCoefficient(soft_ub_diff, coef);

2539

2540 const int ct = solver->CreateNewConstraint(kint64min, bound);

2541 solver->SetCoefficient(ct, lp_cumuls[pos], 1);

2542 solver->SetCoefficient(ct, soft_ub_diff, -1);

2543 }

2544

2545 for (int pos = 0; pos < path_size; ++pos) {

2546 const int64_t node = path[pos];

2547 if (!dimension_->HasCumulVarSoftLowerBound(node)) continue;

2548 const int64_t coef = dimension_->GetCumulVarSoftLowerBoundCoefficient(node);

2549 if (coef == 0) continue;

2550 const int64_t bound = std::max<int64_t>(

2551 0, CapSub(dimension_->GetCumulVarSoftLowerBound(node), cumul_offset));

2552 if (current_route_min_cumuls_[pos] >= bound) {

2553

2554 continue;

2555 }

2556 const int soft_lb_diff = solver->CreateNewPositiveVariable();

2558 absl::StrFormat("soft_lb_diff(%ld)", pos));

2559 solver->SetObjectiveCoefficient(soft_lb_diff, coef);

2560

2561 const int ct = solver->CreateNewConstraint(bound, kint64max);

2562 solver->SetCoefficient(ct, lp_cumuls[pos], 1);

2563 solver->SetCoefficient(ct, soft_lb_diff, 1);

2564 }

2565

2566

2567

2568

2569 const int64_t span_cost_coef =

2570 dimension_->GetSpanCostCoefficientForVehicle(vehicle);

2571 const int64_t slack_cost_coef = CapAdd(

2572 span_cost_coef, dimension_->GetSlackCostCoefficientForVehicle(vehicle));

2573 if (slack_cost_coef > 0) {

2574

2575

2576 const int span_without_fixed_transit_var =

2577 solver->CreateNewPositiveVariable();

2579 "span_without_fixed_transit_var");

2580 solver->AddLinearConstraint(total_fixed_transit, total_fixed_transit,

2581 {{lp_cumuls.back(), 1},

2582 {lp_cumuls.front(), -1},

2583 {span_without_fixed_transit_var, -1}});

2584 solver->SetObjectiveCoefficient(span_without_fixed_transit_var,

2585 slack_cost_coef);

2586 }

2587

2588 if (dimension_->HasSoftSpanUpperBounds()) {

2589 const BoundCost bound_cost =

2590 dimension_->GetSoftSpanUpperBoundForVehicle(vehicle);

2591 if (bound_cost.bound < kint64max && bound_cost.cost > 0) {

2592 const int span_violation = solver->CreateNewPositiveVariable();

2594

2595 const int violation =

2596 solver->CreateNewConstraint(kint64min, bound_cost.bound);

2597 solver->SetCoefficient(violation, lp_cumuls.back(), 1.0);

2598 solver->SetCoefficient(violation, lp_cumuls.front(), -1.0);

2599 solver->SetCoefficient(violation, span_violation, -1.0);

2600

2601 solver->SetObjectiveCoefficient(span_violation, bound_cost.cost);

2602 }

2603 }

2604 if (solver->IsCPSATSolver() &&

2605 dimension_->HasQuadraticCostSoftSpanUpperBounds()) {

2606

2607 const BoundCost bound_cost =

2608 dimension_->GetQuadraticCostSoftSpanUpperBoundForVehicle(vehicle);

2609 if (bound_cost.bound < kint64max && bound_cost.cost > 0) {

2610 const int span_violation = solver->CreateNewPositiveVariable();

2612 solver, span_violation,

2613 absl::StrFormat("quadratic_span_violation(%ld)", vehicle));

2614

2615 const int violation =

2616 solver->CreateNewConstraint(kint64min, bound_cost.bound);

2617 solver->SetCoefficient(violation, lp_cumuls.back(), 1.0);

2618 solver->SetCoefficient(violation, lp_cumuls.front(), -1.0);

2619 solver->SetCoefficient(violation, span_violation, -1.0);

2620

2621 const int squared_span_violation = solver->CreateNewPositiveVariable();

2623 solver, squared_span_violation,

2624 absl::StrFormat("squared_span_violation(%ld)", vehicle));

2625 solver->AddProductConstraint(squared_span_violation,

2626 {span_violation, span_violation});

2627

2628 solver->SetObjectiveCoefficient(squared_span_violation, bound_cost.cost);

2629 }

2630 }

2631

2632 if (dimension_->global_span_cost_coefficient() > 0) {

2633

2634 int ct = solver->CreateNewConstraint(kint64min, 0);

2635 solver->SetCoefficient(ct, min_start_cumul_, 1);

2636 solver->SetCoefficient(ct, lp_cumuls.front(), -1);

2637

2638 ct = solver->CreateNewConstraint(0, kint64max);

2639 solver->SetCoefficient(ct, max_end_cumul_, 1);

2640 solver->SetCoefficient(ct, lp_cumuls.back(), -1);

2641 }

2642

2643 if (route_transit_cost != nullptr) {

2644 if (span_cost_coef > 0) {

2645 *route_transit_cost = CapProd(total_fixed_transit, span_cost_coef);

2646 } else {

2647 *route_transit_cost = 0;

2648 }

2649 }

2650}

2651

2652namespace {

2653bool AllValuesContainedExcept(const IntVar& var, absl::Span<const int> values,

2654 const absl::flat_hash_set<int>& ignored_values) {

2655 for (int val : values) {

2656 if (!ignored_values.contains(val) && !var.Contains(val)) return false;

2657 }

2658 return true;

2659}

2660}

2661

2662bool DimensionCumulOptimizerCore::SetGlobalConstraints(

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

2664 bool optimize_costs, bool optimize_resource_assignment,

2666

2667

2668 const int64_t global_span_coeff = dimension_->global_span_cost_coefficient();

2669 if (optimize_costs && global_span_coeff > 0) {

2670

2671 const int global_span_var = solver->CreateNewPositiveVariable();

2673 solver->AddLinearConstraint(

2674 0, 0,

2675 {{global_span_var, 1}, {max_end_cumul_, -1}, {min_start_cumul_, 1}});

2676

2677

2678

2679

2680 solver->SetObjectiveCoefficient(global_span_var, global_span_coeff);

2681 }

2682

2683

2684 for (const auto [first_node, second_node, offset, performed_constraint] :

2685 dimension_->GetNodePrecedences()) {

2686 if (next_accessor(first_node) == -1 || next_accessor(second_node) == -1) {

2687 continue;

2688 }

2689 const int first_cumul_var = index_to_cumul_variable_[first_node];

2690 const int second_cumul_var = index_to_cumul_variable_[second_node];

2692 first_cumul_var < 0, second_cumul_var < 0, performed_constraint)) {

2694 break;

2696 continue;

2698 return false;

2699 }

2700 DCHECK_NE(first_cumul_var, second_cumul_var)

2701 << "Dimension " << dimension_->name()

2702 << " has a self-precedence on node " << first_node << ".";

2703

2704

2705 const int ct = solver->CreateNewConstraint(offset, kint64max);

2706 solver->SetCoefficient(ct, second_cumul_var, 1);

2707 solver->SetCoefficient(ct, first_cumul_var, -1);

2708 }

2709

2710 if (optimize_resource_assignment &&

2711 !SetGlobalConstraintsForResourceAssignment(next_accessor, cumul_offset,

2712 solver)) {

2713 return false;

2714 }

2715 return true;

2716}

2717

2718bool DimensionCumulOptimizerCore::SetGlobalConstraintsForResourceAssignment(

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

2721 if (!solver->IsCPSATSolver()) {

2722

2723

2724 return true;

2725 }

2726

2728 const RoutingModel& model = *dimension_->model();

2729 const int num_vehicles = model.vehicles();

2730 const auto& resource_groups = model.GetResourceGroups();

2731 for (int rg_index : model.GetDimensionResourceGroupIndices(dimension_)) {

2732

2733

2734

2735

2736

2737

2738

2739

2740

2741

2742

2743 const ResourceGroup& resource_group = *resource_groups[rg_index];

2744 DCHECK(!resource_group.GetVehiclesRequiringAResource().empty());

2745

2747 int num_required_resources = 0;

2748

2749

2750 std::vector<int> vehicle_constraints(model.vehicles(), kNoConstraint);

2751 const int num_resource_classes = resource_group.GetResourceClassesCount();

2752 std::vector<absl::flat_hash_set<int>>& ignored_resources_per_class =

2753 resource_class_ignored_resources_per_group_[rg_index];

2754 ignored_resources_per_class.assign(num_resource_classes, {});

2755 for (int v : resource_group.GetVehiclesRequiringAResource()) {

2756 const IntVar& resource_var = *model.ResourceVar(v, rg_index);

2757 if (model.IsEnd(next_accessor(model.Start(v))) &&

2758 !model.IsVehicleUsedWhenEmpty(v)) {

2759 if (resource_var.Bound() && resource_var.Value() >= 0) {

2760

2761 return false;

2762 }

2763

2764 continue;

2765 }

2766

2767 if (resource_var.Bound()) {

2768 const int resource_index = resource_var.Value();

2769 if (resource_index < 0) {

2770

2771 return false;

2772 }

2773 ignored_resources_per_class

2774 [resource_group.GetResourceClassIndex(resource_index).value()]

2775 .insert(resource_index);

2776

2777 const int start_index = index_to_cumul_variable_[model.Start(v)];

2778 const int end_index = index_to_cumul_variable_[model.End(v)];

2779 if (!TightenStartEndVariableBoundsWithResource(

2780 *dimension_, resource_group.GetResource(resource_index),

2781 GetVariableBounds(start_index, *solver), start_index,

2782 GetVariableBounds(end_index, *solver), end_index, cumul_offset,

2783 solver)) {

2784 return false;

2785 }

2786 continue;

2787 }

2788 num_required_resources++;

2789 vehicle_constraints[v] = solver->CreateNewConstraint(1, 1);

2790 }

2791

2792

2793

2794 std::vector<int> resource_class_cstrs(num_resource_classes, kNoConstraint);

2795 int num_available_resources = 0;

2796 for (RCIndex rc_index(0); rc_index < num_resource_classes; rc_index++) {

2797 const ResourceGroup::Attributes& attributes =

2798 resource_group.GetDimensionAttributesForClass(dimension_->index(),

2799 rc_index);

2800 if (attributes.start_domain().Max() < cumul_offset ||

2801 attributes.end_domain().Max() < cumul_offset) {

2802

2803

2804

2805 continue;

2806 }

2807 const int rc = rc_index.value();

2808 const int num_available_class_resources =

2809 resource_group.GetResourceIndicesInClass(rc_index).size() -

2810 ignored_resources_per_class[rc].size();

2811 DCHECK_GE(num_available_class_resources, 0);

2812 if (num_available_class_resources > 0) {

2813 num_available_resources += num_available_class_resources;

2814 resource_class_cstrs[rc] =

2815 solver->CreateNewConstraint(0, num_available_class_resources);

2816 }

2817 }

2818

2819 if (num_required_resources > num_available_resources) {

2820

2821

2822 return false;

2823 }

2824

2825 std::vector<int>& resource_class_to_vehicle_assignment_vars =

2826 resource_class_to_vehicle_assignment_variables_per_group_[rg_index];

2827 resource_class_to_vehicle_assignment_vars.assign(

2828 num_resource_classes * num_vehicles, -1);

2829

2830

2831

2832

2833

2834 DCHECK_EQ(resource_group.Index(), rg_index);

2835 for (int v : resource_group.GetVehiclesRequiringAResource()) {

2836 if (vehicle_constraints[v] == kNoConstraint) continue;

2837 IntVar* const resource_var = model.ResourceVar(v, rg_index);

2838 std::unique_ptr<IntVarIterator> it(

2839 resource_var->MakeDomainIterator(false));

2840 std::vector<bool> resource_class_considered(num_resource_classes, false);

2841 for (int r : InitAndGetValues(it.get())) {

2842 if (r < 0) continue;

2843 const RCIndex rc_index = resource_group.GetResourceClassIndex(r);

2844 const int rc = rc_index.value();

2845 if (resource_class_considered[rc]) {

2846 continue;

2847 }

2848 resource_class_considered[rc] = true;

2849 if (resource_class_cstrs[rc] == kNoConstraint) continue;

2850

2851

2852

2853

2854

2855 DCHECK(AllValuesContainedExcept(

2856 *resource_var, resource_group.GetResourceIndicesInClass(rc_index),

2857 ignored_resources_per_class[rc]))

2859 resource_group.GetResourceIndicesInClass(rc_index),

2860 resource_var->Min(), resource_var->Max());

2861

2862 const int assign_rc_to_v = solver->AddVariable(0, 1);

2864 solver, assign_rc_to_v,

2865 absl::StrFormat("assign_rc_to_v(%ld, %ld)", rc, v));

2866 resource_class_to_vehicle_assignment_vars[rc * num_vehicles + v] =

2867 assign_rc_to_v;

2868

2869

2870

2871 DCHECK_LT(vehicle_constraints[v], resource_class_cstrs[rc]);

2872 solver->SetCoefficient(vehicle_constraints[v], assign_rc_to_v, 1);

2873 solver->SetCoefficient(resource_class_cstrs[rc], assign_rc_to_v, 1);

2874

2875 const auto& add_domain_constraint =

2876 [&solver, cumul_offset, assign_rc_to_v](const Domain& domain,

2877 int cumul_variable) {

2879 return;

2880 }

2881 ClosedInterval cumul_bounds;

2882 if (!GetDomainOffsetBounds(domain, cumul_offset, &cumul_bounds)) {

2883

2884 solver->SetVariableBounds(assign_rc_to_v, 0, 0);

2885 return;

2886 }

2887 const int cumul_constraint = solver->AddLinearConstraint(

2888 cumul_bounds.start, cumul_bounds.end, {{cumul_variable, 1}});

2889 solver->SetEnforcementLiteral(cumul_constraint, assign_rc_to_v);

2890 };

2891 const ResourceGroup::Attributes& attributes =

2892 resource_group.GetDimensionAttributesForClass(dimension_->index(),

2893 rc_index);

2894 add_domain_constraint(attributes.start_domain(),

2895 index_to_cumul_variable_[model.Start(v)]);

2896 add_domain_constraint(attributes.end_domain(),

2897 index_to_cumul_variable_[model.End(v)]);

2898 }

2899 }

2900 }

2901 return true;

2902}

2903

2904#undef SET_DEBUG_VARIABLE_NAME

2905

2906void DimensionCumulOptimizerCore::SetValuesFromLP(

2907 absl::Span<const int> lp_variables, int64_t offset, int64_t default_value,

2908 RoutingLinearSolverWrapper* solver, std::vector<int64_t>* lp_values) const {

2909 if (lp_values == nullptr) return;

2910 lp_values->assign(lp_variables.size(), default_value);

2911 for (int i = 0; i < lp_variables.size(); i++) {

2912 const int lp_var = lp_variables[i];

2913 if (lp_var < 0) continue;

2914 (*lp_values)[i] = CapAdd(solver->GetVariableValue(lp_var), offset);

2915 }

2916}

2917

2918void DimensionCumulOptimizerCore::SetResourceIndices(

2919 RoutingLinearSolverWrapper* solver,

2920 std::vector<std::vector<int>>* resource_indices_per_group) const {

2921 if (resource_indices_per_group == nullptr ||

2922 resource_class_to_vehicle_assignment_variables_per_group_.empty()) {

2923 return;

2924 }

2925 using RCIndex = RoutingModel::ResourceClassIndex;

2926 const RoutingModel& model = *dimension_->model();

2927 const int num_vehicles = model.vehicles();

2928 DCHECK(!model.GetDimensionResourceGroupIndices(dimension_).empty());

2929 const auto& resource_groups = model.GetResourceGroups();

2930 resource_indices_per_group->resize(resource_groups.size());

2931 for (int rg_index : model.GetDimensionResourceGroupIndices(dimension_)) {

2932 const ResourceGroup& resource_group = *resource_groups[rg_index];

2933 DCHECK(!resource_group.GetVehiclesRequiringAResource().empty());

2934

2936 resource_indices_per_class =

2937 resource_group.GetResourceIndicesPerClass();

2938 const int num_resource_classes = resource_group.GetResourceClassesCount();

2939 std::vector<int> current_resource_pos_for_class(num_resource_classes, 0);

2940 std::vector<int>& resource_indices =

2941 resource_indices_per_group->at(rg_index);

2942 resource_indices.assign(num_vehicles, -1);

2943

2944 const std::vector<int>& resource_class_to_vehicle_assignment_vars =

2945 resource_class_to_vehicle_assignment_variables_per_group_[rg_index];

2946 DCHECK_EQ(resource_class_to_vehicle_assignment_vars.size(),

2947 num_resource_classes * num_vehicles);

2948 const std::vector<absl::flat_hash_set<int>>& ignored_resources_per_class =

2949 resource_class_ignored_resources_per_group_[rg_index];

2950 DCHECK_EQ(ignored_resources_per_class.size(), num_resource_classes);

2951 for (int v : resource_group.GetVehiclesRequiringAResource()) {

2952 const IntVar& resource_var = *model.ResourceVar(v, rg_index);

2953 if (resource_var.Bound()) {

2954 resource_indices[v] = resource_var.Value();

2955 continue;

2956 }

2957 for (int rc = 0; rc < num_resource_classes; rc++) {

2958 const int assignment_var =

2959 resource_class_to_vehicle_assignment_vars[rc * num_vehicles + v];

2960 if (assignment_var >= 0 &&

2961 solver->GetVariableValue(assignment_var) == 1) {

2962

2963 const std::vector<int>& class_resource_indices =

2964 resource_indices_per_class[RCIndex(rc)];

2965 int& pos = current_resource_pos_for_class[rc];

2966 while (ignored_resources_per_class[rc].contains(

2967 class_resource_indices[pos])) {

2968 pos++;

2969 DCHECK_LT(pos, class_resource_indices.size());

2970 }

2971 resource_indices[v] = class_resource_indices[pos++];

2972 break;

2973 }

2974 }

2975 }

2976 }

2977}

2978

2979

2980

3005

3014

3026

3036

3037namespace {

3038

3039template <typename T>

3040void MoveValuesToIndicesFrom(std::vector<T>* out_values,

3041 absl::Span<const int> out_indices_to_evaluate,

3042 const std::function<int(int)>& index_evaluator,

3043 std::vector<T>& values_to_copy) {

3044 if (out_values == nullptr) {

3045 DCHECK(values_to_copy.empty());

3046 return;

3047 }

3048 DCHECK_EQ(values_to_copy.size(), out_indices_to_evaluate.size());

3049 for (int i = 0; i < out_indices_to_evaluate.size(); i++) {

3050 const int output_index = index_evaluator(out_indices_to_evaluate[i]);

3051 DCHECK_LT(output_index, out_values->size());

3052 out_values->at(output_index) = std::move(values_to_copy[i]);

3053 }

3054}

3055

3056}

3057

3206

3391

3397

3428

3445

3475

3522

3727

3728}