Detailed Description

ShiftVariableBoundsPreprocessor For each variable, inspects its bounds and "shift" them if necessary, so that its domain contains zero. A variable that was shifted will always have at least one of its bounds to zero. Doing it all at once allows to have a better precision when modifying the constraint bounds by using an accurate summation algorithm.

Example:

A variable with bound [1e10, infinity] will be shifted to [0, infinity].
A variable with domain [-1e10, 1e10] will not be shifted. Note that compared to the first case, doing so here may introduce unnecessary numerical errors if the variable value in the final solution is close to zero.

The expected impact of this is:

Better behavior of the scaling.
Better precision and numerical accuracy of the simplex method.
Slightly improved speed (because adding a column with a variable value of zero takes no work later).

Todo
(user): Having for each variable one of their bounds at zero is a requirement for the DualizerPreprocessor and for the implied free column in the ImpliedFreePreprocessor. However, shifting a variable with a domain like [-1e10, 1e10] may introduce numerical issues. Relax the definition of a free variable so that only having a domain containing 0.0 is enough?

Definition at line 1002 of file preprocessor.h.

#include <preprocessor.h>

Inheritance diagram for operations_research::glop::ShiftVariableBoundsPreprocessor:

Public Member Functions
	ShiftVariableBoundsPreprocessor (const GlopParameters *parameters)
	ShiftVariableBoundsPreprocessor (const ShiftVariableBoundsPreprocessor &)=delete
ShiftVariableBoundsPreprocessor &	operator= (const ShiftVariableBoundsPreprocessor &)=delete
	~ShiftVariableBoundsPreprocessor () final=default
bool	Run (LinearProgram *lp) final
void	RecoverSolution (ProblemSolution *solution) const final
const DenseRow &	offsets () const
Public Member Functions inherited from operations_research::glop::Preprocessor
	Preprocessor (const GlopParameters *parameters)
	Preprocessor (const Preprocessor &)=delete
Preprocessor &	operator= (const Preprocessor &)=delete
virtual	~Preprocessor ()
ProblemStatus	status () const
virtual void	UseInMipContext ()
void	SetTimeLimit (TimeLimit *time_limit)

Additional Inherited Members
Protected Member Functions inherited from operations_research::glop::Preprocessor
bool	IsSmallerWithinFeasibilityTolerance (Fractional a, Fractional b) const
bool	IsSmallerWithinPreprocessorZeroTolerance (Fractional a, Fractional b) const
Protected Attributes inherited from operations_research::glop::Preprocessor
ProblemStatus	status_
const GlopParameters &	parameters_
bool	in_mip_context_
std::unique_ptr< TimeLimit >	infinite_time_limit_
TimeLimit *	time_limit_

Constructor & Destructor Documentation

◆ ShiftVariableBoundsPreprocessor() [1/2]

operations_research::glop::ShiftVariableBoundsPreprocessor::ShiftVariableBoundsPreprocessor ( const GlopParameters * parameters )

inlineexplicit

Definition at line 1004 of file preprocessor.h.

◆ ShiftVariableBoundsPreprocessor() [2/2]

operations_research::glop::ShiftVariableBoundsPreprocessor::ShiftVariableBoundsPreprocessor ( const ShiftVariableBoundsPreprocessor & )

delete

◆ ~ShiftVariableBoundsPreprocessor()

operations_research::glop::ShiftVariableBoundsPreprocessor::~ShiftVariableBoundsPreprocessor ( )

finaldefault

Member Function Documentation

◆ offsets()

const DenseRow & operations_research::glop::ShiftVariableBoundsPreprocessor::offsets ( ) const

inline

Definition at line 1014 of file preprocessor.h.

◆ operator=()

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

delete

◆ RecoverSolution()

void operations_research::glop::ShiftVariableBoundsPreprocessor::RecoverSolution ( ProblemSolution * solution ) const

finalvirtual

Stores the optimal solution of the linear program that was passed to Run(). The given solution needs to be set to the optimal solution of the linear program "modified" by Run().

Implements operations_research::glop::Preprocessor.

Definition at line 3772 of file preprocessor.cc.

◆ Run()

bool operations_research::glop::ShiftVariableBoundsPreprocessor::Run ( LinearProgram * lp )

finalvirtual

ShiftVariableBoundsPreprocessor

Save the linear program bounds before shifting them.

Abort early if there is nothing to do.

Shift the variable bounds and compute the changes to the constraint bounds and objective offset in a precise way.

In the integer case, we truncate the number because if for instance the lower bound is a positive integer + epsilon, we only want to shift by the integer and leave the lower bound at epsilon.

Todo: (user): This would not be needed, if we always make the bound of an integer variable integer before applying this preprocessor.

Apply the changes to the constraint bound and objective offset.

This can happen for bad input where we get floating point overflow. We can even get nan if we have two overflow in opposite direction.