32#include "absl/algorithm/container.h"
33#include "absl/cleanup/cleanup.h"
34#include "absl/container/flat_hash_map.h"
35#include "absl/container/flat_hash_set.h"
36#include "absl/flags/flag.h"
37#include "absl/log/check.h"
38#include "absl/log/log.h"
39#include "absl/log/vlog_is_on.h"
40#include "absl/numeric/bits.h"
41#include "absl/numeric/int128.h"
42#include "absl/random/distributions.h"
43#include "absl/strings/str_cat.h"
44#include "absl/types/span.h"
53#include "ortools/sat/cp_model.pb.h"
62#include "ortools/sat/routes_support_graph.pb.h"
64#include "ortools/sat/sat_parameters.pb.h"
69ABSL_FLAG(
bool, cp_model_dump_routes_support_graphs,
false,
70 "DEBUG ONLY. When set to true, SolveCpModel() dumps the arcs with "
71 "non-zero LP values of the routes constraints, at decision level 0, "
72 "which are used to subsequently generate cuts. The values are "
73 "written as a SupportGraphProto in text format to "
74 "'FLAGS_cp_model_dump_prefix'support_graph_{counter}.pb.txt.");
93void ComputeMinLowerBoundOfSharedVariables(
94 const absl::flat_hash_map<IntegerVariable, IntegerValue>& new_lbs,
95 absl::flat_hash_map<IntegerVariable, IntegerValue>* current_lbs) {
96 if (new_lbs.empty()) current_lbs->clear();
97 for (
auto it = current_lbs->begin(); it != current_lbs->end();) {
98 const IntegerVariable var = it->first;
99 auto other_it = new_lbs.find(var);
100 if (other_it == new_lbs.end()) {
105 current_lbs->erase(it++);
108 it->second = std::min(it->second, other_it->second);
117 int num_nodes,
const std::vector<int>& tails,
const std::vector<int>& heads,
118 const std::vector<Literal>& literals,
Model* model)
122 binary_relation_repository_(
124 trail_(*model->GetOrCreate<
Trail>()),
128 in_subset_(num_nodes, false),
129 index_in_subset_(num_nodes, -1),
130 incoming_arc_indices_(num_nodes),
131 outgoing_arc_indices_(num_nodes),
132 reachable_(num_nodes, false),
133 next_reachable_(num_nodes, false),
134 node_var_lower_bounds_(num_nodes),
135 next_node_var_lower_bounds_(num_nodes),
137 model->GetOrCreate<SatParameters>()->routing_cut_dp_effort()) {}
140 if (!VLOG_IS_ON(1))
return;
141 std::vector<std::pair<std::string, int64_t>> stats;
142 stats.push_back({
"RoutingDp/num_full_dp_calls", num_full_dp_calls_});
143 stats.push_back({
"RoutingDp/num_full_dp_skips", num_full_dp_skips_});
145 {
"RoutingDp/num_full_dp_early_abort", num_full_dp_early_abort_});
147 {
"RoutingDp/num_full_dp_work_abort", num_full_dp_work_abort_});
148 stats.push_back({
"RoutingDp/num_full_dp_rc_skip", num_full_dp_rc_skip_});
150 {
"RoutingDp/num_full_dp_unique_arc", num_full_dp_unique_arc_});
151 for (
const auto& [name, count] : num_by_type_) {
152 stats.push_back({absl::StrCat(
"RoutingDp/num_bounds_", name), count});
154 shared_stats_->AddStats(stats);
159void MinOutgoingFlowHelper::PrecomputeDataForSubset(
160 absl::Span<const int> subset) {
161 cannot_be_first_.clear();
162 cannot_be_last_.clear();
164 const int num_nodes = in_subset_.size();
165 in_subset_.assign(num_nodes,
false);
166 index_in_subset_.assign(num_nodes, -1);
167 for (
int i = 0;
i < subset.size(); ++
i) {
168 const int n = subset[
i];
169 in_subset_[n] =
true;
170 index_in_subset_[n] =
i;
173 has_incoming_arcs_from_outside_.assign(num_nodes,
false);
174 has_outgoing_arcs_to_outside_.assign(num_nodes,
false);
175 incoming_arcs_from_outside_.assign(num_nodes, {});
176 outgoing_arcs_to_outside_.assign(num_nodes, {});
178 for (
auto& v : incoming_arc_indices_) v.clear();
179 for (
auto& v : outgoing_arc_indices_) v.clear();
180 for (
int i = 0;
i < tails_.size(); ++
i) {
181 const int tail = tails_[
i];
182 const int head = heads_[
i];
185 if (tail == head)
continue;
186 const bool tail_in = in_subset_[tail];
187 const bool head_in = in_subset_[head];
189 if (tail_in && head_in) {
190 outgoing_arc_indices_[tail].push_back(
i);
191 incoming_arc_indices_[head].push_back(
i);
192 }
else if (tail_in && !head_in) {
193 outgoing_arcs_to_outside_[tail].Add(
i);
194 has_outgoing_arcs_to_outside_[tail] =
true;
195 }
else if (!tail_in && head_in) {
196 incoming_arcs_from_outside_[head].Add(
i);
197 has_incoming_arcs_from_outside_[head] =
true;
205 PrecomputeDataForSubset(subset);
206 DCHECK_EQ(helper.
num_nodes(), in_subset_.size());
207 DCHECK_EQ(helper.
num_arcs(), tails_.size());
209 int min_outgoing_flow = 1;
210 std::string best_name;
212 for (
const bool negate_expressions : {
false,
true}) {
213 for (
const bool use_incoming : {
true,
false}) {
215 const absl::Span<SpecialBinPackingHelper::ItemOrBin> objects =
216 RelaxIntoSpecialBinPackingProblem(subset, d, negate_expressions,
217 use_incoming, helper);
218 const int bound = bin_packing_helper_.ComputeMinNumberOfBins(
219 objects, objects_that_cannot_be_bin_and_reach_minimum_, info);
220 if (bound >= min_outgoing_flow) {
221 min_outgoing_flow = bound;
222 best_name = absl::StrCat((use_incoming ?
"in" :
"out"), info,
223 (negate_expressions ?
"_neg" :
""),
"_", d);
224 cannot_be_first_.clear();
225 cannot_be_last_.clear();
226 auto& vec = use_incoming ? cannot_be_first_ : cannot_be_last_;
227 for (
const int i : objects_that_cannot_be_bin_and_reach_minimum_) {
228 vec.push_back(objects[
i].node);
230 best_bound->
Update(bound,
"AutomaticDimension", cannot_be_first_,
237 if (min_outgoing_flow > 1) num_by_type_[best_name]++;
238 return min_outgoing_flow;
241absl::Span<SpecialBinPackingHelper::ItemOrBin>
242MinOutgoingFlowHelper::RelaxIntoSpecialBinPackingProblem(
243 absl::Span<const int> subset,
int dimension,
bool negate_expressions,
245 tmp_bin_packing_problem_.clear();
264 const int num_nodes = in_subset_.size();
265 std::vector<IntegerValue> min_lower_bound_of_others(num_nodes,
267 std::vector<IntegerValue> max_upper_bound_of_others(num_nodes,
271 const auto lb_when_first = [&helper,
this](
int n,
int dimension,
272 bool negate_expressions) {
274 if (negate_expressions) expr = expr.
Negated();
276 if (incoming_arcs_from_outside_[n].IsUnique()) {
277 const int a = incoming_arcs_from_outside_[n].Get();
280 if (negate_expressions) tail_expr = tail_expr.
Negated();
281 const IntegerValue offset =
289 const auto ub_when_last = [&helper,
this](
int n,
int dimension,
290 bool negate_expressions) {
292 if (negate_expressions) expr = expr.
Negated();
294 if (outgoing_arcs_to_outside_[n].IsUnique()) {
295 const int a = outgoing_arcs_to_outside_[n].Get();
296 AffineExpression head_expr =
298 if (negate_expressions) head_expr = head_expr.
Negated();
299 const IntegerValue offset =
308 for (
const bool forward_pass : {
true,
false}) {
311 const int size = subset.size();
312 for (
int i = 0;
i < size; ++
i) {
313 const int n = forward_pass ? subset[
i] : subset[size - 1 -
i];
319 min_lower_bound_of_others[n] =
320 std::min(min_lower_bound_of_others[n], local_min);
321 max_upper_bound_of_others[n] =
322 std::max(max_upper_bound_of_others[n], local_max);
325 if (has_incoming_arcs_from_outside_[n]) {
326 local_min = std::min(local_min,
327 lb_when_first(n, dimension, negate_expressions));
329 if (has_outgoing_arcs_to_outside_[n]) {
331 std::max(local_max, ub_when_last(n, dimension, negate_expressions));
336 for (
const int n : subset) {
337 const absl::Span<const int> arcs =
338 use_incoming ? incoming_arc_indices_[n] : outgoing_arc_indices_[n];
340 for (
const int a : arcs) {
342 a, dimension, negate_expressions));
345 SpecialBinPackingHelper::ItemOrBin obj;
353 const IntegerValue lb = lb_when_first(n, dimension, negate_expressions);
354 if (max_upper_bound_of_others[n] > lb) {
355 obj.capacity = max_upper_bound_of_others[n] - lb;
358 const IntegerValue ub = ub_when_last(n, dimension, negate_expressions);
359 if (ub > min_lower_bound_of_others[n]) {
360 obj.capacity = ub - min_lower_bound_of_others[n];
368 if ((use_incoming && !has_incoming_arcs_from_outside_[n]) ||
369 (!use_incoming && !has_outgoing_arcs_to_outside_[n])) {
372 }
else if (arcs.empty()) {
379 tmp_bin_packing_problem_.push_back(obj);
382 return absl::MakeSpan(tmp_bin_packing_problem_);
386 absl::Span<ItemOrBin> objects,
387 std::vector<int>& objects_that_cannot_be_bin_and_reach_minimum,
389 objects_that_cannot_be_bin_and_reach_minimum.clear();
390 if (objects.empty())
return 0;
392 IntegerValue sum_of_demands(0);
394 int64_t max_capacity = 0;
395 int max_num_items = 0;
396 bool all_demands_are_non_negative =
true;
398 sum_of_demands =
CapAddI(sum_of_demands, obj.demand);
401 if (obj.demand < 0) {
402 all_demands_are_non_negative =
false;
404 gcd = std::gcd(gcd, std::abs(obj.demand.value()));
407 max_capacity = std::max(max_capacity, obj.capacity.value());
417 absl::StrAppend(&info,
"_gcd");
425 const int result = ComputeMinNumberOfBinsInternal(
426 objects, objects_that_cannot_be_bin_and_reach_minimum);
434 if (result > 1 && all_demands_are_non_negative &&
435 max_bounded_subset_sum_exact_.ComplexityEstimate(
436 max_num_items, max_capacity) < dp_effort_ &&
439 const int new_result = ComputeMinNumberOfBinsInternal(
440 objects, objects_that_cannot_be_bin_and_reach_minimum);
441 CHECK_GE(new_result, result);
442 if (new_result > result) {
443 absl::StrAppend(&info,
"_dp");
454 absl::Span<ItemOrBin> objects) {
455 tmp_demands_.clear();
456 int64_t max_capacity = 0;
459 tmp_demands_.push_back(obj.demand.value());
462 max_capacity = std::max(max_capacity, obj.capacity.value());
465 const int64_t max_reachable =
466 max_bounded_subset_sum_exact_.MaxSubsetSum(tmp_demands_, max_capacity);
467 bool some_change =
false;
468 if (max_reachable < max_capacity) {
470 if (obj.capacity > max_reachable) {
472 obj.capacity = max_reachable;
479int SpecialBinPackingHelper::ComputeMinNumberOfBinsInternal(
480 absl::Span<ItemOrBin> objects,
481 std::vector<int>& objects_that_cannot_be_bin_and_reach_minimum) {
482 objects_that_cannot_be_bin_and_reach_minimum.clear();
499 std::stable_sort(objects.begin(), objects.end(),
500 [](
const ItemOrBin& a,
const ItemOrBin&
b) {
501 if (a.type != b.type) {
504 return a.type > b.type;
506 return a.capacity + a.demand >
b.capacity +
b.demand;
510 IntegerValue sum_of_demands(0);
511 for (
const ItemOrBin& obj : objects) {
512 sum_of_demands += obj.demand;
519 IntegerValue sum_of_capacity(0);
520 for (; num_bins < objects.size(); ++num_bins) {
523 const ItemOrBin& obj = objects[num_bins];
524 if (obj.type != MUST_BE_BIN && sum_of_demands <= sum_of_capacity) {
527 if (obj.type == MUST_BE_ITEM) {
532 DCHECK_GT(sum_of_demands, sum_of_capacity);
533 return objects.size() + 1;
535 sum_of_capacity =
CapAddI(sum_of_capacity, obj.capacity);
537 sum_of_demands -= obj.demand;
545 if (num_bins > 0 && num_bins != objects.size()) {
546 const int worst_used_bin = num_bins - 1;
547 if (objects[worst_used_bin].type == MUST_BE_BIN) {
550 for (
int i = num_bins;
i < objects.size(); ++
i) {
551 objects_that_cannot_be_bin_and_reach_minimum.push_back(
i);
555 CHECK_EQ(objects[worst_used_bin].type, ITEM_OR_BIN);
556 sum_of_demands += objects[worst_used_bin].demand;
557 sum_of_capacity -= objects[worst_used_bin].capacity;
558 const IntegerValue slack = sum_of_demands - sum_of_capacity;
559 CHECK_GE(slack, 0) << num_bins <<
" " << objects.size() <<
" "
560 << objects[worst_used_bin].type;
562 for (
int i = num_bins;
i < objects.size(); ++
i) {
563 if (objects[
i].type == MUST_BE_ITEM)
continue;
567 const IntegerValue new_demand = sum_of_demands - objects[
i].demand;
568 const IntegerValue new_capacity = sum_of_capacity + objects[
i].capacity;
569 if (new_demand > new_capacity) {
570 objects_that_cannot_be_bin_and_reach_minimum.push_back(
i);
580 int num_bins, absl::Span<const ItemOrBin> objects) {
581 if (num_bins >= objects.size())
return true;
582 CHECK_GE(num_bins, 1);
583 tmp_capacities_.resize(num_bins);
584 for (
int i = 0;
i < num_bins; ++
i) {
585 tmp_capacities_[
i] = objects[
i].capacity;
589 for (
const ItemOrBin object : objects.subspan(num_bins)) {
591 for (
int b = 0;
b < num_bins; ++
b) {
592 if (
object.demand <= tmp_capacities_[
b]) {
594 tmp_capacities_[
b] -=
object.demand;
598 if (!placed)
return false;
604 absl::Span<const int> subset) {
605 DCHECK_GE(subset.size(), 1);
606 DCHECK(absl::c_all_of(next_reachable_, [](
bool b) {
return !
b; }));
607 DCHECK(absl::c_all_of(node_var_lower_bounds_,
608 [](
const auto& m) {
return m.empty(); }));
609 DCHECK(absl::c_all_of(next_node_var_lower_bounds_,
610 [](
const auto& m) {
return m.empty(); }));
611 PrecomputeDataForSubset(subset);
615 reachable_ = in_subset_;
618 int longest_path_length = 1;
619 absl::flat_hash_map<IntegerVariable, IntegerValue> tmp_lbs;
620 while (longest_path_length < subset.size()) {
621 bool at_least_one_next_node_reachable =
false;
622 for (
const int head : subset) {
623 bool is_reachable =
false;
624 for (
const int incoming_arc_index : incoming_arc_indices_[head]) {
625 const int tail = tails_[incoming_arc_index];
626 const Literal lit = literals_[incoming_arc_index];
627 if (!reachable_[tail])
continue;
631 if (!binary_relation_repository_.PropagateLocalBounds(
632 integer_trail_, lit, node_var_lower_bounds_[tail], &tmp_lbs)) {
639 next_node_var_lower_bounds_[head] = tmp_lbs;
642 ComputeMinLowerBoundOfSharedVariables(
643 tmp_lbs, &next_node_var_lower_bounds_[head]);
647 next_reachable_[head] = is_reachable;
648 if (next_reachable_[head]) at_least_one_next_node_reachable =
true;
650 if (!at_least_one_next_node_reachable) {
653 std::swap(reachable_, next_reachable_);
654 std::swap(node_var_lower_bounds_, next_node_var_lower_bounds_);
655 for (
const int n : subset) {
656 next_node_var_lower_bounds_[n].clear();
658 ++longest_path_length;
662 int max_longest_paths = 0;
663 for (
const int n : subset) {
664 if (reachable_[n]) ++max_longest_paths;
667 next_reachable_[n] =
false;
668 node_var_lower_bounds_[n].clear();
669 next_node_var_lower_bounds_[n].clear();
671 return GetMinOutgoingFlow(subset.size(), longest_path_length,
675int MinOutgoingFlowHelper::GetMinOutgoingFlow(
int subset_size,
676 int longest_path_length,
677 int max_longest_paths) {
678 if (max_longest_paths * longest_path_length < subset_size) {
682 DCHECK_GT(longest_path_length, 1);
685 return max_longest_paths +
687 subset_size - max_longest_paths * longest_path_length,
688 longest_path_length - 1);
698 bool operator==(
const Path& p)
const {
699 return node_set == p.node_set && last_node == p.last_node;
702 template <
typename H>
704 return H::combine(std::move(h), p.node_set, p.last_node);
711 absl::Span<const int> subset) {
712 DCHECK_GE(subset.size(), 1);
713 DCHECK_LE(subset.size(), 32);
714 PrecomputeDataForSubset(subset);
716 std::vector<int> longest_path_length_by_end_node(subset.size(), 1);
718 absl::flat_hash_map<IntegerVariable, IntegerValue> tmp_lbs;
719 absl::flat_hash_map<Path, absl::flat_hash_map<IntegerVariable, IntegerValue>>
721 std::vector<Path> paths;
722 std::vector<Path> next_paths;
723 for (
int i = 0;
i < subset.size(); ++
i) {
726 {.node_set =
static_cast<uint32_t
>(1 <<
i), .last_node = subset[
i]});
727 path_var_bounds[paths.back()] = {};
729 int longest_path_length = 1;
730 for (
int path_length = 1; path_length <= subset.size(); ++path_length) {
731 for (
const Path& path : paths) {
734 DCHECK(path_var_bounds.contains(path));
735 const absl::flat_hash_map<IntegerVariable, IntegerValue> path_bounds =
736 std::move(path_var_bounds.extract(path).mapped());
739 longest_path_length = path_length;
740 longest_path_length_by_end_node[index_in_subset_[path.last_node]] =
745 for (
const int outgoing_arc_index :
746 outgoing_arc_indices_[path.last_node]) {
747 const int head = heads_[outgoing_arc_index];
748 const int head_index_in_subset = index_in_subset_[head];
749 DCHECK_NE(head_index_in_subset, -1);
750 if (path.node_set & (1 << head_index_in_subset))
continue;
751 const Path new_path = {
752 .node_set = path.node_set | (1 << head_index_in_subset),
757 if (!binary_relation_repository_.PropagateLocalBounds(
758 integer_trail_, literals_[outgoing_arc_index], path_bounds,
763 const auto [it, inserted] = path_var_bounds.insert({new_path, tmp_lbs});
766 next_paths.push_back(new_path);
770 ComputeMinLowerBoundOfSharedVariables(tmp_lbs, &it->second);
774 std::swap(paths, next_paths);
778 int max_longest_paths = 0;
779 for (
int i = 0;
i < subset.size(); ++
i) {
780 if (longest_path_length_by_end_node[
i] == longest_path_length) {
785 return GetMinOutgoingFlow(subset.size(), longest_path_length,
792 bool use_forward_direction) {
793 cannot_be_first_.clear();
794 cannot_be_last_.clear();
795 if (k >= subset.size())
return true;
796 if (subset.size() > 31)
return true;
801 if (special_node >= 0) {
802 tmp_subset_.assign(subset.begin(), subset.end());
804 for (
int i = 0;
i < tmp_subset_.size(); ++
i) {
805 if (tmp_subset_[
i] == special_node) {
807 std::swap(tmp_subset_[0], tmp_subset_[
i]);
814 subset = tmp_subset_;
817 PrecomputeDataForSubset(subset);
818 ++num_full_dp_calls_;
823 adjacency.
reserve(subset.size());
824 for (
int i = 0;
i < subset.size(); ++
i) {
826 const int node = subset[
i];
827 if (helper !=
nullptr) {
828 CHECK(use_forward_direction);
829 for (
int j = 0; j < subset.size(); ++j) {
830 if (
i == j)
continue;
836 if (use_forward_direction) {
837 for (
const int arc : outgoing_arc_indices_[node]) {
841 for (
const int arc : incoming_arc_indices_[node]) {
854 uint32_t last_nodes_set;
868 absl::flat_hash_map<IntegerVariable, IntegerValue> lbs;
875 absl::int128 sum_of_reduced_costs = 0;
878 const int size = subset.size();
879 const uint32_t final_mask = (1 << size) - 1;
881 const auto& can_be_last_set = use_forward_direction
882 ? has_outgoing_arcs_to_outside_
883 : has_incoming_arcs_from_outside_;
884 const auto& can_be_first_set = use_forward_direction
885 ? has_incoming_arcs_from_outside_
886 : has_outgoing_arcs_to_outside_;
888 uint32_t can_be_last_mask = 0;
889 for (
int i = 0;
i < subset.size(); ++
i) {
890 if (can_be_last_set[subset[
i]]) {
891 can_be_last_mask |= (1 <<
i);
897 int64_t allocated_memory_estimate = 0;
900 std::vector<State> states;
901 states.push_back(State());
904 const auto update_using_unique_arc = [manager,
this](UniqueArc unique_arc,
906 if (!unique_arc.IsUnique())
return true;
907 if (manager ==
nullptr)
return true;
909 ++num_full_dp_unique_arc_;
910 const Literal unique_lit = literals_[unique_arc.Get()];
913 ++num_full_dp_rc_skip_;
917 absl::flat_hash_map<IntegerVariable, IntegerValue> copy = state.lbs;
918 return binary_relation_repository_.PropagateLocalBounds(
919 integer_trail_, unique_lit, copy, &state.lbs);
923 if (special_node >= 0) {
924 states.back().node_set = 1;
925 states.back().last_nodes_set = 1;
929 const UniqueArc unique_arc = use_forward_direction
930 ? incoming_arcs_from_outside_[subset[0]]
931 : outgoing_arcs_to_outside_[subset[0]];
932 if (!update_using_unique_arc(unique_arc, states.back())) {
937 while (!states.empty()) {
938 if (allocated_memory_estimate > 1e7) {
939 ++num_full_dp_work_abort_;
942 const State from_state = std::move(states.back());
946 const int num_routes = absl::popcount(from_state.last_nodes_set);
950 if (num_routes < k) {
951 const int num_extra = k - num_routes - 1;
952 for (
int i = 0;
i + num_extra < size; ++
i) {
953 if (from_state.node_set >>
i)
continue;
954 if (!can_be_first_set[subset[
i]])
continue;
959 const uint32_t head_mask = (1 <<
i);
960 to_state.node_set = from_state.node_set | head_mask;
961 to_state.last_nodes_set = from_state.last_nodes_set | head_mask;
962 to_state.lbs = from_state.lbs;
963 to_state.sum_of_reduced_costs = from_state.sum_of_reduced_costs;
965 const UniqueArc unique_arc =
966 use_forward_direction ? incoming_arcs_from_outside_[subset[
i]]
967 : outgoing_arcs_to_outside_[subset[
i]];
968 if (!update_using_unique_arc(unique_arc, to_state)) {
972 if (to_state.node_set == final_mask) {
973 ++num_full_dp_early_abort_;
976 states.push_back(std::move(to_state));
982 for (
int i = 0;
i < size; ++
i) {
983 const uint32_t tail_mask = 1 <<
i;
984 if ((from_state.last_nodes_set & tail_mask) == 0)
continue;
985 const int tail = subset[
i];
986 for (
const auto [head, literal] : adjacency[
i]) {
987 const uint32_t head_mask = (1 << index_in_subset_[head]);
988 if (from_state.node_set & head_mask)
continue;
994 if (manager !=
nullptr) {
995 DCHECK_EQ(helper,
nullptr);
996 to_state.sum_of_reduced_costs =
997 from_state.sum_of_reduced_costs +
1000 ++num_full_dp_rc_skip_;
1006 to_state.lbs = from_state.lbs;
1007 if (helper !=
nullptr) {
1009 integer_trail_, tail, head, from_state.lbs, &to_state.lbs)) {
1013 if (!binary_relation_repository_.PropagateLocalBounds(
1014 integer_trail_, literal, from_state.lbs, &to_state.lbs)) {
1019 to_state.node_set = from_state.node_set | head_mask;
1020 to_state.last_nodes_set = from_state.last_nodes_set | head_mask;
1021 to_state.last_nodes_set ^= tail_mask;
1022 allocated_memory_estimate += to_state.lbs.size();
1023 if (to_state.node_set == final_mask) {
1025 if (to_state.last_nodes_set & ~can_be_last_mask)
continue;
1029 bool infeasible =
false;
1030 int last_mask = to_state.last_nodes_set;
1031 for (
int j = 0; last_mask; j++, last_mask /= 2) {
1032 if ((last_mask & 1) == 0)
continue;
1034 const UniqueArc unique_arc =
1035 use_forward_direction ? outgoing_arcs_to_outside_[subset[j]]
1036 : incoming_arcs_from_outside_[subset[j]];
1037 if (!update_using_unique_arc(unique_arc, to_state)) {
1046 ++num_full_dp_early_abort_;
1049 states.push_back(std::move(to_state));
1065struct LocalRelation {
1066 IntegerValue tail_coeff = 0;
1067 IntegerValue head_coeff = 0;
1071 bool empty()
const {
return tail_coeff == 0 && head_coeff == 0; }
1072 bool operator==(
const LocalRelation& r)
const {
1073 return tail_coeff == r.tail_coeff && head_coeff == r.head_coeff &&
1074 lhs == r.lhs && rhs == r.rhs;
1078IntegerVariable UniqueSharedVariable(
const sat::Relation& r1,
1080 DCHECK_NE(r1.a.var, r1.b.var);
1081 DCHECK_NE(r2.a.var, r2.b.var);
1082 if (r1.a.var == r2.a.var && r1.b.var != r2.b.var)
return r1.a.var;
1083 if (r1.a.var == r2.b.var && r1.b.var != r2.a.var)
return r1.a.var;
1084 if (r1.b.var == r2.a.var && r1.a.var != r2.b.var)
return r1.b.var;
1085 if (r1.b.var == r2.b.var && r1.a.var != r2.a.var)
return r1.b.var;
1089class RouteRelationsBuilder {
1091 using HeadMinusTailBounds = RouteRelationsHelper::HeadMinusTailBounds;
1093 RouteRelationsBuilder(
1094 int num_nodes, absl::Span<const int> tails, absl::Span<const int> heads,
1095 absl::Span<const Literal> literals,
1096 absl::Span<const AffineExpression> flat_node_dim_expressions,
1097 const BinaryRelationRepository& binary_relation_repository)
1098 : num_nodes_(num_nodes),
1099 num_arcs_(tails.size()),
1102 literals_(literals),
1103 binary_relation_repository_(binary_relation_repository) {
1104 if (!flat_node_dim_expressions.empty()) {
1105 DCHECK_EQ(flat_node_dim_expressions.size() % num_nodes, 0);
1106 num_dimensions_ = flat_node_dim_expressions.size() / num_nodes;
1107 flat_node_dim_expressions_.assign(flat_node_dim_expressions.begin(),
1108 flat_node_dim_expressions.end());
1112 int num_dimensions()
const {
return num_dimensions_; }
1114 std::vector<AffineExpression>& flat_node_dim_expressions() {
1115 return flat_node_dim_expressions_;
1118 std::vector<HeadMinusTailBounds>& flat_arc_dim_relations() {
1119 return flat_arc_dim_relations_;
1122 std::vector<IntegerValue>& flat_shortest_path_lbs() {
1123 return flat_shortest_path_lbs_;
1126 bool BuildNodeExpressions() {
1127 if (flat_node_dim_expressions_.empty()) {
1131 ComputeDimensionOfEachVariable();
1132 if (num_dimensions_ == 0)
return false;
1139 ComputeAdjacentRelationsPerNodeAndDimension();
1142 std::queue<std::pair<int, int>> node_dim_pairs =
1143 ComputeVarAssociationsFromSharedVariableOfAdjacentRelations();
1144 if (node_dim_pairs.empty())
return false;
1148 ComputeVarAssociationsFromRelationsWithSingleFreeVar(node_dim_pairs);
1153 void BuildArcRelations(Model* model) {
1156 ComputeArcRelations(model);
1163 void BuildShortestPaths(Model* model) {
1164 if (num_nodes_ >= 100)
return;
1166 auto& integer_trail = *model->GetOrCreate<IntegerTrail>();
1167 std::vector<IntegerValue> flat_trivial_lbs(num_nodes_ * num_nodes_);
1168 const auto trivial = [
this, &flat_trivial_lbs](
int i,
1169 int j) -> IntegerValue& {
1173 return flat_trivial_lbs[
i * num_nodes_ + j];
1175 flat_shortest_path_lbs_.resize(num_nodes_ * num_nodes_ * num_dimensions_,
1176 std::numeric_limits<IntegerValue>::max());
1178 for (
int dim = 0; dim < num_dimensions_; ++dim) {
1180 for (
int i = 1;
i < num_nodes_; ++
i) {
1181 const AffineExpression& i_expr = node_expression(i, dim);
1182 const IntegerValue i_ub = integer_trail.LevelZeroUpperBound(i_expr);
1183 for (
int j = 1; j < num_nodes_; ++j) {
1184 if (i == j)
continue;
1185 const AffineExpression& j_expr = node_expression(j, dim);
1186 trivial(i, j) = integer_trail.LevelZeroLowerBound(j_expr) - i_ub;
1191 const auto path = [
this](
int dim,
int i,
int j) -> IntegerValue& {
1192 return flat_shortest_path_lbs_[dim * num_nodes_ * num_nodes_ +
1193 i * num_nodes_ + j];
1195 for (
int arc = 0; arc < tails_.size(); ++arc) {
1196 const int tail = tails_[arc];
1197 const int head = heads_[arc];
1198 if (tail == 0 || head == 0 || tail == head)
continue;
1199 path(dim, tail, head) =
1200 std::max(trivial(tail, head),
1201 flat_arc_dim_relations_[arc * num_dimensions_ + dim].lhs);
1205 for (
int k = 1; k < num_nodes_; ++k) {
1206 for (
int i = 1;
i < num_nodes_; ++
i) {
1207 if (i == k)
continue;
1208 for (
int j = 1; j < num_nodes_; ++j) {
1209 if (j == k || j == i)
continue;
1211 std::min(path(dim, i, j),
1212 std::max(trivial(i, j),
1213 CapAddI(path(dim, i, k), path(dim, k, j))));
1221 AffineExpression& node_expression(
int node,
int dimension) {
1222 return flat_node_dim_expressions_[node * num_dimensions_ + dimension];
1225 void ProcessNewArcRelation(
int arc_index,
int dimension, LocalRelation r) {
1226 if (r.empty())
return;
1227 if (r.head_coeff < 0) {
1228 r.tail_coeff = -r.tail_coeff;
1229 r.head_coeff = -r.head_coeff;
1232 std::swap(r.lhs, r.rhs);
1234 if (r.head_coeff != 1 || r.tail_coeff != -1)
return;
1237 HeadMinusTailBounds& relation =
1238 flat_arc_dim_relations_[arc_index * num_dimensions_ + dimension];
1239 relation.lhs = std::max(relation.lhs, r.lhs);
1240 relation.rhs = std::min(relation.rhs, r.rhs);
1243 void ComputeDimensionOfEachVariable() {
1249 ConnectedComponentsFinder<IntegerVariable> cc_finder;
1250 for (
int i = 0;
i < num_arcs_; ++
i) {
1251 if (tails_[i] == heads_[i])
continue;
1252 num_arcs_per_literal_[literals_[
i]]++;
1253 for (
const int relation_index :
1254 binary_relation_repository_.IndicesOfRelationsEnforcedBy(
1256 const auto& r = binary_relation_repository_.relation(relation_index);
1257 if (r.a.var == kNoIntegerVariable || r.b.var == kNoIntegerVariable) {
1260 cc_finder.
AddEdge(r.a.var, r.b.var);
1263 const std::vector<std::vector<IntegerVariable>> connected_components =
1265 for (
int i = 0;
i < connected_components.size(); ++
i) {
1266 for (
const IntegerVariable var : connected_components[i]) {
1267 dimension_by_var_[var] =
i;
1270 num_dimensions_ = connected_components.size();
1273 void ComputeAdjacentRelationsPerNodeAndDimension() {
1274 adjacent_relation_indices_ = std::vector<std::vector<std::vector<int>>>(
1275 num_dimensions_, std::vector<std::vector<int>>(num_nodes_));
1276 for (
int i = 0;
i < num_arcs_; ++
i) {
1277 if (tails_[i] == heads_[i])
continue;
1281 if (num_arcs_per_literal_[literals_[i]] > 1)
continue;
1282 for (
const int relation_index :
1283 binary_relation_repository_.IndicesOfRelationsEnforcedBy(
1285 const auto& r = binary_relation_repository_.relation(relation_index);
1286 if (r.a.var == kNoIntegerVariable || r.b.var == kNoIntegerVariable) {
1289 const int dimension = dimension_by_var_[r.a.var];
1290 adjacent_relation_indices_[dimension][tails_[
i]].push_back(
1292 adjacent_relation_indices_[dimension][heads_[
i]].push_back(
1300 std::queue<std::pair<int, int>>
1301 ComputeVarAssociationsFromSharedVariableOfAdjacentRelations() {
1302 flat_node_dim_expressions_ = std::vector<AffineExpression>(
1303 num_nodes_ * num_dimensions_, AffineExpression());
1304 std::queue<std::pair<int, int>> result;
1305 for (
int n = 0; n < num_nodes_; ++n) {
1306 for (
int d = 0; d < num_dimensions_; ++d) {
1312 for (
const int r1_index : adjacent_relation_indices_[d][n]) {
1313 const auto& r1 = binary_relation_repository_.relation(r1_index);
1314 for (
const int r2_index : adjacent_relation_indices_[d][n]) {
1315 if (r1_index == r2_index)
continue;
1316 const auto& r2 = binary_relation_repository_.relation(r2_index);
1317 const IntegerVariable shared_var = UniqueSharedVariable(r1, r2);
1318 if (shared_var == kNoIntegerVariable)
continue;
1319 DCHECK_EQ(dimension_by_var_[shared_var], d);
1320 AffineExpression& node_expr = node_expression(n, d);
1321 if (node_expr.IsConstant()) {
1322 result.push({n, d});
1323 }
else if (node_expr.var != shared_var) {
1324 VLOG(2) <<
"Several vars per node and dimension in route with "
1325 << num_nodes_ <<
" nodes and " << num_arcs_ <<
" arcs";
1328 node_expr = shared_var;
1336 void ComputeVarAssociationsFromRelationsWithSingleFreeVar(
1337 std::queue<std::pair<int, int>>& node_dim_pairs_to_process) {
1338 std::vector<std::vector<int>> adjacent_arcs_per_node(num_nodes_);
1339 for (
int i = 0;
i < num_arcs_; ++
i) {
1340 if (tails_[i] == heads_[i])
continue;
1341 adjacent_arcs_per_node[tails_[
i]].push_back(i);
1342 adjacent_arcs_per_node[heads_[
i]].push_back(i);
1344 while (!node_dim_pairs_to_process.empty()) {
1345 const auto [node, dimension] = node_dim_pairs_to_process.front();
1346 const AffineExpression node_expr = node_expression(node, dimension);
1347 DCHECK(!node_expr.IsConstant());
1348 node_dim_pairs_to_process.pop();
1349 for (
const int arc_index : adjacent_arcs_per_node[node]) {
1350 const int tail = tails_[arc_index];
1351 const int head = heads_[arc_index];
1352 DCHECK(node == tail || node == head);
1353 int other_node = node == tail ? head : tail;
1354 if (!node_expression(other_node, dimension).IsConstant()) {
1358 bool candidate_var_is_unique =
true;
1359 for (
const int relation_index :
1360 binary_relation_repository_.IndicesOfRelationsEnforcedBy(
1361 literals_[arc_index])) {
1362 const auto& r = binary_relation_repository_.relation(relation_index);
1363 if (r.a.var == kNoIntegerVariable || r.b.var == kNoIntegerVariable) {
1366 if (r.a.var == node_expr.var) {
1367 if (candidate_var != kNoIntegerVariable &&
1368 candidate_var != r.b.var) {
1369 candidate_var_is_unique =
false;
1372 candidate_var = r.b.var;
1374 if (r.b.var == node_expr.var) {
1375 if (candidate_var != kNoIntegerVariable &&
1376 candidate_var != r.a.var) {
1377 candidate_var_is_unique =
false;
1380 candidate_var = r.a.var;
1383 if (candidate_var != kNoIntegerVariable && candidate_var_is_unique) {
1384 node_expression(other_node, dimension) = candidate_var;
1385 node_dim_pairs_to_process.push({other_node, dimension});
1391 void ComputeArcRelations(Model* model) {
1392 auto& binary_implication_graph =
1393 *model->GetOrCreate<BinaryImplicationGraph>();
1394 const auto& integer_encoder = *model->GetOrCreate<IntegerEncoder>();
1395 const auto& trail = *model->GetOrCreate<Trail>();
1396 const auto& integer_trail = *model->GetOrCreate<IntegerTrail>();
1397 DCHECK_EQ(trail.CurrentDecisionLevel(), 0);
1399 flat_arc_dim_relations_ = std::vector<HeadMinusTailBounds>(
1400 num_arcs_ * num_dimensions_, HeadMinusTailBounds());
1401 binary_implication_graph.ResetWorkDone();
1402 for (
int i = 0;
i < num_arcs_; ++
i) {
1403 const int tail = tails_[
i];
1404 const int head = heads_[
i];
1405 if (tail == head)
continue;
1408 const Literal arc_literal_singleton[1] = {literals_[
i]};
1409 absl::Span<const Literal> implied_literals =
1410 binary_implication_graph.WorkDone() < 1e8
1411 ? binary_implication_graph.GetAllImpliedLiterals(literals_[i])
1412 : absl::MakeSpan(arc_literal_singleton);
1416 absl::flat_hash_set<IntegerVariable> implied_views;
1417 absl::flat_hash_set<IntegerVariable> negated_implied_views;
1418 absl::flat_hash_map<IntegerVariable, IntegerValue> implied_lower_bounds;
1419 for (
const Literal implied : implied_literals) {
1420 implied_views.insert(integer_encoder.GetLiteralView(implied));
1421 negated_implied_views.insert(
1422 integer_encoder.GetLiteralView(implied.Negated()));
1423 for (
const auto& [var, lb] :
1424 integer_encoder.GetIntegerLiterals(implied)) {
1425 auto it = implied_lower_bounds.find(var);
1426 if (it == implied_lower_bounds.end()) {
1427 implied_lower_bounds[var] = lb;
1429 it->second = std::max(it->second, lb);
1435 auto get_bounds = [&](
const NodeExpression& expr) {
1436 if (expr.var != kNoIntegerVariable) {
1437 if (implied_views.contains(expr.var)) {
1438 IntegerValue constant_value = expr.coeff + expr.offset;
1439 return std::make_pair(constant_value, constant_value);
1441 if (implied_views.contains(
NegationOf(expr.var))) {
1442 IntegerValue constant_value = -expr.coeff + expr.offset;
1443 return std::make_pair(constant_value, constant_value);
1445 if (negated_implied_views.contains(expr.var) ||
1446 negated_implied_views.contains(
NegationOf(expr.var))) {
1447 return std::make_pair(expr.offset, expr.offset);
1450 const AffineExpression e(expr.var, expr.coeff, expr.offset);
1451 IntegerValue lb = integer_trail.LevelZeroLowerBound(e);
1452 auto it = implied_lower_bounds.find(e.var);
1453 if (it != implied_lower_bounds.end()) {
1454 lb = std::max(lb, e.ValueAt(it->second));
1456 IntegerValue ub = integer_trail.LevelZeroUpperBound(e);
1457 it = implied_lower_bounds.find(
NegationOf(e.var));
1458 if (it != implied_lower_bounds.end()) {
1459 ub = std::min(ub, e.ValueAt(-it->second));
1461 return std::make_pair(lb, ub);
1465 auto to_constant = [&](NodeExpression& expr) {
1466 if (expr.var == kNoIntegerVariable)
return true;
1467 if (integer_trail.IsFixed(expr.var)) {
1468 expr.offset += integer_trail.FixedValue(expr.var) * expr.coeff;
1473 const auto [min, max] = get_bounds(expr);
1475 expr = NodeExpression(kNoIntegerVariable, 0, min);
1480 for (
int dimension = 0; dimension < num_dimensions_; ++dimension) {
1481 NodeExpression tail_expr(node_expression(tail, dimension));
1482 NodeExpression head_expr(node_expression(head, dimension));
1483 for (
const Literal implied_lit : implied_literals) {
1484 for (
const int relation_index :
1485 binary_relation_repository_.IndicesOfRelationsEnforcedBy(
1487 auto r = binary_relation_repository_.relation(relation_index);
1491 if ((r.a.var != kNoIntegerVariable && r.a.var == head_expr.var) ||
1492 (r.b.var != kNoIntegerVariable && r.b.var == tail_expr.
var)) {
1493 std::swap(r.a, r.b);
1497 if (r.a.var == kNoIntegerVariable) {
1498 if (!to_constant(tail_expr))
continue;
1499 }
else if (r.b.var == kNoIntegerVariable) {
1500 if (!to_constant(head_expr))
continue;
1504 if (!((tail_expr.
var == r.a.var && head_expr.var == r.b.var) ||
1505 (tail_expr.
var == r.b.var && head_expr.var == r.a.var))) {
1508 ComputeArcRelation(i, dimension, tail_expr, head_expr, r,
1514 if (!tail_expr.IsEmpty() && !head_expr.IsEmpty()) {
1515 for (
const int relation_index :
1516 binary_relation_repository_.IndicesOfRelationsBetween(
1517 tail_expr.
var, head_expr.var)) {
1519 i, dimension, tail_expr, head_expr,
1520 binary_relation_repository_.relation(relation_index),
1530 std::pair<IntegerValue, IntegerValue> bounds;
1531 if (head_expr.var == tail_expr.
var) {
1532 const NodeExpression offset_expr(head_expr.var,
1533 head_expr.coeff - tail_expr.
coeff,
1534 head_expr.offset - tail_expr.offset);
1535 bounds = get_bounds(offset_expr);
1537 const auto [tail_min, tail_max] = get_bounds(tail_expr);
1538 const auto [head_min, head_max] = get_bounds(head_expr);
1539 bounds = {head_min - tail_max, head_max - tail_min};
1541 ProcessNewArcRelation(i, dimension,
1544 .lhs = bounds.first,
1545 .rhs = bounds.second});
1552 void ComputeArcRelation(
int arc_index,
int dimension,
1553 const NodeExpression& tail_expr,
1554 const NodeExpression& head_expr, sat::Relation r,
1555 const IntegerTrail& integer_trail) {
1556 DCHECK((r.a.var == tail_expr.var && r.b.var == head_expr.var) ||
1557 (r.a.var == head_expr.var && r.b.var == tail_expr.var));
1558 if (r.a.var != tail_expr.var) std::swap(r.a, r.b);
1559 if (r.a.coeff == 0 || tail_expr.coeff == 0) {
1560 LocalRelation result = ComputeArcUnaryRelation(head_expr, tail_expr,
1561 r.b.coeff, r.lhs, r.rhs);
1562 std::swap(result.tail_coeff, result.head_coeff);
1563 ProcessNewArcRelation(arc_index, dimension, result);
1566 if (r.b.coeff == 0 || head_expr.coeff == 0) {
1567 ProcessNewArcRelation(arc_index, dimension,
1568 ComputeArcUnaryRelation(tail_expr, head_expr,
1569 r.a.coeff, r.lhs, r.rhs));
1572 const auto [lhs, rhs] =
1574 {integer_trail.LowerBound(tail_expr.var),
1575 integer_trail.UpperBound(tail_expr.var)},
1576 {integer_trail.LowerBound(head_expr.var),
1577 integer_trail.UpperBound(head_expr.var)});
1578 ProcessNewArcRelation(
1579 arc_index, dimension,
1580 {.tail_coeff = -1, .head_coeff = 1, .lhs = lhs, .rhs = rhs});
1586 LocalRelation ComputeArcUnaryRelation(
const NodeExpression& tail_expr,
1587 const NodeExpression& head_expr,
1588 IntegerValue coeff, IntegerValue lhs,
1590 DCHECK_NE(coeff, 0);
1596 if (tail_expr.coeff == 0)
return {};
1597 const int64_t k = std::abs(tail_expr.coeff.value()) /
1598 std::gcd(tail_expr.coeff.value(), coeff.value());
1603 const IntegerValue tail_coeff = (k * coeff) / tail_expr.coeff;
1604 const IntegerValue head_coeff = head_expr.coeff != 0 ? 0 : -tail_coeff;
1605 const IntegerValue domain_offset =
1606 tail_coeff * tail_expr.offset + head_coeff * head_expr.offset;
1610 k * lhs + domain_offset,
1611 k * rhs + domain_offset,
1615 const int num_nodes_;
1616 const int num_arcs_;
1617 absl::Span<const int> tails_;
1618 absl::Span<const int> heads_;
1619 absl::Span<const Literal> literals_;
1620 const BinaryRelationRepository& binary_relation_repository_;
1622 int num_dimensions_;
1623 absl::flat_hash_map<IntegerVariable, int> dimension_by_var_;
1624 absl::flat_hash_map<Literal, int> num_arcs_per_literal_;
1628 std::vector<std::vector<std::vector<int>>> adjacent_relation_indices_;
1632 std::vector<AffineExpression> flat_node_dim_expressions_;
1633 std::vector<HeadMinusTailBounds> flat_arc_dim_relations_;
1634 std::vector<IntegerValue> flat_shortest_path_lbs_;
1640 int num_nodes, absl::Span<const int> tails, absl::Span<const int> heads,
1641 absl::Span<const Literal> literals,
1644 RouteRelationsBuilder builder(num_nodes, tails, heads, literals, {},
1645 binary_relation_repository);
1646 if (!builder.BuildNodeExpressions())
return result;
1649 std::move(builder.flat_node_dim_expressions());
1655IntegerValue GetDifferenceLowerBound(
1656 const NodeExpression& x_expr,
const NodeExpression& y_expr,
1658 const std::pair<IntegerValue, IntegerValue>& x_var_bounds,
1659 const std::pair<IntegerValue, IntegerValue>& y_var_bounds) {
1682 auto lower_bound = [&](IntegerValue k) {
1683 const IntegerValue y_coeff = y_expr.coeff - k * r.
b.
coeff;
1684 const IntegerValue x_coeff = k * (-r.
a.
coeff) - x_expr.coeff;
1685 return y_coeff * (y_coeff >= 0 ? y_var_bounds.first : y_var_bounds.second) +
1686 x_coeff * (x_coeff >= 0 ? x_var_bounds.first : x_var_bounds.second) +
1687 k * (k >= 0 ? r.
lhs : r.
rhs);
1691 IntegerValue result = lower_bound(0);
1692 result = std::max(result, lower_bound(k_x));
1693 result = std::max(result, lower_bound(k_x + 1));
1694 result = std::max(result, lower_bound(k_y));
1695 result = std::max(result, lower_bound(k_y + 1));
1696 return result + y_expr.offset - x_expr.offset;
1703 const std::pair<IntegerValue, IntegerValue>& x_var_bounds,
1704 const std::pair<IntegerValue, IntegerValue>& y_var_bounds) {
1705 DCHECK_EQ(x_expr.
var, r.
a.
var);
1706 DCHECK_EQ(y_expr.
var, r.
b.
var);
1709 DCHECK_NE(x_expr.
coeff, 0);
1710 DCHECK_NE(y_expr.
coeff, 0);
1713 const IntegerValue lb =
1714 GetDifferenceLowerBound(x_expr, y_expr, r, x_var_bounds, y_var_bounds);
1715 const IntegerValue ub = -GetDifferenceLowerBound(
1716 x_expr.
Negated(), y_expr.
Negated(), r, x_var_bounds, y_var_bounds);
1721 int num_nodes,
const std::vector<int>& tails,
const std::vector<int>& heads,
1722 const std::vector<Literal>& literals,
1723 absl::Span<const AffineExpression> flat_node_dim_expressions,
1725 CHECK(model !=
nullptr);
1726 if (flat_node_dim_expressions.empty())
return nullptr;
1727 RouteRelationsBuilder builder(
num_nodes, tails, heads, literals,
1728 flat_node_dim_expressions,
1729 binary_relation_repository);
1730 builder.BuildArcRelations(model);
1731 builder.BuildShortestPaths(model);
1733 builder.num_dimensions(), std::move(builder.flat_node_dim_expressions()),
1734 std::move(builder.flat_arc_dim_relations()),
1735 std::move(builder.flat_shortest_path_lbs())));
1736 if (VLOG_IS_ON(2)) helper->LogStats();
1741 int num_dimensions, std::vector<AffineExpression> flat_node_dim_expressions,
1742 std::vector<HeadMinusTailBounds> flat_arc_dim_relations,
1743 std::vector<IntegerValue> flat_shortest_path_lbs)
1744 : num_nodes_(flat_node_dim_expressions.size() / num_dimensions),
1745 num_dimensions_(num_dimensions),
1746 flat_node_dim_expressions_(
std::move(flat_node_dim_expressions)),
1747 flat_arc_dim_relations_(
std::move(flat_arc_dim_relations)),
1748 flat_shortest_path_lbs_(
std::move(flat_shortest_path_lbs)) {
1749 DCHECK_GE(num_dimensions_, 1);
1750 DCHECK_EQ(flat_node_dim_expressions_.size(), num_nodes_ * num_dimensions_);
1754 int arc,
int dimension,
bool negate_expressions)
const {
1758 return negate_expressions ? -r.rhs : r.lhs;
1762 absl::Span<const int> sorted_arc_indices) {
1766 if (!sorted_arc_indices.empty() && sorted_arc_indices.front() ==
i) {
1767 sorted_arc_indices.remove_prefix(1);
1770 for (
int d = 0; d < num_dimensions_; ++d) {
1771 flat_arc_dim_relations_[new_size++] =
1772 flat_arc_dim_relations_[
i * num_dimensions_ + d];
1775 flat_arc_dim_relations_.resize(new_size);
1778void RouteRelationsHelper::LogStats()
const {
1783 for (
int d = 0; d < num_dimensions_; ++d) {
1785 int num_relations = 0;
1795 LOG(INFO) <<
"dimension " << d <<
": " << num_vars <<
" vars and "
1796 << num_relations <<
" relations";
1807IntegerVariable ToPositiveIntegerVariable(
int i) {
1812int ToNodeVariableIndex(IntegerVariable var) {
1814 return var.value() >> 1;
1822 const CpModelProto& model) {
1824 for (
const ConstraintProto& ct : model.constraints()) {
1825 if (ct.constraint_case() != ConstraintProto::kLinear)
continue;
1826 const absl::Span<const int> vars = ct.linear().vars();
1827 if (ct.enforcement_literal().size() != 1 || vars.size() != 2)
continue;
1828 if (vars[0] == vars[1])
continue;
1829 repository.AddPartialRelation(ToLiteral(ct.enforcement_literal(0)),
1830 ToPositiveIntegerVariable(vars[0]),
1831 ToPositiveIntegerVariable(vars[1]));
1838int MaybeFillRoutesConstraintNodeExpressions(
1841 for (
const int node : routes.tails()) {
1842 max_node = std::max(max_node, node);
1844 for (
const int node : routes.heads()) {
1845 max_node = std::max(max_node, node);
1847 const int num_nodes = max_node + 1;
1848 std::vector<int> tails(routes.tails().begin(), routes.tails().end());
1849 std::vector<int> heads(routes.heads().begin(), routes.heads().end());
1850 std::vector<Literal> literals;
1851 literals.reserve(routes.literals_size());
1852 for (
int lit : routes.literals()) {
1853 literals.push_back(ToLiteral(lit));
1857 num_nodes, tails, heads, literals, repository);
1858 if (cumuls.num_dimensions == 0)
return 0;
1860 for (
int d = 0; d < cumuls.num_dimensions; ++d) {
1861 RoutesConstraintProto::NodeExpressions& dimension =
1862 *routes.add_dimensions();
1863 for (
int n = 0; n < num_nodes; ++n) {
1865 LinearExpressionProto& node_expr = *dimension.add_exprs();
1869 ? expr.coeff.value()
1870 : -expr.coeff.value());
1872 node_expr.set_offset(expr.constant.value());
1875 return cumuls.num_dimensions;
1881 const CpModelProto& input_model, CpModelProto& output_model) {
1882 std::vector<RoutesConstraintProto*> routes_to_fill;
1883 for (ConstraintProto& ct : *output_model.mutable_constraints()) {
1884 if (ct.constraint_case() != ConstraintProto::kRoutes)
continue;
1885 if (!ct.routes().dimensions().empty())
continue;
1886 routes_to_fill.push_back(ct.mutable_routes());
1888 if (routes_to_fill.empty())
return {0, 0};
1890 int total_num_dimensions = 0;
1892 ComputePartialBinaryRelationRepository(input_model);
1893 for (RoutesConstraintProto* routes : routes_to_fill) {
1894 total_num_dimensions +=
1895 MaybeFillRoutesConstraintNodeExpressions(*routes, partial_repository);
1897 return {
static_cast<int>(routes_to_fill.size()), total_num_dimensions};
1902class RoutingCutHelper {
1904 RoutingCutHelper(
int num_nodes,
bool is_route_constraint,
1905 absl::Span<const AffineExpression> flat_node_dim_expressions,
1906 absl::Span<const int> tails, absl::Span<const int> heads,
1907 absl::Span<const Literal> literals,
Model* model)
1908 : num_nodes_(num_nodes),
1909 is_route_constraint_(is_route_constraint),
1910 tails_(tails.
begin(), tails.
end()),
1911 heads_(heads.
begin(), heads.
end()),
1912 literals_(literals.
begin(), literals.
end()),
1913 params_(*model->GetOrCreate<SatParameters>()),
1914 trail_(*model->GetOrCreate<
Trail>()),
1915 integer_trail_(*model->GetOrCreate<IntegerTrail>()),
1916 binary_relation_repository_(
1917 *model->GetOrCreate<BinaryRelationRepository>()),
1918 random_(model->GetOrCreate<ModelRandomGenerator>()),
1919 encoder_(model->GetOrCreate<IntegerEncoder>()),
1920 in_subset_(num_nodes, false),
1921 self_arc_literal_(num_nodes_),
1922 self_arc_lp_value_(num_nodes_),
1923 nodes_incoming_weight_(num_nodes_),
1924 nodes_outgoing_weight_(num_nodes_),
1925 min_outgoing_flow_helper_(num_nodes, tails_, heads_, literals_, model),
1926 route_relations_helper_(RouteRelationsHelper::Create(
1927 num_nodes, tails_, heads_, literals_, flat_node_dim_expressions,
1928 *model->GetOrCreate<BinaryRelationRepository>(), model)) {}
1930 int num_nodes()
const {
return num_nodes_; }
1932 bool is_route_constraint()
const {
return is_route_constraint_; }
1935 absl::Span<const ArcWithLpValue> relevant_arcs()
const {
1936 return relevant_arcs_;
1944 absl::Span<const std::pair<int, int>> ordered_arcs()
const {
1945 return ordered_arcs_;
1950 void InitializeForNewLpSolution(LinearConstraintManager* manager);
1954 absl::Span<const ArcWithLpValue> SymmetrizedRelevantArcs() {
1955 symmetrized_relevant_arcs_ = relevant_arcs_;
1959 if (is_route_constraint_) {
1961 for (
const ArcWithLpValue& arc : symmetrized_relevant_arcs_) {
1962 if (arc.tail == 0 || arc.head == 0)
continue;
1963 symmetrized_relevant_arcs_[new_size++] = arc;
1965 symmetrized_relevant_arcs_.resize(new_size);
1968 return symmetrized_relevant_arcs_;
1972 bool TrySubsetCut(
int known_bound, std::string name,
1973 absl::Span<const int> subset,
1974 LinearConstraintManager* manager);
1979 int ShortestPathBound(
int bound, absl::Span<const int> subset);
1992 bool TryBlossomSubsetCut(std::string name,
1993 absl::Span<const ArcWithLpValue> symmetrized_edges,
1994 absl::Span<const int> subset,
1995 LinearConstraintManager* manager);
1999 void TryInfeasiblePathCuts(LinearConstraintManager* manager);
2008 BestChoice PickBestNode(absl::Span<const int> cannot_be_first,
2009 absl::Span<const int> cannot_be_last);
2013 void FilterFalseArcsAtLevelZero();
2021 bool AddOutgoingCut(LinearConstraintManager* manager, std::string name,
2022 int subset_size,
const std::vector<bool>& in_subset,
2023 int64_t rhs_lower_bound);
2025 bool MaybeAddStrongerFlowCut(LinearConstraintManager* manager,
2026 std::string name,
int k,
2027 absl::Span<const int> cannot_be_first,
2028 absl::Span<const int> cannot_be_last,
2029 const std::vector<bool>& in_subset);
2031 void GenerateCutsForInfeasiblePaths(
2032 int start_node,
int max_path_length,
2033 const CompactVectorVector<
int, std::pair<int, double>>&
2034 outgoing_arcs_with_lp_values,
2035 LinearConstraintManager* manager, TopNCuts& top_n_cuts);
2037 const int num_nodes_;
2038 const bool is_route_constraint_;
2039 std::vector<int> tails_;
2040 std::vector<int> heads_;
2041 std::vector<Literal> literals_;
2042 std::vector<ArcWithLpValue> relevant_arcs_;
2043 std::vector<std::pair<int, double>> relevant_arc_indices_;
2044 std::vector<ArcWithLpValue> symmetrized_relevant_arcs_;
2045 std::vector<std::pair<int, int>> ordered_arcs_;
2047 const SatParameters& params_;
2048 const Trail& trail_;
2049 const IntegerTrail& integer_trail_;
2050 const BinaryRelationRepository& binary_relation_repository_;
2051 ModelRandomGenerator* random_;
2052 IntegerEncoder* encoder_;
2054 std::vector<bool> in_subset_;
2057 std::vector<int> nodes_with_self_arc_;
2058 std::vector<Literal> self_arc_literal_;
2059 std::vector<double> self_arc_lp_value_;
2062 std::vector<double> nodes_incoming_weight_;
2063 std::vector<double> nodes_outgoing_weight_;
2067 MaxBoundedSubsetSum max_bounded_subset_sum_;
2068 MaxBoundedSubsetSumExact max_bounded_subset_sum_exact_;
2069 MinOutgoingFlowHelper min_outgoing_flow_helper_;
2070 std::unique_ptr<RouteRelationsHelper> route_relations_helper_;
2073void RoutingCutHelper::FilterFalseArcsAtLevelZero() {
2077 const int size =
static_cast<int>(tails_.size());
2078 const VariablesAssignment& assignment = trail_.
Assignment();
2079 std::vector<int> removed_arcs;
2080 for (
int i = 0;
i < size; ++
i) {
2081 if (assignment.LiteralIsFalse(literals_[i])) {
2082 removed_arcs.push_back(i);
2085 tails_[new_size] = tails_[
i];
2086 heads_[new_size] = heads_[
i];
2087 literals_[new_size] = literals_[
i];
2090 if (new_size < size) {
2091 tails_.resize(new_size);
2092 heads_.resize(new_size);
2093 literals_.resize(new_size);
2094 if (route_relations_helper_ !=
nullptr) {
2095 route_relations_helper_->RemoveArcs(removed_arcs);
2100void RoutingCutHelper::InitializeForNewLpSolution(
2101 LinearConstraintManager* manager) {
2102 FilterFalseArcsAtLevelZero();
2106 relevant_arcs_.clear();
2107 relevant_arc_indices_.clear();
2108 nodes_with_self_arc_.clear();
2111 const auto& lp_values = manager->LpValues();
2112 std::vector<std::pair<double, int>> relevant_arc_by_decreasing_lp_values;
2113 for (
int i = 0;
i < literals_.size(); ++
i) {
2114 const IntegerVariable direct_view = encoder_->
GetLiteralView(literals_[i]);
2115 const double lp_value =
2117 ? lp_values[direct_view]
2118 : 1.0 - lp_values[encoder_->
GetLiteralView(literals_[i].Negated())];
2125 if (tails_[i] == heads_[i]) {
2126 const int node = tails_[
i];
2127 nodes_with_self_arc_.push_back(node);
2128 self_arc_lp_value_[node] = lp_value;
2129 self_arc_literal_[node] = literals_[
i];
2133 if (lp_value < 1e-6)
continue;
2134 relevant_arcs_.push_back({tails_[
i], heads_[
i], lp_value});
2135 relevant_arc_indices_.push_back({
i, lp_value});
2136 relevant_arc_by_decreasing_lp_values.push_back({lp_value,
i});
2138 std::sort(relevant_arc_by_decreasing_lp_values.begin(),
2139 relevant_arc_by_decreasing_lp_values.end(),
2140 std::greater<std::pair<double, int>>());
2144 ordered_arcs_.clear();
2145 for (
const auto& [score, arc] : relevant_arc_by_decreasing_lp_values) {
2146 if (is_route_constraint_) {
2147 if (tails_[arc] == 0 || heads_[arc] == 0)
continue;
2149 ordered_arcs_.push_back({tails_[arc], heads_[arc]});
2152 if (absl::GetFlag(FLAGS_cp_model_dump_routes_support_graphs) &&
2154 static std::atomic<int> counter = 0;
2155 const std::string name =
2156 absl::StrCat(absl::GetFlag(FLAGS_cp_model_dump_prefix),
2157 "support_graph_", counter++,
".pb.txt");
2158 LOG(INFO) <<
"Dumping routes support graph to '" << name <<
"'.";
2159 RoutesSupportGraphProto support_graph_proto;
2160 for (
auto& [tail, head, lp_value] : relevant_arcs_) {
2161 auto* arc = support_graph_proto.add_arc_lp_values();
2162 arc->set_tail(tail);
2163 arc->set_head(head);
2164 arc->set_lp_value(lp_value);
2185std::pair<double, double> GetIncomingAndOutgoingLpFlow(
2186 absl::Span<const ArcWithLpValue> relevant_arcs,
2187 const std::vector<bool>& in_subset,
int outside_node_to_ignore = -1) {
2188 double outgoing_flow = 0.0;
2189 double incoming_flow = 0.0;
2190 for (
const auto arc : relevant_arcs) {
2191 const bool tail_in = in_subset[arc.tail];
2192 const bool head_in = in_subset[arc.head];
2193 if (tail_in && !head_in) {
2194 if (arc.head == outside_node_to_ignore)
continue;
2195 outgoing_flow += arc.lp_value;
2196 }
else if (!tail_in && head_in) {
2197 if (arc.tail == outside_node_to_ignore)
continue;
2198 incoming_flow += arc.lp_value;
2201 return {incoming_flow, outgoing_flow};
2206RoutingCutHelper::BestChoice RoutingCutHelper::PickBestNode(
2207 absl::Span<const int> cannot_be_first,
2208 absl::Span<const int> cannot_be_last) {
2210 std::vector<BestChoice> bests;
2211 double best_weight = 0.0;
2212 for (
const int n : cannot_be_first) {
2213 const double weight = nodes_incoming_weight_[n];
2214 if (bests.empty() || weight > best_weight) {
2216 bests.push_back({n,
true, weight});
2217 best_weight = weight;
2218 }
else if (weight == best_weight) {
2219 bests.push_back({n,
true, weight});
2222 for (
const int n : cannot_be_last) {
2223 const double weight = nodes_outgoing_weight_[n];
2224 if (bests.empty() || weight > best_weight) {
2226 bests.push_back({n,
false, weight});
2227 best_weight = weight;
2228 }
else if (weight == best_weight) {
2229 bests.push_back({n,
false, weight});
2232 if (bests.empty())
return {-1,
true};
2233 return bests.size() == 1
2235 : bests[absl::Uniform<int>(*random_, 0, bests.size())];
2238bool RoutingCutHelper::MaybeAddStrongerFlowCut(
2239 LinearConstraintManager* manager, std::string name,
int k,
2240 absl::Span<const int> cannot_be_first, absl::Span<const int> cannot_be_last,
2241 const std::vector<bool>& in_subset) {
2242 if (cannot_be_first.empty() && cannot_be_last.empty())
return false;
2246 const BestChoice best_choice = PickBestNode(cannot_be_first, cannot_be_last);
2247 const int best_node = best_choice.node;
2248 const bool incoming = best_choice.incoming;
2249 CHECK_GE(best_node, 0);
2251 const auto consider_arc = [incoming, &in_subset](
int t,
int h) {
2252 return incoming ? !in_subset[t] && in_subset[h]
2253 : in_subset[t] && !in_subset[h];
2261 for (
const auto arc : relevant_arcs_) {
2262 if (!consider_arc(arc.tail, arc.head))
continue;
2263 if (arc.tail != best_node && arc.head != best_node) {
2264 flow += arc.lp_value;
2270 if (flow <
static_cast<double>(k) - kTolerance) {
2271 LinearConstraintBuilder cut_builder(encoder_, IntegerValue(k),
2273 for (
int i = 0;
i < tails_.size(); ++
i) {
2274 if (!consider_arc(tails_[i], heads_[i]))
continue;
2275 if (tails_[i] != best_node && heads_[i] != best_node) {
2276 CHECK(cut_builder.AddLiteralTerm(literals_[i], IntegerValue(1)));
2279 return manager->AddCut(cut_builder.Build(), name);
2284bool RoutingCutHelper::AddOutgoingCut(LinearConstraintManager* manager,
2285 std::string name,
int subset_size,
2286 const std::vector<bool>& in_subset,
2287 int64_t rhs_lower_bound) {
2289 const auto [in_flow, out_flow] =
2290 GetIncomingAndOutgoingLpFlow(relevant_arcs_, in_subset);
2291 const double out_violation =
static_cast<double>(rhs_lower_bound) - out_flow;
2292 const double in_violation =
static_cast<double>(rhs_lower_bound) - in_flow;
2293 if (out_violation <= 1e-3 && in_violation <= 1e-3)
return false;
2297 LinearConstraintBuilder outgoing(encoder_, IntegerValue(rhs_lower_bound),
2299 LinearConstraintBuilder incoming(encoder_, IntegerValue(rhs_lower_bound),
2304 for (
int i = 0;
i < tails_.size(); ++
i) {
2305 const bool tail_in = in_subset[tails_[
i]];
2306 const bool head_in = in_subset[heads_[
i]];
2307 if (tail_in && !head_in) {
2308 CHECK(outgoing.AddLiteralTerm(literals_[i], IntegerValue(1)));
2309 }
else if (!tail_in && head_in) {
2310 CHECK(incoming.AddLiteralTerm(literals_[i], IntegerValue(1)));
2318 const double out_efficacy = out_violation / std::sqrt(outgoing.NumTerms());
2319 const double in_efficacy = in_violation / std::sqrt(incoming.NumTerms());
2322 LinearConstraintBuilder& cut_builder =
2323 (out_efficacy >= in_efficacy) ? outgoing : incoming;
2331 int num_optional_nodes_in = 0;
2332 int num_optional_nodes_out = 0;
2333 int optional_loop_in = -1;
2334 int optional_loop_out = -1;
2335 for (
const int n : nodes_with_self_arc_) {
2337 num_optional_nodes_in++;
2338 if (optional_loop_in == -1 ||
2339 self_arc_lp_value_[n] < self_arc_lp_value_[optional_loop_in]) {
2340 optional_loop_in = n;
2343 num_optional_nodes_out++;
2344 if (optional_loop_out == -1 ||
2345 self_arc_lp_value_[n] < self_arc_lp_value_[optional_loop_out]) {
2346 optional_loop_out = n;
2353 CHECK(rhs_lower_bound == 1 || num_optional_nodes_in == 0);
2356 if (num_optional_nodes_in + num_optional_nodes_out > 0) {
2358 if (num_optional_nodes_in == subset_size &&
2359 (optional_loop_in == -1 ||
2360 self_arc_lp_value_[optional_loop_in] > 1.0 - 1e-6)) {
2363 if (num_optional_nodes_out == num_nodes_ - subset_size &&
2364 (optional_loop_out == -1 ||
2365 self_arc_lp_value_[optional_loop_out] > 1.0 - 1e-6)) {
2370 if (num_optional_nodes_in == subset_size) {
2371 CHECK_EQ(rhs_lower_bound, 1);
2372 CHECK(cut_builder.AddLiteralTerm(self_arc_literal_[optional_loop_in],
2377 if (num_optional_nodes_out == num_nodes_ - subset_size) {
2378 CHECK_EQ(rhs_lower_bound, 1);
2379 CHECK(cut_builder.AddLiteralTerm(self_arc_literal_[optional_loop_out],
2384 return manager->AddCut(cut_builder.Build(), name);
2387int RoutingCutHelper::ShortestPathBound(
int bound,
2388 absl::Span<const int> subset) {
2389 if (!is_route_constraint_)
return bound;
2390 if (!nodes_with_self_arc_.empty())
return bound;
2391 if (route_relations_helper_ ==
nullptr)
return bound;
2392 if (!route_relations_helper_->HasShortestPathsInformation())
return bound;
2394 params_.routing_cut_subset_size_for_shortest_paths_bound()) {
2398 while (bound < subset.size()) {
2400 bound, subset, route_relations_helper_.get())) {
2409bool RoutingCutHelper::TrySubsetCut(
int known_bound, std::string name,
2410 absl::Span<const int> subset,
2411 LinearConstraintManager* manager) {
2412 DCHECK_GE(subset.size(), 1);
2413 DCHECK_LT(subset.size(), num_nodes_);
2416 in_subset_.assign(num_nodes_,
false);
2417 for (
const int n : subset) {
2418 in_subset_[n] =
true;
2423 if (is_route_constraint_) CHECK_NE(n, 0);
2428 bool all_subset_nodes_are_mandatory =
true;
2429 if (is_route_constraint_) {
2430 for (
const int n : nodes_with_self_arc_) {
2431 if (in_subset_[n]) {
2432 all_subset_nodes_are_mandatory =
false;
2445 if (!is_route_constraint_ || !all_subset_nodes_are_mandatory) {
2446 return AddOutgoingCut(manager, name, subset.size(), in_subset_,
2453 double total_outgoing_weight = 0.0;
2454 double total_incoming_weight = 0.0;
2455 nodes_incoming_weight_.assign(num_nodes_, 0);
2456 nodes_outgoing_weight_.assign(num_nodes_, 0);
2457 for (
const auto arc : relevant_arcs_) {
2458 if (in_subset_[arc.tail] != in_subset_[arc.head]) {
2459 if (in_subset_[arc.tail]) {
2460 total_outgoing_weight += arc.lp_value;
2462 total_incoming_weight += arc.lp_value;
2464 nodes_outgoing_weight_[arc.tail] += arc.lp_value;
2465 nodes_incoming_weight_[arc.head] += arc.lp_value;
2469 BestBoundHelper best_bound(name);
2470 best_bound.Update(1,
"");
2471 best_bound.Update(known_bound,
"Hierarchical");
2479 if (route_relations_helper_ !=
nullptr) {
2481 subset, *route_relations_helper_, &best_bound);
2484 params_.routing_cut_subset_size_for_tight_binary_relation_bound()) {
2487 best_bound.Update(bound,
"AutomaticTight");
2488 }
else if (subset.size() <
2489 params_.routing_cut_subset_size_for_binary_relation_bound()) {
2491 best_bound.Update(bound,
"Automatic");
2494 if (subset.size() <=
2495 params_.routing_cut_subset_size_for_exact_binary_relation_bound()) {
2504 const double threshold =
static_cast<double>(best_bound.bound()) - 1e-4;
2505 for (
const int n : subset) {
2506 if (nodes_incoming_weight_[n] > 0.1 &&
2507 total_incoming_weight - nodes_incoming_weight_[n] < threshold &&
2509 best_bound.bound(), subset,
nullptr, manager, n,
2511 best_bound.Update(best_bound.bound(),
"", {n}, {});
2513 if (nodes_outgoing_weight_[n] > 0.1 &&
2514 total_outgoing_weight - nodes_outgoing_weight_[n] < threshold &&
2516 best_bound.bound(), subset,
nullptr, manager, n,
2518 best_bound.Update(best_bound.bound(),
"", {}, {n});
2523 if (MaybeAddStrongerFlowCut(manager,
2524 absl::StrCat(best_bound.name(),
"Lifted"),
2525 best_bound.bound(), best_bound.CannotBeFirst(),
2526 best_bound.CannotBeLast(), in_subset_)) {
2530 return AddOutgoingCut(manager, best_bound.name(), subset.size(), in_subset_,
2531 best_bound.bound());
2534bool RoutingCutHelper::TryBlossomSubsetCut(
2535 std::string name, absl::Span<const ArcWithLpValue> symmetrized_edges,
2536 absl::Span<const int> subset, LinearConstraintManager* manager) {
2537 DCHECK_GE(subset.size(), 1);
2538 DCHECK_LT(subset.size(), num_nodes_);
2541 for (
const int n : subset) in_subset_[n] =
true;
2542 auto cleanup = ::absl::MakeCleanup([subset,
this]() {
2543 for (
const int n : subset) in_subset_[n] =
false;
2548 absl::flat_hash_set<std::pair<int, int>> special_edges;
2549 int num_inverted = 0;
2550 double sum_inverted = 0.0;
2552 double best_change = 1.0;
2553 ArcWithLpValue
const* best_swap =
nullptr;
2554 for (
const ArcWithLpValue& arc : symmetrized_edges) {
2555 if (in_subset_[arc.tail] == in_subset_[arc.head])
continue;
2557 if (arc.lp_value > 0.5) {
2559 special_edges.insert({arc.tail, arc.head});
2560 sum_inverted += 1.0 - arc.lp_value;
2562 sum += arc.lp_value;
2565 const double change = std::abs(2 * arc.lp_value - 1.0);
2566 if (change < best_change) {
2567 best_change = change;
2574 if (num_inverted % 2 == 0) {
2575 if (best_swap ==
nullptr)
return false;
2576 if (special_edges.contains({best_swap->tail, best_swap->head})) {
2578 special_edges.erase({best_swap->tail, best_swap->head});
2579 sum_inverted -= (1.0 - best_swap->lp_value);
2580 sum += best_swap->lp_value;
2583 special_edges.insert({best_swap->tail, best_swap->head});
2584 sum_inverted += (1.0 - best_swap->lp_value);
2585 sum -= best_swap->lp_value;
2588 if (sum + sum_inverted > 0.99)
return false;
2592 if (!is_route_constraint_) {
2593 for (
const auto [tail, head] : special_edges) {
2594 if (tail == 0)
return false;
2601 int best_optional_index = -1;
2602 if (special_edges.size() == 1) {
2603 int num_other_optional = 0;
2604 const auto [special_tail, special_head] = *special_edges.begin();
2605 for (
const int n : nodes_with_self_arc_) {
2606 if (n != special_head && n != special_tail) {
2607 ++num_other_optional;
2608 if (best_optional_index == -1 ||
2609 self_arc_lp_value_[n] < self_arc_lp_value_[best_optional_index]) {
2610 best_optional_index = n;
2614 if (num_other_optional + 2 < num_nodes_) best_optional_index = -1;
2621 int num_actual_inverted = 0;
2622 absl::flat_hash_set<std::pair<int, int>> processed_arcs;
2623 LinearConstraintBuilder builder(encoder_, IntegerValue(1), kMaxIntegerValue);
2627 if (best_optional_index != -1) {
2628 absl::StrAppend(&name,
"_opt");
2633 CHECK(builder.AddLiteralTerm(self_arc_literal_[best_optional_index],
2637 for (
int i = 0;
i < tails_.size(); ++
i) {
2638 if (tails_[i] == heads_[i])
continue;
2639 if (in_subset_[tails_[i]] == in_subset_[heads_[i]])
continue;
2641 const std::pair<int, int> key = {tails_[
i], heads_[
i]};
2642 const std::pair<int, int> r_key = {heads_[
i], tails_[
i]};
2643 const std::pair<int, int> s_key = std::min(key, r_key);
2644 if (special_edges.contains(s_key) && !processed_arcs.contains(key)) {
2645 processed_arcs.insert(key);
2646 CHECK(builder.AddLiteralTerm(literals_[i], IntegerValue(-1)));
2647 if (!processed_arcs.contains(r_key)) {
2648 ++num_actual_inverted;
2654 CHECK(builder.AddLiteralTerm(literals_[i], IntegerValue(1)));
2656 builder.AddConstant(IntegerValue(num_actual_inverted));
2657 if (num_actual_inverted % 2 == 0)
return false;
2659 return manager->AddCut(builder.Build(), name);
2662void RoutingCutHelper::TryInfeasiblePathCuts(LinearConstraintManager* manager) {
2663 const int max_path_length = params_.routing_cut_max_infeasible_path_length();
2664 if (max_path_length <= 0)
return;
2668 std::vector<int> keys;
2669 std::vector<std::pair<int, double>> values;
2670 for (
const auto [arc_index, lp_value] : relevant_arc_indices_) {
2671 const int tail = tails_[arc_index];
2672 const int head = heads_[arc_index];
2675 DCHECK_NE(tail, head);
2676 if (tail == 0 || head == 0)
continue;
2677 keys.push_back(tail);
2678 values.push_back({arc_index, lp_value});
2680 CompactVectorVector<int, std::pair<int, double>> outgoing_arcs_with_lp_values;
2681 outgoing_arcs_with_lp_values.ResetFromFlatMapping(keys, values, num_nodes_);
2683 TopNCuts top_n_cuts(5);
2684 for (
int i = 1;
i < num_nodes_; ++
i) {
2685 GenerateCutsForInfeasiblePaths(
2686 i, max_path_length, outgoing_arcs_with_lp_values, manager, top_n_cuts);
2688 top_n_cuts.TransferToManager(manager);
2693void RoutingCutHelper::GenerateCutsForInfeasiblePaths(
2694 int start_node,
int max_path_length,
2695 const CompactVectorVector<
int, std::pair<int, double>>&
2696 outgoing_arcs_with_lp_values,
2697 LinearConstraintManager* manager, TopNCuts& top_n_cuts) {
2707 double sum_of_lp_values = 0.0;
2711 absl::flat_hash_map<IntegerVariable, IntegerValue> bounds;
2717 std::stack<State> states;
2720 std::vector<bool> path_nodes(num_nodes_,
false);
2722 std::vector<Literal> path_literals;
2724 path_nodes[start_node] =
true;
2725 states.push({start_node});
2726 while (!states.empty()) {
2727 State& state = states.top();
2728 DCHECK_EQ(states.size(), path_literals.size() + 1);
2730 const int path_length =
static_cast<int>(path_literals.size());
2731 const auto& outgoing_arcs = outgoing_arcs_with_lp_values[state.last_node];
2733 bool new_state_pushed =
false;
2734 while (state.iteration < outgoing_arcs.size()) {
2735 const auto [arc_index, lp_value] = outgoing_arcs[state.iteration++];
2737 next_state.last_node = heads_[arc_index];
2738 next_state.sum_of_lp_values = state.sum_of_lp_values + lp_value;
2739 next_state.iteration = 0;
2741 if (path_nodes[next_state.last_node])
continue;
2750 if (next_state.sum_of_lp_values <=
2751 static_cast<double>(path_length) + 1e-4) {
2755 const Literal next_literal = literals_[arc_index];
2756 next_state.bounds = state.bounds;
2758 integer_trail_, next_literal, state.bounds, &next_state.bounds)) {
2760 if (path_length < max_path_length) {
2761 path_nodes[next_state.last_node] =
true;
2762 path_literals.push_back(literals_[arc_index]);
2763 states.push(std::move(next_state));
2764 new_state_pushed =
true;
2767 }
else if (path_length > 0) {
2768 LinearConstraintBuilder cut_builder(encoder_, 0, path_length);
2769 for (
const Literal literal : path_literals) {
2770 CHECK(cut_builder.AddLiteralTerm(literal, IntegerValue(1)));
2772 CHECK(cut_builder.AddLiteralTerm(next_literal, IntegerValue(1)));
2773 top_n_cuts.AddCut(cut_builder.Build(),
"CircuitInfeasiblePath",
2774 manager->LpValues());
2777 if (!new_state_pushed) {
2778 if (!path_literals.empty()) {
2779 path_literals.pop_back();
2781 path_nodes[state.last_node] =
false;
2790 absl::Span<
const std::pair<int, int>> arcs,
2791 int stop_at_num_components,
2792 std::vector<int>* subset_data,
2793 std::vector<absl::Span<const int>>* subsets) {
2802 int num_components = num_nodes;
2803 std::vector<int> parent(num_nodes);
2804 std::vector<int> root(num_nodes);
2805 for (
int i = 0;
i < num_nodes; ++
i) {
2809 auto get_root_and_compress_path = [&root](
int node) {
2811 while (root[r] != r) r = root[r];
2812 while (root[node] != r) {
2813 const int next = root[node];
2819 for (
const auto& [initial_tail, initial_head] : arcs) {
2820 if (num_components <= stop_at_num_components)
break;
2821 const int tail = get_root_and_compress_path(initial_tail);
2822 const int head = get_root_and_compress_path(initial_head);
2826 const int new_node = parent.size();
2827 parent.push_back(new_node);
2828 parent[head] = new_node;
2829 parent[tail] = new_node;
2833 root.push_back(new_node);
2834 root[head] = new_node;
2835 root[tail] = new_node;
2850 std::vector<int>* subset_data,
2851 std::vector<absl::Span<const int>>* subsets,
2856 const int num_nodes = parent.size();
2857 subset_data->resize(std::min(num_nodes, node_limit));
2862 for (
int i = 0;
i < num_nodes; ++
i) {
2863 if (parent[
i] !=
i) {
2871 std::vector<int> subtree_starts(num_nodes, -1);
2872 std::vector<int> stack;
2873 stack.reserve(num_nodes);
2874 for (
int i = 0;
i < parent.size(); ++
i) {
2875 if (parent[
i] !=
i)
continue;
2878 while (!stack.empty()) {
2879 const int node = stack.back();
2882 if (subtree_starts[node] >= 0) {
2884 if (node < node_limit) {
2885 (*subset_data)[out_index++] = node;
2887 const int start = subtree_starts[node];
2888 const int size = out_index - start;
2889 subsets->push_back(absl::MakeSpan(&(*subset_data)[start], size));
2894 subtree_starts[node] = out_index;
2895 for (
const int child : graph[node]) {
2896 stack.push_back(child);
2903 int num_nodes, absl::Span<const ArcWithLpValue> relevant_arcs) {
2907 for (
const auto& [tail, head, lp_value] : relevant_arcs) {
2914 std::vector<int> min_cut_subset;
2915 std::vector<int> parent(num_nodes, 0);
2916 for (
int s = 1; s < num_nodes; ++s) {
2917 const int t = parent[s];
2920 bool parent_of_t_in_subset =
false;
2921 for (
const int i : min_cut_subset) {
2922 if (
i == parent[t]) parent_of_t_in_subset =
true;
2923 if (
i != s && parent[
i] == t) parent[
i] = s;
2925 if (parent_of_t_in_subset) {
2926 parent[s] = parent[t];
2936 if (arc.tail <= arc.head)
continue;
2937 std::swap(arc.tail, arc.head);
2939 std::sort(arcs->begin(), arcs->end(),
2941 return std::tie(a.tail, a.head) < std::tie(b.tail, b.head);
2948 if (arc.tail == last_tail && arc.head == last_head) {
2949 (*arcs)[new_size - 1].lp_value += arc.lp_value;
2952 (*arcs)[new_size++] = arc;
2953 last_tail = arc.tail;
2954 last_head = arc.head;
2956 arcs->resize(new_size);
2962 std::vector<absl::Span<const int>> subsets,
2964 const int num_nodes = subset_data.size();
2972 std::vector<bool> cut_was_added(num_nodes,
false);
2973 std::vector<int> shortest_path_lb(num_nodes, 0);
2976 for (
const absl::Span<const int> subset : subsets) {
2977 if (subset.size() <= 1)
continue;
2978 if (subset.size() == num_nodes)
continue;
2987 int lb_for_that_subset = 1;
2988 bool included_cut_was_added =
false;
2989 const int start =
static_cast<int>(subset.data() - subset_data.data());
2990 for (
int i = start;
i < subset.size(); ++
i) {
2991 lb_for_that_subset = std::max(lb_for_that_subset, shortest_path_lb[
i]);
2992 if (cut_was_added[
i]) {
2993 included_cut_was_added =
true;
3001 lb_for_that_subset = helper.ShortestPathBound(lb_for_that_subset, subset);
3002 shortest_path_lb[start] = lb_for_that_subset;
3006 if (included_cut_was_added && subset.size() + 1 < num_nodes)
continue;
3007 if (helper.TrySubsetCut(lb_for_that_subset, cut_name, subset, manager)) {
3009 cut_was_added[start] =
true;
3024 const int num_nodes = helper.num_nodes();
3025 if (num_nodes <= 2)
return;
3027 std::vector<int> subset_data;
3028 std::vector<absl::Span<const int>> subsets;
3037 if (helper.is_route_constraint()) {
3038 subsets.push_back(absl::MakeSpan(&subset_data[1], num_nodes - 1));
3042 TryAllSubsets(
"Circuit", subset_data, subsets, helper, manager);
3058 if (num_added != 0)
return;
3059 absl::Span<const ArcWithLpValue> symmetrized_relevant_arcs =
3060 helper.SymmetrizedRelevantArcs();
3061 std::vector<int> parent =
3067 TryAllSubsets(
"CircuitExact", subset_data, subsets, helper, manager);
3072 if (num_added != 0)
return;
3073 if (num_nodes <= 2)
return;
3074 std::vector<ArcWithLpValue> for_blossom;
3075 for_blossom.reserve(symmetrized_relevant_arcs.size());
3077 if (arc.lp_value > 0.5) arc.lp_value = 1.0 - arc.lp_value;
3078 if (arc.lp_value < 1e-6)
continue;
3079 for_blossom.push_back(arc);
3083 int last_added_start = -1;
3084 for (
const absl::Span<const int> subset : subsets) {
3085 if (subset.size() <= 1)
continue;
3086 if (subset.size() == num_nodes)
continue;
3087 const int start =
static_cast<int>(subset.data() - subset_data.data());
3088 if (start <= last_added_start)
continue;
3089 if (helper.TryBlossomSubsetCut(
"CircuitBlossom", symmetrized_relevant_arcs,
3092 last_added_start = start;
3100std::vector<IntegerVariable> GetAssociatedVariables(
3101 absl::Span<const Literal> literals,
Model* model) {
3102 auto* encoder = model->GetOrCreate<IntegerEncoder>();
3103 std::vector<IntegerVariable> result;
3104 for (
const Literal l : literals) {
3105 const IntegerVariable direct_view = encoder->GetLiteralView(l);
3107 result.push_back(direct_view);
3109 result.push_back(encoder->GetLiteralView(l.Negated()));
3122 int num_nodes, absl::Span<const int> tails, absl::Span<const int> heads,
3123 absl::Span<const Literal> literals,
Model* model) {
3124 auto helper = std::make_unique<RoutingCutHelper>(
3127 absl::Span<const AffineExpression>{}, tails, heads, literals, model);
3129 result.
vars = GetAssociatedVariables(literals, model);
3130 result.generate_cuts =
3132 helper->InitializeForNewLpSolution(manager);
3140 int num_nodes, absl::Span<const int> tails, absl::Span<const int> heads,
3141 absl::Span<const Literal> literals,
3142 absl::Span<const AffineExpression> flat_node_dim_expressions,
3144 auto helper = std::make_unique<RoutingCutHelper>(
3145 num_nodes,
true, flat_node_dim_expressions, tails,
3146 heads, literals, model);
3148 result.
vars = GetAssociatedVariables(literals, model);
3151 helper->InitializeForNewLpSolution(manager);
3153 helper->TryInfeasiblePathCuts(manager);
3162 int num_nodes, absl::Span<const int> tails, absl::Span<const int> heads,
3163 absl::Span<const AffineExpression> arc_capacities,
3164 std::function<
void(
const std::vector<bool>& in_subset,
3165 IntegerValue* min_incoming_flow,
3166 IntegerValue* min_outgoing_flow)>
3176 IntegerValue offset;
3178 std::vector<Arc> relevant_arcs;
3185 std::vector<std::pair<double, int>> arc_by_decreasing_lp_values;
3186 for (
int i = 0;
i < arc_capacities.size(); ++
i) {
3187 const double lp_value = arc_capacities[
i].LpValue(lp_values);
3188 if (!arc_capacities[
i].IsConstant()) {
3189 gcd = std::gcd(gcd, std::abs(arc_capacities[
i].coeff.value()));
3191 if (lp_value < 1e-6 && arc_capacities[
i].constant == 0)
continue;
3192 relevant_arcs.push_back(
3193 {tails[
i], heads[
i], lp_value, arc_capacities[
i].constant});
3194 arc_by_decreasing_lp_values.push_back({lp_value,
i});
3196 if (gcd == 0)
return;
3197 std::sort(arc_by_decreasing_lp_values.begin(),
3198 arc_by_decreasing_lp_values.end(),
3199 std::greater<std::pair<double, int>>());
3201 std::vector<std::pair<int, int>> ordered_arcs;
3202 for (
const auto& [score, arc] : arc_by_decreasing_lp_values) {
3203 if (tails[arc] == -1)
continue;
3204 if (heads[arc] == -1)
continue;
3205 ordered_arcs.push_back({tails[arc], heads[arc]});
3207 std::vector<int> subset_data;
3208 std::vector<absl::Span<const int>> subsets;
3214 std::vector<bool> in_subset(num_nodes,
false);
3215 for (
const absl::Span<const int> subset : subsets) {
3216 DCHECK(!subset.empty());
3217 DCHECK_LE(subset.size(), num_nodes);
3220 for (
const int n : subset) in_subset[n] =
true;
3222 IntegerValue min_incoming_flow;
3223 IntegerValue min_outgoing_flow;
3224 get_flows(in_subset, &min_incoming_flow, &min_outgoing_flow);
3228 IntegerValue incoming_offset(0);
3229 IntegerValue outgoing_offset(0);
3236 double lp_outgoing_flow = 0.0;
3237 double lp_incoming_flow = 0.0;
3238 for (
const auto arc : relevant_arcs) {
3239 if (arc.tail != -1 && in_subset[arc.tail]) {
3240 if (arc.head == -1 || !in_subset[arc.head]) {
3241 incoming_offset += arc.offset;
3242 lp_outgoing_flow += arc.lp_value;
3245 if (arc.head != -1 && in_subset[arc.head]) {
3246 outgoing_offset += arc.offset;
3247 lp_incoming_flow += arc.lp_value;
3258 const IntegerValue test_incoming = min_incoming_flow - incoming_offset;
3259 const IntegerValue new_incoming =
3260 CeilRatio(test_incoming, IntegerValue(gcd)) * IntegerValue(gcd);
3261 const IntegerValue incoming_delta = new_incoming - test_incoming;
3262 if (incoming_delta > 0) min_incoming_flow += incoming_delta;
3265 const IntegerValue test_outgoing = min_outgoing_flow - outgoing_offset;
3266 const IntegerValue new_outgoing =
3267 CeilRatio(test_outgoing, IntegerValue(gcd)) * IntegerValue(gcd);
3268 const IntegerValue outgoing_delta = new_outgoing - test_outgoing;
3269 if (outgoing_delta > 0) min_outgoing_flow += outgoing_delta;
3272 if (lp_incoming_flow <
ToDouble(min_incoming_flow) - 1e-6) {
3273 VLOG(2) <<
"INCOMING CUT " << lp_incoming_flow
3274 <<
" >= " << min_incoming_flow <<
" size " << subset.size()
3275 <<
" offset " << incoming_offset <<
" gcd " << gcd;
3277 for (
int i = 0;
i < tails.size(); ++
i) {
3278 if ((tails[
i] == -1 || !in_subset[tails[
i]]) &&
3279 (heads[
i] != -1 && in_subset[heads[
i]])) {
3280 cut.
AddTerm(arc_capacities[
i], 1.0);
3286 if (lp_outgoing_flow <
ToDouble(min_outgoing_flow) - 1e-6) {
3287 VLOG(2) <<
"OUGOING CUT " << lp_outgoing_flow
3288 <<
" >= " << min_outgoing_flow <<
" size " << subset.size()
3289 <<
" offset " << outgoing_offset <<
" gcd " << gcd;
3291 for (
int i = 0;
i < tails.size(); ++
i) {
3292 if ((tails[
i] != -1 && in_subset[tails[
i]]) &&
3293 (heads[
i] == -1 || !in_subset[heads[
i]])) {
3294 cut.
AddTerm(arc_capacities[
i], 1.0);
3301 for (
const int n : subset) in_subset[n] =
false;
3306 int num_nodes,
const std::vector<int>& tails,
const std::vector<int>& heads,
3307 const std::vector<AffineExpression>& arc_capacities,
3308 std::function<
void(
const std::vector<bool>& in_subset,
3309 IntegerValue* min_incoming_flow,
3310 IntegerValue* min_outgoing_flow)>
3315 if (!expr.IsConstant()) result.
vars.push_back(expr.var);
3319 manager->LpValues(), manager, model);
std::vector< std::vector< T > > FindConnectedComponents()
bool AddEdge(T node1, T node2)
static IntegralType CeilOfRatio(IntegralType numerator, IntegralType denominator)
static IntegralType FloorOfRatio(IntegralType numerator, IntegralType denominator)
ArcIndex AddArcWithCapacity(NodeIndex tail, NodeIndex head, FlowQuantity capacity)
Status Solve(NodeIndex source, NodeIndex sink)
void GetSourceSideMinCut(std::vector< NodeIndex > *result)
Keep the best min outgoing/incoming flow out of a subset.
void Update(int new_bound, std::string name, absl::Span< const int > cannot_be_first={}, absl::Span< const int > cannot_be_last={})
bool PropagateLocalBounds(const IntegerTrail &integer_trail, Literal lit, const absl::flat_hash_map< IntegerVariable, IntegerValue > &input, absl::flat_hash_map< IntegerVariable, IntegerValue > *output) const
void reserve(int size)
Reserve memory if it is already known or tightly estimated.
void AppendToLastVector(const V &value)
int Add(absl::Span< const V > values)
IntegerVariable GetLiteralView(Literal lit) const
IntegerValue LevelZeroUpperBound(IntegerVariable var) const
IntegerValue LevelZeroLowerBound(IntegerVariable var) const
Returns globally valid lower/upper bound on the given integer variable.
void AddTerm(IntegerVariable var, IntegerValue coeff)
absl::int128 ReducedCostsGap() const
absl::int128 GetLiteralReducedCost(Literal l) const
bool AddCut(LinearConstraint ct, std::string type_name, std::string extra_info="")
int ComputeTightMinOutgoingFlow(absl::Span< const int > subset)
int ComputeMinOutgoingFlow(absl::Span< const int > subset)
bool SubsetMightBeServedWithKRoutes(int k, absl::Span< const int > subset, RouteRelationsHelper *helper=nullptr, LinearConstraintManager *manager=nullptr, int special_node=-1, bool use_forward_direction=true)
int ComputeDimensionBasedMinOutgoingFlow(absl::Span< const int > subset, const RouteRelationsHelper &helper, BestBoundHelper *best_bound)
MinOutgoingFlowHelper(int num_nodes, const std::vector< int > &tails, const std::vector< int > &heads, const std::vector< Literal > &literals, Model *model)
bool PathExists(int tail, int head) const
const HeadMinusTailBounds & GetArcRelation(int arc, int dimension) const
IntegerValue GetArcOffsetLowerBound(int arc, int dimension, bool negate_expressions) const
const AffineExpression & GetNodeExpression(int node, int dimension) const
Returns the expression associated with the given node and dimension.
static std::unique_ptr< RouteRelationsHelper > Create(int num_nodes, const std::vector< int > &tails, const std::vector< int > &heads, const std::vector< Literal > &literals, absl::Span< const AffineExpression > flat_node_dim_expressions, const BinaryRelationRepository &binary_relation_repository, Model *model)
bool PropagateLocalBoundsUsingShortestPaths(const IntegerTrail &integer_trail, int tail, int head, const absl::flat_hash_map< IntegerVariable, IntegerValue > &input, absl::flat_hash_map< IntegerVariable, IntegerValue > *output) const
int num_dimensions() const
Returns the number of "dimensions", such as time or vehicle load.
void RemoveArcs(absl::Span< const int > sorted_arc_indices)
RouteRelationsHelper()=default
Visible for testing.
Simple class to add statistics by name and print them at the end.
int ComputeMinNumberOfBins(absl::Span< ItemOrBin > objects, std::vector< int > &objects_that_cannot_be_bin_and_reach_minimum, std::string &info)
bool UseDpToTightenCapacities(absl::Span< ItemOrBin > objects)
bool GreedyPackingWorks(int num_bins, absl::Span< const ItemOrBin > objects)
int CurrentDecisionLevel() const
const VariablesAssignment & Assignment() const
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
void STLSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
constexpr double kTolerance
H AbslHashValue(H h, std::shared_ptr< Variable > i)
IntegerValue FloorRatio(IntegerValue dividend, IntegerValue positive_divisor)
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
bool RefIsPositive(int ref)
CutGenerator CreateStronglyConnectedGraphCutGenerator(int num_nodes, absl::Span< const int > tails, absl::Span< const int > heads, absl::Span< const Literal > literals, Model *model)
IntegerValue CeilRatio(IntegerValue dividend, IntegerValue positive_divisor)
std::vector< int > ComputeGomoryHuTree(int num_nodes, absl::Span< const ArcWithLpValue > relevant_arcs)
const LiteralIndex kNoLiteralIndex(-1)
std::pair< int, int > MaybeFillMissingRoutesConstraintNodeExpressions(const CpModelProto &input_model, CpModelProto &output_model)
int TryAllSubsets(std::string cut_name, absl::Span< const int > subset_data, std::vector< absl::Span< const int > > subsets, RoutingCutHelper &helper, LinearConstraintManager *manager)
std::vector< IntegerVariable > NegationOf(absl::Span< const IntegerVariable > vars)
Returns the vector of the negated variables.
bool WriteModelProtoToFile(const M &proto, absl::string_view filename)
RoutingCumulExpressions DetectDimensionsAndCumulExpressions(int num_nodes, absl::Span< const int > tails, absl::Span< const int > heads, absl::Span< const Literal > literals, const BinaryRelationRepository &binary_relation_repository)
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue.value())
std::pair< IntegerValue, IntegerValue > GetDifferenceBounds(const NodeExpression &x_expr, const NodeExpression &y_expr, const sat::Relation &r, const std::pair< IntegerValue, IntegerValue > &x_var_bounds, const std::pair< IntegerValue, IntegerValue > &y_var_bounds)
const IntegerVariable kNoIntegerVariable(-1)
IntegerVariable PositiveVariable(IntegerVariable i)
CutGenerator CreateFlowCutGenerator(int num_nodes, const std::vector< int > &tails, const std::vector< int > &heads, const std::vector< AffineExpression > &arc_capacities, std::function< void(const std::vector< bool > &in_subset, IntegerValue *min_incoming_flow, IntegerValue *min_outgoing_flow)> get_flows, Model *model)
IntegerValue CapAddI(IntegerValue a, IntegerValue b)
void SeparateSubtourInequalities(RoutingCutHelper &helper, LinearConstraintManager *manager)
CutGenerator CreateCVRPCutGenerator(int num_nodes, absl::Span< const int > tails, absl::Span< const int > heads, absl::Span< const Literal > literals, absl::Span< const AffineExpression > flat_node_dim_expressions, Model *model)
void SeparateFlowInequalities(int num_nodes, absl::Span< const int > tails, absl::Span< const int > heads, absl::Span< const AffineExpression > arc_capacities, std::function< void(const std::vector< bool > &in_subset, IntegerValue *min_incoming_flow, IntegerValue *min_outgoing_flow)> get_flows, const util_intops::StrongVector< IntegerVariable, double > &lp_values, LinearConstraintManager *manager, Model *model)
void SymmetrizeArcs(std::vector< ArcWithLpValue > *arcs)
void ExtractAllSubsetsFromForest(absl::Span< const int > parent, std::vector< int > *subset_data, std::vector< absl::Span< const int > > *subsets, int node_limit)
bool VariableIsPositive(IntegerVariable i)
bool AtMinOrMaxInt64I(IntegerValue t)
void GenerateInterestingSubsets(int num_nodes, absl::Span< const std::pair< int, int > > arcs, int stop_at_num_components, std::vector< int > *subset_data, std::vector< absl::Span< const int > > *subsets)
double ToDouble(IntegerValue value)
In SWIG mode, we don't want anything besides these top-level includes.
LinearRange operator==(const LinearExpr &lhs, const LinearExpr &rhs)
ClosedInterval::Iterator end(ClosedInterval interval)
ClosedInterval::Iterator begin(ClosedInterval interval)
ABSL_FLAG(bool, cp_model_dump_routes_support_graphs, false, "DEBUG ONLY. When set to true, SolveCpModel() dumps the arcs with " "non-zero LP values of the routes constraints, at decision level 0, " "which are used to subsequently generate cuts. The values are " "written as a SupportGraphProto in text format to " "'FLAGS_cp_model_dump_prefix'support_graph_{counter}.pb.txt.")
AffineExpression Negated() const
absl::AnyInvocable< bool(LinearConstraintManager *manager)> generate_cuts
std::vector< IntegerVariable > vars
NodeExpression Negated() const
std::vector< AffineExpression > flat_node_dim_expressions