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();
339 int64_t CalculateDegeneracy();
347 void IgnoreTrivialConstraintMultipliers(
348 std::vector<std::pair<glop::RowIndex, double>>* lp_multipliers);
349 void ScaleMultipliers(
350 absl::Span<
const std::pair<glop::RowIndex, double>> lp_multipliers,
351 bool take_objective_into_account, IntegerValue* scaling,
352 std::vector<std::pair<glop::RowIndex, IntegerValue>>* output)
const;
356 bool ScalingCanOverflow(
357 int power,
bool take_objective_into_account,
358 absl::Span<
const std::pair<glop::RowIndex, double>> multipliers,
359 int64_t overflow_cap)
const;
367 template <
bool check_overflow = true>
368 bool ComputeNewLinearConstraint(
369 absl::Span<
const std::pair<glop::RowIndex, IntegerValue>>
372 IntegerValue* upper_bound)
const;
377 void AdjustNewLinearConstraint(
378 std::vector<std::pair<glop::RowIndex, IntegerValue>>* integer_multipliers,
380 IntegerValue* upper_bound)
const;
383 using LinearExpression = std::vector<std::pair<glop::ColIndex, IntegerValue>>;
387 void ConvertToLinearConstraint(
400 void ReducedCostStrengtheningDeductions(
double cp_objective_delta);
407 glop::ColIndex GetMirrorVariable(IntegerVariable positive_variable);
411 void UpdateAverageReducedCosts();
422 void UpdateSimplexIterationLimit(int64_t min_iter, int64_t max_iter);
425 absl::Span<const glop::ColIndex> IntegerLpRowCols(glop::RowIndex row)
const;
426 absl::Span<const IntegerValue> IntegerLpRowCoeffs(glop::RowIndex row)
const;
428 void ComputeIntegerLpScalingFactors();
432 std::vector<double> row_factors_;
433 std::vector<double> col_factors_;
434 std::vector<double> col_max_;
435 std::vector<double> col_min_;
440 static constexpr double kCpEpsilon = 1e-4;
443 static constexpr double kLpEpsilon = 1e-6;
447 static constexpr double kZeroTolerance = 1e-12;
458 struct LinearConstraintInternal {
466 bool lb_is_trivial =
false;
467 bool ub_is_trivial =
false;
469 std::vector<glop::ColIndex> integer_lp_cols_;
470 std::vector<IntegerValue> integer_lp_coeffs_;
472 std::vector<glop::ColIndex> tmp_cols_;
473 std::vector<IntegerValue> tmp_coeffs_;
474 std::vector<IntegerVariable> tmp_vars_;
476 LinearExpression integer_objective_;
477 IntegerValue integer_objective_offset_ = IntegerValue(0);
478 IntegerValue objective_infinity_norm_ = IntegerValue(0);
484 glop::GlopParameters simplex_params_;
489 int64_t next_simplex_iter_ = 500;
495 ZeroHalfCutHelper zero_half_cut_helper_;
496 CoverCutHelper cover_cut_helper_;
497 IntegerRoundingCutHelper integer_rounding_cut_helper_;
499 bool problem_proven_infeasible_by_cuts_ =
false;
502 ScatteredIntegerVector tmp_scattered_vector_;
504 std::vector<double> tmp_lp_values_;
505 std::vector<IntegerValue> tmp_var_lbs_;
506 std::vector<IntegerValue> tmp_var_ubs_;
507 std::vector<glop::RowIndex> tmp_slack_rows_;
508 std::vector<std::pair<glop::ColIndex, IntegerValue>> tmp_terms_;
511 std::vector<std::pair<glop::RowIndex, double>> tmp_lp_multipliers_;
512 std::vector<std::pair<glop::RowIndex, double>> tmp_cg_multipliers_;
513 std::vector<std::pair<glop::RowIndex, IntegerValue>> tmp_integer_multipliers_;
519 std::vector<IntegerVariable> integer_variables_;
520 std::vector<IntegerVariable> extended_integer_variables_;
524 std::vector<int> orbit_indices_;
528 bool objective_is_defined_ =
false;
529 bool objective_cp_is_part_of_lp_ =
false;
530 IntegerVariable objective_cp_;
537 const SatParameters& parameters_;
540 IntegerTrail* integer_trail_;
542 GenericLiteralWatcher* watcher_;
543 IntegerEncoder* integer_encoder_;
544 ProductDetector* product_detector_;
545 ObjectiveDefinition* objective_definition_;
546 SharedStatistics* shared_stats_;
547 SharedResponseManager* shared_response_manager_;
548 ModelRandomGenerator* random_;
549 LinearConstraintSymmetrizer* symmetrizer_;
550 LinearPropagator* linear_propagator_;
554 BoolRLTCutHelper rlt_cut_helper_;
557 ImpliedBoundsProcessor implied_bounds_processor_;
561 LinearProgrammingDispatcher* dispatcher_;
563 std::vector<IntegerLiteral> integer_reason_;
564 std::vector<IntegerLiteral> deductions_;
565 std::vector<IntegerLiteral> deductions_reason_;
572 int rev_optimal_constraints_size_ = 0;
573 std::vector<std::unique_ptr<IntegerSumLE128>> optimal_constraints_;
574 std::vector<int64_t> cumulative_optimal_constraint_sizes_;
579 int lp_solution_level_ = 0;
580 bool lp_solution_is_set_ =
false;
581 bool lp_solution_is_integer_ =
false;
582 std::vector<double> lp_solution_;
583 std::vector<double> lp_reduced_cost_;
587 int previous_level_ = 0;
588 bool lp_at_optimal_ =
false;
589 double lp_objective_lower_bound_;
594 std::vector<double> level_zero_lp_solution_;
598 bool lp_at_level_zero_is_final_ =
false;
599 int num_force_lp_call_on_next_propagate_ = 0;
602 ModelLpVariableMapping& mirror_lp_variable_;
603 ModelLpValues& expanded_lp_solution_;
604 ModelReducedCosts& expanded_reduced_costs_;
607 bool lp_constraint_is_registered_ =
false;
609 std::vector<CutGenerator> cut_generators_;
612 bool compute_reduced_cost_averages_ =
false;
613 int num_calls_since_reduced_cost_averages_reset_ = 0;
614 std::vector<double> sum_cost_up_;
615 std::vector<double> sum_cost_down_;
616 std::vector<int> num_cost_up_;
617 std::vector<int> num_cost_down_;
618 std::vector<double> rc_scores_;
622 int rev_rc_start_ = 0;
624 std::vector<std::pair<double, int>> positions_by_decreasing_rc_score_;
627 IncrementalAverage average_degeneracy_;
628 bool is_degenerate_ =
false;
632 int64_t total_num_simplex_iterations_ = 0;
636 FirstFewValues<10> reachable_;
637 int64_t total_num_cut_propagations_ = 0;
638 int64_t total_num_eq_propagations_ = 0;
641 int64_t num_lp_changes_ = 0;
644 int64_t num_solves_ = 0;
645 mutable int64_t num_adjusts_ = 0;
646 mutable int64_t num_cut_overflows_ = 0;
647 mutable int64_t num_bad_cuts_ = 0;
648 mutable int64_t num_scaling_issues_ = 0;
649 std::vector<int64_t> num_solves_by_status_;
652 bool enabled_ =
true;