#include <preprocessor.h>

Inheritance diagram for operations_research::glop::ProportionalRowPreprocessor:

Public Member Functions
	ProportionalRowPreprocessor (const GlopParameters *parameters)

	ProportionalRowPreprocessor (const ProportionalRowPreprocessor &)=delete

ProportionalRowPreprocessor &	operator= (const ProportionalRowPreprocessor &)=delete

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

ProportionalRowPreprocessor Removes the proportional rows from the problem. The linear programming literature also calls such rows duplicates, see the same remark above for columns in ProportionalColumnPreprocessor.

Definition at line 350 of file preprocessor.h.

Constructor & Destructor Documentation

◆ ProportionalRowPreprocessor() [1/2]

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

inlineexplicit

Definition at line 352 of file preprocessor.h.

◆ ProportionalRowPreprocessor() [2/2]

operations_research::glop::ProportionalRowPreprocessor::ProportionalRowPreprocessor ( const ProportionalRowPreprocessor & )

delete

◆ ~ProportionalRowPreprocessor()

operations_research::glop::ProportionalRowPreprocessor::~ProportionalRowPreprocessor ( )

finaldefault

Member Function Documentation

◆ operator=()

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

delete

◆ RecoverSolution()

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

Make sure that all non-zero dual values on the proportional rows are assigned to the correct row with the correct sign and that the statuses are correct.

If the representative is ConstraintStatus::BASIC, then all rows in this class will be ConstraintStatus::BASIC and there is nothing to do.

If the row is FIXED it will behave as a row ConstraintStatus::AT_UPPER_BOUND or ConstraintStatus::AT_LOWER_BOUND depending on the corresponding dual variable sign.

If one of the two conditions below are true, set the row status to ConstraintStatus::BASIC.

Note: the source which is not row can't be FIXED (see presolve).

If the row status is still ConstraintStatus::FIXED_VALUE, we need to relax its status.

Implements operations_research::glop::Preprocessor.

Definition at line 1030 of file preprocessor.cc.

◆ Run()

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

finalvirtual

ProportionalRowPreprocessor

Use the first coefficient of each row to compute the proportionality factor. Note that the sign is important.

Note(user): using the first coefficient may not give the best precision.

The new row bounds (only meaningful for the proportional rows).

Where the new bounds are coming from. Only for the constraints that stay in the lp and are modified, kInvalidRow otherwise.

Initialization. We need the first representative of each proportional row class to point to itself for the loop below.

Todo: (user): Already return such a mapping from FindProportionalColumns()?

Compute the bound of each representative as implied by the rows which are proportional to it. Also keep the source row of each bound.

For now, delete all the rows that are proportional to another one.

Note: we will unmark the final representative of this class later.

Todo: (user): if the bounds are equal, use the largest row in magnitude?

For maximum precision, and also to simplify the postsolve, we choose a representative for each class of proportional columns that has at least one of the two tightest bounds.

In this case, a simple change of representative is enough. The constraint bounds of the representative will not change.

Report ProblemStatus::PRIMAL_INFEASIBLE if the new lower bound is not lower than the new upper bound modulo the default tolerance.

Special case for fixed rows.

This is the only case where a more complex postsolve is needed. To maximize precision, the class representative is changed to either upper_source or lower_source depending of which row has the largest proportionality factor.

Initialize the new bounds with the implied ones.

Take care of small numerical imprecision by making sure that lb <= ub.

Note: if the imprecision was greater than the tolerance, the code at the beginning of this block would have reported ProblemStatus::PRIMAL_INFEASIBLE.