#include <reduced_costs.h>

Public Member Functions
	ReducedCosts (const CompactSparseMatrix &matrix_, const DenseRow &objective, const RowToColMapping &basis, const VariablesInfo &variables_info, const BasisFactorization &basis_factorization, absl::BitGenRef random)
	Takes references to the linear program data we need.

	ReducedCosts (const ReducedCosts &)=delete
	This type is neither copyable nor movable.

ReducedCosts &	operator= (const ReducedCosts &)=delete

bool	NeedsBasisRefactorization () const

Fractional	TestEnteringReducedCostPrecision (ColIndex entering_col, const ScatteredColumn &direction)

Fractional	ComputeMaximumDualResidual ()

Fractional	ComputeMaximumDualInfeasibility ()

Fractional	ComputeSumOfDualInfeasibilities ()

Fractional	ComputeMaximumDualInfeasibilityOnNonBoxedVariables ()

void	UpdateBeforeBasisPivot (ColIndex entering_col, RowIndex leaving_row, const ScatteredColumn &direction, UpdateRow *update_row)

void	SetNonBasicVariableCostToZero (ColIndex col, Fractional *current_cost)

void	SetParameters (const GlopParameters &parameters)
	Sets the pricing parameters. This does not change the pricing rule.

bool	AreReducedCostsPrecise ()

bool	AreReducedCostsRecomputed ()

void	MakeReducedCostsPrecise ()

void	PerturbCosts ()

void	ShiftCostIfNeeded (bool increasing_rc_is_needed, ColIndex col)

bool	HasCostShift () const

bool	StepIsDualDegenerate (bool increasing_rc_is_needed, ColIndex col)

void	ClearAndRemoveCostShifts ()

void	ResetForNewObjective ()
	Invalidates all internal structure that depends on the objective function.

void	UpdateDataOnBasisPermutation ()
	Invalidates the data that depends on the order of the column in basis_.

DenseRow::ConstView	GetReducedCosts ()

DenseRow::ConstView	GetFullReducedCosts ()

const DenseColumn &	GetDualValues ()
	Returns the dual values associated to the current basis.

std::string	StatString () const
	Stats related functions.

Fractional	GetDualFeasibilityTolerance () const
	Returns the current dual feasibility tolerance.

bool	IsValidPrimalEnteringCandidate (ColIndex col) const
	Does basic checking of an entering candidate.

const DenseRow &	GetCostPerturbations () const
	Visible for testing.

double	DeterministicTime () const
	The deterministic time used by this class.

void	AddRecomputationWatcher (bool *watcher)

Detailed Description

Maintains the reduced costs of the non-basic variables and some related quantities.

Terminology:

To each non-basic column 'a' of A, we can associate an "edge" in the kernel of A equal to 1.0 on the index of 'a' and '-B^{-1}.a' on the basic variables.
'B^{-1}.a' is called the "right inverse" of 'a'.
The reduced cost of a column is equal to the scalar product of this column's edge with the cost vector (objective_), and corresponds to the variation in the objective function when we add this edge to the current solution.
The dual values are the "left inverse" of the basic objective by B. That is 'basic_objective_.B^{-1}'
The reduced cost of a column is also equal to the scalar product of this column with the vector of the dual values.

Definition at line 53 of file reduced_costs.h.

Constructor & Destructor Documentation

◆ ReducedCosts() [1/2]

operations_research::glop::ReducedCosts::ReducedCosts	(	const CompactSparseMatrix &	matrix_,
		const DenseRow &	objective,
		const RowToColMapping &	basis,
		const VariablesInfo &	variables_info,
		const BasisFactorization &	basis_factorization,
		absl::BitGenRef	random )

Takes references to the linear program data we need.

Definition at line 43 of file reduced_costs.cc.

◆ ReducedCosts() [2/2]

operations_research::glop::ReducedCosts::ReducedCosts ( const ReducedCosts & )

delete

This type is neither copyable nor movable.

Member Function Documentation

◆ AddRecomputationWatcher()

void operations_research::glop::ReducedCosts::AddRecomputationWatcher ( bool * watcher )

inline

Registers a boolean that will be set to true each time the reduced costs are or will be recomputed. This allows anyone that depends on this to know that it cannot just assume an incremental changes and needs to updates its data. Important: UpdateBeforeBasisPivot() will not trigger this.

Definition at line 202 of file reduced_costs.h.

◆ AreReducedCostsPrecise()

bool operations_research::glop::ReducedCosts::AreReducedCostsPrecise ( )

inline

Returns true if the current reduced costs are computed with maximum precision.

Definition at line 115 of file reduced_costs.h.

◆ AreReducedCostsRecomputed()

bool operations_research::glop::ReducedCosts::AreReducedCostsRecomputed ( )

inline

Returns true if the current reduced costs where just recomputed or will be on the next call to GetReducedCosts().

Definition at line 119 of file reduced_costs.h.

◆ ClearAndRemoveCostShifts()

void operations_research::glop::ReducedCosts::ClearAndRemoveCostShifts ( )

Removes any cost shift and cost perturbation. This also lazily forces a recomputation of all the derived quantities. This effectively resets the class to its initial state.

Definition at line 317 of file reduced_costs.cc.

◆ ComputeMaximumDualInfeasibility()

Fractional operations_research::glop::ReducedCosts::ComputeMaximumDualInfeasibility ( )

Trigger a recomputation if needed so that reduced_costs_ is valid.

Definition at line 125 of file reduced_costs.cc.

◆ ComputeMaximumDualInfeasibilityOnNonBoxedVariables()

Fractional operations_research::glop::ReducedCosts::ComputeMaximumDualInfeasibilityOnNonBoxedVariables ( )

Same as ComputeMaximumDualInfeasibility() but ignore boxed variables. Because we can always switch bounds of boxed variables, if this is under the dual tolerance, then we can easily have a dual feasible solution and do not need to run a dual phase I algorithm.

Trigger a recomputation if needed so that reduced_costs_ is valid.

Definition at line 145 of file reduced_costs.cc.

◆ ComputeMaximumDualResidual()

Fractional operations_research::glop::ReducedCosts::ComputeMaximumDualResidual ( )

Computes the current dual residual and infeasibility. Note that these functions are not really fast (many scalar products will be computed) and shouldn't be called at each iteration.

These function will compute the reduced costs if needed. ComputeMaximumDualResidual() also needs ComputeBasicObjectiveLeftInverse() and do not depends on reduced costs.

Definition at line 110 of file reduced_costs.cc.

◆ ComputeSumOfDualInfeasibilities()

Fractional operations_research::glop::ReducedCosts::ComputeSumOfDualInfeasibilities ( )

Trigger a recomputation if needed so that reduced_costs_ is valid.

Definition at line 167 of file reduced_costs.cc.

◆ DeterministicTime()

double operations_research::glop::ReducedCosts::DeterministicTime ( ) const

inline

The deterministic time used by this class.

Definition at line 196 of file reduced_costs.h.

◆ GetCostPerturbations()

const DenseRow & operations_research::glop::ReducedCosts::GetCostPerturbations ( ) const

inline

Visible for testing.

Definition at line 193 of file reduced_costs.h.

◆ GetDualFeasibilityTolerance()

Fractional operations_research::glop::ReducedCosts::GetDualFeasibilityTolerance ( ) const

inline

Returns the current dual feasibility tolerance.

Definition at line 185 of file reduced_costs.h.

◆ GetDualValues()

const DenseColumn & operations_research::glop::ReducedCosts::GetDualValues ( )

Returns the dual values associated to the current basis.

Definition at line 346 of file reduced_costs.cc.

◆ GetFullReducedCosts()

DenseRow::ConstView operations_research::glop::ReducedCosts::GetFullReducedCosts ( )

Same as GetReducedCosts() but trigger a recomputation if not already done to have access to the reduced costs on all positions, not just the relevant one.

Definition at line 327 of file reduced_costs.cc.

◆ GetReducedCosts()

DenseRow::ConstView operations_research::glop::ReducedCosts::GetReducedCosts ( )

Returns the current reduced costs. If AreReducedCostsPrecise() is true, then for basic columns, this gives the error between 'c_B' and 'y.B' and for non-basic columns, this is the classic reduced cost. If it is false, then this is defined only for the columns in variables_info_.GetIsRelevantBitRow().

Definition at line 335 of file reduced_costs.cc.

◆ HasCostShift()

bool operations_research::glop::ReducedCosts::HasCostShift ( ) const

inline

Returns true if ShiftCostIfNeeded() was applied since the last ClearAndRemoveCostShifts().

Definition at line 149 of file reduced_costs.h.

◆ IsValidPrimalEnteringCandidate()

bool operations_research::glop::ReducedCosts::IsValidPrimalEnteringCandidate ( ColIndex col ) const

Does basic checking of an entering candidate.

Definition at line 505 of file reduced_costs.cc.

◆ MakeReducedCostsPrecise()

void operations_research::glop::ReducedCosts::MakeReducedCostsPrecise ( )

Makes sure the next time the reduced cost are needed, they will be recomputed with maximum precision (i.e. from scratch with a basis refactorization first).

Definition at line 232 of file reduced_costs.cc.

◆ NeedsBasisRefactorization()

bool operations_research::glop::ReducedCosts::NeedsBasisRefactorization ( ) const

If this is true, then the caller must re-factorize the basis before the next call to GetReducedCosts().

Definition at line 68 of file reduced_costs.cc.

◆ operator=()

ReducedCosts & operations_research::glop::ReducedCosts::operator= ( const ReducedCosts & )

delete

◆ PerturbCosts()

void operations_research::glop::ReducedCosts::PerturbCosts ( )

Randomly perturb the costs. Both Koberstein and Huangfu recommend doing that before the dual simplex starts in their Phd thesis.

The perturbation follows what is explained in Huangfu Q (2013) "High performance simplex solver", Ph.D, dissertation, University of Edinburgh, section 3.2.3, page 58.

The perturbation direction is such that a dual-feasible solution stays feasible. This is important.

Here we don't necessarily maintain the dual-feasibility of a dual feasible solution, however we can always shift the variable to its other bound (because it is boxed) to restore dual-feasiblity. This is done by MakeBoxedVariableDualFeasible() at the end of the dual phase-I algorithm.

Definition at line 240 of file reduced_costs.cc.

◆ ResetForNewObjective()

void operations_research::glop::ReducedCosts::ResetForNewObjective ( )

Invalidates all internal structure that depends on the objective function.

Definition at line 218 of file reduced_costs.cc.

◆ SetNonBasicVariableCostToZero()

void operations_research::glop::ReducedCosts::SetNonBasicVariableCostToZero	(	ColIndex	col,
		Fractional *	current_cost )

Sets the cost of the given non-basic variable to zero and updates its reduced cost. Note that changing the cost of a non-basic variable only impacts its reduced cost and not the one of any other variables. The current_cost pointer must be equal to the address of objective[col] where objective is the DenseRow passed at construction.

Definition at line 206 of file reduced_costs.cc.

◆ SetParameters()

void operations_research::glop::ReducedCosts::SetParameters ( const GlopParameters & parameters )

Sets the pricing parameters. This does not change the pricing rule.

Definition at line 214 of file reduced_costs.cc.

◆ ShiftCostIfNeeded()

void operations_research::glop::ReducedCosts::ShiftCostIfNeeded	(	bool	increasing_rc_is_needed,
		ColIndex	col )

Shifts the cost of the given non-basic column such that its current reduced cost becomes 0.0. Actually, this shifts the cost a bit more according to the positive_direction parameter.

This is explained in Koberstein's thesis (section 6.2.2.3) and helps on degenerate problems. As of july 2013, this allowed to pass dano3mip and dbic1 without cycling forever. Note that contrary to what is explained in the thesis, we do not shift any other variable costs. If any becomes infeasible, it will be selected and shifted in subsequent iterations.

We always want a minimum step size, so if we have a negative step or a step that is really small, we will shift the cost of the given column.

Definition at line 291 of file reduced_costs.cc.

◆ StatString()

std::string operations_research::glop::ReducedCosts::StatString ( ) const

inline

Stats related functions.

Definition at line 182 of file reduced_costs.h.

◆ StepIsDualDegenerate()

bool operations_research::glop::ReducedCosts::StepIsDualDegenerate	(	bool	increasing_rc_is_needed,
		ColIndex	col )

Returns true if this step direction make the given column even more infeasible. This is just used for reporting stats.

Definition at line 310 of file reduced_costs.cc.

◆ TestEnteringReducedCostPrecision()

Fractional operations_research::glop::ReducedCosts::TestEnteringReducedCostPrecision	(	ColIndex	entering_col,
		const ScatteredColumn &	direction )

Checks the precision of the entering variable choice now that the direction is computed. Returns its precise version. This will also trigger a reduced cost recomputation if it was deemed too imprecise.

Update the reduced cost of the entering variable with the precise version.

At this point, we have an entering variable that will move the objective in the good direction. We check the precision of the reduced cost and edges norm, but even if they are imprecise, we finish this pivot and will recompute them during the next call to ChooseEnteringColumn().

Estimate the accuracy of the reduced costs using the entering variable.

Definition at line 72 of file reduced_costs.cc.

◆ UpdateBeforeBasisPivot()

void operations_research::glop::ReducedCosts::UpdateBeforeBasisPivot	(	ColIndex	entering_col,
		RowIndex	leaving_row,
		const ScatteredColumn &	direction,
		UpdateRow *	update_row )

Updates any internal data BEFORE the given simplex pivot is applied to B.

Note

no updates are needed in case of a bound flip. The arguments are in order:

The index of the entering non-basic column of A.
The index in B of the leaving basic variable.
The 'direction', i.e. the right inverse of the entering column.

If we are recomputing everything when requested, no need to update.

Note: it is important to update basic_objective_ AFTER calling UpdateReducedCosts().

Definition at line 186 of file reduced_costs.cc.

◆ UpdateDataOnBasisPermutation()

void operations_research::glop::ReducedCosts::UpdateDataOnBasisPermutation ( )

Invalidates the data that depends on the order of the column in basis_.

Definition at line 226 of file reduced_costs.cc.

The documentation for this class was generated from the following files:

ortools/glop/reduced_costs.h
ortools/glop/reduced_costs.cc

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ ReducedCosts() [1/2]

◆ ReducedCosts() [2/2]

Member Function Documentation

◆ AddRecomputationWatcher()

◆ AreReducedCostsPrecise()

◆ AreReducedCostsRecomputed()

◆ ClearAndRemoveCostShifts()

◆ ComputeMaximumDualInfeasibility()

◆ ComputeMaximumDualInfeasibilityOnNonBoxedVariables()

◆ ComputeMaximumDualResidual()

◆ ComputeSumOfDualInfeasibilities()

◆ DeterministicTime()

◆ GetCostPerturbations()

◆ GetDualFeasibilityTolerance()

◆ GetDualValues()

◆ GetFullReducedCosts()

◆ GetReducedCosts()

◆ HasCostShift()

◆ IsValidPrimalEnteringCandidate()

◆ MakeReducedCostsPrecise()

◆ NeedsBasisRefactorization()

◆ operator=()

◆ PerturbCosts()

◆ ResetForNewObjective()

◆ SetNonBasicVariableCostToZero()

◆ SetParameters()

◆ ShiftCostIfNeeded()

◆ StatString()

◆ StepIsDualDegenerate()

◆ TestEnteringReducedCostPrecision()

◆ UpdateBeforeBasisPivot()

◆ UpdateDataOnBasisPermutation()