141 const GlopParameters&
GetParameters()
const {
return parameters_; }
191 return dual_edge_norms_.GetEdgeSquaredNorms();
195 return variables_info_.GetNotBasicBitRow();
217 ColIndex
GetBasis(RowIndex row)
const;
220 return update_row_.ComputeAndGetUnitRowLeftInverse(row);
256 transpose_was_changed_ =
true;
257 return &transposed_matrix_;
260 return variables_info_.MutableLowerBounds();
263 return variables_info_.MutableUpperBounds();
273 total(
"total", this),
274 normal(
"normal", this),
275 bound_flip(
"bound_flip", this),
276 refactorize(
"refactorize", this),
277 degenerate(
"degenerate", this),
278 num_dual_flips(
"num_dual_flips", this),
279 degenerate_run_size(
"degenerate_run_size", this) {}
289 struct RatioTestStats :
public StatsGroup {
292 bound_shift(
"bound_shift", this),
293 abs_used_pivot(
"abs_used_pivot", this),
294 abs_tested_pivot(
"abs_tested_pivot", this),
295 abs_skipped_pivot(
"abs_skipped_pivot", this),
296 direction_density(
"direction_density", this),
297 leaving_choices(
"leaving_choices", this),
298 num_perfect_ties(
"num_perfect_ties", this) {}
299 DoubleDistribution bound_shift;
300 DoubleDistribution abs_used_pivot;
301 DoubleDistribution abs_tested_pivot;
302 DoubleDistribution abs_skipped_pivot;
303 RatioDistribution direction_density;
304 IntegerDistribution leaving_choices;
305 IntegerDistribution num_perfect_ties;
308 enum class Phase { FEASIBILITY, OPTIMIZATION, PUSH };
310 enum class RefactorizationReason {
320 ABSL_MUST_USE_RESULT Status SolveInternal(
double start_time,
bool maximize,
329 void PropagateParameters();
343 std::string GetPrettySolverStats()
const;
347 std::string SimpleVariableInfo(ColIndex col)
const;
350 void DisplayIterationInfo(
bool primal, RefactorizationReason reason =
351 RefactorizationReason::DEFAULT);
354 void DisplayErrors();
357 void DisplayInfoOnVariables()
const;
360 void DisplayVariableBounds();
376 void DisplayRevisedSimplexDebugInfo();
379 void DisplayProblem()
const;
388 Fractional ComputeInitialProblemObjectiveValue()
const;
392 void SetVariableNames();
398 void SetNonBasicVariableStatusAndDeriveValue(ColIndex col,
404 bool BasisIsConsistent()
const;
409 void UpdateBasis(ColIndex entering_col, RowIndex basis_row,
419 bool InitializeMatrixAndTestIfUnchanged(
const LinearProgram& lp,
420 bool lp_is_in_equation_form,
421 bool* only_change_is_new_rows,
422 bool* only_change_is_new_cols,
423 ColIndex* num_new_cols);
427 bool OldBoundsAreUnchangedAndNewVariablesHaveOneBoundAtZero(
428 const LinearProgram& lp,
bool lp_is_in_equation_form,
429 ColIndex num_new_cols);
432 bool InitializeObjectiveAndTestIfUnchanged(
const LinearProgram& lp);
435 void InitializeObjectiveLimit();
439 ABSL_MUST_USE_RESULT Status CreateInitialBasis();
443 ABSL_MUST_USE_RESULT Status
447 ABSL_MUST_USE_RESULT Status Initialize(
const LinearProgram& lp);
448 ABSL_MUST_USE_RESULT Status FinishInitialization(
bool solve_from_scratch);
454 void DisplayBasicVariableStatistics();
463 RowIndex ComputeNumberOfEmptyRows();
467 ColIndex ComputeNumberOfEmptyColumns();
472 int ComputeNumberOfSuperBasicVariables()
const;
484 void CorrectErrorsOnVariableValues();
487 void ComputeVariableValuesError();
492 void ComputeDirection(ColIndex col);
495 Fractional ComputeDirectionError(ColIndex col);
502 template <
bool is_entering_reduced_cost_positive>
504 const DenseRow& upper_bounds, RowIndex row)
const;
510 template <
bool is_entering_reduced_cost_positive>
511 Fractional ComputeHarrisRatioAndLeavingCandidates(
519 Status ChooseLeavingVariableRow(ColIndex entering_col,
521 RowIndex* leaving_row,
530 void PrimalPhaseIChooseLeavingVariableRow(ColIndex entering_col,
533 RowIndex* leaving_row,
545 ABSL_MUST_USE_RESULT Status DualChooseLeavingVariableRow(
546 RowIndex* leaving_row,
Fractional* cost_variation,
554 void DualPhaseIUpdatePrice(RowIndex leaving_row, ColIndex entering_col);
558 template <
bool use_dense_update = false>
564 template <
typename Cols>
565 void DualPhaseIUpdatePriceOnReducedCostChange(
const Cols& cols);
574 ABSL_MUST_USE_RESULT Status DualPhaseIChooseLeavingVariableRow(
575 RowIndex* leaving_row,
Fractional* cost_variation,
586 template <
typename BoxedVariableCols>
587 void MakeBoxedVariableDualFeasible(
const BoxedVariableCols& cols,
588 bool update_basic_values);
592 Fractional ComputeStepToMoveBasicVariableToBound(RowIndex leaving_row,
596 bool TestPivot(ColIndex entering_col, RowIndex leaving_row);
607 ABSL_MUST_USE_RESULT Status UpdateAndPivot(ColIndex entering_col,
608 RowIndex leaving_row,
612 void DisplayAllStats();
621 Status RefactorizeBasisIfNeeded(
bool* refactorize);
624 ABSL_MUST_USE_RESULT Status PrimalMinimize(TimeLimit*
time_limit);
627 ABSL_MUST_USE_RESULT Status DualMinimize(
bool feasibility_phase,
635 ABSL_MUST_USE_RESULT Status PrimalPush(TimeLimit*
time_limit);
645 ABSL_MUST_USE_RESULT Status Polish(TimeLimit*
time_limit);
650 ColIndex SlackColIndex(RowIndex row)
const;
657 void AdvanceDeterministicTime(TimeLimit*
time_limit);
663 RowIndex num_rows_ = RowIndex(0);
666 ColIndex num_cols_ = ColIndex(0);
671 ColIndex first_slack_col_ = ColIndex(0);
678 CompactSparseMatrix compact_matrix_;
681 CompactSparseMatrix transposed_matrix_;
706 DenseRow dual_infeasibility_improvement_direction_;
707 int num_dual_infeasible_positions_;
710 ScatteredColumn initially_all_zero_scratchpad_;
719 StrictITIVector<ColIndex, std::string> variable_name_;
722 RefactorizationReason last_refactorization_reason_;
730 DenseRow solution_dual_ray_row_combination_;
731 BasisState solution_state_;
732 bool solution_state_has_been_set_externally_;
738 bool transpose_was_changed_ =
false;
744 ScatteredColumn direction_;
754 absl::BitGen absl_random_;
757 absl::BitGenRef random_;
760 SolverLogger default_logger_;
761 SolverLogger* logger_ = &default_logger_;
764 BasisFactorization basis_factorization_;
767 VariablesInfo variables_info_;
768 PrimalEdgeNorms primal_edge_norms_;
769 DualEdgeNorms dual_edge_norms_;
770 DynamicMaximum<RowIndex> dual_prices_;
771 VariableValues variable_values_;
772 UpdateRow update_row_;
774 EnteringVariable entering_variable_;
775 PrimalPrices primal_prices_;
782 std::vector<ColIndex> bound_flip_candidates_;
785 uint64_t num_iterations_ = 0;
788 uint64_t num_feasibility_iterations_ = 0;
791 uint64_t num_optimization_iterations_ = 0;
794 uint64_t num_push_iterations_ = 0;
797 int64_t num_update_price_operations_ = 0;
800 double total_time_ = 0.0;
803 double feasibility_time_ = 0.0;
806 double optimization_time_ = 0.0;
809 double push_time_ = 0.0;
813 double last_deterministic_time_update_ = 0.0;
816 IterationStats iteration_stats_;
818 mutable RatioTestStats ratio_test_stats_;
822 mutable StatsGroup function_stats_;
830 GlopParameters parameters_;
831 GlopParameters initial_parameters_;
835 LuFactorization test_lu_;
838 int num_consecutive_degenerate_iterations_;
841 Phase phase_ = Phase::FEASIBILITY;
848 bool objective_limit_reached_;
857 std::vector<RowIndex> equivalent_leaving_choices_;