#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_

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 1003 of file preprocessor.h.

Constructor & Destructor Documentation

◆ ShiftVariableBoundsPreprocessor() [1/2]

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

inlineexplicit

Definition at line 1005 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 1015 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 3774 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.