#include <preprocessor.h>

Inheritance diagram for operations_research::glop::ImpliedFreePreprocessor:

Public Member Functions
	ImpliedFreePreprocessor (const GlopParameters *parameters)

	ImpliedFreePreprocessor (const ImpliedFreePreprocessor &)=delete

ImpliedFreePreprocessor &	operator= (const ImpliedFreePreprocessor &)=delete

	~ImpliedFreePreprocessor () 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

ImpliedFreePreprocessor It is possible to compute "implied" bounds on a variable from the bounds of all the other variables and the constraints in which this variable take place. If such "implied" bounds are inside the variable bounds, then the variable bounds can be relaxed and the variable is said to be "implied free".

This preprocessor detects the implied free variables and make as many as possible free with a priority towards low-degree columns. This transformation will make the simplex algorithm more efficient later, but will also make it possible to reduce the problem by applying subsequent transformations:

The SingletonPreprocessor already deals with implied free singleton variables and removes the columns and the rows in which they appear.
Any multiple of the column of a free variable can be added to any other column without changing the linear program solution. This is the dual counterpart of the fact that any multiple of an equality row can be added to any row.

Todo
(user): Only process doubleton columns so we have more chance in the later passes to create more doubleton columns? Such columns lead to a smaller problem thanks to the DoubletonFreeColumnPreprocessor.

Definition at line 628 of file preprocessor.h.

Constructor & Destructor Documentation

◆ ImpliedFreePreprocessor() [1/2]

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

inlineexplicit

Definition at line 630 of file preprocessor.h.

◆ ImpliedFreePreprocessor() [2/2]

operations_research::glop::ImpliedFreePreprocessor::ImpliedFreePreprocessor ( const ImpliedFreePreprocessor & )

delete

◆ ~ImpliedFreePreprocessor()

operations_research::glop::ImpliedFreePreprocessor::~ImpliedFreePreprocessor ( )

finaldefault

Member Function Documentation

◆ operator=()

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

delete

◆ RecoverSolution()

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

Skip variables that the preprocessor didn't change.

Implements operations_research::glop::Preprocessor.

Definition at line 1596 of file preprocessor.cc.

◆ Run()

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

finalvirtual

ImpliedFreePreprocessor

For each constraint with n entries and each of its variable, we want the bounds implied by the (n - 1) other variables and the constraint. We use two handy utility classes that allow us to do that efficiently while dealing properly with infinite bounds.

Todo: (user) : Replace SumWithNegativeInfiniteAndOneMissing and SumWithPositiveInfiniteAndOneMissing with IntervalSumWithOneMissing.

Initialize the sums by adding all the bounds of the variables.

The inequality constraint_lb <= sum(entries) <= constraint_ub can be rewritten as: sum(entries) + (-activity) = 0, where (-activity) has bounds [-constraint_ub, -constraint_lb]. We use this latter convention to simplify our code.

Once a variable is freed, none of the rows in which it appears can be used to make another variable free.

It is better to process columns with a small degree first:

Degree-two columns make it possible to remove a row from the problem.
This way there is more chance to make more free columns.
It is better to have low degree free columns since a free column will always end up in the simplex basis (except if there is more than the number of rows in the problem).

Todo
(user): Only process degree-two so in subsequent passes more degree-two columns could be made free. And only when no other reduction can be applied, process the higher degree column?

Todo
(user): Be smarter about the order that maximizes the number of free column. For instance if we have 3 doubleton columns that use the rows (1,2) (2,3) and (3,4) then it is better not to make (2,3) free so the two other two can be made free.

Now loop over the columns in order and make all implied-free columns free.

If the variable is already free or fixed, we do nothing.

Detect if the variable is implied free.

If the row contains another implied free variable, then the bounds implied by it will just be [-kInfinity, kInfinity] so we can skip it.

This is the contribution of this column to the sum above.

If X is the variable with index col and Y the sum of all the other variables and of (-activity), then coeff * X + Y = 0. Since Y's bounds are [lb_sum without X, ub_sum without X], it is easy to derive the implied bounds on X.

Important: If entry_lb (resp. entry_ub) are large, we cannot have a good precision on the sum without. So we do add a defensive tolerance that depends on these magnitude.

Detect infeasible cases.

Detect fixed variable cases (there are two kinds).

Note: currently we don't do anything here except counting them.

This case is already dealt with by the ForcingAndImpliedFreeConstraintPreprocessor since it means that (at least) one of the row is forcing.

Todo: (user): As of July 2013, with our preprocessors this case is never triggered on the Netlib. Note however that if it appears it can have a big impact since by fixing the variable, the two involved constraints are forcing and can be removed too (with all the variables they touch). The postsolve step is quite involved though.

Is the variable implied free? Note that for an infinite lower_bound or upper_bound the respective inequality is always true.

This is a tricky part. We're freeing this variable, which means that after solve, the modified variable will have status either VariableStatus::FREE or VariableStatus::BASIC. In the former case (VariableStatus::FREE, value = 0.0), we need to "fix" the status (technically, our variable isn't free!) to either VariableStatus::AT_LOWER_BOUND or VariableStatus::AT_UPPER_BOUND (note that we skipped fixed variables), and "fix" the value to that bound's value as well. We make the decision and the precomputation here: we simply offset the variable by one of its bounds, and store which bound that was. Note that if the modified variable turns out to be VariableStatus::BASIC, we'll simply un-offset its value too; and let the status be VariableStatus::BASIC.

Todo: (user): This trick is already used in the DualizerPreprocessor, maybe we should just have a preprocessor that shifts all the variables bounds to have at least one of them at 0.0, will that improve precision and speed of the simplex? One advantage is that we can compute the new constraint bounds with better precision using AccurateSum.