#include <lp_data.h>

Public Types
enum class	VariableType { CONTINUOUS , INTEGER , IMPLIED_INTEGER }

Public Member Functions
	LinearProgram ()

	LinearProgram (const LinearProgram &)=delete
	This type is neither copyable nor movable.

LinearProgram &	operator= (const LinearProgram &)=delete

void	Clear ()
	Clears, i.e. reset the object to its initial value.

void	SetName (absl::string_view name)
	Name setter and getter.

const std::string &	name () const

ColIndex	CreateNewVariable ()

ColIndex	CreateNewSlackVariable (bool is_integer_slack_variable, Fractional lower_bound, Fractional upper_bound, const std::string &name)

RowIndex	CreateNewConstraint ()

ColIndex	FindOrCreateVariable (absl::string_view variable_id)

RowIndex	FindOrCreateConstraint (absl::string_view constraint_id)

void	SetVariableName (ColIndex col, absl::string_view name)

void	SetConstraintName (RowIndex row, absl::string_view name)

void	SetVariableType (ColIndex col, VariableType type)
	Set the type of the variable.

bool	IsVariableInteger (ColIndex col) const
	Returns whether the variable at column col is constrained to be integer.

bool	IsVariableBinary (ColIndex col) const
	Returns whether the variable at column col must take binary values or not.

void	SetVariableBounds (ColIndex col, Fractional lower_bound, Fractional upper_bound)

void	SetConstraintBounds (RowIndex row, Fractional lower_bound, Fractional upper_bound)

void	SetCoefficient (RowIndex row, ColIndex col, Fractional value)
	Defines the coefficient for col / row.

void	SetObjectiveCoefficient (ColIndex col, Fractional value)

void	SetObjectiveOffset (Fractional objective_offset)

void	SetObjectiveScalingFactor (Fractional objective_scaling_factor)

void	SetMaximizationProblem (bool maximize)

void	CleanUp ()

bool	IsCleanedUp () const

std::string	GetVariableName (ColIndex col) const

std::string	GetConstraintName (RowIndex row) const

VariableType	GetVariableType (ColIndex col) const
	Returns the type of variable.

bool	IsMaximizationProblem () const

const SparseMatrix &	GetSparseMatrix () const

const SparseMatrix &	GetTransposeSparseMatrix () const

SparseMatrix *	GetMutableTransposeSparseMatrix ()

void	UseTransposeMatrixAsReference ()

void	ClearTransposeMatrix ()
	Release the memory used by the transpose matrix.

const SparseColumn &	GetSparseColumn (ColIndex col) const

SparseColumn *	GetMutableSparseColumn (ColIndex col)
	Gets a pointer to the underlying SparseColumn with the given index.

ColIndex	num_variables () const
	Returns the number of variables.

RowIndex	num_constraints () const
	Returns the number of constraints.

EntryIndex	num_entries () const
	Returns the number of entries in the linear program matrix.

const DenseColumn &	constraint_lower_bounds () const

const DenseColumn &	constraint_upper_bounds () const

const DenseRow &	objective_coefficients () const
	Returns the objective coefficients (or cost) of variables as a row vector.

const DenseRow &	variable_lower_bounds () const

const DenseRow &	variable_upper_bounds () const

StrictITIVector< ColIndex, VariableType >	variable_types () const
	Returns a row vector of VariableType representing types of variables.

const std::vector< ColIndex > &	IntegerVariablesList () const

const std::vector< ColIndex > &	BinaryVariablesList () const

const std::vector< ColIndex > &	NonBinaryVariablesList () const

Fractional	GetObjectiveCoefficientForMinimizationVersion (ColIndex col) const

Fractional	objective_offset () const
	Returns the objective offset and scaling factor.

Fractional	objective_scaling_factor () const

bool	SolutionIsWithinVariableBounds (const DenseRow &solution, Fractional absolute_tolerance) const
	Checks if each variable respects its bounds, nothing else.

bool	SolutionIsLPFeasible (const DenseRow &solution, Fractional absolute_tolerance) const

bool	SolutionIsInteger (const DenseRow &solution, Fractional absolute_tolerance) const

bool	SolutionIsMIPFeasible (const DenseRow &solution, Fractional absolute_tolerance) const
	Tests if the solution is both LP-feasible and integer within the tolerance.

void	ComputeSlackVariableValues (DenseRow *solution) const

Fractional	ApplyObjectiveScalingAndOffset (Fractional value) const

Fractional	RemoveObjectiveScalingAndOffset (Fractional value) const

std::string	GetDimensionString () const
	A short string with the problem dimension.

std::string	GetObjectiveStatsString () const
	A short line with some stats on the problem coefficients.

std::string	GetBoundsStatsString () const

std::string	Dump () const

std::string	DumpSolution (const DenseRow &variable_values) const

std::string	GetProblemStats () const

std::string	GetPrettyProblemStats () const

std::string	GetNonZeroStats () const

std::string	GetPrettyNonZeroStats () const

void	AddSlackVariablesWhereNecessary (bool detect_integer_constraints)

ColIndex	GetFirstSlackVariable () const

ColIndex	GetSlackVariable (RowIndex row) const

void	PopulateFromDual (const LinearProgram &dual, RowToColMapping *duplicated_rows)

void	PopulateFromLinearProgram (const LinearProgram &linear_program)
	Populates the calling object with the given LinearProgram.

void	PopulateFromPermutedLinearProgram (const LinearProgram &lp, const RowPermutation &row_permutation, const ColumnPermutation &col_permutation)

void	PopulateFromLinearProgramVariables (const LinearProgram &linear_program)

void	AddConstraints (const SparseMatrix &coefficients, const DenseColumn &left_hand_sides, const DenseColumn &right_hand_sides, const StrictITIVector< RowIndex, std::string > &names)

void	AddConstraintsWithSlackVariables (const SparseMatrix &coefficients, const DenseColumn &left_hand_sides, const DenseColumn &right_hand_sides, const StrictITIVector< RowIndex, std::string > &names, bool detect_integer_constraints_for_slack)

void	Swap (LinearProgram *linear_program)

void	DeleteColumns (const DenseBooleanRow &columns_to_delete)

void	DeleteSlackVariables ()

void	Scale (SparseMatrixScaler *scaler)
	Scales the problem using the given scaler.

Fractional	ScaleObjective (GlopParameters::CostScalingAlgorithm method)

Fractional	ScaleBounds ()

void	DeleteRows (const DenseBooleanColumn &rows_to_delete)

bool	IsValid (Fractional max_valid_magnitude=kInfinity) const

bool	UpdateVariableBoundsToIntersection (const DenseRow &variable_lower_bounds, const DenseRow &variable_upper_bounds)

bool	IsInEquationForm () const

bool	BoundsOfIntegerVariablesAreInteger (Fractional tolerance) const

bool	BoundsOfIntegerConstraintsAreInteger (Fractional tolerance) const

void	NotifyThatColumnsAreClean ()

void	SetDcheckBounds (bool dcheck_bounds)
	If true, checks bound validity in debug mode.

DenseColumn *	mutable_constraint_lower_bounds ()

DenseColumn *	mutable_constraint_upper_bounds ()

void	RemoveNearZeroEntries (Fractional threshold)
	Removes objective and coefficient with magnitude <= threshold.

Friends
void	Scale (LinearProgram lp, SparseMatrixScaler scaler, GlopParameters::ScalingAlgorithm scaling_method)

Detailed Description

The LinearProgram class is used to store a linear problem in a form accepted by LPSolver.

In addition to the simple setter functions used to create such problems, the class also contains a few more advanced modification functions used primarily by preprocessors. A client shouldn't need to use them directly.

Definition at line 59 of file lp_data.h.

Member Enumeration Documentation

◆ VariableType

enum class operations_research::glop::LinearProgram::VariableType

strong

Enumerator
CONTINUOUS	The variable can take any value between and including its lower and upper bound.
INTEGER	The variable must only take integer values.
IMPLIED_INTEGER	The variable is implied integer variable i.e. it was continuous variable in the LP and was detected to take only integer values.

Definition at line 61 of file lp_data.h.

Constructor & Destructor Documentation

◆ LinearProgram() [1/2]

operations_research::glop::LinearProgram::LinearProgram ( )

LinearProgram

Definition at line 120 of file lp_data.cc.

◆ LinearProgram() [2/2]

operations_research::glop::LinearProgram::LinearProgram ( const LinearProgram & )

delete

This type is neither copyable nor movable.

Member Function Documentation

◆ AddConstraints()

void operations_research::glop::LinearProgram::AddConstraints	(	const SparseMatrix &	coefficients,
		const DenseColumn &	left_hand_sides,
		const DenseColumn &	right_hand_sides,
		const StrictITIVector< RowIndex, std::string > &	names )

Adds constraints to the linear program. The constraints are specified using a sparse matrix of the coefficients, and vectors that represent the left-hand side and the right-hand side of the constraints, i.e. left_hand_sides <= coefficients * variables <= right_hand_sides. The sizes of the columns and the names must be the same as the number of rows of the sparse matrix; the number of columns of the matrix must be equal to the number of variables of the linear program.

Copy constraint bounds and names from linear_program.

Definition at line 983 of file lp_data.cc.

◆ AddConstraintsWithSlackVariables()

void operations_research::glop::LinearProgram::AddConstraintsWithSlackVariables	(	const SparseMatrix &	coefficients,
		const DenseColumn &	left_hand_sides,
		const DenseColumn &	right_hand_sides,
		const StrictITIVector< RowIndex, std::string > &	names,
		bool	detect_integer_constraints_for_slack )

Calls the AddConstraints method. After adding the constraints it adds slack variables to the constraints.

Definition at line 1008 of file lp_data.cc.

◆ AddSlackVariablesWhereNecessary()

void operations_research::glop::LinearProgram::AddSlackVariablesWhereNecessary ( bool detect_integer_constraints )

Adds slack variables to the problem for all rows which don't have slack variables. The new slack variables have bounds set to opposite of the bounds of the corresponding constraint, and changes all constraints to equality constraints with both bounds set to 0.0. If a constraint uses only integer variables and all their coefficients are integer, it will mark the slack variable as integer too.

It is an error to call CreateNewVariable() or CreateNewConstraint() on a linear program on which this method was called.

Note: many of the slack variables may not be useful at all, but in order not to recompute the matrix from one Solve() to the next, we always include all of them for a given lp matrix.

Todo: (user): investigate the impact on the running time. It seems low because we almost never iterate on fixed variables.

Clean up the matrix. We're going to add entries, but we'll only be adding them to new columns, and only one entry per column, which does not invalidate the "cleanness" of the matrix.

Detect which constraints produce an integer slack variable. A constraint has an integer slack variable, if it contains only integer variables with integer coefficients. We do not check the bounds of the constraints, because in such case, they will be tightened to integer values by the preprocessors.

We don't use the transpose, because it might not be valid and it would be inefficient to update it and invalidate it again at the end of this preprocessor.

Extend the matrix of the problem with an identity matrix.

Slack variable is already present in this constraint.

Definition at line 708 of file lp_data.cc.

◆ ApplyObjectiveScalingAndOffset()

Fractional operations_research::glop::LinearProgram::ApplyObjectiveScalingAndOffset ( Fractional value ) const

Functions to translate the sum(solution * objective_coefficients()) to the real objective of the problem and back. Note that these can also be used to translate bounds of the objective in the same way.

Definition at line 559 of file lp_data.cc.

◆ BinaryVariablesList()

const std::vector< ColIndex > & operations_research::glop::LinearProgram::BinaryVariablesList ( ) const

Returns a list (technically a vector) of the ColIndices of the binary integer variables. This vector is lazily computed.

Definition at line 294 of file lp_data.cc.

◆ BoundsOfIntegerConstraintsAreInteger()

bool operations_research::glop::LinearProgram::BoundsOfIntegerConstraintsAreInteger ( Fractional tolerance ) const

Returns true if all integer constraints in the linear program have strictly integer bounds.

Using transpose for this is faster (complexity = O(number of non zeros in matrix)) than directly iterating through entries (complexity = O(number of constraints * number of variables)).

To match what the IntegerBoundsPreprocessor is doing, we require all coefficient to be EXACTLY integer here.

Definition at line 1523 of file lp_data.cc.

◆ BoundsOfIntegerVariablesAreInteger()

bool operations_research::glop::LinearProgram::BoundsOfIntegerVariablesAreInteger ( Fractional tolerance ) const

Returns true if all integer variables in the linear program have strictly integer bounds.

Definition at line 1507 of file lp_data.cc.

◆ CleanUp()

void operations_research::glop::LinearProgram::CleanUp ( )

Calls CleanUp() on each columns. That is, removes duplicates, zeros, and orders the coefficients by row.

Definition at line 356 of file lp_data.cc.

◆ Clear()

void operations_research::glop::LinearProgram::Clear ( )

Clears, i.e. reset the object to its initial value.

Definition at line 143 of file lp_data.cc.

◆ ClearTransposeMatrix()

void operations_research::glop::LinearProgram::ClearTransposeMatrix ( )

Release the memory used by the transpose matrix.

Definition at line 413 of file lp_data.cc.

◆ ComputeSlackVariableValues()

void operations_research::glop::LinearProgram::ComputeSlackVariableValues ( DenseRow * solution ) const

Fills the value of the slack from the other variable values. This requires that the slack have been added.

Definition at line 544 of file lp_data.cc.

◆ constraint_lower_bounds()

const DenseColumn & operations_research::glop::LinearProgram::constraint_lower_bounds ( ) const

inline

Return the lower bounds (resp. upper bounds) of constraints as a column vector. Note that the bound values may be +/- infinity.

Definition at line 223 of file lp_data.h.

◆ constraint_upper_bounds()

const DenseColumn & operations_research::glop::LinearProgram::constraint_upper_bounds ( ) const

inline

Definition at line 226 of file lp_data.h.

◆ CreateNewConstraint()

RowIndex operations_research::glop::LinearProgram::CreateNewConstraint ( )

Creates a new constraint and returns its index. By default, the constraint bounds will be [0, 0].

Definition at line 200 of file lp_data.cc.

◆ CreateNewSlackVariable()

ColIndex operations_research::glop::LinearProgram::CreateNewSlackVariable	(	bool	is_integer_slack_variable,
		Fractional	lower_bound,
		Fractional	upper_bound,
		const std::string &	name )

Creates a new slack variable and returns its index. Do not use this method to create non-slack variables.

Definition at line 185 of file lp_data.cc.

◆ CreateNewVariable()

ColIndex operations_research::glop::LinearProgram::CreateNewVariable ( )

Creates a new variable and returns its index. By default, the column bounds will be [0, infinity).

Definition at line 171 of file lp_data.cc.

◆ DeleteColumns()

void operations_research::glop::LinearProgram::DeleteColumns ( const DenseBooleanRow & columns_to_delete )

Removes the given column indices from the LinearProgram. This needs to allocate O(num_variables) memory to update variable_table_.

Remove the id of the deleted columns and adjust the index of the other.

This safely deletes the entry and moves the iterator one step ahead.

Eventually update transpose_matrix_.

Definition at line 1076 of file lp_data.cc.

◆ DeleteRows()

void operations_research::glop::LinearProgram::DeleteRows ( const DenseBooleanColumn & rows_to_delete )

Removes the given row indices from the LinearProgram. This needs to allocate O(num_variables) memory.

Deal with row-indexed data and construct the row mapping that will need to be applied to every column entry.

Remove the rows from the matrix.

Remove the id of the deleted rows and adjust the index of the other.

This safely deletes the entry and moves the iterator one step ahead.

Eventually update transpose_matrix_.

Definition at line 1269 of file lp_data.cc.

◆ DeleteSlackVariables()

void operations_research::glop::LinearProgram::DeleteSlackVariables ( )

Removes slack variables from the linear program. The method restores the bounds on constraints from the bounds of the slack variables, resets the index of the first slack variable, and removes the relevant columns from the matrix.

Restore the bounds on the constraints corresponding to the slack variables.

Slack variables appear only in the constraints for which they were created. We can find this constraint by looking at the (only) entry in the columnm of the slack variable.

Definition at line 1125 of file lp_data.cc.

◆ Dump()

std::string operations_research::glop::LinearProgram::Dump ( ) const

Returns a stringified LinearProgram. We use the LP file format used by lp_solve (see http://lpsolve.sourceforge.net/5.1/index.htm).

Objective line.

Constraints.

Variables.

Integer variables.

Todo: (user): if needed provide similar output for binary variables.

Definition at line 569 of file lp_data.cc.

◆ DumpSolution()

std::string operations_research::glop::LinearProgram::DumpSolution ( const DenseRow & variable_values ) const

Returns a string that contains the provided solution of the LP in the format var1 = X, var2 = Y, var3 = Z, ...

Definition at line 658 of file lp_data.cc.

◆ FindOrCreateConstraint()

RowIndex operations_research::glop::LinearProgram::FindOrCreateConstraint ( absl::string_view constraint_id )

Definition at line 227 of file lp_data.cc.

◆ FindOrCreateVariable()

ColIndex operations_research::glop::LinearProgram::FindOrCreateVariable ( absl::string_view variable_id )

Same as CreateNewVariable() or CreateNewConstraint() but also assign an immutable id to the variable or constraint so they can be retrieved later. By default, the name is also set to this id, but it can be changed later without changing the id.

Note: these ids are NOT copied over by the Populate*() functions.

Todo: (user): Move these and the two corresponding hash_table into a new LinearProgramBuilder class to simplify the code of some functions like DeleteColumns() here and make the behavior on copy clear? or simply remove them as it is almost as easy to maintain a hash_table on the client side.

Definition at line 214 of file lp_data.cc.

◆ GetBoundsStatsString()

std::string operations_research::glop::LinearProgram::GetBoundsStatsString ( ) const

Definition at line 474 of file lp_data.cc.

◆ GetConstraintName()

std::string operations_research::glop::LinearProgram::GetConstraintName ( RowIndex row ) const

Definition at line 375 of file lp_data.cc.

◆ GetDimensionString()

std::string operations_research::glop::LinearProgram::GetDimensionString ( ) const

A short string with the problem dimension.

static_cast<int64_t> is needed because the Android port uses int32_t.

Definition at line 434 of file lp_data.cc.

◆ GetFirstSlackVariable()

ColIndex operations_research::glop::LinearProgram::GetFirstSlackVariable ( ) const

Returns the index of the first slack variable in the linear program. Returns kInvalidCol if slack variables were not injected into the problem yet.

Definition at line 762 of file lp_data.cc.

◆ GetMutableSparseColumn()

SparseColumn * operations_research::glop::LinearProgram::GetMutableSparseColumn ( ColIndex col )

Gets a pointer to the underlying SparseColumn with the given index.

Definition at line 422 of file lp_data.cc.

◆ GetMutableTransposeSparseMatrix()

SparseMatrix * operations_research::glop::LinearProgram::GetMutableTransposeSparseMatrix ( )

Some transformations are better done on the transpose representation. These two functions are here for that. Note that calling the first function and modifying the matrix does not change the result of any function in this class until UseTransposeMatrixAsReference() is called. This is because the transpose matrix is only used by GetTransposeSparseMatrix() and this function will recompute the whole transpose from the matrix. In particular, do not call GetTransposeSparseMatrix() while you modify the matrix returned by GetMutableTransposeSparseMatrix() otherwise all your changes will be lost.

IMPORTANT: The matrix dimension cannot change. Otherwise this will cause problems. This is checked in debug mode when calling UseTransposeMatrixAsReference().

This enables a client to start modifying the matrix and then abort and not call UseTransposeMatrixAsReference(). Then, the other client of GetTransposeSparseMatrix() will still see the correct matrix.

Definition at line 395 of file lp_data.cc.

◆ GetNonZeroStats()

std::string operations_research::glop::LinearProgram::GetNonZeroStats ( ) const

Returns a comma-separated string of numbers containing (in that order) fill rate, max number of entries (length) in a row, average row length, standard deviation of row length, max column length, average column length, standard deviation of column length Useful for profiling algorithms.

Todo: (user): Theses are statistics about the underlying matrix and should be moved to SparseMatrix.

Definition at line 697 of file lp_data.cc.

◆ GetObjectiveCoefficientForMinimizationVersion()

Fractional operations_research::glop::LinearProgram::GetObjectiveCoefficientForMinimizationVersion ( ColIndex col ) const

Returns the objective coefficient (or cost) of the given variable for the minimization version of the problem. That is, this is the same as GetObjectiveCoefficient() for a minimization problem and the opposite for a maximization problem.

Definition at line 428 of file lp_data.cc.

◆ GetObjectiveStatsString()

std::string operations_research::glop::LinearProgram::GetObjectiveStatsString ( ) const

A short line with some stats on the problem coefficients.

Definition at line 461 of file lp_data.cc.

◆ GetPrettyNonZeroStats()

std::string operations_research::glop::LinearProgram::GetPrettyNonZeroStats ( ) const

Returns a string containing the same information as with GetNonZeroStats(), but in a much more human-readable form, for example: Fill rate : 9.61% Entries in row (Max / average / std, dev.) : 9 / 3.07 / 1.94 Entries in column (Max / average / std, dev.): 4 / 2.59 / 0.96

Definition at line 701 of file lp_data.cc.

◆ GetPrettyProblemStats()

std::string operations_research::glop::LinearProgram::GetPrettyProblemStats ( ) const

Returns a string containing the same information as with GetProblemStats(), but in a much more human-readable form, for example: Number of rows : 27 Number of variables in file : 32 Number of entries (non-zeros) : 83 Number of entries in the objective : 5 Number of entries in the right-hand side : 7 Number of <= constraints : 19 Number of >= constraints : 0 Number of = constraints : 8 Number of range constraints : 0 Number of non-negative variables : 32 Number of boxed variables : 0 Number of free variables : 0 Number of fixed variables : 0 Number of other variables : 0

Definition at line 675 of file lp_data.cc.

◆ GetProblemStats()

std::string operations_research::glop::LinearProgram::GetProblemStats ( ) const

Returns a comma-separated string of integers containing (in that order) num_constraints_, num_variables_in_file_, num_entries_, num_objective_non_zeros_, num_rhs_non_zeros_, num_less_than_constraints_, num_greater_than_constraints_, num_equal_constraints_, num_range_constraints_, num_non_negative_variables_, num_boxed_variables_, num_free_variables_, num_fixed_variables_, num_other_variables_ Very useful for reporting in the way used in journal articles.

Definition at line 669 of file lp_data.cc.

◆ GetSlackVariable()

ColIndex operations_research::glop::LinearProgram::GetSlackVariable ( RowIndex row ) const

Returns the index of the slack variable corresponding to the given constraint. Returns kInvalidCol if slack variables were not injected into the problem yet.

Definition at line 766 of file lp_data.cc.

◆ GetSparseColumn()

const SparseColumn & operations_research::glop::LinearProgram::GetSparseColumn ( ColIndex col ) const

Gets the underlying SparseColumn with the given index. This is the same as GetSparseMatrix().column(col);

Definition at line 418 of file lp_data.cc.

◆ GetSparseMatrix()

const SparseMatrix & operations_research::glop::LinearProgram::GetSparseMatrix ( ) const

inline

Returns the underlying SparseMatrix or its transpose (which may need to be computed).

Definition at line 183 of file lp_data.h.

◆ GetTransposeSparseMatrix()

const SparseMatrix & operations_research::glop::LinearProgram::GetTransposeSparseMatrix ( ) const

Definition at line 385 of file lp_data.cc.

◆ GetVariableName()

std::string operations_research::glop::LinearProgram::GetVariableName ( ColIndex col ) const

Functions that return the name of a variable or constraint. If the name is empty, they return a special name that depends on the index.

Definition at line 369 of file lp_data.cc.

◆ GetVariableType()

LinearProgram::VariableType operations_research::glop::LinearProgram::GetVariableType ( ColIndex col ) const

Returns the type of variable.

Definition at line 381 of file lp_data.cc.

◆ IntegerVariablesList()

const std::vector< ColIndex > & operations_research::glop::LinearProgram::IntegerVariablesList ( ) const

Returns a list (technically a vector) of the ColIndices of the integer variables. This vector is lazily computed.

Definition at line 289 of file lp_data.cc.

◆ IsCleanedUp()

bool operations_research::glop::LinearProgram::IsCleanedUp ( ) const

Returns true if all the columns are ordered by rows and contain no duplicates or zero entries (i.e. if IsCleanedUp() is true for all columns).

Definition at line 363 of file lp_data.cc.

◆ IsInEquationForm()

bool operations_research::glop::LinearProgram::IsInEquationForm ( ) const

Returns true if the linear program is in equation form Ax = 0 and all slack variables have been added. This is also called "computational form" in some of the literature.

Definition at line 1494 of file lp_data.cc.

◆ IsMaximizationProblem()

bool operations_research::glop::LinearProgram::IsMaximizationProblem ( ) const

inline

Returns true (resp. false) when the problem is a maximization (resp. minimization) problem.

Definition at line 179 of file lp_data.h.

◆ IsValid()

bool operations_research::glop::LinearProgram::IsValid ( Fractional max_valid_magnitude = kInfinity ) const

Does basic checking on the linear program:

returns false if some coefficient are NaNs.
returns false if some coefficient other than the bounds are +/- infinity.
Note
these conditions are also guarded by DCHECK on each of the SetXXX() function above.
This also returns false if any finite value has a magnitude larger than the given threshold.

Definition at line 1316 of file lp_data.cc.

◆ IsVariableBinary()

bool operations_research::glop::LinearProgram::IsVariableBinary ( ColIndex col ) const

Returns whether the variable at column col must take binary values or not.

Todo: (user): bounds of binary variables (and of integer ones) should be integer. Add a preprocessor for that.

Definition at line 309 of file lp_data.cc.

◆ IsVariableInteger()

bool operations_research::glop::LinearProgram::IsVariableInteger ( ColIndex col ) const

Returns whether the variable at column col is constrained to be integer.

Definition at line 304 of file lp_data.cc.

◆ mutable_constraint_lower_bounds()

DenseColumn * operations_research::glop::LinearProgram::mutable_constraint_lower_bounds ( )

inline

In our presolve, the calls and the extra test inside SetConstraintBounds() can be visible when a lot of substitutions are performed.

Definition at line 561 of file lp_data.h.

◆ mutable_constraint_upper_bounds()

DenseColumn * operations_research::glop::LinearProgram::mutable_constraint_upper_bounds ( )

inline

Definition at line 564 of file lp_data.h.

◆ name()

const std::string & operations_research::glop::LinearProgram::name ( ) const

inline

Definition at line 83 of file lp_data.h.

◆ NonBinaryVariablesList()

const std::vector< ColIndex > & operations_research::glop::LinearProgram::NonBinaryVariablesList ( ) const

Returns a list (technically a vector) of the ColIndices of the non-binary integer variables. This vector is lazily computed.

Definition at line 299 of file lp_data.cc.

◆ NotifyThatColumnsAreClean()

void operations_research::glop::LinearProgram::NotifyThatColumnsAreClean ( )

inline

Advanced usage. Bypass the costly call to CleanUp() when we known that the change we made kept the matrix columns "clean" (see the comment of CleanUp()). This is unsafe but can save a big chunk of the running time when one does a small amount of incremental changes to the problem (like adding a new row with no duplicates or zero entries).

Definition at line 551 of file lp_data.h.

◆ num_constraints()

RowIndex operations_research::glop::LinearProgram::num_constraints ( ) const

inline

Returns the number of constraints.

Definition at line 216 of file lp_data.h.

◆ num_entries()

EntryIndex operations_research::glop::LinearProgram::num_entries ( ) const

inline

Returns the number of entries in the linear program matrix.

Definition at line 219 of file lp_data.h.

◆ num_variables()

ColIndex operations_research::glop::LinearProgram::num_variables ( ) const

inline

Returns the number of variables.

Definition at line 213 of file lp_data.h.

◆ objective_coefficients()

const DenseRow & operations_research::glop::LinearProgram::objective_coefficients ( ) const

inline

Returns the objective coefficients (or cost) of variables as a row vector.

Definition at line 231 of file lp_data.h.

◆ objective_offset()

Fractional operations_research::glop::LinearProgram::objective_offset ( ) const

inline

Returns the objective offset and scaling factor.

Definition at line 268 of file lp_data.h.

◆ objective_scaling_factor()

Fractional operations_research::glop::LinearProgram::objective_scaling_factor ( ) const

inline

Definition at line 269 of file lp_data.h.

◆ operator=()

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

delete

◆ PopulateFromDual()

void operations_research::glop::LinearProgram::PopulateFromDual	(	const LinearProgram &	dual,
		RowToColMapping *	duplicated_rows )

Populates the calling object with the dual of the LinearProgram passed as parameter. For the general form that we solve, min c.x s.t. A_1 x = b_1 A_2 x <= b_2 A_3 x >= b_3 l <= x <= u With x: n-column of unknowns l,u: n-columns of bound coefficients c: n-row of cost coefficients A_i: m_i×n-matrix of coefficients b_i: m_i-column of right-hand side coefficients

The dual is

max b_1.y_1 + b_2.y_2 + b_3.y_3 + l.v + u.w s.t. y_1 A_1 + y_2 A_2 + y_3 A_3 + v + w = c y_1 free, y_2 <= 0, y_3 >= 0, v >= 0, w <= 0 With: y_i: m_i-row of unknowns v,w: n-rows of unknowns

If range constraints are present, each of the corresponding row is duplicated (with one becoming lower bounded and the other upper bounded). For such ranged row in the primal, duplicated_rows[row] is set to the column index in the dual of the corresponding column duplicate. For non-ranged row, duplicated_rows[row] is set to kInvalidCol.

IMPORTANT: The linear_program argument must not have any free constraints.

IMPORTANT: This function always interprets the argument in its minimization form. So the dual solution of the dual needs to be negated if we want to compute the solution of a maximization problem given as an argument.

Todo: (user): Do not interpret as a minimization problem?

We always take the dual in its minimization form thanks to the GetObjectiveCoefficientForMinimizationVersion() below, so this will always be a maximization problem.

Taking the dual does not change the offset nor the objective scaling factor.

Create the dual variables y, with bounds depending on the type of constraints in the primal.

Note: for a ranged constraint, the loop will be continued here. This is wanted because we want to deal with the lower_bound afterwards.

This code does not support free rows in linear_program.

Create the dual slack variables v.

Create the dual surplus variables w.

Store the transpose of the matrix.

Take care of ranged constraints.

upper_bound was done in a loop above, now do the lower_bound.

We know that the columns are ordered by rows.

Definition at line 775 of file lp_data.cc.

◆ PopulateFromLinearProgram()

void operations_research::glop::LinearProgram::PopulateFromLinearProgram ( const LinearProgram & linear_program )

Populates the calling object with the given LinearProgram.

Definition at line 873 of file lp_data.cc.

◆ PopulateFromLinearProgramVariables()

void operations_research::glop::LinearProgram::PopulateFromLinearProgramVariables ( const LinearProgram & linear_program )

Populates the calling object with the variables of the given LinearProgram. The function preserves the bounds, the integrality, the names of the variables and their objective coefficients. No constraints are copied (the matrix in the destination has 0 rows).

Definition at line 946 of file lp_data.cc.

◆ PopulateFromPermutedLinearProgram()

void operations_research::glop::LinearProgram::PopulateFromPermutedLinearProgram	(	const LinearProgram &	lp,
		const RowPermutation &	row_permutation,
		const ColumnPermutation &	col_permutation )

Populates the calling object with the given LinearProgram while permuting variables and constraints. This is useful mainly for testing to generate a model with the same optimal objective value.

Populate matrix coefficients.

Populate constraints.

Populate variables.

There is no vector based accessor to names, because they may be created on the fly.

Populate singular fields.

Definition at line 894 of file lp_data.cc.

◆ RemoveNearZeroEntries()

void operations_research::glop::LinearProgram::RemoveNearZeroEntries ( Fractional threshold )

Removes objective and coefficient with magnitude <= threshold.

Definition at line 1561 of file lp_data.cc.

◆ RemoveObjectiveScalingAndOffset()

Fractional operations_research::glop::LinearProgram::RemoveObjectiveScalingAndOffset ( Fractional value ) const

Definition at line 564 of file lp_data.cc.

◆ Scale()

void operations_research::glop::LinearProgram::Scale ( SparseMatrixScaler * scaler )

Scales the problem using the given scaler.

◆ ScaleBounds()

Fractional operations_research::glop::LinearProgram::ScaleBounds ( )

Definition at line 1234 of file lp_data.cc.

◆ ScaleObjective()

Fractional operations_research::glop::LinearProgram::ScaleObjective ( GlopParameters::CostScalingAlgorithm method )

While Scale() makes sure the coefficients inside the linear program matrix are in [-1, 1], the objective coefficients, variable bounds and constraint bounds can still take large values (originally or due to the matrix scaling).

It makes a lot of sense to also scale them given that internally we use absolute tolerances, and that it is nice to have the same behavior if users scale their problems. For instance one could change the unit of ALL the variables from Bytes to MBytes if they denote memory quantities. Or express a cost in dollars instead of thousands of dollars.

Here, we are quite prudent and just make sure that the range of the non-zeros magnitudes contains one. So for instance if all non-zeros costs are in [1e4, 1e6], we will divide them by 1e4 so that the new range is [1, 1e2].

Todo: (user): Another more aggressive idea is to set the median/mean/geomean of the magnitudes to one. Investigate if this leads to better results. It does look more robust.

Both functions update objective_scaling_factor()/objective_offset() and return the scaling coefficient so that:

For ScaleObjective(), the old coefficients can be retrieved by multiplying the new ones by the returned factor.
For ScaleBounds(), the old variable and constraint bounds can be retrieved by multiplying the new ones by the returned factor.

Definition at line 1199 of file lp_data.cc.

◆ SetCoefficient()

void operations_research::glop::LinearProgram::SetCoefficient	(	RowIndex	row,
		ColIndex	col,
		Fractional	value )

Defines the coefficient for col / row.

Definition at line 326 of file lp_data.cc.

◆ SetConstraintBounds()

void operations_research::glop::LinearProgram::SetConstraintBounds	(	RowIndex	row,
		Fractional	lower_bound,
		Fractional	upper_bound )

Defines lower and upper bounds for the constraint at row. Note that the bounds may be set to +/- infinity. If the constraint wasn't created before, all the rows from the current GetNumberOfRows() to the given row will be created with a range [0,0].

Definition at line 318 of file lp_data.cc.

◆ SetConstraintName()

void operations_research::glop::LinearProgram::SetConstraintName	(	RowIndex	row,
		absl::string_view	name )

Definition at line 254 of file lp_data.cc.

◆ SetDcheckBounds()

void operations_research::glop::LinearProgram::SetDcheckBounds ( bool dcheck_bounds )

inline

If true, checks bound validity in debug mode.

Definition at line 557 of file lp_data.h.

◆ SetMaximizationProblem()

void operations_research::glop::LinearProgram::SetMaximizationProblem ( bool maximize )

Defines the optimization direction. When maximize is true (resp. false), the objective is maximized (resp. minimized). The default is false.

Definition at line 352 of file lp_data.cc.

◆ SetName()

void operations_research::glop::LinearProgram::SetName ( absl::string_view name )

inline

Name setter and getter.

Definition at line 82 of file lp_data.h.

◆ SetObjectiveCoefficient()

void operations_research::glop::LinearProgram::SetObjectiveCoefficient	(	ColIndex	col,
		Fractional	value )

Defines the objective coefficient of column col. It is set to 0.0 by default.

Definition at line 335 of file lp_data.cc.

◆ SetObjectiveOffset()

void operations_research::glop::LinearProgram::SetObjectiveOffset ( Fractional objective_offset )

Define the objective offset (0.0 by default) and scaling factor (positive and equal to 1.0 by default). This is mainly used for displaying purpose and the real objective is factor * (objective + offset).

Definition at line 340 of file lp_data.cc.

◆ SetObjectiveScalingFactor()

void operations_research::glop::LinearProgram::SetObjectiveScalingFactor ( Fractional objective_scaling_factor )

Definition at line 345 of file lp_data.cc.

◆ SetVariableBounds()

void operations_research::glop::LinearProgram::SetVariableBounds	(	ColIndex	col,
		Fractional	lower_bound,
		Fractional	upper_bound )

Defines lower and upper bounds for the variable at col. Note that the bounds may be set to +/- infinity. The variable must have been created before or this will crash in non-debug mode.

Definition at line 258 of file lp_data.cc.

◆ SetVariableName()

void operations_research::glop::LinearProgram::SetVariableName	(	ColIndex	col,
		absl::string_view	name )

Functions to set the name of a variable or constraint. Note that you won't be able to find those named variables/constraints with FindOrCreate{Variable|Constraint}().

Todo: (user): Add PopulateIdsFromNames() so names added via Set{Variable|Constraint}Name() can be found.

Definition at line 241 of file lp_data.cc.

◆ SetVariableType()

void operations_research::glop::LinearProgram::SetVariableType	(	ColIndex	col,
		VariableType	type )

Set the type of the variable.

Definition at line 245 of file lp_data.cc.

◆ SolutionIsInteger()

bool operations_research::glop::LinearProgram::SolutionIsInteger	(	const DenseRow &	solution,
		Fractional	absolute_tolerance ) const

Tests if the solution is integer within the given tolerance, i.e., all integer variables have integer values within the absolute tolerance level. The solution does not need to satisfy the linear constraints.

Definition at line 526 of file lp_data.cc.

◆ SolutionIsLPFeasible()

bool operations_research::glop::LinearProgram::SolutionIsLPFeasible	(	const DenseRow &	solution,
		Fractional	absolute_tolerance ) const

Tests if the solution is LP-feasible within the given tolerance, i.e., satisfies all linear constraints within the absolute tolerance level. The solution does not need to satisfy the integer constraints.

Definition at line 506 of file lp_data.cc.

◆ SolutionIsMIPFeasible()

bool operations_research::glop::LinearProgram::SolutionIsMIPFeasible	(	const DenseRow &	solution,
		Fractional	absolute_tolerance ) const

Tests if the solution is both LP-feasible and integer within the tolerance.

Definition at line 538 of file lp_data.cc.

◆ SolutionIsWithinVariableBounds()

bool operations_research::glop::LinearProgram::SolutionIsWithinVariableBounds	(	const DenseRow &	solution,
		Fractional	absolute_tolerance ) const

Checks if each variable respects its bounds, nothing else.

Definition at line 490 of file lp_data.cc.

◆ Swap()

void operations_research::glop::LinearProgram::Swap ( LinearProgram * linear_program )

Swaps the content of this LinearProgram with the one passed as argument. Works in O(1).

Definition at line 1042 of file lp_data.cc.

◆ UpdateVariableBoundsToIntersection()

bool operations_research::glop::LinearProgram::UpdateVariableBoundsToIntersection	(	const DenseRow &	variable_lower_bounds,
		const DenseRow &	variable_upper_bounds )

Updates the bounds of the variables to the intersection of their original bounds and the bounds specified by variable_lower_bounds and variable_upper_bounds. If the new bounds of all variables are non-empty, returns true; otherwise, returns false.

Definition at line 1017 of file lp_data.cc.

◆ UseTransposeMatrixAsReference()

void operations_research::glop::LinearProgram::UseTransposeMatrixAsReference ( )

Definition at line 406 of file lp_data.cc.

◆ variable_lower_bounds()

const DenseRow & operations_research::glop::LinearProgram::variable_lower_bounds ( ) const

inline

Return the lower bounds (resp. upper bounds) of variables as a row vector.

Note: the bound values may be +/- infinity.

Definition at line 237 of file lp_data.h.

◆ variable_types()

StrictITIVector< ColIndex, VariableType > operations_research::glop::LinearProgram::variable_types ( ) const

inline

Returns a row vector of VariableType representing types of variables.

Definition at line 245 of file lp_data.h.

◆ variable_upper_bounds()

const DenseRow & operations_research::glop::LinearProgram::variable_upper_bounds ( ) const

inline

Definition at line 240 of file lp_data.h.

Friends And Related Symbol Documentation

◆ Scale

void Scale	(	LinearProgram *	lp,
		SparseMatrixScaler *	scaler,
		GlopParameters::ScalingAlgorithm	scaling_method )

friend

This is separated from LinearProgram class because of a cyclic dependency when scaling as an LP.

Definition at line 68 of file lp_data_utils.cc.

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

ortools/lp_data/lp_data.h
ortools/lp_data/lp_data.cc

Public Types

Public Member Functions

Friends

Detailed Description

Member Enumeration Documentation

◆ VariableType

Constructor & Destructor Documentation

◆ LinearProgram() [1/2]

◆ LinearProgram() [2/2]

Member Function Documentation

◆ AddConstraints()

◆ AddConstraintsWithSlackVariables()

◆ AddSlackVariablesWhereNecessary()

◆ ApplyObjectiveScalingAndOffset()

◆ BinaryVariablesList()

◆ BoundsOfIntegerConstraintsAreInteger()

◆ BoundsOfIntegerVariablesAreInteger()

◆ CleanUp()

◆ Clear()

◆ ClearTransposeMatrix()

◆ ComputeSlackVariableValues()

◆ constraint_lower_bounds()

◆ constraint_upper_bounds()

◆ CreateNewConstraint()

◆ CreateNewSlackVariable()

◆ CreateNewVariable()

◆ DeleteColumns()

◆ DeleteRows()

◆ DeleteSlackVariables()

◆ Dump()

◆ DumpSolution()

◆ FindOrCreateConstraint()

◆ FindOrCreateVariable()

◆ GetBoundsStatsString()

◆ GetConstraintName()

◆ GetDimensionString()

◆ GetFirstSlackVariable()

◆ GetMutableSparseColumn()

◆ GetMutableTransposeSparseMatrix()

◆ GetNonZeroStats()

◆ GetObjectiveCoefficientForMinimizationVersion()

◆ GetObjectiveStatsString()

◆ GetPrettyNonZeroStats()

◆ GetPrettyProblemStats()

◆ GetProblemStats()

◆ GetSlackVariable()

◆ GetSparseColumn()

◆ GetSparseMatrix()

◆ GetTransposeSparseMatrix()

◆ GetVariableName()

◆ GetVariableType()

◆ IntegerVariablesList()

◆ IsCleanedUp()

◆ IsInEquationForm()

◆ IsMaximizationProblem()

◆ IsValid()

◆ IsVariableBinary()

◆ IsVariableInteger()

◆ mutable_constraint_lower_bounds()

◆ mutable_constraint_upper_bounds()

◆ name()

◆ NonBinaryVariablesList()

◆ NotifyThatColumnsAreClean()

◆ num_constraints()

◆ num_entries()

◆ num_variables()

◆ objective_coefficients()

◆ objective_offset()

◆ objective_scaling_factor()

◆ operator=()

◆ PopulateFromDual()

◆ PopulateFromLinearProgram()

◆ PopulateFromLinearProgramVariables()

◆ PopulateFromPermutedLinearProgram()

◆ RemoveNearZeroEntries()

◆ RemoveObjectiveScalingAndOffset()

◆ Scale()

◆ ScaleBounds()

◆ ScaleObjective()

◆ SetCoefficient()