Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::glop::ShiftVariableBoundsPreprocessor Class Referencefinal

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:
operations_research::glop::Preprocessor

Public Member Functions

 ShiftVariableBoundsPreprocessor (const GlopParameters *parameters)
 ShiftVariableBoundsPreprocessor (const ShiftVariableBoundsPreprocessor &)=delete
ShiftVariableBoundsPreprocessoroperator= (const ShiftVariableBoundsPreprocessor &)=delete
 ~ShiftVariableBoundsPreprocessor () final=default
bool Run (LinearProgram *lp) final
void RecoverSolution (ProblemSolution *solution) const final
const DenseRowoffsets () const
Public Member Functions inherited from operations_research::glop::Preprocessor
 Preprocessor (const GlopParameters *parameters)
 Preprocessor (const Preprocessor &)=delete
Preprocessoroperator= (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 GlopParametersparameters_
bool in_mip_context_
std::unique_ptr< TimeLimitinfinite_time_limit_
TimeLimittime_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.

Implements operations_research::glop::Preprocessor.

Definition at line 3689 of file preprocessor.cc.


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