#include <preprocessor.h>

Inheritance diagram for operations_research::glop::DoubletonEqualityRowPreprocessor:

Public Member Functions
	DoubletonEqualityRowPreprocessor (const GlopParameters *parameters)

	DoubletonEqualityRowPreprocessor (const DoubletonEqualityRowPreprocessor &)=delete

DoubletonEqualityRowPreprocessor &	operator= (const DoubletonEqualityRowPreprocessor &)=delete

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

DoubletonEqualityRowPreprocessor Reduce equality constraints involving two variables (i.e. aX + bY = c), by substitution (and thus removal) of one of the variables by the other in all the constraints that it is involved in.

Definition at line 852 of file preprocessor.h.

Constructor & Destructor Documentation

◆ DoubletonEqualityRowPreprocessor() [1/2]

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

inlineexplicit

Definition at line 854 of file preprocessor.h.

◆ DoubletonEqualityRowPreprocessor() [2/2]

operations_research::glop::DoubletonEqualityRowPreprocessor::DoubletonEqualityRowPreprocessor ( const DoubletonEqualityRowPreprocessor & )

delete

◆ ~DoubletonEqualityRowPreprocessor()

operations_research::glop::DoubletonEqualityRowPreprocessor::~DoubletonEqualityRowPreprocessor ( )

finaldefault

Member Function Documentation

◆ operator=()

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

delete

◆ RecoverSolution()

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

In non-fastbuild mode, we rely on the rest of the code producing an ProblemStatus::ABNORMAL status here.

When the modified variable is either basic or free, we keep it as is, and simply make the deleted one basic.

Several code paths set the deleted column as basic. The code that sets its value in that case is below, after the switch() block.

The bound was induced by a bound of one of the two original variables. Put that original variable at its bound, and make the other one basic.

If the modified column is VariableStatus::BASIC, then its value is already set correctly. If it's the deleted column that is basic, its value is set below the switch() block.

Restore the value of the deleted column if it is VariableStatus::BASIC.

Make the deleted constraint status FIXED.

Now we need to reconstruct the dual. This is a bit tricky and is basically the same as inverting a really structed and easy to invert matrix. For n doubleton rows, looking only at the new_basic_columns, there is exactly n by construction (one per row). We consider only this n x n matrix, and we must choose dual row values so that we make the reduced costs zero on all these columns.

There is always an order that make this matrix triangular. We start with a singleton column which fix its corresponding row and then work on the square submatrix left. We can always start and continue, because if we take the first substituted row of the current submatrix, if its deleted column was in the submatrix we have a singleton column. If it is outside, we have 2 n - 1 entries for a matrix with n columns, so one must be singleton.

Note(user): Another advantage of working on the "original" matrix before this presolve is an increased precision.

Todo: (user): We can probably use something better than a vector of set, but the number of entry is really sparse though. And the size of a set<int> is 24 bytes, same as a std::vector<int>.

Adjust the dual value of the deleted constraint so that col have a reduced costs of zero.

Update singleton

Fix potential bad ConstraintStatus::FIXED_VALUE statuses.

Implements operations_research::glop::Preprocessor.

Definition at line 3271 of file preprocessor.cc.

◆ Run()

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

finalvirtual

DoubletonEqualityRowPreprocessor

This is needed at postsolve.

Todo: (user): Get rid of the FIXED status instead to avoid spending time/memory for no good reason here.

This is needed for postsolving dual.

Note: we don't update the transpose during this preprocessor run.

Heuristic: We try to subtitute sparse columns first to avoid a complexity explosion. Note that if we do long chain of substitution, we can still end up with a complexity of O(num_rows x num_cols) instead of O(num_entries).

Todo: (user): There is probably some more robust ways.

Iterate over the rows that were already doubletons before this preprocessor run, and whose items don't belong to a column that we deleted during this run. This implies that the rows are only ever touched once per run, because we only modify rows that have an item on a deleted column.

Collect the two row items. Skip the ones involving a deleted column.

Note: we filled r.col[] and r.coeff[] by item order, and currently we always pick the first column as the to-be-deleted one.

Todo: (user): make a smarter choice of which column to delete, and swap col[] and coeff[] accordingly.

Discard some cases that will be treated by other preprocessors, or by another run of this one. 1) One or two of the items were in a deleted column.

Fill the RestoreInfo, even if we end up not using it (because we give up on preprocessing this row): it has a bunch of handy shortcuts.

2) One of the columns is fixed: don't bother, it will be treated by the FixedVariablePreprocessor.

Look at the bounds of both variables and exit early if we can delegate to another pre-processor; otherwise adjust the bounds of the remaining variable as necessary. If the current row is: aX + bY = c, then the bounds of Y must be adjusted to satisfy Y = c/b + (-a/b)X

Note: when we compute the coefficients of these equations, we can cause underflows/overflows that could be avoided if we did the computations more carefully; but for now we just treat those cases as ProblemStatus::ABNORMAL.

Todo: (user): consider skipping the problematic rows in this preprocessor, or trying harder to avoid the under/overflow.

Default (and simplest) case: the lower bound didn't change.

Default (and simplest) case: the upper bound didn't change.

3) If the new bounds are fixed (the domain is a singleton) or infeasible, then we let the ForcingAndImpliedFreeConstraintPreprocessor do the work.

Now, perform the substitution. If the current row is: aX + bY = c then any other row containing 'X' with coefficient x can remove the entry in X, and instead add an entry on 'Y' with coefficient x(-b/a) and a constant offset x(c/a). Looking at the matrix, this translates into colY += (-b/a) colX.

Again we don't bother too much with over/underflows.

Note: we do not save again a saved column, so that we only save columns from the initial LP. This is important to limit the memory usage. It complexify a bit the postsolve though.

Apply similar operations on the objective coefficients.

Note: the offset is being updated by SubtractColumnMultipleFromConstraintBound() below.

Carry over the constant factor of the substitution as well.

Todo: (user): rename that method to reflect the fact that it also updates the objective offset, in the other direction.

If we keep substituing the same "dense" columns over and over, we can have a memory in O(num_rows * num_cols) which can be order of magnitude larger than the original problem. It is important to reclaim the memory of the deleted column right away.

Mark the column and the row for deletion.