#include <lp_data_utils.h>

Public Member Functions
void	Clear ()
	Clear all scaling coefficients.

void	Scale (LinearProgram *lp)
	Scale the given LP.

void	Scale (const GlopParameters &params, LinearProgram *lp)

void	ConfigureFromFactors (absl::Span< const double > row_factors, absl::Span< const double > col_factors)

Fractional	ScaleVariableValue (ColIndex col, Fractional value) const
	Transforms value from unscaled domain to the scaled one.

Fractional	ScaleReducedCost (ColIndex col, Fractional value) const

Fractional	ScaleDualValue (RowIndex row, Fractional value) const

Fractional	ScaleConstraintActivity (RowIndex row, Fractional value) const

Fractional	UnscaleVariableValue (ColIndex col, Fractional value) const
	Transforms corresponding value from the scaled domain to the original one.

Fractional	UnscaleReducedCost (ColIndex col, Fractional value) const

Fractional	UnscaleDualValue (RowIndex row, Fractional value) const

Fractional	UnscaleLeftSolveValue (RowIndex row, Fractional value) const

Fractional	UnscaleConstraintActivity (RowIndex row, Fractional value) const

void	UnscaleUnitRowLeftSolve (ColIndex basis_col, ScatteredRow *left_inverse) const

void	UnscaleColumnRightSolve (const RowToColMapping &basis, ColIndex col, ScatteredColumn *right_inverse) const
	Unscale a col vector v such that B.c = matrix_column_col.

Fractional	VariableScalingFactor (ColIndex col) const

Fractional	VariableScalingFactorWithSlack (ColIndex col) const

void	AverageCostScaling (DenseRow *objective)
	Extra scaling function, to scale objective/bounds.

void	ContainOneBoundScaling (DenseRow upper_bounds, DenseRow lower_bounds)

Fractional	BoundsScalingFactor () const

Fractional	ObjectiveScalingFactor () const

Detailed Description

Class to facilitate the conversion between an original "unscaled" LP problem and its scaled version. It is easy to get the direction wrong, so it make sense to have a single place where all the scaling formulas are kept.

Definition at line 52 of file lp_data_utils.h.

Member Function Documentation

◆ AverageCostScaling()

void operations_research::glop::LpScalingHelper::AverageCostScaling ( DenseRow * objective )

Extra scaling function, to scale objective/bounds.

Definition at line 241 of file lp_data_utils.cc.

◆ BoundsScalingFactor()

Fractional operations_research::glop::LpScalingHelper::BoundsScalingFactor ( ) const

inline

Visible for testing. All variable/constraint bounds of the original LP where multiplied by this factor. Nothing else changed.

Definition at line 100 of file lp_data_utils.h.

◆ Clear()

void operations_research::glop::LpScalingHelper::Clear ( )

Clear all scaling coefficients.

Definition at line 124 of file lp_data_utils.cc.

◆ ConfigureFromFactors()

void operations_research::glop::LpScalingHelper::ConfigureFromFactors	(	absl::Span< const double >	row_factors,
		absl::Span< const double >	col_factors )

Definition at line 107 of file lp_data_utils.cc.

◆ ContainOneBoundScaling()

void operations_research::glop::LpScalingHelper::ContainOneBoundScaling	(	DenseRow *	upper_bounds,
		DenseRow *	lower_bounds )

Definition at line 261 of file lp_data_utils.cc.

◆ ObjectiveScalingFactor()

Fractional operations_research::glop::LpScalingHelper::ObjectiveScalingFactor ( ) const

inline

Visible for testing. All objective coefficients of the original LP where multiplied by this factor. Nothing else changed.

Definition at line 104 of file lp_data_utils.h.

◆ Scale() [1/2]

void operations_research::glop::LpScalingHelper::Scale	(	const GlopParameters &	params,
		LinearProgram *	lp )

It is possible the scaler didn't do anything. we still allocate the vector though since we don't test that below.

Definition at line 91 of file lp_data_utils.cc.

◆ Scale() [2/2]

void operations_research::glop::LpScalingHelper::Scale ( LinearProgram * lp )

Scale the given LP.

Definition at line 89 of file lp_data_utils.cc.

◆ ScaleConstraintActivity()

Fractional operations_research::glop::LpScalingHelper::ScaleConstraintActivity	(	RowIndex	row,
		Fractional	value ) const

The activity move with the row_scale and the bound_scaling_factor.

Definition at line 163 of file lp_data_utils.cc.

◆ ScaleDualValue()

Fractional operations_research::glop::LpScalingHelper::ScaleDualValue	(	RowIndex	row,
		Fractional	value ) const

The dual value move like the objective and the inverse of the row scale.

Definition at line 157 of file lp_data_utils.cc.

◆ ScaleReducedCost()

Fractional operations_research::glop::LpScalingHelper::ScaleReducedCost	(	ColIndex	col,
		Fractional	value ) const

The reduced cost move like the objective and the col scale.

Definition at line 151 of file lp_data_utils.cc.

◆ ScaleVariableValue()

Fractional operations_research::glop::LpScalingHelper::ScaleVariableValue	(	ColIndex	col,
		Fractional	value ) const

Transforms value from unscaled domain to the scaled one.

Definition at line 146 of file lp_data_utils.cc.

◆ UnscaleColumnRightSolve()

void operations_research::glop::LpScalingHelper::UnscaleColumnRightSolve	(	const RowToColMapping &	basis,
		ColIndex	col,
		ScatteredColumn *	right_inverse ) const

Unscale a col vector v such that B.c = matrix_column_col.

[RowScale * B * BColScale] * inverse = RowScale * column * ColScale. That is B * (BColScale * inverse) = column * ColScale[col].

Definition at line 220 of file lp_data_utils.cc.

◆ UnscaleConstraintActivity()

Fractional operations_research::glop::LpScalingHelper::UnscaleConstraintActivity	(	RowIndex	row,
		Fractional	value ) const

The activity move with the row_scale and the bound_scaling_factor.

Definition at line 195 of file lp_data_utils.cc.

◆ UnscaleDualValue()

Fractional operations_research::glop::LpScalingHelper::UnscaleDualValue	(	RowIndex	row,
		Fractional	value ) const

The dual value move like the objective and the inverse of the row scale.

Definition at line 181 of file lp_data_utils.cc.

◆ UnscaleLeftSolveValue()

Fractional operations_research::glop::LpScalingHelper::UnscaleLeftSolveValue	(	RowIndex	row,
		Fractional	value ) const

In the scaled domain, we are takeing a sum coeff * scaling * row, so to get the same effect in the unscaled domain, we want to multiply by (coeff * scaling).

Definition at line 187 of file lp_data_utils.cc.

◆ UnscaleReducedCost()

Fractional operations_research::glop::LpScalingHelper::UnscaleReducedCost	(	ColIndex	col,
		Fractional	value ) const

The reduced cost move like the objective and the col scale.

Definition at line 175 of file lp_data_utils.cc.

◆ UnscaleUnitRowLeftSolve()

void operations_research::glop::LpScalingHelper::UnscaleUnitRowLeftSolve	(	ColIndex	basis_col,
		ScatteredRow *	left_inverse ) const

Unscale a row vector v such that v.B = unit_row. When basis_col is the index of the Column that correspond to the unit position in matrix B.

We have left_inverse * [RowScale * B * ColScale] = unit_row.

Definition at line 201 of file lp_data_utils.cc.

◆ UnscaleVariableValue()

Fractional operations_research::glop::LpScalingHelper::UnscaleVariableValue	(	ColIndex	col,
		Fractional	value ) const

Transforms corresponding value from the scaled domain to the original one.

Just the opposite of ScaleVariableValue().

Definition at line 169 of file lp_data_utils.cc.

◆ VariableScalingFactor()

Fractional operations_research::glop::LpScalingHelper::VariableScalingFactor ( ColIndex col ) const

A variable value in the original domain must be multiplied by this factor to be in the scaled domain.

During scaling a col was multiplied by ColScalingFactor() and the variable bounds divided by it.

Definition at line 130 of file lp_data_utils.cc.

◆ VariableScalingFactorWithSlack()

Fractional operations_research::glop::LpScalingHelper::VariableScalingFactorWithSlack ( ColIndex col ) const

Same as VariableScalingFactor() except that ColIndex greater than the number of columns will be interpreted as "slack" variable whose scaling factor depends on the row.

Definition at line 136 of file lp_data_utils.cc.

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

ortools/lp_data/lp_data_utils.h
ortools/lp_data/lp_data_utils.cc

Public Member Functions