#include <preprocessor.h>

Inheritance diagram for operations_research::glop::DoubletonFreeColumnPreprocessor:

Public Member Functions
	DoubletonFreeColumnPreprocessor (const GlopParameters *parameters)

	DoubletonFreeColumnPreprocessor (const DoubletonFreeColumnPreprocessor &)=delete

DoubletonFreeColumnPreprocessor &	operator= (const DoubletonFreeColumnPreprocessor &)=delete

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

DoubletonFreeColumnPreprocessor This preprocessor removes one of the two rows in which a doubleton column of a free variable appears. Since we can add any multiple of such a column to any other column, the way this works is that we can always remove all the entries on one row.

Actually, we can remove all the entries except the one of the free column. But we will be left with a singleton row that we can delete in the same way as what is done in SingletonPreprocessor. That is by reporting the constraint bounds into the one of the originally free variable. After this operation, the doubleton free column will become a singleton and may or may not be removed later by the SingletonPreprocessor.

Note: this preprocessor can be seen as the dual of the DoubletonEqualityRowPreprocessor since when taking the dual, an equality row becomes a free variable and vice versa.

Note(user): As far as I know, this doubleton free column procedure is more general than what can be found in the research papers or in any of the linear solver open source codes as of July 2013. All of them only process such columns if one of the two rows is also an equality which is not actually required. Most probably, commercial solvers do use it though.

Definition at line 676 of file preprocessor.h.

Constructor & Destructor Documentation

◆ DoubletonFreeColumnPreprocessor() [1/2]

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

inlineexplicit

Definition at line 678 of file preprocessor.h.

◆ DoubletonFreeColumnPreprocessor() [2/2]

operations_research::glop::DoubletonFreeColumnPreprocessor::DoubletonFreeColumnPreprocessor ( const DoubletonFreeColumnPreprocessor & )

delete

◆ ~DoubletonFreeColumnPreprocessor()

operations_research::glop::DoubletonFreeColumnPreprocessor::~DoubletonFreeColumnPreprocessor ( )

finaldefault

Member Function Documentation

◆ operator=()

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

delete

◆ RecoverSolution()

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

Correct the constraint status.

The default is good here:

Correct the primal variable value.

In all cases, we will make the variable r.col VariableStatus::BASIC, so we need to adjust the dual value of the deleted row so that the variable reduced cost is zero. Note that there is nothing to do if the variable was already basic.

We want current_reduced_cost - dual * coeff = 0, so:

Implements operations_research::glop::Preprocessor.

Definition at line 1728 of file preprocessor.cc.

◆ Run()

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

finalvirtual

DoubletonFreeColumnPreprocessor

We will modify the matrix transpose and then push the change to the linear program by calling lp->UseTransposeMatrixAsReference(). Note that original_matrix will not change during this preprocessor run.

Only consider doubleton free columns.

Collect the two column items. Note that we skip a column involving a deleted row since it is no longer a doubleton then.

Since the column didn't touch any previously deleted row, we are sure that the coefficients were left untouched.

We prefer deleting the row with the larger coefficient magnitude because we will divide by this magnitude.

Todo: (user): Impact?

Save the deleted row for postsolve. Note that we remove it from the transpose at the same time. This last operation is not strictly needed, but it is faster to do it this way (both here and later when we will take the transpose of the final transpose matrix).

Move the bound of the deleted constraint to the initially free variable.

Add a multiple of the deleted row to the modified row except on column r.col where the coefficient will be left unchanged.

We also need to correct the objective value of the variables involved in the deleted row.

This detects if the objective should actually be zero, but because of the numerical error in the formula above, we have a really low objective instead. The logic is the same as in AddMultipleToSparseVectorAndIgnoreCommonIndex().

The order is important.