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
struct	ParsedConstraint
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)
StatusOr< ParsedConstraint >	ParseConstraint (absl::string_view constraint)
bool	ParseLp (absl::string_view model, LinearProgram *lp)
	Like ModelProtoFromLpFormat(), but outputs a glop::LinearProgram.
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	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)
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 (StrictITISpan< ColIndex, const 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)
template<typename Container>
BeginEndReverseIteratorWrapper< Container >	Reverse (const Container &c)
template<typename Container>
BeginEndReverseIteratorWrapper< Container >	Reverse (const Container &c)

Variables
	e_
constexpr const uint64_t	kDeterministicSeed = 42
constexpr Fractional	kRangeMax = std::numeric_limits<Fractional>::max()
	Range max for type Fractional. DBL_MAX for double for example.
constexpr Fractional	kInfinity = std::numeric_limits<Fractional>::infinity()
	Infinity for type Fractional.
constexpr Fractional	kEpsilon = std::numeric_limits<Fractional>::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 360 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 357 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 366 of file lp_types.h.

◆ ColumnPermutation

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

Definition at line 106 of file permutation.h.

◆ ConstraintStatusColumn

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

Column of constraints (slack variables) statuses.

Definition at line 397 of file lp_types.h.

◆ DenseBitColumn

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

Column of bits.

Definition at line 386 of file lp_types.h.

◆ DenseBitRow

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

Row of bits.

Definition at line 375 of file lp_types.h.

◆ DenseBooleanColumn

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

Column of booleans.

Definition at line 383 of file lp_types.h.

◆ DenseBooleanRow

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

Row of booleans.

Definition at line 354 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 380 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 351 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 81 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 361 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 389 of file lp_types.h.

◆ RowPermutation

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

Definition at line 105 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 394 of file lp_types.h.

◆ ScatteredColumnIterator

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

Definition at line 194 of file scattered_vector.h.

◆ ScatteredRowIterator

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

Definition at line 195 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 396 of file lp_utils.h.

◆ SumWithPositiveInfiniteAndOneMissing

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

Definition at line 395 of file lp_utils.h.

◆ VariableStatusRow

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

Row of variable statuses.

Definition at line 372 of file lp_types.h.

◆ VariableTypeRow

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

Row of variable types.

Definition at line 369 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 234 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 105 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 200 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 178 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()

template<typename RowIndexedVector>

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

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

Empty size means identity.

Permute into tmp and swap.

Definition at line 127 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 237 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 218 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 312 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 290 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 32 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()

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 433 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 3400 of file preprocessor.cc.

◆ Fractionality()

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 94 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 245 of file lp_types.h.

◆ operator<<() [2/4]

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

inline

Definition at line 172 of file lp_types.h.

◆ operator<<() [3/4]

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

inline

Definition at line 223 of file lp_types.h.

◆ operator<<() [4/4]

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

inline

Definition at line 189 of file lp_types.h.

◆ ParseConstraint()

absl::StatusOr< ParsedConstraint > operations_research::glop::ParseConstraint ( absl::string_view constraint )

Parses a constraint in the format used by LinearProgram::Dump(). Returns an InvalidArgumentError with an appropriate error message when the parsing fails.

Get the name, if present.

Get the left bound and the relation sign, if present.

Get the addands, if present.

If the left sign was EQ there can be no right side.

Get the right sign and the right bound, if present.

If the right sign is EQ, there can be no left side.

There was no constraint!

Calculate bounds to set.

Definition at line 365 of file lp_parser.cc.

◆ ParseLp()

ABSL_MUST_USE_RESULT bool operations_research::glop::ParseLp	(	absl::string_view	model,
		LinearProgram *	lp )

Like ModelProtoFromLpFormat(), but outputs a glop::LinearProgram.

Definition at line 465 of file lp_parser.cc.

◆ 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 271 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.

Caching the pointers help.

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.

◆ Reverse() [1/2]

template<typename Container>

BeginEndReverseIteratorWrapper< Container > util::Reverse ( const Container & c )

Definition at line 115 of file iterators.h.

◆ Reverse() [2/2]

template<typename Container>

BeginEndReverseIteratorWrapper< Container > util::Reverse ( const Container & c )

Definition at line 115 of file iterators.h.

◆ 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 65 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 73 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/3]

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

inline

Definition at line 35 of file lp_print_utils.h.

◆ Stringify() [2/3]

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/3]

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.

◆ 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()

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

inlinestatic

Definition at line 74 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 201 of file scattered_vector.h.

◆ TransposedView() [2/2]

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

inline

Definition at line 204 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 96 of file revised_simplex.cc.

◆ kEpsilon

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

constexpr

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

Definition at line 90 of file lp_types.h.

◆ kInfinity

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

constexpr

Infinity for type Fractional.

Definition at line 87 of file lp_types.h.

◆ kRangeMax

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

constexpr

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

Definition at line 84 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()

◆ 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()

◆ LoadLinearProgramFromModelOrRequest()