Classes
class	AddSlackVariablesPreprocessor

class	BasisFactorization

struct	BasisState

class	ColumnDeletionHelper
	Help preprocessors deal with column deletion. More...

class	ColumnPriorityQueue

class	ColumnsSaver

class	ColumnView

class	CompactSparseMatrix

class	CompactSparseMatrixView

class	DataWrapper
	Data templates. More...

class	DataWrapper< LinearProgram >

class	DataWrapper< MPModelProto >

class	DoubletonEqualityRowPreprocessor

class	DoubletonFreeColumnPreprocessor

class	DualEdgeNorms

class	DualizerPreprocessor

class	DynamicMaximum

class	EmptyColumnPreprocessor
	Removes the empty columns from the problem. More...

class	EmptyConstraintPreprocessor
	Removes the constraints with no coefficients from the problem. More...

class	EnteringVariable

class	EtaFactorization

class	FixedVariablePreprocessor
	Removes the fixed variables from the problem. More...

class	ForcingAndImpliedFreeConstraintPreprocessor

class	FreeConstraintPreprocessor
	Removes the constraints with no bounds from the problem. More...

class	ImpliedFreePreprocessor

class	InitialBasis

class	LinearProgram

class	LPDecomposer

class	LpScalingHelper

class	LPSolver
	A full-fledged linear programming solver. More...

class	LuFactorization

class	MainLpPreprocessor

class	Markowitz

struct	MatrixEntry
	Holds a triplet (row, col, coefficient). More...

class	MatrixNonZeroPattern

class	MatrixView

class	Permutation

class	Preprocessor

class	PrimalEdgeNorms

class	PrimalPrices

struct	ProblemSolution
	Contains the solution of a LinearProgram as returned by a preprocessor. More...

class	ProportionalColumnPreprocessor

class	ProportionalRowPreprocessor

class	RandomAccessSparseColumn

class	RankOneUpdateElementaryMatrix

class	RankOneUpdateFactorization

class	ReducedCosts

class	RevisedSimplex
	Entry point of the revised simplex algorithm implementation. More...

class	RevisedSimplexDictionary

class	RowDeletionHelper
	Help preprocessors deal with row deletion. More...

class	ScalingPreprocessor

struct	ScatteredColumn

class	ScatteredColumnEntry
	Specializations used in the code. More...

struct	ScatteredRow

class	ScatteredRowEntry

struct	ScatteredVector

class	ScatteredVectorEntry

class	ShiftVariableBoundsPreprocessor

class	SingletonColumnSignPreprocessor

class	SingletonPreprocessor

class	SingletonUndo
	Stores the information needed to undo a singleton row/column deletion. More...

class	SparseColumn

class	SparseColumnEntry

class	SparseMatrix

class	SparseMatrixScaler

class	SparseMatrixWithReusableColumnMemory

class	SparseRow

class	SparseRowEntry

class	SparseVector

class	SparseVectorEntry

class	Status

class	StrictITISpan

class	StrictITIVector

class	SumWithOneMissing

class	ToMinimizationPreprocessor
	Changes the problem from maximization to minimization (if applicable). More...

class	TriangularMatrix

class	UnconstrainedVariablePreprocessor

class	UpdateRow

class	VariablesInfo

class	VariableValues

class	VectorIterator

Typedefs
typedef int32_t	Index

typedef double	Fractional

typedef StrictITIVector< ColIndex, Fractional >	DenseRow
	Row-vector types. Row-vector types are indexed by a column index.

typedef StrictITIVector< ColIndex, bool >	DenseBooleanRow
	Row of booleans.

typedef StrictITIVector< ColIndex, ColIndex >	ColMapping
	Row of column indices. Used to represent mappings between columns.

typedef std::vector< ColIndex >	ColIndexVector
	Vector of row or column indices. Useful to list the non-zero positions.

typedef std::vector< RowIndex >	RowIndexVector

typedef StrictITIVector< ColIndex, RowIndex >	ColToRowMapping

typedef StrictITIVector< ColIndex, VariableType >	VariableTypeRow
	Row of variable types.

typedef StrictITIVector< ColIndex, VariableStatus >	VariableStatusRow
	Row of variable statuses.

typedef Bitset64< ColIndex >	DenseBitRow
	Row of bits.

typedef StrictITIVector< RowIndex, Fractional >	DenseColumn
	Column-vector types. Column-vector types are indexed by a row index.

typedef StrictITIVector< RowIndex, bool >	DenseBooleanColumn
	Column of booleans.

typedef Bitset64< RowIndex >	DenseBitColumn
	Column of bits.

typedef StrictITIVector< RowIndex, RowIndex >	RowMapping
	Column of row indices. Used to represent mappings between rows.

typedef StrictITIVector< RowIndex, ColIndex >	RowToColMapping

typedef StrictITIVector< RowIndex, ConstraintStatus >	ConstraintStatusColumn
	Column of constraints (slack variables) statuses.

typedef AccurateSum< Fractional >	KahanSum

typedef SumWithOneMissing< true >	SumWithPositiveInfiniteAndOneMissing

typedef SumWithOneMissing< false >	SumWithNegativeInfiniteAndOneMissing

typedef Permutation< RowIndex >	RowPermutation

typedef Permutation< ColIndex >	ColumnPermutation

using	ScatteredColumnIterator = VectorIterator<ScatteredColumnEntry>

using	ScatteredRowIterator = VectorIterator<ScatteredRowEntry>

using	SparseColumnIterator = VectorIterator<SparseColumnEntry>

using	SparseRowIterator = VectorIterator<SparseRowEntry>

typedef util_intops::StrongVector< RowIndex, SparseRow >	RowMajorSparseMatrix
	A matrix stored by rows.

Enumerations
enum class	ProblemStatus : int8_t { OPTIMAL , PRIMAL_INFEASIBLE , DUAL_INFEASIBLE , INFEASIBLE_OR_UNBOUNDED , PRIMAL_UNBOUNDED , DUAL_UNBOUNDED , INIT , PRIMAL_FEASIBLE , DUAL_FEASIBLE , ABNORMAL , INVALID_PROBLEM , IMPRECISE }
	Different statuses for a given problem. More...

enum class	VariableType : int8_t { UNCONSTRAINED , LOWER_BOUNDED , UPPER_BOUNDED , UPPER_AND_LOWER_BOUNDED , FIXED_VARIABLE }
	Different types of variables. More...

enum class	VariableStatus : int8_t { BASIC , FIXED_VALUE , AT_LOWER_BOUND , AT_UPPER_BOUND , FREE }

enum class	ConstraintStatus : int8_t { BASIC , FIXED_VALUE , AT_LOWER_BOUND , AT_UPPER_BOUND , FREE }

Functions
std::string	ValidateParameters (const GlopParameters &params)

void	FixConstraintWithFixedStatuses (const DenseColumn &row_lower_bounds, const DenseColumn &row_upper_bounds, ProblemSolution *solution)

std::string	GetErrorCodeString (Status::ErrorCode error_code)
	Returns the string representation of the ErrorCode enum.

bool	AreBoundsValid (Fractional lower_bound, Fractional upper_bound)

void	ComputeSlackVariablesValues (const LinearProgram &linear_program, DenseRow *values)

void	Scale (LinearProgram lp, SparseMatrixScaler scaler)

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

std::string	StringifyRational (const double x, const double precision)

std::string	Stringify (const Fractional x, bool fraction)

std::string	StringifyMonomial (const Fractional a, absl::string_view x, bool fraction)

std::string	Stringify (const float a)

std::string	Stringify (const double a)

std::string	Stringify (const long double a)

std::string	GetProblemStatusString (ProblemStatus problem_status)
	Returns the string representation of the ProblemStatus enum.

std::string	GetVariableTypeString (VariableType variable_type)
	Returns the string representation of the VariableType enum.

std::string	GetVariableStatusString (VariableStatus status)
	Returns the string representation of the VariableStatus enum.

std::string	GetConstraintStatusString (ConstraintStatus status)
	Returns the string representation of the ConstraintStatus enum.

ConstraintStatus	VariableToConstraintStatus (VariableStatus status)
	Returns the ConstraintStatus corresponding to a given VariableStatus.

	DEFINE_STRONG_INDEX_TYPE (ColIndex)

	DEFINE_STRONG_INDEX_TYPE (RowIndex)

ColIndex	RowToColIndex (RowIndex row)
	Get the ColIndex corresponding to the column # row.

RowIndex	ColToRowIndex (ColIndex col)
	Get the RowIndex corresponding to the row # col.

Index	ColToIntIndex (ColIndex col)
	Get the integer index corresponding to the col.

Index	RowToIntIndex (RowIndex row)
	Get the integer index corresponding to the row.

	DEFINE_STRONG_INT64_TYPE (EntryIndex)

static double	ToDouble (double f)

static double	ToDouble (long double f)

bool	IsFinite (Fractional value)

constexpr RowIndex	kInvalidRow (-1)

constexpr ColIndex	kInvalidCol (-1)

std::ostream &	operator<< (std::ostream &os, ProblemStatus status)

std::ostream &	operator<< (std::ostream &os, VariableType type)

std::ostream &	operator<< (std::ostream &os, VariableStatus status)

std::ostream &	operator<< (std::ostream &os, ConstraintStatus status)

static double	DeterministicTimeForFpOperations (int64_t n)

template<typename SparseColumnLike >
Fractional	SquaredNormTemplate (const SparseColumnLike &column)

Fractional	SquaredNorm (const SparseColumn &v)

Fractional	SquaredNorm (const ColumnView &v)

Fractional	PreciseSquaredNorm (const SparseColumn &v)

Fractional	SquaredNorm (const ScatteredColumn &v)

Fractional	PreciseSquaredNorm (const ScatteredColumn &v)

Fractional	SquaredNorm (absl::Span< const Fractional > data)

Fractional	SquaredNormAndResetToZero (absl::Span< Fractional > data)

Fractional	SquaredNorm (const DenseColumn &column)

Fractional	PreciseSquaredNorm (const DenseColumn &column)

Fractional	InfinityNorm (const DenseColumn &v)
	Returns the maximum of the `coefficients` of 'v'.

template<typename SparseColumnLike >
Fractional	InfinityNormTemplate (const SparseColumnLike &column)

Fractional	InfinityNorm (const SparseColumn &v)

Fractional	InfinityNorm (const ColumnView &v)

double	Density (const DenseRow &row)

void	RemoveNearZeroEntries (Fractional threshold, DenseRow *row)

Fractional	RestrictedInfinityNorm (const ColumnView &column, const DenseBooleanColumn &rows_to_consider, RowIndex *row_index)

void	SetSupportToFalse (const ColumnView &column, DenseBooleanColumn *b)

bool	IsDominated (const ColumnView &column, const DenseColumn &radius)
	Returns true iff for all 'row' we have '\|column[row]\| <= radius[row]'.

Fractional	Square (Fractional f)

static Fractional	Fractionality (Fractional f)

template<class DenseRowOrColumn1 , class DenseRowOrColumn2 >
Fractional	ScalarProduct (const DenseRowOrColumn1 &u, const DenseRowOrColumn2 &v)

template<class DenseRowOrColumn >
Fractional	ScalarProduct (const DenseRowOrColumn &u, const SparseColumn &v)

template<class DenseRowOrColumn >
Fractional	ScalarProduct (const DenseRowOrColumn &u, const ScatteredColumn &v)

template<class DenseRowOrColumn , class DenseRowOrColumn2 >
Fractional	PreciseScalarProduct (const DenseRowOrColumn &u, const DenseRowOrColumn2 &v)

template<class DenseRowOrColumn >
Fractional	PreciseScalarProduct (const DenseRowOrColumn &u, const SparseColumn &v)

template<class DenseRowOrColumn >
Fractional	PartialScalarProduct (const DenseRowOrColumn &u, const SparseColumn &v, int max_index)
	Computes a scalar product for entries with index not greater than max_index.

const DenseRow &	Transpose (const DenseRow &row)
	Similar comment as the other Transpose() implementation above.

template<typename IndexType >
void	ComputeNonZeros (const StrictITIVector< IndexType, Fractional > &input, std::vector< IndexType > *non_zeros)
	Computes the positions of the non-zeros of a dense vector.

template<typename Container >
bool	IsAllZero (const Container &input)
	Returns true if the given Fractional container is all zeros.

template<typename BoolVector >
bool	IsAllFalse (const BoolVector &v)
	Returns true if the given vector of bool is all false.

template<typename IndexType , typename PermutationIndexType >
void	PermuteWithScratchpad (const Permutation< PermutationIndexType > &permutation, StrictITIVector< IndexType, Fractional > zero_scratchpad, StrictITIVector< IndexType, Fractional > input_output)
	Permutes the given dense vector. It uses for this an all zero scratchpad.

template<typename IndexType >
void	PermuteWithKnownNonZeros (const Permutation< IndexType > &permutation, StrictITIVector< IndexType, Fractional > zero_scratchpad, StrictITIVector< IndexType, Fractional > output, std::vector< IndexType > *non_zeros)

template<typename IndexType , typename ScatteredRowOrCol >
void	ClearAndResizeVectorWithNonZeros (IndexType size, ScatteredRowOrCol *v)
	Sets a dense vector for which the non zeros are known to be non_zeros.

template<typename IndexType >
void	ChangeSign (StrictITIVector< IndexType, Fractional > *data)
	Changes the sign of all the entries in the given vector.

ColMapping	FindProportionalColumns (const SparseMatrix &matrix, Fractional tolerance)

ColMapping	FindProportionalColumnsUsingSimpleAlgorithm (const SparseMatrix &matrix, Fractional tolerance)

bool	AreFirstColumnsAndRowsExactlyEquals (RowIndex num_rows, ColIndex num_cols, const SparseMatrix &matrix_a, const CompactSparseMatrix &matrix_b)

bool	IsRightMostSquareMatrixIdentity (const SparseMatrix &matrix)
	Returns true iff the rightmost square matrix is an identity matrix.

bool	LoadMPModelProtoFromModelOrRequest (const std::string &input_file_path, MPModelProto *model)

bool	LoadLinearProgramFromModelOrRequest (const std::string &input_file_path, LinearProgram *linear_program)

absl::StatusOr< MPModelProto >	MpsDataToMPModelProto (absl::string_view mps_data)
	Parses an MPS model from a string.

absl::StatusOr< MPModelProto >	MpsFileToMPModelProto (absl::string_view mps_file)
	Parses an MPS model from a file.

class	ABSL_DEPRECATED ("Use the direct methods instead") MPSReader

template<typename IndexType , typename ITIVectorType >
void	ApplyPermutation (const Permutation< IndexType > &perm, const ITIVectorType &b, ITIVectorType *result)

template<typename IndexType , typename ITIVectorType >
void	ApplyInversePermutation (const Permutation< IndexType > &perm, const ITIVectorType &b, ITIVectorType *result)

template<typename RowIndexedVector >
void	ApplyColumnPermutationToRowIndexedVector (const Permutation< ColIndex > &col_perm, RowIndexedVector *v)

template<typename RowIndexedVector >
void	ApplyColumnPermutationToRowIndexedVector (const Permutation< ColIndex > &col_perm, RowIndexedVector v, RowIndexedVector tmp)

void	LinearProgramToMPModelProto (const LinearProgram &input, MPModelProto *output)
	Converts a LinearProgram to a MPModelProto.

void	MPModelProtoToLinearProgram (const MPModelProto &input, LinearProgram *output)
	Converts a MPModelProto to a LinearProgram.

const ScatteredRow &	TransposedView (const ScatteredColumn &c)

const ScatteredColumn &	TransposedView (const ScatteredRow &r)

const RowIndex	kNonPivotal (-1)

Variables
	e_

constexpr const uint64_t	kDeterministicSeed = 42

constexpr double	kRangeMax = std::numeric_limits<double>::max()
	Range max for type Fractional. DBL_MAX for double for example.

constexpr double	kInfinity = std::numeric_limits<double>::infinity()
	Infinity for type Fractional.

constexpr double	kEpsilon = std::numeric_limits<double>::epsilon()
	Epsilon for type Fractional, i.e. the smallest e such that 1.0 + e != 1.0 .

Detailed Description

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

EmptyColumnPreprocessor

ProportionalColumnPreprocessor

UnconstrainedVariablePreprocessor

Typedef Documentation

◆ ColIndexVector

typedef std::vector<ColIndex> operations_research::glop::ColIndexVector

Vector of row or column indices. Useful to list the non-zero positions.

Definition at line 362 of file lp_types.h.

◆ ColMapping

typedef StrictITIVector<ColIndex, ColIndex> operations_research::glop::ColMapping

Row of column indices. Used to represent mappings between columns.

Definition at line 359 of file lp_types.h.

◆ ColToRowMapping

typedef StrictITIVector<ColIndex, RowIndex> operations_research::glop::ColToRowMapping

Row of row indices. Useful for knowing which row corresponds to a particular column in the basis, or for storing the number of rows for a given column.

Definition at line 368 of file lp_types.h.

◆ ColumnPermutation

typedef Permutation<ColIndex> operations_research::glop::ColumnPermutation

Definition at line 97 of file permutation.h.

◆ ConstraintStatusColumn

typedef StrictITIVector<RowIndex, ConstraintStatus> operations_research::glop::ConstraintStatusColumn

Column of constraints (slack variables) statuses.

Definition at line 399 of file lp_types.h.

◆ DenseBitColumn

typedef Bitset64<RowIndex> operations_research::glop::DenseBitColumn

Column of bits.

Definition at line 388 of file lp_types.h.

◆ DenseBitRow

typedef Bitset64<ColIndex> operations_research::glop::DenseBitRow

Row of bits.

Definition at line 377 of file lp_types.h.

◆ DenseBooleanColumn

typedef StrictITIVector<RowIndex, bool> operations_research::glop::DenseBooleanColumn

Column of booleans.

Definition at line 385 of file lp_types.h.

◆ DenseBooleanRow

typedef StrictITIVector<ColIndex, bool> operations_research::glop::DenseBooleanRow

Row of booleans.

Definition at line 356 of file lp_types.h.

◆ DenseColumn

typedef StrictITIVector<RowIndex, Fractional> operations_research::glop::DenseColumn

Column-vector types. Column-vector types are indexed by a row index.

Column of fractional values.

Definition at line 382 of file lp_types.h.

◆ DenseRow

typedef StrictITIVector<ColIndex, Fractional> operations_research::glop::DenseRow

Row-vector types. Row-vector types are indexed by a column index.

Row of fractional values.

Definition at line 353 of file lp_types.h.

◆ Fractional

typedef double operations_research::glop::Fractional

The type Fractional denotes the type of numbers on which the computations are performed. This is defined as double here, but it could as well be float, DoubleDouble, QuadDouble, or infinite-precision rationals. Floating-point representations are binary fractional numbers, thus the name. (See http://en.wikipedia.org/wiki/Fraction_(mathematics) .)

Definition at line 83 of file lp_types.h.

◆ Index

typedef int32_t operations_research::glop::Index

This type is defined to avoid cast issues during index conversions, e.g. converting ColIndex into RowIndex. All types should use 'Index' instead of int32_t.

Definition at line 43 of file lp_types.h.

◆ KahanSum

typedef AccurateSum<Fractional> operations_research::glop::KahanSum

Todo: (user): For some Fractional types, it may not gain much (or even nothing if we are in infinite precision) to use this sum. A solution is to templatize this class and specialize it to a normal sum for the Fractional type we want so in this case the PreciseXXX() functions below will become equivalent to their normal version.

Definition at line 37 of file lp_utils.h.

◆ RowIndexVector

typedef std::vector<RowIndex> operations_research::glop::RowIndexVector

Definition at line 363 of file lp_types.h.

◆ RowMajorSparseMatrix

typedef util_intops::StrongVector<RowIndex, SparseRow> operations_research::glop::RowMajorSparseMatrix

A matrix stored by rows.

Definition at line 61 of file sparse_row.h.

◆ RowMapping

typedef StrictITIVector<RowIndex, RowIndex> operations_research::glop::RowMapping

Column of row indices. Used to represent mappings between rows.

Definition at line 391 of file lp_types.h.

◆ RowPermutation

typedef Permutation<RowIndex> operations_research::glop::RowPermutation

Definition at line 96 of file permutation.h.

◆ RowToColMapping

typedef StrictITIVector<RowIndex, ColIndex> operations_research::glop::RowToColMapping

Column of column indices. Used to represent which column corresponds to a particular row in the basis, or for storing the number of columns for a given row.

Definition at line 396 of file lp_types.h.

◆ ScatteredColumnIterator

using operations_research::glop::ScatteredColumnIterator = VectorIterator<ScatteredColumnEntry>

Definition at line 190 of file scattered_vector.h.

◆ ScatteredRowIterator

using operations_research::glop::ScatteredRowIterator = VectorIterator<ScatteredRowEntry>

Definition at line 191 of file scattered_vector.h.

◆ SparseColumnIterator

using operations_research::glop::SparseColumnIterator = VectorIterator<SparseColumnEntry>

Definition at line 42 of file sparse_column.h.

◆ SparseRowIterator

using operations_research::glop::SparseRowIterator = VectorIterator<SparseRowEntry>

Definition at line 36 of file sparse_row.h.

◆ SumWithNegativeInfiniteAndOneMissing

typedef SumWithOneMissing<false> operations_research::glop::SumWithNegativeInfiniteAndOneMissing

Definition at line 391 of file lp_utils.h.

◆ SumWithPositiveInfiniteAndOneMissing

typedef SumWithOneMissing<true> operations_research::glop::SumWithPositiveInfiniteAndOneMissing

Definition at line 390 of file lp_utils.h.

◆ VariableStatusRow

typedef StrictITIVector<ColIndex, VariableStatus> operations_research::glop::VariableStatusRow

Row of variable statuses.

Definition at line 374 of file lp_types.h.

◆ VariableTypeRow

typedef StrictITIVector<ColIndex, VariableType> operations_research::glop::VariableTypeRow

Row of variable types.

Definition at line 371 of file lp_types.h.

Enumeration Type Documentation

◆ ConstraintStatus

enum class operations_research::glop::ConstraintStatus : int8_t

strong

Different constraints statuses. The meaning is the same for the constraint activity relative to its bounds as it is for a variable value relative to its bounds. Actually, this is the VariableStatus of the slack variable associated to a constraint modulo a change of sign. The difference is that because of precision error, a constraint activity cannot exactly be equal to one of its bounds or to zero.

Enumerator
BASIC
FIXED_VALUE
AT_LOWER_BOUND
AT_UPPER_BOUND
FREE

Definition at line 236 of file lp_types.h.

◆ ProblemStatus

enum class operations_research::glop::ProblemStatus : int8_t

strong

Different statuses for a given problem.

Enumerator
OPTIMAL	The problem has been solved to optimality. Both the primal and dual have a feasible solution.
PRIMAL_INFEASIBLE	The problem has been proven primal-infeasible. Note that the problem is not necessarily DUAL_UNBOUNDED (See Chvatal p.60). The solver does not have a dual unbounded ray in this case.
DUAL_INFEASIBLE	The problem has been proven dual-infeasible. Note that the problem is not necessarily PRIMAL_UNBOUNDED (See Chvatal p.60). The solver does note have a primal unbounded ray in this case,
INFEASIBLE_OR_UNBOUNDED	The problem is either INFEASIBLE or UNBOUNDED (this applies to both the primal and dual algorithms). This status is only returned by the presolve step and means that a primal or dual unbounded ray was found during presolve. Note that because some presolve techniques assume that a feasible solution exists to simplify the problem further, it is difficult to distinguish between infeasibility and unboundedness. If a client needs to distinguish, it is possible to run the primal algorithm on the same problem with a 0 objective function to know if the problem was PRIMAL_INFEASIBLE.
PRIMAL_UNBOUNDED	The problem has been proven feasible and unbounded. That means that the problem is DUAL_INFEASIBLE and that the solver has a primal unbounded ray.
DUAL_UNBOUNDED	The problem has been proven dual-feasible and dual-unbounded. That means the problem is PRIMAL_INFEASIBLE and that the solver has a dual unbounded ray to prove it.
INIT	The solver didn't had a chance to prove anything. All the statuses below correspond to a case where the solver was interrupted. This can happen because of a timeout, an iteration limit or an error.
PRIMAL_FEASIBLE	The problem has been proven primal-feasible but may still be PRIMAL_UNBOUNDED.
DUAL_FEASIBLE	The problem has been proven dual-feasible, but may still be DUAL_UNBOUNDED. That means that if the primal is feasible, then it has a finite optimal solution.
ABNORMAL	An error occurred during the solving process.
INVALID_PROBLEM	The input problem was invalid (see LinearProgram.IsValid()).
IMPRECISE	The problem was solved to a feasible status, but the solution checker found the primal and/or dual infeasibilities too important for the specified parameters.

Definition at line 107 of file lp_types.h.

◆ VariableStatus

enum class operations_research::glop::VariableStatus : int8_t

strong

Different variables statuses. If a solution is OPTIMAL or FEASIBLE, then all the properties described here should be satisfied. These properties should also be true during the execution of the revised simplex algorithm, except that because of bound-shifting, the variable may not be at their exact bounds until the shifts are removed.

Enumerator
BASIC	The basic status is special and takes precedence over all the other statuses. It means that the variable is part of the basis.
FIXED_VALUE	Only possible status of a FIXED_VARIABLE not in the basis. The variable value should be exactly equal to its bounds (which are the same).
AT_LOWER_BOUND	Only possible statuses of a non-basic variable which is not UNCONSTRAINED or FIXED. The variable value should be at its exact specified bound (which must be finite).
AT_UPPER_BOUND
FREE	Only possible status of an UNCONSTRAINED non-basic variable. Its value should be zero. Note during crossover, this status is relaxed, and any variable that can currently move in both directions can be marked as free.

Definition at line 202 of file lp_types.h.

◆ VariableType

enum class operations_research::glop::VariableType : int8_t

strong

Different types of variables.

Enumerator
UNCONSTRAINED
LOWER_BOUNDED
UPPER_BOUNDED
UPPER_AND_LOWER_BOUNDED
FIXED_VARIABLE

Definition at line 180 of file lp_types.h.

Function Documentation

◆ ABSL_DEPRECATED()

class operations_research::glop::ABSL_DEPRECATED ( "Use the direct methods instead" )

Implementation class. Please use the 2 functions above.

Reads a linear program in the mps format.

All Parse() methods clear the previously parsed instance and store the result in the given Data class.

Todo: (user): Remove the MPSReader class.

Parses instance from a file.

Loads instance from string. Useful with MapReduce. Automatically detects the file's format (free or fixed).

Definition at line 43 of file mps_reader.h.

◆ ApplyColumnPermutationToRowIndexedVector() [1/2]

template<typename RowIndexedVector >

void operations_research::glop::ApplyColumnPermutationToRowIndexedVector	(	const Permutation< ColIndex > &	col_perm,
		RowIndexedVector *	v )

Specialization of ApplyPermutation(): apply a column permutation to a row-indexed vector v.

Definition at line 118 of file permutation.h.

◆ ApplyColumnPermutationToRowIndexedVector() [2/2]

template<typename RowIndexedVector >

void operations_research::glop::ApplyColumnPermutationToRowIndexedVector	(	const Permutation< ColIndex > &	col_perm,
		RowIndexedVector *	v,
		RowIndexedVector *	tmp )

Definition at line 125 of file permutation.h.

◆ ApplyInversePermutation()

template<typename IndexType , typename ITIVectorType >

void operations_research::glop::ApplyInversePermutation	(	const Permutation< IndexType > &	perm,
		const ITIVectorType &	b,
		ITIVectorType *	result )

Applies the inverse of perm to the vector b. Overwrites result to store the result.

Empty size means identity.

Definition at line 223 of file permutation.h.

◆ ApplyPermutation()

template<typename IndexType , typename ITIVectorType >

void operations_research::glop::ApplyPermutation	(	const Permutation< IndexType > &	perm,
		const ITIVectorType &	b,
		ITIVectorType *	result )

Applies the permutation perm to the vector b. Overwrites result to store the result.

Todo: (user): Try to restrict this method to using the same integer type in the permutation and for the vector indices, i.e. IndexType == ITIVectorType::IndexType. Some client code will need to be refactored.

Empty size means identity.

Definition at line 204 of file permutation.h.

◆ AreBoundsValid()

bool operations_research::glop::AreBoundsValid	(	Fractional	lower_bound,
		Fractional	upper_bound )

inline

Helper function to check the bounds of the SetVariableBounds() and SetConstraintBounds() functions.

Definition at line 707 of file lp_data.h.

◆ AreFirstColumnsAndRowsExactlyEquals()

bool operations_research::glop::AreFirstColumnsAndRowsExactlyEquals	(	RowIndex	num_rows,
		ColIndex	num_cols,
		const SparseMatrix &	matrix_a,
		const CompactSparseMatrix &	matrix_b )

Returns true iff the two given matrices have exactly the same first num_rows entries on the first num_cols columns. The two given matrices must be ordered by rows (this is DCHECKed, but only for the first one at this point).

Todo: (user): Also DCHECK() that matrix_b is ordered by rows.

Definition at line 198 of file matrix_utils.cc.

◆ ChangeSign()

template<typename IndexType >

void operations_research::glop::ChangeSign ( StrictITIVector< IndexType, Fractional > * data )

inline

Changes the sign of all the entries in the given vector.

Definition at line 307 of file lp_utils.h.

◆ ClearAndResizeVectorWithNonZeros()

template<typename IndexType , typename ScatteredRowOrCol >

void operations_research::glop::ClearAndResizeVectorWithNonZeros	(	IndexType	size,
		ScatteredRowOrCol *	v )

inline

Sets a dense vector for which the non zeros are known to be non_zeros.

Only use the sparse version if there is less than 5% non-zeros positions compared to the wanted size. Note that in most cases the vector will already be of the correct size.

Definition at line 285 of file lp_utils.h.

◆ ColToIntIndex()

Index operations_research::glop::ColToIntIndex ( ColIndex col )

inline

Get the integer index corresponding to the col.

Definition at line 60 of file lp_types.h.

◆ ColToRowIndex()

RowIndex operations_research::glop::ColToRowIndex ( ColIndex col )

inline

Get the RowIndex corresponding to the row # col.

Definition at line 57 of file lp_types.h.

◆ ComputeNonZeros()

template<typename IndexType >

void operations_research::glop::ComputeNonZeros	(	const StrictITIVector< IndexType, Fractional > &	input,
		std::vector< IndexType > *	non_zeros )

inline

Computes the positions of the non-zeros of a dense vector.

Definition at line 216 of file lp_utils.h.

◆ ComputeSlackVariablesValues()

void operations_research::glop::ComputeSlackVariablesValues	(	const LinearProgram &	linear_program,
		DenseRow *	values )

For all constraints in linear_program, if the constraint has a slack variable, change its value in *values so that the constraints itself is satisfied.

Note: this obviously won't always imply that the bounds of the slack variable itself will be satisfied. The code assumes (and DCHECKs) that all constraints with a slack variable have their upper and lower bounds both set to 0. This is ensured by LinearProgram::AddSlackVariablesWhereNecessary().

If there are no slack variable, we can give up.

Row in the initial matrix (column in the transposed).

Definition at line 27 of file lp_data_utils.cc.

◆ DEFINE_STRONG_INDEX_TYPE() [1/2]

operations_research::glop::DEFINE_STRONG_INDEX_TYPE ( ColIndex )

ColIndex is the type for integers representing column/variable indices. int32s are enough for handling even the largest problems.

◆ DEFINE_STRONG_INDEX_TYPE() [2/2]

operations_research::glop::DEFINE_STRONG_INDEX_TYPE ( RowIndex )

RowIndex is the type for integers representing row/constraint indices. int32s are enough for handling even the largest problems.

◆ DEFINE_STRONG_INT64_TYPE()

operations_research::glop::DEFINE_STRONG_INT64_TYPE ( EntryIndex )

EntryIndex is the type for integers representing entry indices. An entry in a sparse matrix is a pair (row, value) for a given known column. See classes SparseColumn and SparseMatrix.

◆ Density()

double operations_research::glop::Density ( const DenseRow & row )

Returns the fraction of non-zero entries of the given row.

Todo: (user): Take a Scattered row/col instead. This is only used to report stats, but we should still have a sparse version to do it faster.

Definition at line 176 of file lp_utils.cc.

◆ DeterministicTimeForFpOperations()

static double operations_research::glop::DeterministicTimeForFpOperations ( int64_t n )

inlinestatic

This is used during the deterministic time computation to convert a given number of floating-point operations to something in the same order of magnitude as a second (on a 2014 desktop).

Definition at line 435 of file lp_types.h.

◆ FindProportionalColumns()

ColMapping operations_research::glop::FindProportionalColumns	(	const SparseMatrix &	matrix,
		Fractional	tolerance )

Finds the proportional columns of the given matrix: all the pairs of columns such that one is a non-zero scalar multiple of the other. The returned mapping for a given column will either be:

The index of the first column which is proportional with this one.
Or kInvalidCol if this column is not proportional to any other.

Because of precision errors, two columns are declared proportional if the multiples (>= 1.0) defined by all the couple of coefficients of the same row are equal up to the given absolute tolerance.

The complexity is in most cases O(num entries of the matrix). However, compared to the less efficient algorithm below, it is highly unlikely but possible that some pairs of proportional columns are not detected.

Compute the fingerprint of each columns and sort them.

Find a representative of each proportional columns class. This only compares columns with a close-enough fingerprint.

Note: we use the same tolerance for the fingerprints.

Todo: (user): Derive precise bounds on what this tolerance should be so that no proportional columns are missed.

Sort the mapping so that the representative of each class is the smallest column. To achieve this, the current representative is used as a pointer to the new one, a bit like in an union find algorithm.

Definition at line 123 of file matrix_utils.cc.

◆ FindProportionalColumnsUsingSimpleAlgorithm()

ColMapping operations_research::glop::FindProportionalColumnsUsingSimpleAlgorithm	(	const SparseMatrix &	matrix,
		Fractional	tolerance )

A simple version of FindProportionalColumns() that compares all the columns pairs one by one. This is slow, but here for reference. The complexity is O(num_cols * num_entries).

Definition at line 179 of file matrix_utils.cc.

◆ FixConstraintWithFixedStatuses()

void operations_research::glop::FixConstraintWithFixedStatuses	(	const DenseColumn &	row_lower_bounds,
		const DenseColumn &	row_upper_bounds,
		ProblemSolution *	solution )

Because of numerical imprecision, a preprocessor like DoubletonEqualityRowPreprocessor can transform a constraint/variable domain like [1, 1+1e-7] to a fixed domain (for ex by multiplying the above domain by 1e9). This causes an issue because at postsolve, a FIXED_VALUE status now needs to be transformed to a AT_LOWER_BOUND/AT_UPPER_BOUND status. This is what this function is doing for the constraint statuses only.

Todo: (user): A better solution would simply be to get rid of the FIXED status altogether, it is better to simply use AT_LOWER_BOUND/AT_UPPER_BOUND depending on the constraining bound in the optimal solution. Note that we can always at the end transform any variable/constraint with a fixed domain to FIXED_VALUE if needed to keep the same external API.

We need to fix the status and we just need to make sure that the bound we choose satisfies the LP optimality conditions.

Definition at line 3402 of file preprocessor.cc.

◆ Fractionality()

static Fractional operations_research::glop::Fractionality ( Fractional f )

inlinestatic

Returns distance from a given fractional number to the closest integer. It means that the result is always contained in range of [0.0, 0.5].

Definition at line 45 of file lp_utils.h.

◆ GetConstraintStatusString()

std::string operations_research::glop::GetConstraintStatusString ( ConstraintStatus status )

Returns the string representation of the ConstraintStatus enum.

Fallback. We don't use "default:" so the compiler will return an error if we forgot one enum case above.

Definition at line 94 of file lp_types.cc.

◆ GetErrorCodeString()

std::string operations_research::glop::GetErrorCodeString ( Status::ErrorCode error_code )

Returns the string representation of the ErrorCode enum.

Fallback. We don't use "default:" so the compiler will return an error if we forgot one enum case above.

Definition at line 30 of file status.cc.

◆ GetProblemStatusString()

std::string operations_research::glop::GetProblemStatusString ( ProblemStatus problem_status )

Returns the string representation of the ProblemStatus enum.

Fallback. We don't use "default:" so the compiler will return an error if we forgot one enum case above.

Definition at line 23 of file lp_types.cc.

◆ GetVariableStatusString()

std::string operations_research::glop::GetVariableStatusString ( VariableStatus status )

Returns the string representation of the VariableStatus enum.

Fallback. We don't use "default:" so the compiler will return an error if we forgot one enum case above.

Definition at line 75 of file lp_types.cc.

◆ GetVariableTypeString()

std::string operations_research::glop::GetVariableTypeString ( VariableType variable_type )

Returns the string representation of the VariableType enum.

Fallback. We don't use "default:" so the compiler will return an error if we forgot one enum case above.

Definition at line 56 of file lp_types.cc.

◆ InfinityNorm() [1/3]

Fractional operations_research::glop::InfinityNorm ( const ColumnView & v )

Definition at line 172 of file lp_utils.cc.

◆ InfinityNorm() [2/3]

Fractional operations_research::glop::InfinityNorm ( const DenseColumn & v )

Returns the maximum of the coefficients of 'v'.

Definition at line 151 of file lp_utils.cc.

◆ InfinityNorm() [3/3]

Fractional operations_research::glop::InfinityNorm ( const SparseColumn & v )

Definition at line 168 of file lp_utils.cc.

◆ InfinityNormTemplate()

template<typename SparseColumnLike >

Fractional operations_research::glop::InfinityNormTemplate ( const SparseColumnLike & column )

Definition at line 160 of file lp_utils.cc.

◆ IsAllFalse()

template<typename BoolVector >

bool operations_research::glop::IsAllFalse ( const BoolVector & v )

Returns true if the given vector of bool is all false.

Definition at line 238 of file lp_utils.h.

◆ IsAllZero()

template<typename Container >

bool operations_research::glop::IsAllZero ( const Container & input )

inline

Returns true if the given Fractional container is all zeros.

Definition at line 229 of file lp_utils.h.

◆ IsDominated()

bool operations_research::glop::IsDominated	(	const ColumnView &	column,
		const DenseColumn &	radius )

Returns true iff for all 'row' we have '|column[row]| <= radius[row]'.

Definition at line 224 of file lp_utils.cc.

◆ IsFinite()

bool operations_research::glop::IsFinite ( Fractional value )

inline

Returns true if the given value is finite, that means for a double: not a NaN and not +/- infinity.

Definition at line 96 of file lp_types.h.

◆ IsRightMostSquareMatrixIdentity()

bool operations_research::glop::IsRightMostSquareMatrixIdentity ( const SparseMatrix & matrix )

Returns true iff the rightmost square matrix is an identity matrix.

Definition at line 239 of file matrix_utils.cc.

◆ kInvalidCol()

ColIndex operations_research::glop::kInvalidCol ( - 1 )

constexpr

◆ kInvalidRow()

RowIndex operations_research::glop::kInvalidRow ( - 1 )

constexpr

Constants to represent invalid row or column index. It is important that their values be the same because during transposition, one needs to be converted into the other.

◆ kNonPivotal()

const RowIndex operations_research::glop::kNonPivotal ( - 1 )

Todo: (user): Consider using kInvalidRow for this?

◆ LinearProgramToMPModelProto()

void operations_research::glop::LinearProgramToMPModelProto	(	const LinearProgram &	input,
		MPModelProto *	output )

Converts a LinearProgram to a MPModelProto.

We need the matrix transpose because a LinearProgram stores the data column-wise but the MPModelProto uses a row-wise format.

Definition at line 27 of file proto_utils.cc.

◆ LoadLinearProgramFromModelOrRequest()

bool operations_research::glop::LoadLinearProgramFromModelOrRequest	(	const std::string &	input_file_path,
		LinearProgram *	linear_program )

Definition at line 59 of file model_reader.cc.

◆ LoadMPModelProtoFromModelOrRequest()

bool operations_research::glop::LoadMPModelProtoFromModelOrRequest	(	const std::string &	input_file_path,
		MPModelProto *	model )

Helper function to read data from model files into MPModelProto and LinearProgram.

If the input proto is in binary format, both ReadFileToProto could return true. Instead use the actual number of variables found to test the correct format of the input.

Definition at line 27 of file model_reader.cc.

◆ MPModelProtoToLinearProgram()

void operations_research::glop::MPModelProtoToLinearProgram	(	const MPModelProto &	input,
		LinearProgram *	output )

Converts a MPModelProto to a LinearProgram.

Todo: (user): clean up loops to use natural range iteration.

Todo: (user): implement strong proto validation in the linear solver server and re-use it here.

Definition at line 58 of file proto_utils.cc.

◆ MpsDataToMPModelProto()

absl::StatusOr< MPModelProto > operations_research::glop::MpsDataToMPModelProto ( absl::string_view mps_data )

Parses an MPS model from a string.

Definition at line 360 of file mps_reader.cc.

◆ MpsFileToMPModelProto()

absl::StatusOr< MPModelProto > operations_research::glop::MpsFileToMPModelProto ( absl::string_view mps_file )

Parses an MPS model from a file.

Definition at line 370 of file mps_reader.cc.

◆ operator<<() [1/4]

std::ostream & operations_research::glop::operator<<	(	std::ostream &	os,
		ConstraintStatus	status )

inline

Definition at line 247 of file lp_types.h.

◆ operator<<() [2/4]

std::ostream & operations_research::glop::operator<<	(	std::ostream &	os,
		ProblemStatus	status )

inline

Definition at line 174 of file lp_types.h.

◆ operator<<() [3/4]

std::ostream & operations_research::glop::operator<<	(	std::ostream &	os,
		VariableStatus	status )

inline

Definition at line 225 of file lp_types.h.

◆ operator<<() [4/4]

std::ostream & operations_research::glop::operator<<	(	std::ostream &	os,
		VariableType	type )

inline

Definition at line 191 of file lp_types.h.

◆ PartialScalarProduct()

template<class DenseRowOrColumn >

Fractional operations_research::glop::PartialScalarProduct	(	const DenseRowOrColumn &	u,
		const SparseColumn &	v,
		int	max_index )

Computes a scalar product for entries with index not greater than max_index.

Definition at line 134 of file lp_utils.h.

◆ PermuteWithKnownNonZeros()

template<typename IndexType >

void operations_research::glop::PermuteWithKnownNonZeros	(	const Permutation< IndexType > &	permutation,
		StrictITIVector< IndexType, Fractional > *	zero_scratchpad,
		StrictITIVector< IndexType, Fractional > *	output,
		std::vector< IndexType > *	non_zeros )

inline

Same as PermuteAndComputeNonZeros() except that we assume that the given non-zeros are the initial non-zeros positions of output.

Definition at line 266 of file lp_utils.h.

◆ PermuteWithScratchpad()

template<typename IndexType , typename PermutationIndexType >

void operations_research::glop::PermuteWithScratchpad	(	const Permutation< PermutationIndexType > &	permutation,
		StrictITIVector< IndexType, Fractional > *	zero_scratchpad,
		StrictITIVector< IndexType, Fractional > *	input_output )

inline

Permutes the given dense vector. It uses for this an all zero scratchpad.

Definition at line 244 of file lp_utils.h.

◆ PreciseScalarProduct() [1/2]

template<class DenseRowOrColumn , class DenseRowOrColumn2 >

Fractional operations_research::glop::PreciseScalarProduct	(	const DenseRowOrColumn &	u,
		const DenseRowOrColumn2 &	v )

Definition at line 111 of file lp_utils.h.

◆ PreciseScalarProduct() [2/2]

template<class DenseRowOrColumn >

Fractional operations_research::glop::PreciseScalarProduct	(	const DenseRowOrColumn &	u,
		const SparseColumn &	v )

Definition at line 122 of file lp_utils.h.

◆ PreciseSquaredNorm() [1/3]

Fractional operations_research::glop::PreciseSquaredNorm ( const DenseColumn & column )

Definition at line 143 of file lp_utils.cc.

◆ PreciseSquaredNorm() [2/3]

Fractional operations_research::glop::PreciseSquaredNorm ( const ScatteredColumn & v )

Definition at line 63 of file lp_utils.cc.

◆ PreciseSquaredNorm() [3/3]

Fractional operations_research::glop::PreciseSquaredNorm ( const SparseColumn & v )

Definition at line 44 of file lp_utils.cc.

◆ RemoveNearZeroEntries()

void operations_research::glop::RemoveNearZeroEntries	(	Fractional	threshold,
		DenseRow *	row )

Sets to 0.0 all entries of the given row whose fabs() is lower than the given threshold.

Definition at line 185 of file lp_utils.cc.

◆ RestrictedInfinityNorm()

Fractional operations_research::glop::RestrictedInfinityNorm	(	const ColumnView &	column,
		const DenseBooleanColumn &	rows_to_consider,
		RowIndex *	row_index )

Returns the maximum of the coefficients of the given column restricted to the rows_to_consider. Also returns the first RowIndex 'row' that attains this maximum. If the maximum is 0.0, then row_index is left untouched.

Definition at line 203 of file lp_utils.cc.

◆ RowToColIndex()

ColIndex operations_research::glop::RowToColIndex ( RowIndex row )

inline

Get the ColIndex corresponding to the column # row.

Definition at line 54 of file lp_types.h.

◆ RowToIntIndex()

Index operations_research::glop::RowToIntIndex ( RowIndex row )

inline

Get the integer index corresponding to the row.

Definition at line 63 of file lp_types.h.

◆ ScalarProduct() [1/3]

template<class DenseRowOrColumn >

Fractional operations_research::glop::ScalarProduct	(	const DenseRowOrColumn &	u,
		const ScatteredColumn &	v )

Definition at line 97 of file lp_utils.h.

◆ ScalarProduct() [2/3]

template<class DenseRowOrColumn >

Fractional operations_research::glop::ScalarProduct	(	const DenseRowOrColumn &	u,
		const SparseColumn &	v )

Note: This version is heavily used in the pricing.

Todo: (user): Optimize this more (SSE or unroll with two sums). Another option is to skip the u[col] that are 0.0 rather than fetching the coeff and doing a Fractional multiplication.

Definition at line 87 of file lp_utils.h.

◆ ScalarProduct() [3/3]

template<class DenseRowOrColumn1 , class DenseRowOrColumn2 >

Fractional operations_research::glop::ScalarProduct	(	const DenseRowOrColumn1 &	u,
		const DenseRowOrColumn2 &	v )

Returns the scalar product between u and v. The precise versions use KahanSum and are about two times slower.

Computing the sum of 4 elements at once may allow the compiler to generate more efficient code, e.g. using SIMD and checking the loop condition much less frequently.

This produces different results from the case where each multiplication is added to sum separately. An extreme example of this can be derived using the fact that 1e11 + 2e-6 == 1e11, but 1e11 + 8e-6 > 1e11.

While the results are different, they aren't necessarily better or worse. Typically, sum will be of larger magnitude than any individual multiplication, so one might expect, in practice, this method to yield more accurate results. However, if accuracy is vital, use the precise version.

Definition at line 52 of file lp_utils.h.

◆ Scale() [1/2]

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

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

A convenience method for above providing a default algorithm for callers that don't specify one.

Create GlopParameters proto to get default scaling algorithm.

Definition at line 60 of file lp_data_utils.cc.

◆ Scale() [2/2]

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

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.

◆ SetSupportToFalse()

void operations_research::glop::SetSupportToFalse	(	const ColumnView &	column,
		DenseBooleanColumn *	b )

Sets to false the entry b[row] if column[row] is non null.

Note: if 'b' was true only on the non-zero position of column, this can be used as a fast way to clear 'b'.

Definition at line 216 of file lp_utils.cc.

◆ Square()

Fractional operations_research::glop::Square ( Fractional f )

inline

Returns the square of a Fractional. Useful to shorten the code when f is an expression or a long name.

Definition at line 41 of file lp_utils.h.

◆ SquaredNorm() [1/5]

Fractional operations_research::glop::SquaredNorm ( absl::Span< const Fractional > data )

We expand ourselves since we don't really care about the floating point order of operation and this seems faster.

Definition at line 74 of file lp_utils.cc.

◆ SquaredNorm() [2/5]

Fractional operations_research::glop::SquaredNorm ( const ColumnView & v )

Definition at line 40 of file lp_utils.cc.

◆ SquaredNorm() [3/5]

Fractional operations_research::glop::SquaredNorm ( const DenseColumn & column )

Definition at line 139 of file lp_utils.cc.

◆ SquaredNorm() [4/5]

Fractional operations_research::glop::SquaredNorm ( const ScatteredColumn & v )

Definition at line 52 of file lp_utils.cc.

◆ SquaredNorm() [5/5]

Fractional operations_research::glop::SquaredNorm ( const SparseColumn & v )

Returns the norm^2 (sum of the square of the entries) of the given column. The precise version uses KahanSum and are about two times slower.

Definition at line 36 of file lp_utils.cc.

◆ SquaredNormAndResetToZero()

Fractional operations_research::glop::SquaredNormAndResetToZero ( absl::Span< Fractional > data )

We expand ourselves since we don't really care about the floating point order of operation and this seems faster.

Definition at line 103 of file lp_utils.cc.

◆ SquaredNormTemplate()

template<typename SparseColumnLike >

Fractional operations_research::glop::SquaredNormTemplate ( const SparseColumnLike & column )

Definition at line 28 of file lp_utils.cc.

◆ Stringify() [1/4]

std::string operations_research::glop::Stringify ( const double a )

inline

Definition at line 35 of file lp_print_utils.h.

◆ Stringify() [2/4]

std::string operations_research::glop::Stringify ( const float a )

inline

Returns a string representing a floating-point number in decimal, with a precision corresponding to the type of the argument.

Definition at line 31 of file lp_print_utils.h.

◆ Stringify() [3/4]

std::string operations_research::glop::Stringify	(	Fractional	x,
		bool	fraction )

If fraction is true, returns a string corresponding to the rational approximation or a decimal approximation otherwise. Note that the absolute difference between the output fraction and "x" will never exceed std::numeric_limits<T>::epsilon().

Definition at line 46 of file lp_print_utils.cc.

◆ Stringify() [4/4]

std::string operations_research::glop::Stringify ( const long double a )

inline

Definition at line 39 of file lp_print_utils.h.

◆ StringifyMonomial()

std::string operations_research::glop::StringifyMonomial	(	const Fractional	a,
		absl::string_view	x,
		bool	fraction )

Returns a string that pretty-prints a monomial ax with coefficient a and variable name x

Pretty prints a monomial a*x using Stringify(x, fraction) to display a, taking care of the sign of x, whether a is 0, 1, -1, integer. Note that the absolute difference between the output fraction and "x" will never exceed std::numeric_limits<T>::epsilon().

Definition at line 54 of file lp_print_utils.cc.

◆ StringifyRational()

std::string operations_research::glop::StringifyRational	(	const double	x,
		const double	precision )

Returns a string "num/den" representing the rational approximation of x. The absolute difference between the output fraction and the input "x" will not exceed "precision".

Definition at line 33 of file lp_print_utils.cc.

◆ ToDouble() [1/2]

static double operations_research::glop::ToDouble ( double f )

inlinestatic

Definition at line 74 of file lp_types.h.

◆ ToDouble() [2/2]

static double operations_research::glop::ToDouble ( long double f )

inlinestatic

Definition at line 76 of file lp_types.h.

◆ Transpose()

const DenseRow & operations_research::glop::Transpose ( const DenseColumn & col )

Similar comment as the other Transpose() implementation above.

Transposition functions implemented below with a cast so it should actually have no complexity cost.

This cast based implementation should be safe, as long as DenseRow and DenseColumn are implemented by the same underlying type. We still do some DCHECK to be sure it works as expected in addition to the unit tests.

Definition at line 199 of file lp_utils.h.

◆ TransposedView() [1/2]

const ScatteredRow & operations_research::glop::TransposedView ( const ScatteredColumn & c )

inline

Definition at line 197 of file scattered_vector.h.

◆ TransposedView() [2/2]

const ScatteredColumn & operations_research::glop::TransposedView ( const ScatteredRow & r )

inline

Definition at line 200 of file scattered_vector.h.

◆ ValidateParameters()

std::string operations_research::glop::ValidateParameters ( const GlopParameters & params )

Verifies that the given parameters are correct. Returns an empty string if it is the case, or an human-readable error message otherwise.

Definition at line 52 of file parameters_validation.cc.

◆ VariableToConstraintStatus()

ConstraintStatus operations_research::glop::VariableToConstraintStatus ( VariableStatus status )

Returns the ConstraintStatus corresponding to a given VariableStatus.

Fallback. We don't use "default:" so the compiler will return an error if we forgot one enum case above.

This will never be reached and is here only to guarantee compilation.

Definition at line 113 of file lp_types.cc.

Variable Documentation

◆ e_

operations_research::glop::e_

An eta matrix E corresponds to the identity matrix except for one column e of index j. In particular, B.E is the matrix of the new basis obtained from B by replacing the j-th vector of B by B.e, note that this is exactly what happens during a "pivot" of the current basis in the simplex algorithm.

E = [ 1 ... 0 e_0 0 ... 0 ... ... ... ... ... ... ...

Definition at line 41 of file basis_representation.h.

◆ kDeterministicSeed

const uint64_t operations_research::glop::kDeterministicSeed = 42

constexpr

Definition at line 95 of file revised_simplex.cc.

◆ kEpsilon

double operations_research::glop::kEpsilon = std::numeric_limits<double>::epsilon()

constexpr

Epsilon for type Fractional, i.e. the smallest e such that 1.0 + e != 1.0 .

Definition at line 92 of file lp_types.h.

◆ kInfinity

double operations_research::glop::kInfinity = std::numeric_limits<double>::infinity()

constexpr

Infinity for type Fractional.

Definition at line 89 of file lp_types.h.

◆ kRangeMax

double operations_research::glop::kRangeMax = std::numeric_limits<double>::max()

constexpr

Range max for type Fractional. DBL_MAX for double for example.

Definition at line 86 of file lp_types.h.

Classes

Typedefs

Enumerations

Functions

Variables

Detailed Description

Typedef Documentation

◆ ColIndexVector

◆ ColMapping

◆ ColToRowMapping

◆ ColumnPermutation

◆ ConstraintStatusColumn

◆ DenseBitColumn

◆ DenseBitRow

◆ DenseBooleanColumn

◆ DenseBooleanRow

◆ DenseColumn

◆ DenseRow

◆ Fractional

◆ Index

◆ KahanSum

◆ RowIndexVector

◆ RowMajorSparseMatrix

◆ RowMapping

◆ RowPermutation

◆ RowToColMapping

◆ ScatteredColumnIterator

◆ ScatteredRowIterator

◆ SparseColumnIterator

◆ SparseRowIterator

◆ SumWithNegativeInfiniteAndOneMissing

◆ SumWithPositiveInfiniteAndOneMissing

◆ VariableStatusRow

◆ VariableTypeRow

Enumeration Type Documentation

◆ ConstraintStatus

◆ ProblemStatus

◆ VariableStatus

◆ VariableType

Function Documentation

◆ ABSL_DEPRECATED()

◆ ApplyColumnPermutationToRowIndexedVector() [1/2]

◆ ApplyColumnPermutationToRowIndexedVector() [2/2]

◆ ApplyInversePermutation()

◆ ApplyPermutation()

◆ AreBoundsValid()

◆ AreFirstColumnsAndRowsExactlyEquals()

◆ ChangeSign()

◆ ClearAndResizeVectorWithNonZeros()

◆ ColToIntIndex()

◆ ColToRowIndex()

◆ ComputeNonZeros()

◆ ComputeSlackVariablesValues()

◆ DEFINE_STRONG_INDEX_TYPE() [1/2]

◆ DEFINE_STRONG_INDEX_TYPE() [2/2]

◆ DEFINE_STRONG_INT64_TYPE()

◆ Density()

◆ DeterministicTimeForFpOperations()

◆ FindProportionalColumns()

◆ FindProportionalColumnsUsingSimpleAlgorithm()

◆ FixConstraintWithFixedStatuses()

◆ Fractionality()

◆ GetConstraintStatusString()

◆ GetErrorCodeString()

◆ GetProblemStatusString()

◆ GetVariableStatusString()

◆ GetVariableTypeString()

◆ InfinityNorm() [1/3]

◆ InfinityNorm() [2/3]

◆ InfinityNorm() [3/3]

◆ InfinityNormTemplate()

◆ IsAllFalse()

◆ IsAllZero()

◆ IsDominated()

◆ IsFinite()

◆ IsRightMostSquareMatrixIdentity()

◆ kInvalidCol()

◆ kInvalidRow()

◆ kNonPivotal()

◆ LinearProgramToMPModelProto()