145 absl::Span<const IntegerVariable> vars);
158 objective_cp_ = ivar;
159 objective_cp_is_part_of_lp_ =
false;
160 for (
const IntegerVariable var : integer_variables_) {
161 if (var == objective_cp_) {
162 objective_cp_is_part_of_lp_ =
true;
198 return static_cast<int>(extended_integer_variables_.size());
201 return extended_integer_variables_;
215 return average_degeneracy_.CurrentAverage();
220 return total_num_simplex_iterations_;
223 return total_num_cut_propagations_;
226 return total_num_eq_propagations_;
238 return num_solves_by_status_;
242 return constraint_manager_;
247 if (optimal_constraints_.empty())
return nullptr;
248 return optimal_constraints_.back().get();
253 return optimal_constraints_;
260 watcher_->CallOnNextPropagate(watcher_id_);
267 simplex_.LoadStateForNextSolve(state_);
276 std::vector<IntegerLiteral>* integer_reason);
283 bool CreateLpFromConstraintManager();
293 bool PreprocessCut(IntegerVariable first_slack,
CutData* cut);
300 bool AddCutFromConstraints(
301 absl::string_view name,
302 absl::Span<
const std::pair<glop::RowIndex, IntegerValue>>
303 integer_multipliers);
306 bool PostprocessAndAddCut(
const std::string& name,
const std::string& info,
307 IntegerVariable first_slack,
const CutData& cut);
311 void AddObjectiveCut();
314 void AddZeroHalfCuts();
317 void UpdateBoundsOfLpVariables();
322 bool PropagateExactLpReason();
327 bool PropagateExactDualRay();
334 int64_t CalculateDegeneracy();
342 void IgnoreTrivialConstraintMultipliers(
343 std::vector<std::pair<glop::RowIndex, double>>* lp_multipliers);
344 void ScaleMultipliers(
345 absl::Span<
const std::pair<glop::RowIndex, double>> lp_multipliers,
346 bool take_objective_into_account, IntegerValue* scaling,
347 std::vector<std::pair<glop::RowIndex, IntegerValue>>* output)
const;
351 bool ScalingCanOverflow(
352 int power,
bool take_objective_into_account,
353 absl::Span<
const std::pair<glop::RowIndex, double>> multipliers,
354 int64_t overflow_cap)
const;
362 template <
bool check_overflow = true>
363 bool ComputeNewLinearConstraint(
364 absl::Span<
const std::pair<glop::RowIndex, IntegerValue>>
367 IntegerValue* upper_bound)
const;
372 void AdjustNewLinearConstraint(
373 std::vector<std::pair<glop::RowIndex, IntegerValue>>* integer_multipliers,
375 IntegerValue* upper_bound)
const;
378 using LinearExpression = std::vector<std::pair<glop::ColIndex, IntegerValue>>;
382 void ConvertToLinearConstraint(
395 void ReducedCostStrengtheningDeductions(
double cp_objective_delta);
402 glop::ColIndex GetMirrorVariable(IntegerVariable positive_variable);
406 void UpdateAverageReducedCosts();
417 void UpdateSimplexIterationLimit(int64_t min_iter, int64_t max_iter);
420 absl::Span<const glop::ColIndex> IntegerLpRowCols(glop::RowIndex row)
const;
421 absl::Span<const IntegerValue> IntegerLpRowCoeffs(glop::RowIndex row)
const;
423 void ComputeIntegerLpScalingFactors();
427 std::vector<double> row_factors_;
428 std::vector<double> col_factors_;
429 std::vector<double> col_max_;
430 std::vector<double> col_min_;
435 static constexpr double kCpEpsilon = 1e-4;
438 static constexpr double kLpEpsilon = 1e-6;
442 static constexpr double kZeroTolerance = 1e-12;
453 struct LinearConstraintInternal {
461 bool lb_is_trivial =
false;
462 bool ub_is_trivial =
false;
464 std::vector<glop::ColIndex> integer_lp_cols_;
465 std::vector<IntegerValue> integer_lp_coeffs_;
467 std::vector<glop::ColIndex> tmp_cols_;
468 std::vector<IntegerValue> tmp_coeffs_;
469 std::vector<IntegerVariable> tmp_vars_;
471 LinearExpression integer_objective_;
472 IntegerValue integer_objective_offset_ = IntegerValue(0);
473 IntegerValue objective_infinity_norm_ = IntegerValue(0);
479 glop::GlopParameters simplex_params_;
484 int64_t next_simplex_iter_ = 500;
490 ZeroHalfCutHelper zero_half_cut_helper_;
491 CoverCutHelper cover_cut_helper_;
492 IntegerRoundingCutHelper integer_rounding_cut_helper_;
494 bool problem_proven_infeasible_by_cuts_ =
false;
497 ScatteredIntegerVector tmp_scattered_vector_;
499 std::vector<double> tmp_lp_values_;
500 std::vector<IntegerValue> tmp_var_lbs_;
501 std::vector<IntegerValue> tmp_var_ubs_;
502 std::vector<glop::RowIndex> tmp_slack_rows_;
503 std::vector<std::pair<glop::ColIndex, IntegerValue>> tmp_terms_;
506 std::vector<std::pair<glop::RowIndex, double>> tmp_lp_multipliers_;
507 std::vector<std::pair<glop::RowIndex, double>> tmp_cg_multipliers_;
508 std::vector<std::pair<glop::RowIndex, IntegerValue>> tmp_integer_multipliers_;
514 std::vector<IntegerVariable> integer_variables_;
515 std::vector<IntegerVariable> extended_integer_variables_;
519 std::vector<int> orbit_indices_;
523 bool objective_is_defined_ =
false;
524 bool objective_cp_is_part_of_lp_ =
false;
525 IntegerVariable objective_cp_;
532 const SatParameters& parameters_;
535 IntegerTrail* integer_trail_;
537 GenericLiteralWatcher* watcher_;
538 IntegerEncoder* integer_encoder_;
539 ProductDetector* product_detector_;
540 ObjectiveDefinition* objective_definition_;
541 SharedStatistics* shared_stats_;
542 SharedResponseManager* shared_response_manager_;
543 ModelRandomGenerator* random_;
544 LinearConstraintSymmetrizer* symmetrizer_;
545 LinearPropagator* linear_propagator_;
549 BoolRLTCutHelper rlt_cut_helper_;
552 ImpliedBoundsProcessor implied_bounds_processor_;
556 LinearProgrammingDispatcher* dispatcher_;
558 std::vector<IntegerLiteral> integer_reason_;
559 std::vector<IntegerLiteral> deductions_;
560 std::vector<IntegerLiteral> deductions_reason_;
567 int rev_optimal_constraints_size_ = 0;
568 std::vector<std::unique_ptr<IntegerSumLE128>> optimal_constraints_;
569 std::vector<int64_t> cumulative_optimal_constraint_sizes_;
574 int lp_solution_level_ = 0;
575 bool lp_solution_is_set_ =
false;
576 bool lp_solution_is_integer_ =
false;
577 std::vector<double> lp_solution_;
578 std::vector<double> lp_reduced_cost_;
582 int previous_level_ = 0;
583 bool lp_at_optimal_ =
false;
584 double lp_objective_lower_bound_;
589 std::vector<double> level_zero_lp_solution_;
593 bool lp_at_level_zero_is_final_ =
false;
596 ModelLpVariableMapping& mirror_lp_variable_;
597 ModelLpValues& expanded_lp_solution_;
598 ModelReducedCosts& expanded_reduced_costs_;
601 bool lp_constraint_is_registered_ =
false;
603 std::vector<CutGenerator> cut_generators_;
606 bool compute_reduced_cost_averages_ =
false;
607 int num_calls_since_reduced_cost_averages_reset_ = 0;
608 std::vector<double> sum_cost_up_;
609 std::vector<double> sum_cost_down_;
610 std::vector<int> num_cost_up_;
611 std::vector<int> num_cost_down_;
612 std::vector<double> rc_scores_;
616 int rev_rc_start_ = 0;
618 std::vector<std::pair<double, int>> positions_by_decreasing_rc_score_;
621 IncrementalAverage average_degeneracy_;
622 bool is_degenerate_ =
false;
626 int64_t total_num_simplex_iterations_ = 0;
630 FirstFewValues<10> reachable_;
631 int64_t total_num_cut_propagations_ = 0;
632 int64_t total_num_eq_propagations_ = 0;
635 int64_t num_lp_changes_ = 0;
638 int64_t num_solves_ = 0;
639 mutable int64_t num_adjusts_ = 0;
640 mutable int64_t num_cut_overflows_ = 0;
641 mutable int64_t num_bad_cuts_ = 0;
642 mutable int64_t num_scaling_issues_ = 0;
643 std::vector<int64_t> num_solves_by_status_;
646 bool enabled_ =
true;