91 #ifndef OR_TOOLS_GLOP_REVISED_SIMPLEX_H_
92 #define OR_TOOLS_GLOP_REVISED_SIMPLEX_H_
102 #include "ortools/glop/parameters.pb.h"
259 void PropagateParameters();
273 std::string GetPrettySolverStats()
const;
277 std::string SimpleVariableInfo(ColIndex
col)
const;
280 void DisplayIterationInfo()
const;
283 void DisplayErrors()
const;
286 void DisplayInfoOnVariables()
const;
289 void DisplayVariableBounds();
305 void DisplayRevisedSimplexDebugInfo();
308 void DisplayProblem()
const;
317 Fractional ComputeInitialProblemObjectiveValue()
const;
321 void SetVariableNames();
331 void SetNonBasicVariableStatusAndDeriveValue(ColIndex
col,
337 bool BasisIsConsistent()
const;
342 void UpdateBasis(ColIndex entering_col, RowIndex basis_row,
352 bool InitializeMatrixAndTestIfUnchanged(
const LinearProgram& lp,
353 bool* only_change_is_new_rows,
354 bool* only_change_is_new_cols,
355 ColIndex* num_new_cols);
358 bool InitializeBoundsAndTestIfUnchanged(
const LinearProgram& lp);
362 bool OldBoundsAreUnchangedAndNewVariablesHaveOneBoundAtZero(
366 bool InitializeObjectiveAndTestIfUnchanged(
const LinearProgram& lp);
372 void InitializeVariableStatusesForWarmStart(
const BasisState& state,
373 ColIndex num_new_cols);
377 ABSL_MUST_USE_RESULT
Status CreateInitialBasis();
381 ABSL_MUST_USE_RESULT
Status
391 void DisplayBasicVariableStatistics();
400 RowIndex ComputeNumberOfEmptyRows();
404 ColIndex ComputeNumberOfEmptyColumns();
416 void CorrectErrorsOnVariableValues();
419 void ComputeVariableValuesError();
424 void ComputeDirection(ColIndex
col);
434 template <
bool is_entering_reduced_cost_positive>
441 template <
bool is_entering_reduced_cost_positive>
442 Fractional ComputeHarrisRatioAndLeavingCandidates(
450 Status ChooseLeavingVariableRow(ColIndex entering_col,
452 RowIndex* leaving_row,
461 void PrimalPhaseIChooseLeavingVariableRow(ColIndex entering_col,
464 RowIndex* leaving_row,
476 ABSL_MUST_USE_RESULT
Status DualChooseLeavingVariableRow(
477 RowIndex* leaving_row,
Fractional* cost_variation,
485 void DualPhaseIUpdatePrice(RowIndex leaving_row, ColIndex entering_col);
489 template <
typename Cols>
490 void DualPhaseIUpdatePriceOnReducedCostChange(
const Cols& cols);
499 ABSL_MUST_USE_RESULT
Status DualPhaseIChooseLeavingVariableRow(
500 RowIndex* leaving_row,
Fractional* cost_variation,
511 template <
typename BoxedVariableCols>
512 void MakeBoxedVariableDualFeasible(
const BoxedVariableCols& cols,
513 bool update_basic_values);
517 Fractional ComputeStepToMoveBasicVariableToBound(RowIndex leaving_row,
521 bool TestPivot(ColIndex entering_col, RowIndex leaving_row);
532 ABSL_MUST_USE_RESULT
Status UpdateAndPivot(ColIndex entering_col,
533 RowIndex leaving_row,
537 void DisplayAllStats();
544 bool NeedsBasisRefactorization(
bool refactorize);
549 Status RefactorizeBasisIfNeeded(
bool* refactorize);
572 ColIndex SlackColIndex(RowIndex
row)
const;
593 ColIndex first_slack_col_;
632 DenseRow dual_infeasibility_improvement_direction_;
633 int num_dual_infeasible_positions_;
657 DenseRow solution_dual_ray_row_combination_;
659 bool solution_state_has_been_set_externally_;
663 bool notify_that_matrix_is_unchanged_ =
false;
691 std::vector<ColIndex> bound_flip_candidates_;
692 std::vector<std::pair<RowIndex, ColIndex>> pair_to_ignore_;
698 uint64 num_feasibility_iterations_;
701 uint64 num_optimization_iterations_;
707 double feasibility_time_;
710 double optimization_time_;
714 double last_deterministic_time_update_;
720 total(
"total", this),
721 normal(
"normal", this),
722 bound_flip(
"bound_flip", this),
723 degenerate(
"degenerate", this),
724 degenerate_run_size(
"degenerate_run_size", this) {}
731 IterationStats iteration_stats_;
733 struct RatioTestStats :
public StatsGroup {
735 : StatsGroup(
"RatioTestStats"),
736 bound_shift(
"bound_shift", this),
737 abs_used_pivot(
"abs_used_pivot", this),
738 abs_tested_pivot(
"abs_tested_pivot", this),
739 abs_skipped_pivot(
"abs_skipped_pivot", this),
740 direction_density(
"direction_density", this),
741 leaving_choices(
"leaving_choices", this),
742 num_perfect_ties(
"num_perfect_ties", this) {}
743 DoubleDistribution bound_shift;
744 DoubleDistribution abs_used_pivot;
745 DoubleDistribution abs_tested_pivot;
746 DoubleDistribution abs_skipped_pivot;
747 RatioDistribution direction_density;
748 IntegerDistribution leaving_choices;
749 IntegerDistribution num_perfect_ties;
751 mutable RatioTestStats ratio_test_stats_;
755 mutable StatsGroup function_stats_;
763 GlopParameters parameters_;
764 GlopParameters initial_parameters_;
768 LuFactorization test_lu_;
771 int num_consecutive_degenerate_iterations_;
774 bool feasibility_phase_;
781 bool objective_limit_reached_;
784 SparseColumn leaving_candidates_;
790 std::vector<RowIndex> equivalent_leaving_choices_;
ParentType::const_iterator const_iterator
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
RevisedSimplexDictionary(const DenseRow *col_scales, RevisedSimplex *revised_simplex)
ConstIterator end() const
ColIndex GetBasicColumnForRow(RowIndex r) const
RowMajorSparseMatrix::const_iterator ConstIterator
ConstIterator begin() const
SparseRow GetRow(RowIndex r) const
const GlopParameters & GetParameters() const
const DenseRow & GetDualRayRowCombination() const
Fractional GetVariableValue(ColIndex col) const
void SetIntegralityScale(ColIndex col, Fractional scale)
const DenseRow & GetReducedCosts() const
int64 GetNumberOfIterations() const
const DenseRow & GetPrimalRay() const
RowToColMapping GetBasisVector() const
bool objective_limit_reached() const
Fractional GetConstraintActivity(RowIndex row) const
VariableStatus GetVariableStatus(ColIndex col) const
Fractional GetReducedCost(ColIndex col) const
const DenseColumn & GetDualRay() const
ABSL_MUST_USE_RESULT Status Solve(const LinearProgram &lp, TimeLimit *time_limit)
ProblemStatus GetProblemStatus() const
Fractional GetObjectiveValue() const
RowMajorSparseMatrix ComputeDictionary(const DenseRow *column_scales)
Fractional GetDualValue(RowIndex row) const
void ClearIntegralityScales()
void NotifyThatMatrixIsUnchangedForNextSolve()
ConstraintStatus GetConstraintStatus(RowIndex row) const
void ComputeBasicVariablesForState(const LinearProgram &linear_program, const BasisState &state)
ColIndex GetProblemNumCols() const
void LoadStateForNextSolve(const BasisState &state)
RowIndex GetProblemNumRows() const
void ClearStateForNextSolve()
const BasisFactorization & GetBasisFactorization() const
const BasisState & GetState() const
ColIndex GetBasis(RowIndex row) const
void SetParameters(const GlopParameters ¶meters)
double DeterministicTime() const
const ScatteredRow & GetUnitRowLeftInverse(RowIndex row)
const ScatteredRow & ComputeAndGetUnitRowLeftInverse(RowIndex leaving_row)
SharedTimeLimit * time_limit
StrictITIVector< ColIndex, Fractional > DenseRow
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::mt19937 random_engine_t
VariableStatusRow statuses