#include <preprocessor.h>

Inheritance diagram for operations_research::glop::ForcingAndImpliedFreeConstraintPreprocessor:

Public Member Functions
	ForcingAndImpliedFreeConstraintPreprocessor (const GlopParameters *parameters)

	ForcingAndImpliedFreeConstraintPreprocessor (const ForcingAndImpliedFreeConstraintPreprocessor &)=delete

ForcingAndImpliedFreeConstraintPreprocessor &	operator= (const ForcingAndImpliedFreeConstraintPreprocessor &)=delete

	~ForcingAndImpliedFreeConstraintPreprocessor () final=default

bool	Run (LinearProgram *lp) final

void	RecoverSolution (ProblemSolution *solution) const final

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

ForcingAndImpliedFreeConstraintPreprocessor This preprocessor computes for each constraint row the bounds that are implied by the variable bounds and applies one of the following reductions:

If the intersection of the implied bounds and the current constraint bounds is empty (modulo some tolerance), the problem is INFEASIBLE.
If the intersection of the implied bounds and the current constraint bounds is a singleton (modulo some tolerance), then the constraint is said to be forcing and all the variables that appear in it can be fixed to one of their bounds. All these columns and the constraint row is removed.
If the implied bounds are included inside the current constraint bounds (modulo some tolerance) then the constraint is said to be redundant or implied free. Its bounds are relaxed and the constraint will be removed later by the FreeConstraintPreprocessor.
Otherwise, wo do nothing.

Definition at line 580 of file preprocessor.h.

Constructor & Destructor Documentation

◆ ForcingAndImpliedFreeConstraintPreprocessor() [1/2]

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

inlineexplicit

Definition at line 582 of file preprocessor.h.

◆ ForcingAndImpliedFreeConstraintPreprocessor() [2/2]

operations_research::glop::ForcingAndImpliedFreeConstraintPreprocessor::ForcingAndImpliedFreeConstraintPreprocessor ( const ForcingAndImpliedFreeConstraintPreprocessor & )

delete

◆ ~ForcingAndImpliedFreeConstraintPreprocessor()

operations_research::glop::ForcingAndImpliedFreeConstraintPreprocessor::~ForcingAndImpliedFreeConstraintPreprocessor ( )

finaldefault

Member Function Documentation

◆ operator=()

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

delete

◆ RecoverSolution()

void operations_research::glop::ForcingAndImpliedFreeConstraintPreprocessor::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().

Compute for each deleted columns the last deleted row in which it appears.

Sort by row first and then col.

For each deleted row (in order), compute a bound on the dual values so that all the deleted columns for which this row is the last deleted row are dual-feasible. Note that for the other columns, it will always be possible to make them dual-feasible with a later row. There are two possible outcomes:

The dual value stays 0.0, and nothing changes.
The bounds enforce a non-zero dual value, and one column will have a reduced cost of 0.0. This column becomes VariableStatus::BASIC, and the constraint status is changed to ConstraintStatus::AT_LOWER_BOUND, ConstraintStatus::AT_UPPER_BOUND or ConstraintStatus::FIXED_VALUE.

Process column with this last deleted row.

Implements operations_research::glop::Preprocessor.

Definition at line 1306 of file preprocessor.cc.

◆ Run()

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

finalvirtual

ForcingAndImpliedFreeConstraintPreprocessor

Compute the implied constraint bounds from the variable bounds.

Note: the ScalingPreprocessor is currently executed last, so here the problem has not been scaled yet.

Check for infeasibility.

Check if the constraint is forcing. That is, all the variables that appear in it must be at one of their bounds.

We relax the constraint bounds only if the constraint is implied to be free. Such constraints will later be deleted by the FreeConstraintPreprocessor.

Note: we could relax only one of the two bounds, but the impact this would have on the revised simplex algorithm is unclear at this point.

The bounds are really close, so we fix to the bound with the lowest magnitude. As of 2019/11/19, this is "better" than fixing to the mid-point, because at postsolve, we always put non-basic variables to their exact bounds (so, with mid-point there would be a difference of epsilon/2 between the inner solution and the postsolved one, which might cause issues).

The bounds are really close, so we fix to the bound with the lowest magnitude.

Fix the variable, update the constraint bounds and save this column and its cost for the postsolve.

In theory, an M exists such that for any magnitude >= M, we will be at an optimal solution. However, because of numerical errors, if the value is too large, it causes problem when verifying the solution. So we select the smallest such M (at least a resonably small one) during postsolve. It is the reason why we need to store the columns that were fixed.