operations_research::glop::DualizerPreprocessor Class Reference

#include <preprocessor.h>

Inheritance diagram for operations_research::glop::DualizerPreprocessor:

Public Member Functions
	DualizerPreprocessor (const GlopParameters *parameters)
	DualizerPreprocessor (const DualizerPreprocessor &)=delete
DualizerPreprocessor &	operator= (const DualizerPreprocessor &)=delete
	~DualizerPreprocessor () final=default
bool	Run (LinearProgram *lp) final
void	RecoverSolution (ProblemSolution *solution) const final
void	UseInMipContext () final
ProblemStatus	ChangeStatusToDualStatus (ProblemStatus status) const
	Convert the given problem status to the one of its dual.
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
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

DualizerPreprocessor DualizerPreprocessor may change the given program to its dual depending on the value of the parameter solve_dual_problem.

IMPORTANT: FreeConstraintPreprocessor() must be called first since this preprocessor does not deal correctly with free constraints.

Definition at line 943 of file preprocessor.h.

Constructor & Destructor Documentation

DualizerPreprocessor() [1/2]

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

inlineexplicit

Definition at line 945 of file preprocessor.h.

DualizerPreprocessor() [2/2]

operations_research::glop::DualizerPreprocessor::DualizerPreprocessor ( const DualizerPreprocessor & )

delete

~DualizerPreprocessor()

operations_research::glop::DualizerPreprocessor::~DualizerPreprocessor ( )

finaldefault

Member Function Documentation

ChangeStatusToDualStatus()

ProblemStatus operations_research::glop::DualizerPreprocessor::ChangeStatusToDualStatus

(

ProblemStatus

status

)

const

Convert the given problem status to the one of its dual.

Definition at line 3665 of file preprocessor.cc.

operator=()

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

delete

RecoverSolution()

void operations_research::glop::DualizerPreprocessor::RecoverSolution ( ProblemSolution * solution ) const

finalvirtual

Note(user): This assumes that LinearProgram.PopulateFromDual() uses the first ColIndex and RowIndex for the rows and columns of the given problem.

The new variable value corresponds to the dual value of the dual. The shift applied during presolve needs to be removed.

A variable will be VariableStatus::BASIC if the dual constraint is not.

Otherwise, the dual value must be zero (if the solution is feasible), and the variable is at an exact bound or zero if it is VariableStatus::FREE. Note that this works because the bounds are shifted to 0.0 in the presolve!

A basic variable that corresponds to slack/surplus variable is the same as a basic row. The new variable status (that was just set to VariableStatus::BASIC above) needs to be corrected and depends on the variable type (slack/surplus).

The new variable value is set to its exact bound because the dual variable value can be imprecise.

Note the <= in the DCHECK, since we may need to add variables when taking the dual.

Note

the sign need to be corrected because of the special behavior of PopulateFromDual() on a maximization problem, see the comment in the declaration of PopulateFromDual().

A constraint will be ConstraintStatus::BASIC if the dual variable is not.

The duplicated row is always about the lower bound.

ConstraintStatus::AT_LOWER_BOUND/ConstraintStatusAT_UPPER_BOUND/ ConstraintStatus::FIXED depend on the type of the constraint at this position.

If the original row was duplicated, we need to take into account the value of the corresponding dual column.

Because non-basic variable values are exactly at one of their bounds, a new basic constraint will have a dual value exactly equal to zero.

Implements operations_research::glop::Preprocessor.

Definition at line 3556 of file preprocessor.cc.

Run()

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

finalvirtual

DualizerPreprocessor

Store the original problem size and direction.

If we need to decide whether or not to take the dual, we only take it when the matrix has more rows than columns. The number of rows of a linear program gives the size of the square matrices we need to invert and the order of iterations of the simplex method. So solving a program with less rows is likely a better alternative. Note that the number of row of the dual is the number of column of the primal.

Note however that the default is a conservative factor because if the user gives us a primal program, we assume he knows what he is doing and sometimes a problem is a lot faster to solve in a given formulation even if its dimension would say otherwise.

Another reason to be conservative, is that the number of columns of the dual is the number of rows of the primal plus up to two times the number of columns of the primal.

Todo

(user): This effect can be lowered if we use some of the extra variables as slack variable which we are not doing at this point.

Save the linear program bounds. Also make sure that all the bounded variable have at least one bound set to zero. This will be needed to post-solve a dual-basic solution into a primal-basic one.

We need to shift one of the bound to zero.

Fill the information that will be needed during postsolve.

Todo

(user): This will break if PopulateFromDual() is changed. so document the convention or make the function fill these vectors?

Todo

(user): There are two different ways to deal with ranged rows when taking the dual. The default way is to duplicate such rows, see PopulateFromDual() for details. Another way is to call lp->AddSlackVariablesForFreeAndBoxedRows() before calling PopulateFromDual(). Adds an option to switch between the two as this may change the running time?

Note however that the default algorithm is likely to result in a faster solving time because the dual program will have less rows.

Implements operations_research::glop::Preprocessor.

Definition at line 3440 of file preprocessor.cc.

UseInMipContext()

void operations_research::glop::DualizerPreprocessor::UseInMipContext ( )

inlinefinalvirtual

Some preprocessors only need minimal changes when used with integer variables in a MIP context. Setting this to true allows to consider integer variables as integer in these preprocessors.

Not all preprocessors handle integer variables correctly, calling this function on them will cause a LOG(FATAL).

Reimplemented from operations_research::glop::Preprocessor.

Definition at line 952 of file preprocessor.h.

---

The documentation for this class was generated from the following files:

• ortools/glop/preprocessor.h
• ortools/glop/preprocessor.cc