#include <preprocessor.h>

Inheritance diagram for operations_research::glop::AddSlackVariablesPreprocessor:

Public Member Functions
	AddSlackVariablesPreprocessor (const GlopParameters *parameters)

	AddSlackVariablesPreprocessor (const AddSlackVariablesPreprocessor &)=delete

AddSlackVariablesPreprocessor &	operator= (const AddSlackVariablesPreprocessor &)=delete

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

AddSlackVariablesPreprocessor Transforms the linear program to the equation form min c.x, s.t. A.x = 0. This is done by:

Introducing slack variables for all constraints; all these variables are introduced with coefficient 1.0, and their bounds are set to be negative bounds of the corresponding constraint.
Changing the bounds of all constraints to (0, 0) to make them an equality.

As a consequence, the matrix of the linear program always has full row rank after this preprocessor. Note that the slack variables are always added last, so that the rightmost square sub-matrix is always the identity matrix.

Todo: (user): Do not require this step to talk to the revised simplex. On large LPs like supportcase11.mps, this step alone can add 1.5 GB to the solver peak memory for no good reason. The internal matrix representation used in glop is a lot more efficient, and there is no point keeping the slacks in LinearProgram. It is also bad for incrementaly modifying the LP.

Definition at line 1093 of file preprocessor.h.

Constructor & Destructor Documentation

◆ AddSlackVariablesPreprocessor() [1/2]

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

inlineexplicit

Definition at line 1095 of file preprocessor.h.

◆ AddSlackVariablesPreprocessor() [2/2]

operations_research::glop::AddSlackVariablesPreprocessor::AddSlackVariablesPreprocessor ( const AddSlackVariablesPreprocessor & )

delete

◆ ~AddSlackVariablesPreprocessor()

operations_research::glop::AddSlackVariablesPreprocessor::~AddSlackVariablesPreprocessor ( )

finaldefault

Member Function Documentation

◆ operator=()

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

delete

◆ RecoverSolution()

void operations_research::glop::AddSlackVariablesPreprocessor::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 constraint statuses from statuses of slack variables.

The slack variables have reversed bounds - if the value of the variable is at one bound, the value of the constraint is at the opposite bound.

Drop the primal values and variable statuses for slack variables.

Implements operations_research::glop::Preprocessor.

Definition at line 3908 of file preprocessor.cc.