#include <preprocessor.h>

Inheritance diagram for operations_research::glop::UnconstrainedVariablePreprocessor:

Public Member Functions
	UnconstrainedVariablePreprocessor (const GlopParameters *parameters)

	UnconstrainedVariablePreprocessor (const UnconstrainedVariablePreprocessor &)=delete

UnconstrainedVariablePreprocessor &	operator= (const UnconstrainedVariablePreprocessor &)=delete

	~UnconstrainedVariablePreprocessor () final=default

bool	Run (LinearProgram *lp) final

void	RecoverSolution (ProblemSolution *solution) const final

void	RemoveZeroCostUnconstrainedVariable (ColIndex col, Fractional target_bound, LinearProgram *lp)

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

UnconstrainedVariablePreprocessor If for a given variable, none of the constraints block it in one direction and this direction improves the objective, then this variable can be fixed to its bound in this direction. If this bound is infinite and the variable cost is non-zero, then the problem is unbounded.

More generally, by using the constraints and the variables that are unbounded on one side, one can derive bounds on the dual values. These can be translated into bounds on the reduced costs or the columns, which may force variables to their bounds. This is called forcing and dominated columns in the Andersen & Andersen paper.

Definition at line 729 of file preprocessor.h.

Constructor & Destructor Documentation

◆ UnconstrainedVariablePreprocessor() [1/2]

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

inlineexplicit

Definition at line 731 of file preprocessor.h.

◆ UnconstrainedVariablePreprocessor() [2/2]

operations_research::glop::UnconstrainedVariablePreprocessor::UnconstrainedVariablePreprocessor ( const UnconstrainedVariablePreprocessor & )

delete

◆ ~UnconstrainedVariablePreprocessor()

operations_research::glop::UnconstrainedVariablePreprocessor::~UnconstrainedVariablePreprocessor ( )

finaldefault

Member Function Documentation

◆ operator=()

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

delete

◆ RecoverSolution()

void operations_research::glop::UnconstrainedVariablePreprocessor::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 the last deleted column index for each deleted rows.

Sort by col first and then row.

Note: this will be empty if there were no deleted rows.

This is for VariableStatus::FREE rows.

Todo: (user): In presence of free row, we must move them to 0.

Note: currently VariableStatus::FREE rows should be removed before this is called.

activity and sign correction must have the same sign or be zero. If not, we find the first unbounded variable and change it accordingly.

Note: by construction, the variable value will move towards its unbounded direction.

Implements operations_research::glop::Preprocessor.

Definition at line 2093 of file preprocessor.cc.

◆ RemoveZeroCostUnconstrainedVariable()

void operations_research::glop::UnconstrainedVariablePreprocessor::RemoveZeroCostUnconstrainedVariable	(	ColIndex	col,
		Fractional	target_bound,
		LinearProgram *	lp )

Removes the given variable and all the rows in which it appears: If a variable is unconstrained with a zero cost, then all the constraints in which it appears can be made free! More precisely, during postsolve, if such a variable is unconstrained towards +kInfinity, for any activity value of the involved constraints, an M exists such that for each value of the variable >= M the problem will be feasible.

The algorithm during postsolve is to find a feasible value for all such variables while trying to keep their magnitudes small (for better numerical behavior). target_bound should take only two possible values: +/-kInfinity.

Todo: (user): Here, we may render the row free, so subsequent columns processed by the columns loop in Run() have more chance to be removed. However, we need to be more careful during the postsolve() if we do that.

Definition at line 1808 of file preprocessor.cc.

◆ Run()

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

finalvirtual

Runs the preprocessor by modifying the given linear program. Returns true if a postsolve step will be needed (i.e. RecoverSolution() is not the identity function). Also updates status_ to something different from ProblemStatus::INIT if the problem was solved (including bad statuses like ProblemStatus::ABNORMAL, ProblemStatus::INFEASIBLE, etc.).

To simplify the problem if something is almost zero, we use the low tolerance (1e-9 by default) to be defensive. But to detect an infeasibility we want to be sure (especially since the problem is not scaled in the presolver) so we use an higher tolerance.

Todo: (user): Expose it as a parameter. We could rename both to preprocessor_low_tolerance and preprocessor_high_tolerance.

We start by the dual variable bounds from the constraints.

We maintain a queue of columns to process.

Arbitrary limit to avoid corner cases with long loops.

Todo: (user): expose this as a parameter? IMO it isn't really needed as we shouldn't reach this limit except in corner cases.

Compute the bounds on the reduced costs of this column.

If the reduced cost domain do not contain zero (modulo the tolerance), we can move the variable to its corresponding bound. Note that we need to be careful that this variable didn't participate in creating the used reduced cost bound in the first place.

The second condition is here for the case we can choose one of the two directions.

Note: in MIP context, this assumes that the bounds of an integer variable are integer.

If the target bound is infinite and the reduced cost bound is non-zero, then the problem is ProblemStatus::INFEASIBLE_OR_UNBOUNDED.

We can remove this column and all its constraints! We just need to choose proper variable values during the call to RecoverSolution() that make all the constraints satisfiable. Unfortunately, this is not so easy to do in the general case, so we only deal with a simpler case when the cost of the variable is zero, and none of the constraints (even the deleted one) block the variable moving to its infinite target_bound.

Todo: (user): deal with the more generic case.

Note: it is important to check the rows that are already deleted here, otherwise the post-solve will not work.

Todo: (user): this also works if the variable is integer, but we must choose an integer value during the post-solve. Implement this.

The rest of the code will update the dual bounds. There is no need to do it if the column was removed or if it is not unconstrained in some direction.

For MIP, we only exploit the constraints.

Todo: (user): It should probably work with only small modification, investigate.

Change the rhs to reflect the fixed variables. Note that is important to do that after all the calls to RemoveZeroCostUnconstrainedVariable() because RemoveZeroCostUnconstrainedVariable() needs to store the rhs before this modification!