40 const double kMinCutViolation = 1e-4;
43 double GetLiteralLpValue(
46 const IntegerEncoder* encoder) {
47 const IntegerVariable direct_view = encoder->GetLiteralView(lit);
49 return lp_values[direct_view];
51 const IntegerVariable opposite_view = encoder->GetLiteralView(lit.Negated());
53 return 1.0 - lp_values[opposite_view];
59 LinearConstraint GenerateKnapsackCutForCover(
60 const std::vector<IntegerVariable>& vars,
61 const std::vector<IntegerValue>& coeffs,
const IntegerValue upper_bound,
62 const IntegerTrail& integer_trail) {
63 CHECK_EQ(vars.size(), coeffs.size());
66 IntegerValue cut_upper_bound = IntegerValue(0);
67 IntegerValue max_coeff = coeffs[0];
69 IntegerValue slack = -upper_bound;
70 for (
int i = 0; i < vars.size(); ++i) {
71 const IntegerValue var_upper_bound =
72 integer_trail.LevelZeroUpperBound(vars[i]);
73 cut_upper_bound += var_upper_bound;
74 cut.vars.push_back(vars[i]);
75 cut.coeffs.push_back(IntegerValue(1));
76 max_coeff =
std::max(max_coeff, coeffs[i]);
77 slack += coeffs[i] * var_upper_bound;
79 CHECK_GT(slack, 0.0) <<
"Invalid cover for knapsack cut.";
80 cut_upper_bound -=
CeilRatio(slack, max_coeff);
82 cut.ub = cut_upper_bound;
83 VLOG(2) <<
"Generated Knapsack Constraint:" << cut.DebugString();
87 bool SolutionSatisfiesConstraint(
88 const LinearConstraint& constraint,
91 const double tolerance = 1e-6;
92 return (activity <= constraint.ub.value() + tolerance &&
93 activity >= constraint.lb.value() - tolerance)
98 bool SmallRangeAndAllCoefficientsMagnitudeAreTheSame(
99 const LinearConstraint& constraint, IntegerTrail* integer_trail) {
100 if (constraint.vars.empty())
return true;
102 const int64 magnitude = std::abs(constraint.coeffs[0].value());
103 for (
int i = 1; i < constraint.coeffs.size(); ++i) {
104 const IntegerVariable
var = constraint.vars[i];
105 if (integer_trail->LevelZeroUpperBound(
var) -
106 integer_trail->LevelZeroLowerBound(
var) >
110 if (std::abs(constraint.coeffs[i].value()) != magnitude) {
117 bool AllVarsTakeIntegerValue(
118 const std::vector<IntegerVariable> vars,
120 for (IntegerVariable
var : vars) {
121 if (std::abs(lp_values[
var] - std::round(lp_values[
var])) > 1e-6) {
137 int GetSmallestCoverSize(
const LinearConstraint& constraint,
138 const IntegerTrail& integer_trail) {
139 IntegerValue ub = constraint.ub;
140 std::vector<IntegerValue> sorted_terms;
141 for (
int i = 0; i < constraint.vars.size(); ++i) {
142 const IntegerValue coeff = constraint.coeffs[i];
143 const IntegerVariable
var = constraint.vars[i];
144 const IntegerValue var_ub = integer_trail.LevelZeroUpperBound(
var);
145 const IntegerValue var_lb = integer_trail.LevelZeroLowerBound(
var);
146 ub -= var_lb * coeff;
147 sorted_terms.push_back(coeff * (var_ub - var_lb));
149 std::sort(sorted_terms.begin(), sorted_terms.end(),
150 std::greater<IntegerValue>());
151 int smallest_cover_size = 0;
152 IntegerValue sorted_term_sum = IntegerValue(0);
153 while (sorted_term_sum <= ub &&
154 smallest_cover_size < constraint.vars.size()) {
155 sorted_term_sum += sorted_terms[smallest_cover_size++];
157 return smallest_cover_size;
160 bool ConstraintIsEligibleForLifting(
const LinearConstraint& constraint,
161 const IntegerTrail& integer_trail) {
162 for (
const IntegerVariable
var : constraint.vars) {
163 if (integer_trail.LevelZeroLowerBound(
var) != IntegerValue(0) ||
164 integer_trail.LevelZeroUpperBound(
var) != IntegerValue(1)) {
175 const std::vector<IntegerValue>& cut_vars_original_coefficients,
178 std::set<IntegerVariable> vars_in_cut;
179 for (IntegerVariable
var : cut->
vars) {
180 vars_in_cut.insert(
var);
183 std::vector<std::pair<IntegerValue, IntegerVariable>> non_zero_vars;
184 std::vector<std::pair<IntegerValue, IntegerVariable>> zero_vars;
185 for (
int i = 0; i < constraint.
vars.size(); ++i) {
186 const IntegerVariable
var = constraint.
vars[i];
191 if (vars_in_cut.find(
var) != vars_in_cut.end())
continue;
192 const IntegerValue coeff = constraint.
coeffs[i];
193 if (lp_values[
var] <= 1e-6) {
194 zero_vars.push_back({coeff,
var});
196 non_zero_vars.push_back({coeff,
var});
202 std::sort(non_zero_vars.rbegin(), non_zero_vars.rend());
203 std::sort(zero_vars.rbegin(), zero_vars.rend());
205 std::vector<std::pair<IntegerValue, IntegerVariable>> lifting_sequence(
206 std::move(non_zero_vars));
208 lifting_sequence.insert(lifting_sequence.end(), zero_vars.begin(),
212 std::vector<double> lifting_profits;
213 std::vector<double> lifting_weights;
214 for (
int i = 0; i < cut->
vars.size(); ++i) {
215 lifting_profits.push_back(cut->
coeffs[i].value());
216 lifting_weights.push_back(cut_vars_original_coefficients[i].
value());
220 bool is_lifted =
false;
221 bool is_solution_optimal =
false;
223 for (
auto entry : lifting_sequence) {
224 is_solution_optimal =
false;
225 const IntegerValue var_original_coeff = entry.first;
226 const IntegerVariable
var = entry.second;
227 const IntegerValue lifting_capacity = constraint.
ub - entry.first;
228 if (lifting_capacity <= IntegerValue(0))
continue;
229 knapsack_solver.
Init(lifting_profits, lifting_weights,
230 lifting_capacity.value());
236 const double knapsack_upper_bound =
238 const IntegerValue cut_coeff = cut->
ub - knapsack_upper_bound;
239 if (cut_coeff > IntegerValue(0)) {
242 cut->
coeffs.push_back(cut_coeff);
243 lifting_profits.push_back(cut_coeff.value());
244 lifting_weights.push_back(var_original_coeff.value());
254 IntegerValue ub = constraint.
ub;
256 for (
int i = 0; i < constraint.
vars.size(); ++i) {
257 const IntegerVariable
var = constraint.
vars[i];
259 const IntegerValue coeff = constraint.
coeffs[i];
260 if (var_ub.value() - lp_values[
var] <= 1.0 - kMinCutViolation) {
261 constraint_with_left_vars.
vars.push_back(
var);
262 constraint_with_left_vars.
coeffs.push_back(coeff);
266 ub -= coeff * var_lb;
269 constraint_with_left_vars.
ub = ub;
270 constraint_with_left_vars.
lb = constraint.
lb;
271 return constraint_with_left_vars;
276 IntegerValue term_sum = IntegerValue(0);
277 for (
int i = 0; i < constraint.
vars.size(); ++i) {
278 const IntegerVariable
var = constraint.
vars[i];
280 const IntegerValue coeff = constraint.
coeffs[i];
281 term_sum += coeff * var_ub;
283 if (term_sum <= constraint.
ub) {
284 VLOG(2) <<
"Filtered by cover filter";
294 std::vector<double> variable_upper_bound_distances;
295 for (
const IntegerVariable
var : preprocessed_constraint.
vars) {
297 variable_upper_bound_distances.push_back(var_ub.value() - lp_values[
var]);
300 const int smallest_cover_size =
301 GetSmallestCoverSize(preprocessed_constraint, integer_trail);
304 variable_upper_bound_distances.begin(),
305 variable_upper_bound_distances.begin() + smallest_cover_size - 1,
306 variable_upper_bound_distances.end());
307 double cut_lower_bound = 0.0;
308 for (
int i = 0; i < smallest_cover_size; ++i) {
309 cut_lower_bound += variable_upper_bound_distances[i];
311 if (cut_lower_bound >= 1.0 - kMinCutViolation) {
312 VLOG(2) <<
"Filtered by kappa heuristic";
321 std::sort(items.begin(), items.end(), std::greater<KnapsackItem>());
325 if (item.weight <= left_capacity) {
326 profit += item.profit;
327 left_capacity -= item.weight;
329 profit += (left_capacity / item.weight) * item.profit;
340 std::vector<KnapsackItem> items;
341 double capacity = -constraint.
ub.value() - 1.0;
342 double sum_variable_profit = 0;
343 for (
int i = 0; i < constraint.
vars.size(); ++i) {
344 const IntegerVariable
var = constraint.
vars[i];
347 const IntegerValue coeff = constraint.
coeffs[i];
349 item.
profit = var_ub.value() - lp_values[
var];
350 item.
weight = (coeff * (var_ub - var_lb)).value();
351 items.push_back(item);
353 sum_variable_profit += item.
profit;
358 if (sum_variable_profit - 1.0 + kMinCutViolation < 0.0)
return false;
361 const double knapsack_upper_bound =
363 if (knapsack_upper_bound < sum_variable_profit - 1.0 + kMinCutViolation) {
364 VLOG(2) <<
"Filtered by knapsack upper bound";
389 std::vector<LinearConstraint>* knapsack_constraints,
395 if (SmallRangeAndAllCoefficientsMagnitudeAreTheSame(constraint,
403 for (
int i = 0; i < constraint.
vars.size(); ++i) {
404 const IntegerVariable
var = constraint.
vars[i];
405 const IntegerValue coeff = constraint.
coeffs[i];
406 if (coeff > IntegerValue(0)) {
412 canonical_knapsack_form.
ub = constraint.
ub;
414 knapsack_constraints->push_back(canonical_knapsack_form);
421 for (
int i = 0; i < constraint.
vars.size(); ++i) {
422 const IntegerVariable
var = constraint.
vars[i];
423 const IntegerValue coeff = constraint.
coeffs[i];
424 if (coeff > IntegerValue(0)) {
430 canonical_knapsack_form.
ub = -constraint.
lb;
432 knapsack_constraints->push_back(canonical_knapsack_form);
438 const std::vector<LinearConstraint>& base_constraints,
439 const std::vector<IntegerVariable>& vars,
Model*
model) {
444 std::vector<LinearConstraint> knapsack_constraints;
452 if (constraint.vars.size() <= 2)
continue;
456 VLOG(1) <<
"#knapsack constraints: " << knapsack_constraints.size();
466 result.
generate_cuts = [implied_bounds_processor, knapsack_constraints, vars,
467 model, integer_trail](
474 if (AllVarsTakeIntegerValue(vars, lp_values))
return;
477 "Knapsack on demand cover cut generator");
478 int64 skipped_constraints = 0;
485 VLOG(2) <<
"Processing constraint: " << constraint.DebugString();
487 mutable_constraint = constraint;
489 lp_values, &mutable_constraint);
495 if (preprocessed_constraint.
vars.empty())
continue;
499 skipped_constraints++;
504 std::vector<double> profits;
505 profits.reserve(preprocessed_constraint.
vars.size());
508 std::vector<double> weights;
509 weights.reserve(preprocessed_constraint.
vars.size());
511 double capacity = -preprocessed_constraint.
ub.value() - 1.0;
517 double sum_variable_profit = 0;
521 for (
int i = 0; i < preprocessed_constraint.
vars.size(); ++i) {
522 const IntegerVariable
var = preprocessed_constraint.
vars[i];
526 const double variable_profit = var_ub - lp_values[
var];
527 profits.push_back(variable_profit);
529 sum_variable_profit += variable_profit;
532 weights.push_back(
weight);
537 std::vector<IntegerVariable> cut_vars;
538 std::vector<IntegerValue> cut_vars_original_coefficients;
540 VLOG(2) <<
"Knapsack size: " << profits.size();
544 const double time_limit_for_knapsack_solver =
550 bool is_solution_optimal =
false;
552 sum_variable_profit - 1.0 + kMinCutViolation);
556 auto time_limit_for_solver =
557 absl::make_unique<TimeLimit>(time_limit_for_knapsack_solver);
558 const double sum_of_distance_to_ub_for_vars_in_cover =
559 sum_variable_profit -
560 knapsack_solver.
Solve(time_limit_for_solver.get(),
561 &is_solution_optimal);
562 if (is_solution_optimal) {
563 VLOG(2) <<
"Knapsack Optimal solution found yay !";
565 if (time_limit_for_solver->LimitReached()) {
566 VLOG(1) <<
"Knapsack Solver run out of time limit.";
568 if (sum_of_distance_to_ub_for_vars_in_cover < 1.0 - kMinCutViolation) {
571 IntegerValue constraint_ub_for_cut = preprocessed_constraint.
ub;
572 std::set<IntegerVariable> vars_in_cut;
573 for (
int i = 0; i < preprocessed_constraint.
vars.size(); ++i) {
574 const IntegerVariable
var = preprocessed_constraint.
vars[i];
577 cut_vars.push_back(
var);
578 cut_vars_original_coefficients.push_back(
coefficient);
579 vars_in_cut.insert(
var);
586 cut_vars, cut_vars_original_coefficients, constraint_ub_for_cut,
590 bool is_lifted =
false;
591 if (ConstraintIsEligibleForLifting(cut, *integer_trail)) {
593 cut_vars_original_coefficients, *integer_trail,
599 CHECK(!SolutionSatisfiesConstraint(cut, lp_values));
600 manager->AddCut(cut, is_lifted ?
"LiftedKnapsack" :
"Knapsack",
604 if (skipped_constraints > 0) {
605 VLOG(2) <<
"Skipped constraints: " << skipped_constraints;
616 IntegerValue
GetFactorT(IntegerValue rhs_remainder, IntegerValue divisor,
617 IntegerValue max_t) {
619 return rhs_remainder == 0
625 IntegerValue rhs_remainder, IntegerValue divisor, IntegerValue t,
626 IntegerValue max_scaling) {
638 const IntegerValue size = divisor - rhs_remainder;
639 if (max_scaling == 1 || size == 1) {
643 return [t, divisor](IntegerValue coeff) {
646 }
else if (size <= max_scaling) {
647 return [size, rhs_remainder, t, divisor](IntegerValue coeff) {
649 const IntegerValue remainder = t * coeff -
ratio * divisor;
650 const IntegerValue diff = remainder - rhs_remainder;
653 }
else if (max_scaling.value() * rhs_remainder.value() < divisor) {
663 return [t, divisor, max_scaling](IntegerValue coeff) {
665 const IntegerValue remainder = t * coeff -
ratio * divisor;
666 const IntegerValue bucket =
FloorRatio(remainder * max_scaling, divisor);
667 return max_scaling *
ratio + bucket;
692 return [size, rhs_remainder, t, divisor, max_scaling](IntegerValue coeff) {
694 const IntegerValue remainder = t * coeff -
ratio * divisor;
695 const IntegerValue diff = remainder - rhs_remainder;
696 const IntegerValue bucket =
697 diff > 0 ?
CeilRatio(diff * (max_scaling - 1), size)
699 return max_scaling *
ratio + bucket;
712 const int size = lp_values.size();
713 if (size == 0)
return;
726 relevant_indices_.clear();
727 relevant_lp_values_.clear();
728 relevant_coeffs_.clear();
729 relevant_bound_diffs_.clear();
731 adjusted_coeffs_.clear();
734 IntegerValue max_magnitude(0);
735 for (
int i = 0; i < size; ++i) {
738 max_magnitude =
std::max(max_magnitude, magnitude);
744 bool overflow =
false;
745 change_sign_at_postprocessing_.assign(size,
false);
746 for (
int i = 0; i < size; ++i) {
747 if (cut->
coeffs[i] == 0)
continue;
752 double lp_value = lp_values[i];
755 const IntegerValue bound_diff =
756 IntegerValue(
CapSub(ub.value(), lb.value()));
769 const double lb_dist = std::abs(lp_value -
ToDouble(lb));
770 const double ub_dist = std::abs(lp_value -
ToDouble(ub));
773 if ((bias * lb_dist > ub_dist && cut->
coeffs[i] < 0) ||
774 (lb_dist > bias * ub_dist && cut->
coeffs[i] > 0)) {
775 change_sign_at_postprocessing_[i] =
true;
777 lp_value = -lp_value;
792 if (bound_diff == 0) {
793 cut->
coeffs[i] = IntegerValue(0);
797 if (std::abs(lp_value) > 1e-2) {
798 relevant_coeffs_.push_back(cut->
coeffs[i]);
799 relevant_indices_.push_back(i);
800 relevant_lp_values_.push_back(lp_value);
801 relevant_bound_diffs_.push_back(bound_diff);
802 divisors_.push_back(magnitude);
807 if (relevant_coeffs_.empty()) {
808 VLOG(2) <<
"Issue, nothing to cut.";
828 double best_scaled_violation = 0.01;
829 const IntegerValue remainder_threshold(max_magnitude / 1000);
840 if (overflow || max_magnitude >= threshold) {
841 VLOG(2) <<
"Issue, overflow.";
845 const IntegerValue max_t = threshold / max_magnitude;
856 const IntegerValue divisor_threshold = max_magnitude / 10;
857 for (
int i = 0; i < divisors_.size(); ++i) {
858 if (divisors_[i] <= divisor_threshold)
continue;
859 divisors_[new_size++] = divisors_[i];
861 divisors_.resize(new_size);
868 IntegerValue best_divisor(0);
869 for (
const IntegerValue divisor : divisors_) {
871 const IntegerValue initial_rhs_remainder =
873 if (initial_rhs_remainder <= remainder_threshold)
continue;
875 IntegerValue temp_ub = cut->
ub;
876 adjusted_coeffs_.clear();
893 const IntegerValue adjust_threshold =
894 (divisor - initial_rhs_remainder - 1) / IntegerValue(size);
895 if (adjust_threshold > 0) {
899 bool early_abort =
false;
900 double loss_lb = 0.0;
901 const double threshold =
ToDouble(initial_rhs_remainder);
903 for (
int i = 0; i < relevant_coeffs_.size(); ++i) {
905 const IntegerValue coeff = relevant_coeffs_[i];
906 const IntegerValue remainder =
907 CeilRatio(coeff, divisor) * divisor - coeff;
909 if (divisor - remainder <= initial_rhs_remainder) {
912 loss_lb +=
ToDouble(divisor - remainder) * relevant_lp_values_[i];
913 if (loss_lb >= threshold) {
920 const IntegerValue diff = relevant_bound_diffs_[i];
921 if (remainder > 0 && remainder <= adjust_threshold &&
922 CapProd(diff.value(), remainder.value()) <= adjust_threshold) {
923 temp_ub += remainder * diff;
924 adjusted_coeffs_.push_back({i, coeff + remainder});
928 if (early_abort)
continue;
932 const IntegerValue rhs_remainder =
933 temp_ub -
FloorRatio(temp_ub, divisor) * divisor;
934 if (rhs_remainder == 0)
continue;
937 rhs_remainder, divisor,
GetFactorT(rhs_remainder, divisor, max_t),
948 const double threshold = scaling *
ToDouble(rhs_remainder);
955 double violation = -
ToDouble(f(temp_ub));
956 double l2_norm = 0.0;
957 bool early_abort =
false;
958 int adjusted_coeffs_index = 0;
959 for (
int i = 0; i < relevant_coeffs_.size(); ++i) {
960 IntegerValue coeff = relevant_coeffs_[i];
963 if (adjusted_coeffs_index < adjusted_coeffs_.size() &&
964 adjusted_coeffs_[adjusted_coeffs_index].first == i) {
965 coeff = adjusted_coeffs_[adjusted_coeffs_index].second;
966 adjusted_coeffs_index++;
969 if (coeff == 0)
continue;
970 const IntegerValue new_coeff = f(coeff);
971 const double new_coeff_double =
ToDouble(new_coeff);
972 const double lp_value = relevant_lp_values_[i];
974 l2_norm += new_coeff_double * new_coeff_double;
975 violation += new_coeff_double * lp_value;
976 loss += (scaling *
ToDouble(coeff) - new_coeff_double) * lp_value;
977 if (loss >= threshold) {
982 if (early_abort)
continue;
986 violation /= sqrt(l2_norm);
987 if (violation > best_scaled_violation) {
988 best_scaled_violation = violation;
989 best_divisor = divisor;
993 if (best_divisor == 0) {
1003 const IntegerValue initial_rhs_remainder =
1005 const IntegerValue adjust_threshold =
1006 (best_divisor - initial_rhs_remainder - 1) / IntegerValue(size);
1007 if (adjust_threshold > 0) {
1008 for (
int i = 0; i < relevant_indices_.size(); ++i) {
1009 const int index = relevant_indices_[i];
1010 const IntegerValue diff = relevant_bound_diffs_[i];
1011 if (diff > adjust_threshold)
continue;
1015 const IntegerValue remainder =
1016 CeilRatio(coeff, best_divisor) * best_divisor - coeff;
1017 if (
CapProd(diff.value(), remainder.value()) <= adjust_threshold) {
1018 cut->
ub += remainder * diff;
1031 const IntegerValue rhs_remainder =
1033 IntegerValue factor_t =
GetFactorT(rhs_remainder, best_divisor, max_t);
1040 remainders_.clear();
1041 for (
int i = 0; i < size; ++i) {
1042 const IntegerValue coeff = cut->
coeffs[i];
1043 const IntegerValue r =
1044 coeff -
FloorRatio(coeff, best_divisor) * best_divisor;
1045 if (r > rhs_remainder) remainders_.push_back(r);
1048 if (remainders_.size() <= 100) {
1050 for (
const IntegerValue r : remainders_) {
1051 best_rs_.push_back(f(r));
1053 IntegerValue best_d = f(best_divisor);
1058 for (
const IntegerValue t :
1059 {IntegerValue(1),
GetFactorT(rhs_remainder, best_divisor, max_t)}) {
1060 for (IntegerValue s(2); s <= options.
max_scaling; ++s) {
1063 int num_strictly_better = 0;
1065 const IntegerValue d = g(best_divisor);
1066 for (
int i = 0; i < best_rs_.size(); ++i) {
1067 const IntegerValue temp = g(remainders_[i]);
1068 if (temp * best_d < best_rs_[i] * d)
break;
1069 if (temp * best_d > best_rs_[i] * d) num_strictly_better++;
1070 rs_.push_back(temp);
1072 if (rs_.size() == best_rs_.size() && num_strictly_better > 0) {
1084 cut->
ub = f(cut->
ub);
1089 num_lifted_booleans_ = 0;
1090 if (ib_processor !=
nullptr) {
1091 for (
int i = 0; i < size; ++i) {
1092 const IntegerValue coeff = cut->
coeffs[i];
1093 if (coeff == 0)
continue;
1095 IntegerVariable
var = cut->
vars[i];
1096 if (change_sign_at_postprocessing_[i]) {
1114 const IntegerValue coeff_b =
1117 if (coeff_b == 0)
continue;
1119 ++num_lifted_booleans_;
1121 tmp_terms_.push_back({info.
bool_var, coeff_b});
1123 tmp_terms_.push_back({info.
bool_var, -coeff_b});
1124 cut->
ub =
CapAdd(-coeff_b.value(), cut->
ub.value());
1133 for (
int i = 0; i < size; ++i) {
1134 IntegerValue coeff = cut->
coeffs[i];
1135 if (coeff == 0)
continue;
1137 if (coeff == 0)
continue;
1138 if (change_sign_at_postprocessing_[i]) {
1139 cut->
ub = IntegerValue(
1141 tmp_terms_.push_back({cut->
vars[i], -coeff});
1143 cut->
ub = IntegerValue(
1145 tmp_terms_.push_back({cut->
vars[i], coeff});
1159 const int base_size = lp_values.size();
1165 IntegerValue rhs = base_ct.
ub;
1166 IntegerValue sum_of_diff(0);
1167 IntegerValue max_base_magnitude(0);
1168 for (
int i = 0; i < base_size; ++i) {
1169 const IntegerValue coeff = base_ct.
coeffs[i];
1170 const IntegerValue positive_coeff =
IntTypeAbs(coeff);
1171 max_base_magnitude =
std::max(max_base_magnitude, positive_coeff);
1173 if (!
AddProductTo(positive_coeff, bound_diff, &sum_of_diff)) {
1176 const IntegerValue diff = positive_coeff * bound_diff;
1190 double activity = 0.0;
1192 std::sort(terms_.begin(), terms_.end(), [](
const Term&
a,
const Term&
b) {
1193 if (a.dist_to_max_value == b.dist_to_max_value) {
1195 return a.positive_coeff < b.positive_coeff;
1197 return a.dist_to_max_value <
b.dist_to_max_value;
1199 for (
int i = 0; i < terms_.size(); ++i) {
1200 const Term& term = terms_[i];
1201 activity += term.dist_to_max_value;
1210 if (activity > 1.0) {
1225 if (rhs >= 0)
return false;
1226 if (new_size == 0)
return false;
1234 terms_.resize(new_size);
1235 std::sort(terms_.begin(), terms_.end(), [](
const Term&
a,
const Term&
b) {
1236 if (a.positive_coeff == b.positive_coeff) {
1237 return a.dist_to_max_value > b.dist_to_max_value;
1239 return a.positive_coeff >
b.positive_coeff;
1241 in_cut_.assign(base_ct.vars.size(),
false);
1244 cut_.ub = IntegerValue(-1);
1245 IntegerValue max_coeff(0);
1246 for (
const Term term : terms_) {
1247 if (term.diff + rhs < 0) {
1251 in_cut_[term.index] =
true;
1252 max_coeff =
std::max(max_coeff, term.positive_coeff);
1253 cut_.vars.push_back(base_ct.vars[term.index]);
1254 if (base_ct.coeffs[term.index] > 0) {
1255 cut_.coeffs.push_back(IntegerValue(1));
1258 cut_.coeffs.push_back(IntegerValue(-1));
1267 if (max_coeff == 0)
return true;
1268 if (max_coeff < -rhs) {
1269 const IntegerValue m =
FloorRatio(-rhs - 1, max_coeff);
1270 rhs += max_coeff * m;
1289 const IntegerValue slack = -rhs;
1290 const IntegerValue remainder = max_coeff - slack;
1292 const IntegerValue max_scaling(
std::min(
1295 IntegerValue(1), max_scaling);
1297 const IntegerValue scaling = f(max_coeff);
1299 for (
int i = 0; i < cut_.coeffs.size(); ++i) cut_.coeffs[i] *= scaling;
1304 for (
int i = 0; i < base_size; ++i) {
1305 if (in_cut_[i])
continue;
1306 const IntegerValue positive_coeff =
IntTypeAbs(base_ct.coeffs[i]);
1307 const IntegerValue new_coeff = f(positive_coeff);
1308 if (new_coeff == 0)
continue;
1311 if (base_ct.coeffs[i] > 0) {
1313 cut_.coeffs.push_back(new_coeff);
1314 cut_.vars.push_back(base_ct.vars[i]);
1318 cut_.coeffs.push_back(-new_coeff);
1319 cut_.vars.push_back(base_ct.vars[i]);
1333 result.
vars = {z, x, y};
1337 [z, x, y, integer_trail](
1346 const int64 kMaxSafeInteger = (
int64{1} << 53) - 1;
1348 if (
CapProd(x_ub, y_ub) >= kMaxSafeInteger) {
1349 VLOG(3) <<
"Potential overflow in PositiveMultiplicationCutGenerator";
1353 const double x_lp_value = lp_values[x];
1354 const double y_lp_value = lp_values[y];
1355 const double z_lp_value = lp_values[z];
1363 auto try_add_above_cut = [manager, z_lp_value, x_lp_value, y_lp_value,
1364 x, y, z, &lp_values](
1366 if (-z_lp_value + x_lp_value * x_coeff + y_lp_value * y_coeff >=
1367 rhs + kMinCutViolation) {
1369 cut.
vars.push_back(z);
1370 cut.
coeffs.push_back(IntegerValue(-1));
1372 cut.
vars.push_back(x);
1373 cut.
coeffs.push_back(IntegerValue(x_coeff));
1376 cut.
vars.push_back(y);
1377 cut.
coeffs.push_back(IntegerValue(y_coeff));
1380 cut.
ub = IntegerValue(rhs);
1381 manager->AddCut(cut,
"PositiveProduct", lp_values);
1386 auto try_add_below_cut = [manager, z_lp_value, x_lp_value, y_lp_value,
1387 x, y, z, &lp_values](
1389 if (-z_lp_value + x_lp_value * x_coeff + y_lp_value * y_coeff <=
1390 rhs - kMinCutViolation) {
1392 cut.
vars.push_back(z);
1393 cut.
coeffs.push_back(IntegerValue(-1));
1395 cut.
vars.push_back(x);
1396 cut.
coeffs.push_back(IntegerValue(x_coeff));
1399 cut.
vars.push_back(y);
1400 cut.
coeffs.push_back(IntegerValue(y_coeff));
1402 cut.
lb = IntegerValue(rhs);
1404 manager->AddCut(cut,
"PositiveProduct", lp_values);
1415 try_add_above_cut(y_lb, x_lb, x_lb * y_lb);
1416 try_add_above_cut(y_ub, x_ub, x_ub * y_ub);
1417 try_add_below_cut(y_ub, x_lb, x_lb * y_ub);
1418 try_add_below_cut(y_lb, x_ub, x_ub * y_lb);
1427 result.
vars = {y, x};
1431 [y, x, integer_trail](
1437 if (x_lb == x_ub)
return;
1440 if (x_ub > (
int64{1} << 31))
return;
1443 const double y_lp_value = lp_values[y];
1444 const double x_lp_value = lp_values[x];
1449 const int64 y_lb = x_lb * x_lb;
1450 const int64 above_slope = x_ub + x_lb;
1451 const double max_lp_y = y_lb + above_slope * (x_lp_value - x_lb);
1452 if (y_lp_value >= max_lp_y + kMinCutViolation) {
1455 above_cut.
vars.push_back(y);
1456 above_cut.
coeffs.push_back(IntegerValue(1));
1457 above_cut.
vars.push_back(x);
1458 above_cut.
coeffs.push_back(IntegerValue(-above_slope));
1460 above_cut.
ub = IntegerValue(-x_lb * x_ub);
1461 manager->AddCut(above_cut,
"SquareUpper", lp_values);
1470 const int64 x_floor =
static_cast<int64>(std::floor(x_lp_value));
1471 const int64 below_slope = 2 * x_floor + 1;
1472 const double min_lp_y =
1473 below_slope * x_lp_value - x_floor - x_floor * x_floor;
1474 if (min_lp_y >= y_lp_value + kMinCutViolation) {
1478 below_cut.
vars.push_back(y);
1479 below_cut.
coeffs.push_back(IntegerValue(1));
1480 below_cut.
vars.push_back(x);
1481 below_cut.
coeffs.push_back(-IntegerValue(below_slope));
1482 below_cut.
lb = IntegerValue(-x_floor - x_floor * x_floor);
1484 manager->AddCut(below_cut,
"SquareLower", lp_values);
1491 void ImpliedBoundsProcessor::ProcessUpperBoundedConstraint(
1494 ProcessUpperBoundedConstraintWithSlackCreation(
1495 false, IntegerVariable(0), lp_values,
1500 ImpliedBoundsProcessor::GetCachedImpliedBoundInfo(IntegerVariable
var) {
1501 auto it = cache_.find(
var);
1502 if (it != cache_.end())
return it->second;
1507 ImpliedBoundsProcessor::ComputeBestImpliedBound(
1508 IntegerVariable
var,
1510 auto it = cache_.find(
var);
1511 if (it != cache_.end())
return it->second;
1512 BestImpliedBoundInfo result;
1513 const IntegerValue lb = integer_trail_->LevelZeroLowerBound(
var);
1515 implied_bounds_->GetImpliedBounds(
var)) {
1527 const IntegerValue diff = entry.lower_bound - lb;
1529 const double bool_lp_value = entry.is_positive
1530 ? lp_values[entry.literal_view]
1531 : 1.0 - lp_values[entry.literal_view];
1532 const double slack_lp_value =
1537 if (slack_lp_value < -1e-4) {
1538 LinearConstraint ib_cut;
1540 std::vector<std::pair<IntegerVariable, IntegerValue>> terms;
1541 if (entry.is_positive) {
1543 terms.push_back({entry.literal_view, diff});
1544 terms.push_back({
var, IntegerValue(-1)});
1548 terms.push_back({entry.literal_view, -diff});
1549 terms.push_back({
var, IntegerValue(-1)});
1550 ib_cut.ub = -entry.lower_bound;
1553 ib_cut_pool_.AddCut(std::move(ib_cut),
"IB", lp_values);
1559 if (slack_lp_value + 1e-4 < result.slack_lp_value ||
1560 (slack_lp_value < result.slack_lp_value + 1e-4 &&
1561 diff > result.bound_diff)) {
1562 result.bool_lp_value = bool_lp_value;
1563 result.slack_lp_value = slack_lp_value;
1565 result.bound_diff = diff;
1566 result.is_positive = entry.is_positive;
1567 result.bool_var = entry.literal_view;
1570 cache_[
var] = result;
1575 void ImpliedBoundsProcessor::SeparateSomeImpliedBoundCuts(
1577 for (
const IntegerVariable
var :
1578 implied_bounds_->VariablesWithImpliedBounds()) {
1580 ComputeBestImpliedBound(
var, lp_values);
1584 void ImpliedBoundsProcessor::ProcessUpperBoundedConstraintWithSlackCreation(
1585 bool substitute_only_inner_variables, IntegerVariable first_slack,
1589 IntegerValue new_ub = cut->
ub;
1590 bool changed =
false;
1593 int64 overflow_detection = 0;
1595 const int size = cut->
vars.size();
1596 for (
int i = 0; i < size; ++i) {
1597 IntegerVariable
var = cut->
vars[i];
1598 IntegerValue coeff = cut->
coeffs[i];
1620 const int old_size = tmp_terms_.size();
1623 bool keep_term =
false;
1637 if (substitute_only_inner_variables) {
1638 const IntegerValue lb = integer_trail_->LevelZeroLowerBound(
var);
1639 const IntegerValue ub = integer_trail_->LevelZeroUpperBound(
var);
1640 if (lp_values[
var] -
ToDouble(lb) < 1e-2) keep_term =
true;
1641 if (
ToDouble(ub) - lp_values[
var] < 1e-2) keep_term =
true;
1645 if (slack_infos ==
nullptr) {
1652 tmp_terms_.push_back({
var, coeff});
1655 const IntegerValue lb = integer_trail_->LevelZeroLowerBound(
var);
1656 const IntegerValue ub = integer_trail_->LevelZeroUpperBound(
var);
1661 slack_info.
ub = ub - lb;
1667 VLOG(2) <<
"Overflow";
1670 if (slack_infos !=
nullptr) {
1671 tmp_terms_.push_back({first_slack, coeff});
1675 slack_info.
terms.push_back({
var, IntegerValue(1)});
1678 slack_infos->push_back(slack_info);
1685 VLOG(2) <<
"Overflow";
1688 if (slack_infos !=
nullptr) {
1689 tmp_terms_.push_back({first_slack, coeff});
1693 slack_info.
terms.push_back({
var, IntegerValue(1)});
1696 slack_infos->push_back(slack_info);
1704 for (
int i = old_size; i < tmp_terms_.size(); ++i) {
1705 overflow_detection =
1706 CapAdd(overflow_detection, std::abs(tmp_terms_[i].second.value()));
1711 VLOG(2) <<
"Overflow";
1714 if (!changed)
return;
1725 bool ImpliedBoundsProcessor::DebugSlack(IntegerVariable first_slack,
1728 const std::vector<SlackInfo>& info) {
1730 IntegerValue new_ub = cut.
ub;
1731 for (
int i = 0; i < cut.
vars.size(); ++i) {
1733 if (cut.
vars[i] < first_slack) {
1734 tmp_terms_.push_back({cut.
vars[i], cut.
coeffs[i]});
1739 const IntegerValue multiplier = cut.
coeffs[i];
1740 const int index = (cut.
vars[i].value() - first_slack.value()) / 2;
1741 for (
const std::pair<IntegerVariable, IntegerValue>& term :
1742 info[
index].terms) {
1743 tmp_terms_.push_back({term.first, term.second * multiplier});
1745 new_ub -= multiplier * info[
index].offset;
1750 tmp_cut.
ub = new_ub;
1760 for (
int i = 0; i < initial_cut.
vars.size(); ++i) {
1761 tmp_terms_.push_back({initial_cut.
vars[i], initial_cut.
coeffs[i]});
1764 tmp_copy.
ub = new_ub;
1768 if (tmp_cut == tmp_copy)
return true;
1779 void TryToGenerateAllDiffCut(
1780 const std::vector<std::pair<double, IntegerVariable>>& sorted_vars_lp,
1785 std::vector<IntegerVariable> current_set_vars;
1787 for (
auto value_var : sorted_vars_lp) {
1788 sum += value_var.first;
1789 const IntegerVariable
var = value_var.second;
1794 current_set_vars.push_back(
var);
1795 const int64 required_min_sum =
1797 const int64 required_max_sum =
1799 if (sum < required_min_sum || sum > required_max_sum) {
1801 for (IntegerVariable
var : current_set_vars) {
1804 cut.
lb = IntegerValue(required_min_sum);
1805 cut.
ub = IntegerValue(required_max_sum);
1806 manager->
AddCut(cut,
"all_diff", lp_values);
1810 current_set_vars.clear();
1811 current_union =
Domain();
1819 const std::vector<IntegerVariable>& vars,
Model*
model) {
1825 [vars, integer_trail, trail](
1831 if (trail->CurrentDecisionLevel() > 0)
return;
1832 std::vector<std::pair<double, IntegerVariable>> sorted_vars;
1833 for (
const IntegerVariable
var : vars) {
1838 sorted_vars.push_back(std::make_pair(lp_values[
var],
var));
1840 std::sort(sorted_vars.begin(), sorted_vars.end());
1841 TryToGenerateAllDiffCut(sorted_vars, *integer_trail, lp_values,
1844 std::reverse(sorted_vars.begin(), sorted_vars.end());
1845 TryToGenerateAllDiffCut(sorted_vars, *integer_trail, lp_values,
1848 VLOG(1) <<
"Created all_diff cut generator of size: " << vars.size();
1854 IntegerValue MaxCornerDifference(
const IntegerVariable
var,
1855 const IntegerValue w1_i,
1856 const IntegerValue w2_i,
1857 const IntegerTrail& integer_trail) {
1858 const IntegerValue lb = integer_trail.LevelZeroLowerBound(
var);
1859 const IntegerValue ub = integer_trail.LevelZeroUpperBound(
var);
1860 return std::max((w2_i - w1_i) * lb, (w2_i - w1_i) * ub);
1869 IntegerValue MPlusCoefficient(
1870 const std::vector<IntegerVariable>& x_vars,
1871 const std::vector<LinearExpression>& exprs,
1873 const int max_index,
const IntegerTrail& integer_trail) {
1874 IntegerValue coeff = exprs[max_index].offset;
1877 for (
const IntegerVariable
var : x_vars) {
1878 const int target_index = variable_partition[
var];
1879 if (max_index != target_index) {
1880 coeff += MaxCornerDifference(
1891 double ComputeContribution(
1892 const IntegerVariable xi_var,
const std::vector<IntegerVariable>& z_vars,
1893 const std::vector<LinearExpression>& exprs,
1895 const IntegerTrail& integer_trail,
const int target_index) {
1897 CHECK_LT(target_index, exprs.size());
1898 const LinearExpression& target_expr = exprs[target_index];
1899 const double xi_value = lp_values[xi_var];
1901 double contrib = wt_i.value() * xi_value;
1902 for (
int expr_index = 0; expr_index < exprs.size(); ++expr_index) {
1903 if (expr_index == target_index)
continue;
1904 const LinearExpression& max_expr = exprs[expr_index];
1905 const double z_max_value = lp_values[z_vars[expr_index]];
1906 const IntegerValue corner_value = MaxCornerDifference(
1909 contrib += corner_value.value() * z_max_value;
1916 const IntegerVariable target,
const std::vector<LinearExpression>& exprs,
1917 const std::vector<IntegerVariable>& z_vars,
Model*
model) {
1919 std::vector<IntegerVariable> x_vars;
1920 result.
vars = {target};
1921 const int num_exprs = exprs.size();
1922 for (
int i = 0; i < num_exprs; ++i) {
1923 result.
vars.push_back(z_vars[i]);
1924 x_vars.insert(x_vars.end(), exprs[i].vars.begin(), exprs[i].vars.end());
1928 DCHECK(std::all_of(x_vars.begin(), x_vars.end(), [](IntegerVariable
var) {
1929 return VariableIsPositive(var);
1931 result.
vars.insert(result.
vars.end(), x_vars.begin(), x_vars.end());
1935 [x_vars, z_vars, target, num_exprs, exprs, integer_trail,
model](
1939 lp_values.size(), -1);
1941 lp_values.size(), std::numeric_limits<double>::infinity());
1942 for (
int expr_index = 0; expr_index < num_exprs; ++expr_index) {
1943 for (
const IntegerVariable
var : x_vars) {
1944 const double contribution = ComputeContribution(
1945 var, z_vars, exprs, lp_values, *integer_trail, expr_index);
1946 const double prev_contribution = variable_partition_contrib[
var];
1947 if (contribution < prev_contribution) {
1948 variable_partition[
var] = expr_index;
1949 variable_partition_contrib[
var] = contribution;
1956 double violation = lp_values[target];
1957 cut.
AddTerm(target, IntegerValue(-1));
1959 for (
const IntegerVariable xi_var : x_vars) {
1960 const int input_index = variable_partition[xi_var];
1963 if (coeff != IntegerValue(0)) {
1966 violation -= coeff.value() * lp_values[xi_var];
1968 for (
int expr_index = 0; expr_index < num_exprs; ++expr_index) {
1969 const IntegerVariable z_var = z_vars[expr_index];
1970 const IntegerValue z_coeff = MPlusCoefficient(
1971 x_vars, exprs, variable_partition, expr_index, *integer_trail);
1972 if (z_coeff != IntegerValue(0)) {
1975 violation -= z_coeff.value() * lp_values[z_var];
1977 if (violation > 1e-2) {
1978 manager->
AddCut(cut.
Build(),
"LinMax", lp_values);
1986 std::vector<IntegerVariable>* vars) {
1988 for (
int t = 0; t < helper->
NumTasks(); ++t) {
1990 vars->push_back(helper->
Starts()[t].var);
1993 vars->push_back(helper->
Sizes()[t].var);
1996 vars->push_back(helper->
Ends()[t].var);
2007 vars->push_back(direct_view);
2018 LinearConstraintManager*)>
2021 const std::vector<IntegerVariable>& demands,
2027 return [
capacity, demands, trail, integer_trail, helper,
model, cut_name,
2032 const auto demand_is_fixed = [integer_trail, &demands](
int i) {
2033 return demands.empty() || integer_trail->IsFixed(demands[i]);
2035 const auto demand_min = [integer_trail, &demands](
int i) {
2036 return demands.empty() ? IntegerValue(1)
2037 : integer_trail->LowerBound(demands[i]);
2039 const auto demand_max = [integer_trail, &demands](
int i) {
2040 return demands.empty() ? IntegerValue(1)
2041 : integer_trail->UpperBound(demands[i]);
2044 std::vector<int> active_intervals;
2045 for (
int i = 0; i < helper->
NumTasks(); ++i) {
2046 if (!helper->
IsAbsent(i) && demand_max(i) > 0 && helper->
SizeMin(i) > 0) {
2047 active_intervals.push_back(i);
2051 if (active_intervals.size() < 2)
return;
2053 std::sort(active_intervals.begin(), active_intervals.end(),
2054 [helper](
int a,
int b) {
2055 return helper->StartMin(a) < helper->StartMin(b) ||
2056 (helper->StartMin(a) == helper->StartMin(b) &&
2057 helper->EndMax(a) < helper->EndMax(b));
2060 const IntegerValue capacity_max = integer_trail->UpperBound(
capacity);
2062 for (
int i1 = 0; i1 + 1 < active_intervals.size(); ++i1) {
2063 const int start_index = active_intervals[i1];
2068 if (helper->
StartMin(start_index) == processed_start) {
2071 processed_start = helper->
StartMin(start_index);
2076 int end_index_of_max_violation = -1;
2077 double max_relative_violation = 1.01;
2078 IntegerValue span_of_max_violation(0);
2081 double energy_lp = 0.0;
2087 std::vector<int> residual_tasks(active_intervals.begin() + i1,
2088 active_intervals.end());
2090 residual_tasks.begin(), residual_tasks.end(),
2091 [&](
int a,
int b) { return helper->EndMax(a) < helper->EndMax(b); });
2096 for (
int i2 = 0; i2 < residual_tasks.size(); ++i2) {
2097 const int t = residual_tasks[i2];
2099 if (demand_is_fixed(t)) {
2103 energy_lp +=
ToDouble(demand_min(t)) *
2104 helper->
Sizes()[t].LpValue(lp_values);
2107 DCHECK(!demands.empty());
2110 DCHECK(!demands.empty());
2112 ToDouble(demand_min(t)) * helper->
Sizes()[t].LpValue(lp_values);
2126 const double relative_violation =
2127 energy_lp /
ToDouble((max_of_ends - min_of_starts) * capacity_max);
2128 if (relative_violation > max_relative_violation) {
2129 end_index_of_max_violation = i2;
2130 max_relative_violation = relative_violation;
2131 span_of_max_violation = max_of_ends - min_of_starts;
2135 if (end_index_of_max_violation == -1)
continue;
2138 bool cut_generated =
true;
2139 bool has_opt_cuts =
false;
2140 bool has_quadratic_cuts =
false;
2146 for (
int i2 = 0; i2 <= end_index_of_max_violation; ++i2) {
2147 const int t = residual_tasks[i2];
2149 if (demand_is_fixed(t)) {
2156 DCHECK(!demands.empty());
2159 DCHECK(!demands.empty());
2172 has_quadratic_cuts =
true;
2175 has_opt_cuts =
true;
2176 if (!helper->
SizeIsFixed(t) || !demand_is_fixed(t)) {
2177 has_quadratic_cuts =
true;
2180 helper->
SizeMin(t) * demand_min(t))) {
2181 cut_generated =
false;
2187 if (cut_generated) {
2188 std::string full_name = cut_name;
2189 if (has_opt_cuts) full_name.append(
"_opt");
2190 if (has_quadratic_cuts) full_name.append(
"_quad");
2192 manager->
AddCut(cut.
Build(), cut_name, lp_values);
2199 const std::vector<IntervalVariable>& intervals,
2200 const IntegerVariable
capacity,
const std::vector<IntegerVariable>& demands,
2206 model->TakeOwnership(helper);
2208 result.
vars = demands;
2218 const std::vector<IntervalVariable>& intervals,
2219 const IntegerVariable
capacity,
const std::vector<IntegerVariable>& demands,
2225 model->TakeOwnership(helper);
2227 result.
vars = demands;
2247 std::vector<Event> events;
2250 for (
int i = 0; i < helper->
NumTasks(); ++i) {
2259 e1.interval_index = i;
2261 e1.demand = demands[i];
2266 e2.positive =
false;
2267 events.push_back(e1);
2268 events.push_back(e2);
2274 std::sort(events.begin(), events.end(),
2275 [](
const Event i,
const Event j) {
2276 if (i.time == j.time) {
2277 if (i.positive == j.positive) {
2278 return i.interval_index < j.interval_index;
2282 return i.time < j.time;
2285 std::vector<Event> cut_events;
2286 bool added_positive_event =
false;
2287 for (
const Event& e : events) {
2289 added_positive_event =
true;
2290 cut_events.push_back(e);
2293 if (added_positive_event && cut_events.size() > 1) {
2295 bool cut_generated =
true;
2299 for (
const Event& cut_event : cut_events) {
2300 if (helper->
IsPresent(cut_event.interval_index)) {
2301 cut.
AddTerm(cut_event.demand, IntegerValue(1));
2305 integer_trail->LowerBound(cut_event.demand));
2306 if (!cut_generated)
break;
2309 if (cut_generated) {
2312 manager->
AddCut(cut.
Build(),
"Cumulative", lp_values);
2317 for (
int i = 0; i < cut_events.size(); ++i) {
2318 if (cut_events[i].interval_index == e.interval_index) {
2321 cut_events[new_size] = cut_events[i];
2324 cut_events.resize(new_size);
2325 added_positive_event =
false;
2332 const std::vector<IntervalVariable>& intervals,
Model*
model) {
2337 model->TakeOwnership(helper);
2342 "NoOverlapEnergy", helper,
2349 const std::vector<IntervalVariable>& intervals,
Model*
model) {
2354 model->TakeOwnership(helper);
2361 [trail, helper,
model](
2374 for (
int index1 = 0; index1 < helper->
NumTasks(); ++index1) {
2375 if (!helper->
IsPresent(index1))
continue;
2376 for (
int index2 = index1 + 1; index2 < helper->
NumTasks(); ++index2) {
2377 if (!helper->
IsPresent(index2))
continue;
2385 const bool interval_1_can_precede_2 =
2387 const bool interval_2_can_precede_1 =
2390 if (interval_1_can_precede_2 && !interval_2_can_precede_1) {
2394 cut.
AddTerm(helper->
Ends()[index1], IntegerValue(1));
2396 manager->
AddCut(cut.
Build(),
"NoOverlapPrecedence", lp_values);
2397 }
else if (interval_2_can_precede_1 && !interval_1_can_precede_2) {
2401 cut.
AddTerm(helper->
Ends()[index2], IntegerValue(1));
2403 manager->
AddCut(cut.
Build(),
"NoOverlapPrecedence", lp_values);
2412 const std::vector<IntegerVariable>& base_variables,
Model*
model) {
2415 std::vector<IntegerVariable> variables;
2416 std::vector<Literal> literals;
2417 absl::flat_hash_map<LiteralIndex, IntegerVariable> positive_map;
2418 absl::flat_hash_map<LiteralIndex, IntegerVariable> negative_map;
2421 for (
const IntegerVariable
var : base_variables) {
2422 if (integer_trail->LowerBound(
var) != IntegerValue(0))
continue;
2423 if (integer_trail->UpperBound(
var) != IntegerValue(1))
continue;
2424 const LiteralIndex literal_index = encoder->GetAssociatedLiteral(
2427 variables.push_back(
var);
2428 literals.push_back(
Literal(literal_index));
2429 positive_map[literal_index] =
var;
2434 result.
vars = variables;
2437 [variables, literals, implication_graph, positive_map, negative_map,
2440 std::vector<double> packed_values;
2441 for (
int i = 0; i < literals.size(); ++i) {
2442 packed_values.push_back(lp_values[variables[i]]);
2444 const std::vector<std::vector<Literal>> at_most_ones =
2445 implication_graph->GenerateAtMostOnesWithLargeWeight(literals,
2448 for (
const std::vector<Literal>& at_most_one : at_most_ones) {
2454 for (
const Literal l : at_most_one) {
2456 builder.
AddTerm(positive_map.at(l.Index()), IntegerValue(1));
2459 builder.
AddTerm(negative_map.at(l.Index()), IntegerValue(-1));
2464 manager->
AddCut(builder.
Build(),
"clique", lp_values);
#define DCHECK_NE(val1, val2)
#define CHECK_LT(val1, val2)
#define CHECK_EQ(val1, val2)
#define CHECK_GE(val1, val2)
#define CHECK_GT(val1, val2)
#define DCHECK_GE(val1, val2)
#define CHECK_NE(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define VLOG(verboselevel)
We call domain any subset of Int64 = [kint64min, kint64max].
Domain UnionWith(const Domain &domain) const
Returns the union of D and domain.
bool best_solution(int item_id) const
void set_node_limit(const int64 node_limit)
void Init(const std::vector< double > &profits, const std::vector< double > &weights, const double capacity)
double Solve(TimeLimit *time_limit, bool *is_solution_optimal)
void set_solution_upper_bound_threshold(const double solution_upper_bound_threshold)
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
bool LimitReached()
Returns true when the external limit is true, or the deterministic time is over the deterministic lim...
bool TrySimpleKnapsack(const LinearConstraint base_ct, const std::vector< double > &lp_values, const std::vector< IntegerValue > &lower_bounds, const std::vector< IntegerValue > &upper_bounds)
void ProcessUpperBoundedConstraint(const absl::StrongVector< IntegerVariable, double > &lp_values, LinearConstraint *cut)
BestImpliedBoundInfo GetCachedImpliedBoundInfo(IntegerVariable var)
const IntegerVariable GetLiteralView(Literal lit) const
void ComputeCut(RoundingOptions options, const std::vector< double > &lp_values, const std::vector< IntegerValue > &lower_bounds, const std::vector< IntegerValue > &upper_bounds, ImpliedBoundsProcessor *ib_processor, LinearConstraint *cut)
IntegerValue LevelZeroUpperBound(IntegerVariable var) const
IntegerValue LevelZeroLowerBound(IntegerVariable var) const
const Domain & InitialVariableDomain(IntegerVariable var) const
ABSL_MUST_USE_RESULT bool AddLiteralTerm(Literal lit, IntegerValue coeff)
void AddConstant(IntegerValue value)
void AddTerm(IntegerVariable var, IntegerValue coeff)
bool AddCut(LinearConstraint ct, std::string type_name, const absl::StrongVector< IntegerVariable, double > &lp_solution, std::string extra_info="")
LiteralIndex NegatedIndex() const
Class that owns everything related to a particular optimization model.
IntegerValue EndMin(int t) const
bool IsPresent(int t) const
bool SizeIsFixed(int t) const
bool IsAbsent(int t) const
IntegerValue EndMax(int t) const
const std::vector< AffineExpression > & Starts() const
bool IsOptional(int t) const
IntegerValue StartMin(int t) const
Literal PresenceLiteral(int index) const
IntegerValue StartMax(int t) const
const std::vector< AffineExpression > & Sizes() const
IntegerValue SizeMin(int t) const
const std::vector< AffineExpression > & Ends() const
int CurrentDecisionLevel() const
SharedTimeLimit * time_limit
static const int64 kint64max
static const int64 kint64min
void STLSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
bool ContainsKey(const Collection &collection, const Key &key)
static double ToDouble(double f)
void ConvertToKnapsackForm(const LinearConstraint &constraint, std::vector< LinearConstraint > *knapsack_constraints, IntegerTrail *integer_trail)
IntegerValue FloorRatio(IntegerValue dividend, IntegerValue positive_divisor)
bool AddProductTo(IntegerValue a, IntegerValue b, IntegerValue *result)
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
LinearConstraint GetPreprocessedLinearConstraint(const LinearConstraint &constraint, const absl::StrongVector< IntegerVariable, double > &lp_values, const IntegerTrail &integer_trail)
IntType IntTypeAbs(IntType t)
CutGenerator CreateNoOverlapPrecedenceCutGenerator(const std::vector< IntervalVariable > &intervals, Model *model)
IntegerValue CeilRatio(IntegerValue dividend, IntegerValue positive_divisor)
const LiteralIndex kNoLiteralIndex(-1)
bool CanFormValidKnapsackCover(const LinearConstraint &preprocessed_constraint, const absl::StrongVector< IntegerVariable, double > &lp_values, const IntegerTrail &integer_trail)
CutGenerator CreateCumulativeCutGenerator(const std::vector< IntervalVariable > &intervals, const IntegerVariable capacity, const std::vector< IntegerVariable > &demands, Model *model)
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue)
std::function< void(const absl::StrongVector< IntegerVariable, double > &, LinearConstraintManager *)> GenerateCumulativeCut(const std::string &cut_name, SchedulingConstraintHelper *helper, const std::vector< IntegerVariable > &demands, AffineExpression capacity, Model *model)
CutGenerator CreateNoOverlapCutGenerator(const std::vector< IntervalVariable > &intervals, Model *model)
void RemoveZeroTerms(LinearConstraint *constraint)
IntegerValue GetFactorT(IntegerValue rhs_remainder, IntegerValue divisor, IntegerValue max_t)
double GetKnapsackUpperBound(std::vector< KnapsackItem > items, const double capacity)
CutGenerator CreateOverlappingCumulativeCutGenerator(const std::vector< IntervalVariable > &intervals, const IntegerVariable capacity, const std::vector< IntegerVariable > &demands, Model *model)
CutGenerator CreateSquareCutGenerator(IntegerVariable y, IntegerVariable x, Model *model)
bool CanBeFilteredUsingCutLowerBound(const LinearConstraint &preprocessed_constraint, const absl::StrongVector< IntegerVariable, double > &lp_values, const IntegerTrail &integer_trail)
const IntegerVariable kNoIntegerVariable(-1)
void MakeAllCoefficientsPositive(LinearConstraint *constraint)
std::function< IntegerVariable(Model *)> NewIntegerVariableFromLiteral(Literal lit)
IntegerVariable PositiveVariable(IntegerVariable i)
CutGenerator CreateLinMaxCutGenerator(const IntegerVariable target, const std::vector< LinearExpression > &exprs, const std::vector< IntegerVariable > &z_vars, Model *model)
CutGenerator CreateAllDifferentCutGenerator(const std::vector< IntegerVariable > &vars, Model *model)
bool CanBeFilteredUsingKnapsackUpperBound(const LinearConstraint &constraint, const absl::StrongVector< IntegerVariable, double > &lp_values, const IntegerTrail &integer_trail)
std::function< IntegerValue(IntegerValue)> GetSuperAdditiveRoundingFunction(IntegerValue rhs_remainder, IntegerValue divisor, IntegerValue t, IntegerValue max_scaling)
void MakeAllVariablesPositive(LinearConstraint *constraint)
std::vector< IntegerVariable > NegationOf(const std::vector< IntegerVariable > &vars)
IntegerValue GetCoefficientOfPositiveVar(const IntegerVariable var, const LinearExpression &expr)
CutGenerator CreateKnapsackCoverCutGenerator(const std::vector< LinearConstraint > &base_constraints, const std::vector< IntegerVariable > &vars, Model *model)
void AddIntegerVariableFromIntervals(SchedulingConstraintHelper *helper, Model *model, std::vector< IntegerVariable > *vars)
bool ConstraintIsTriviallyTrue(const LinearConstraint &constraint, const IntegerTrail &integer_trail)
std::function< void(Model *)> GreaterOrEqual(IntegerVariable v, int64 lb)
void CleanTermsAndFillConstraint(std::vector< std::pair< IntegerVariable, IntegerValue >> *terms, LinearConstraint *constraint)
bool LiftKnapsackCut(const LinearConstraint &constraint, const absl::StrongVector< IntegerVariable, double > &lp_values, const std::vector< IntegerValue > &cut_vars_original_coefficients, const IntegerTrail &integer_trail, TimeLimit *time_limit, LinearConstraint *cut)
CutGenerator CreatePositiveMultiplicationCutGenerator(IntegerVariable z, IntegerVariable x, IntegerVariable y, Model *model)
CutGenerator CreateCliqueCutGenerator(const std::vector< IntegerVariable > &base_variables, Model *model)
void DivideByGCD(LinearConstraint *constraint)
double ComputeActivity(const LinearConstraint &constraint, const absl::StrongVector< IntegerVariable, double > &values)
double ToDouble(IntegerValue value)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 CapSub(int64 x, int64 y)
int64 SumOfKMinValueInDomain(const Domain &domain, int k)
int64 FloorRatio(int64 value, int64 positive_coeff)
int64 CapAdd(int64 x, int64 y)
int64 CapProd(int64 x, int64 y)
int64 SumOfKMaxValueInDomain(const Domain &domain, int k)
std::vector< double > lower_bounds
std::vector< double > upper_bounds
std::vector< IntegerVariable > vars
std::function< void(const absl::StrongVector< IntegerVariable, double > &lp_values, LinearConstraintManager *manager)> generate_cuts
std::vector< std::pair< IntegerVariable, IntegerValue > > terms
std::vector< IntegerValue > coeffs
std::vector< IntegerVariable > vars
std::string DebugString() const
void AddTerm(IntegerVariable var, IntegerValue coeff)