Algorithmic Classes

Implementation of numerical algorithms. More...

Classes
class	CLUFactor< R >
	Implementation of sparse LU factorization.This class implements a sparse LU factorization with either FOREST-TOMLIN or ETA updates, using dynamic Markowitz pivoting. More...
class	CLUFactorRational
	Implementation of sparse LU factorization with Rational precision.This class implements a sparse LU factorization with either FOREST-TOMLIN or ETA updates, using dynamic Markowitz pivoting. More...
class	LPColBase< R >
	LP column.Class LPColBase provides a datatype for storing the column of an LP a the form similar to \[ \begin{array}{rl} \hbox{max} & c^T x \\ \hbox{s.t.} & Ax \le b \\ & l \le x \le u \end{array} \] Hence, an LPColBase consists of an objective value, a column DSVector and an upper and lower bound to the corresponding variable, which may include \(\pm\infty\). However, it depends on the LP code to use, what values are actually treated as \(\infty\). More...
class	LPRowBase< R >
	(In)equality for LPs.Class LPRowBase provides constraints for linear programs in the form \[ l \le a^Tx \le r, \] where a is a DSVector. l is referred to as left hand side, r as right hand side and a as row vector or the constraint vector. l and r may also take values \(\pm\) #R(infinity). This static member is predefined, but may be overridden to meet the needs of the LP solver to be used. More...
class	SLinSolver< R >
	Sparse Linear Solver virtual base class.Class SLinSolver provides a class for solving sparse linear systems with a matrix \(A\) and arbitrary right-hand side vectors. For doing so, the matrix must be first loaded to an SLinSolver object as an array of pointers to the column SVectors of this matrix. More...
class	SLinSolverRational
	Sparse Linear Solver virtual base class with Rational precision.Class SLinSolverRational provides a class for solving sparse linear systems with a matrix \(A\) and arbitrary right-hand side vectors. For doing so, the matrix must be first loaded to an SLinSolverRational object as an array of pointers to the column SVectorsRational of this matrix. More...
class	SLUFactor< R >
	Implementation of Sparse Linear Solver.This class implements a SLinSolver interface by using the sparse LU factorization implemented in CLUFactor. More...
class	SLUFactorRational
	Implementation of Sparse Linear Solver with Rational precision.This class implements a SLinSolverRational interface by using the sparse LU factorization implemented in CLUFactorRational. More...
class	SPxAutoPR< R >
	Auto pricer.This pricer switches between Devex and Steepest edge pricer based on the difficulty of the problem which is determined by the number of iterations. More...
class	SPxBoundFlippingRT< R >
	Bound flipping ratio test ("long step dual") for SoPlex.Class SPxBoundFlippingRT provides an implementation of the bound flipping ratio test as a derived class of SPxRatioTester. Dual step length is increased beyond some breakpoints and corresponding primal nonbasic variables are set to their other bound to handle the resulting dual infeasibility. More...
class	SPxDantzigPR< R >
	Dantzig pricer.Class SPxDantzigPR is an implementation class of an SPxPricer implementing Dantzig's default pricing strategy, i.e., maximal/minimal reduced cost or maximally violated constraint. More...
class	SPxDefaultRT< R >
	Textbook ratio test for SoPlex.Class SPxDefaultRT provides an implementation of the textbook ratio test as a derived class of SPxRatioTester. This class is not intended for reliably solving LPs (even though it does the job for ``numerically simple'' LPs). Instead, it should serve as a demonstration of how to write ratio tester classes. More...
class	SPxDevexPR< R >
	Devex pricer.The Devex Pricer for SoPlex implements an approximate steepest edge pricing, that does without solving an extra linear system and computing the scalar products. More...
class	SPxEquiliSC< R >
	Equilibrium row/column scaling.This SPxScaler implementation performs equilibrium scaling of the LPs rows and columns. More...
class	SPxFastRT< R >
	Fast shifting ratio test.Class SPxFastRT is an implementation class of SPxRatioTester providing fast and stable ratio test. Stability is achieved by allowing some infeasibility to ensure numerical stability such as the Harris procedure. Performance is achieved by skipping the second phase if the first phase already shows a stable enough pivot. More...
class	SPxGeometSC< R >
	Geometric mean row/column scaling.This SPxScaler implementation performs geometric mean scaling of the LPs rows and columns. More...
class	SPxHarrisRT< R >
	Harris pricing with shifting.Class SPxHarrisRT is a stable implementation of a SPxRatioTester class along the lines of Harris' two phase algorithm. Additionally it uses shifting of bounds in order to avoid cycling. More...
class	SPxHybridPR< R >
	Hybrid pricer.The hybrid pricer for SoPlex tries to guess the best pricing strategy to use for pricing the loaded LP with the loaded algorithm type and basis representation. Currently it does so by switching between SPxSteepPR, SPxDevexPR and SPxParMultPR. More...
class	SPxColId
	Ids for LP columns.Class SPxColId provides DataKeys for the column indices of an SPxLP. More...
class	SPxRowId
	Ids for LP rows.Class SPxRowId provides DataKeys for the row indices of an SPxLP. More...
class	SPxId
	Generic Ids for LP rows or columns.Both SPxColIds and SPxRowIds may be treated uniformly as SPxIds: More...
class	SPxLeastSqSC< R >
	Least squares scaling.This SPxScaler implementation performs least squares scaling as suggested by Curtis and Reid in: On the Automatic Scaling of Matrices for Gaussian Elimination (1972). More...
class	SPxLPBase< R >
	Saving LPs in a form suitable for SoPlex.Class SPxLPBase provides the data structures required for saving a linear program in the form \[ \begin{array}{rl} \hbox{max} & c^T x \\ \hbox{s.t.} & l_r \le Ax \le u_r \\ & l_c \le x \le u_c \end{array} \] suitable for solving with SoPlex. This includes: More...
class	SPxMainSM< R >::PostStep
	Base class for postsolving operations.Class PostStep is an abstract base class providing the interface for operations in the postsolving process. More...
class	SPxMainSM< R >::RowObjPS
	Postsolves row objectives. More...
class	SPxMainSM< R >::FreeConstraintPS
	Postsolves unconstraint constraints. More...
class	SPxMainSM< R >::EmptyConstraintPS
	Postsolves empty constraints. More...
class	SPxMainSM< R >::RowSingletonPS
	Postsolves row singletons. More...
class	SPxMainSM< R >::ForceConstraintPS
	Postsolves forcing constraints. More...
class	SPxMainSM< R >::FixVariablePS
	Postsolves variable fixing. More...
class	SPxMainSM< R >::FixBoundsPS
	Postsolves variable bound fixing. More...
class	SPxMainSM< R >::FreeZeroObjVariablePS
	Postsolves the case when constraints are removed due to a variable with zero objective that is free in one direction. More...
class	SPxMainSM< R >::ZeroObjColSingletonPS
	Postsolves column singletons with zero objective. More...
class	SPxMainSM< R >::FreeColSingletonPS
	Postsolves free column singletons. More...
class	SPxMainSM< R >::DoubletonEquationPS
	Postsolves doubleton equations combined with a column singleton. More...
class	SPxMainSM< R >::DuplicateRowsPS
	Postsolves duplicate rows. More...
class	SPxMainSM< R >::DuplicateColsPS
	Postsolves duplicate columns. More...
class	SPxMainSM< R >::AggregationPS
	Postsolves aggregation. More...
class	SPxMainSM< R >::MultiAggregationPS
	Postsolves multi aggregation. More...
class	SPxMainSM< R >::TightenBoundsPS
	Postsolves variable bound tightening from pseudo objective propagation. More...
class	SPxMainSM< R >
	LP simplifier for removing uneccessary row/columns.This SPxSimplifier is mainly based on the paper "Presolving in linear programming" by E. Andersen and K. Andersen (Mathematical Programming, 1995). It implements all proposed methods and some other preprocessing techniques for removing redundant rows and columns and bounds. Also infeasibility and unboundedness may be detected. More...
class	SPxParMultPR< R >
	Partial multiple pricing.Class SPxParMultPr is an implementation class for SPxPricer implementing Dantzig's default pricing strategy with partial multiple pricing. Partial multiple pricing applies to the entering Simplex only. A set of partialSize eligible pivot indices is selected (partial pricing). In the following Simplex iterations pricing is restricted to these indices (multiple pricing) until no more eliiable pivots are available. Partial multiple pricing significantly reduces the computation time for computing the matrix-vector-product in the Simplex algorithm. More...
class	SPxPricer< R >
	Abstract pricer base class.Class SPxPricer is a pure virtual class defining the interface for pricer classes to be used by SoPlex. The pricer's task is to select a vector to enter or leave the simplex basis, depending on the chosen simplex type. More...
class	SPxRatioTester< R >
	Abstract ratio test base class.Class SPxRatioTester is the virtual base class for computing the ratio test within the Simplex algorithm driven by SoPlex. After a SoPlex solver has been load()ed to an SPxRatioTester, the solver calls selectLeave() for computing the ratio test for the entering simplex and selectEnter() for computing the ratio test in leaving simplex. More...
class	SPxScaler< R >
	LP scaler abstract base class.Instances of classes derived from SPxScaler may be loaded to SoPlex in order to scale LPs before solving them. SoPlex will load() itself to the SPxScaler and then call scale(). Generally any SPxLP can be loaded to a SPxScaler for scale()ing it. The scaling can be undone by calling unscale(). More...
class	SPxSimplifier< R >
	LP simplification abstract base class.Instances of classes derived from SPxSimplifier may be loaded to SoPlex in order to simplify LPs before solving them. SoPlex will call simplify() on itself. Generally any SPxLP can be given to a SPxSimplifier for simplify()ing it. The simplification cannot be undone, but given an primal/dual solution for the simplified SPxLP, the simplifier can reconstruct the primal/dual solution of the unsimplified LP. More...
class	SPxSolverBase< R >
	Sequential object-oriented SimPlex.SPxSolverBase is an LP solver class using the revised Simplex algorithm. It provides two basis representations, namely a column basis and a row basis (see Representation). For both representations, a primal and dual algorithm is available (see Type). More...
class	SPxStarter< R >
	SoPlex start basis generation base class.SPxStarter is the virtual base class for classes generating a starter basis for the Simplex solver SoPlex. When a SPxStarter object has been loaded to a SoPlex solver, the latter will call method generate() in order to have a start basis generated. Implementations of method generate() must terminate by loading the generated basis to SoPlex. Loaded bases must be nonsingular. More...
class	SPxSteepExPR< R >
	Steepest edge pricer.Class SPxSteepExPR implements a steepest edge pricer to be used with SoPlex. Exact initialization of weights is used. More...
class	SPxSteepPR< R >
	Steepest edge pricer.Class SPxSteepPR implements a steepest edge pricer to be used with SoPlex. More...
class	SPxSumST< R >
	Simple heuristic SPxStarter.Testing version of an SPxVectorST using a very simplistic heuristic to build up an approximated solution vector. More...
class	SPxVectorST< R >
	Solution vector based start basis.This version of SPxWeightST can be used to construct a starting basis for an LP to be solved with SoPlex if an approximate solution vector or dual vector (possibly optained by a heuristic) is available. This is done by setting up weights for the SPxWeightST it is derived from. More...
class	SPxWeightPR< R >
	Weighted pricing.Class SPxWeightPR is an implemantation class of SPxPricer that uses weights for columns and rows for selecting the Simplex pivots. The weights are computed by methods computeCP() and computeRP() which may be overridden by derived classes. More...
class	SPxWeightST< R >
	Weighted start basis.Class SPxWeightST is an implementation of a SPxStarter for generating a Simplex starting basis. Using method setupWeights() it sets up arrays weight and coWeight, or equivalently rowWeight and colWeight. (rowWeight and colWeight are just pointers initialized to weight and coWeight according to the representation of SoPlex base passed to method generate().) More...
class	SolBase< R >
	Class for storing a primal-dual solution with basis information. More...
class	SPxBasisBase< R >
	Simplex basis.Consider the linear program as provided from class SPxLP: \[ \begin{array}{rl} \hbox{max} & c^T x \\ \hbox{s.t.} & l_r \le Ax \le u_r \\ & l_c \le x \le u_c \end{array} \] where \(c, l_c, u_c, x \in {\bf R}^n\), \(l_r, u_r \in {\bf R}^m\) and \(A \in {\bf R}^{m \times n}\). Solving this LP with the simplex algorithm requires the definition of a basis. Such can be defined as a set of column vectors or a set of row vectors building a non-singular matrix. We will refer to the first case as the columnwise representation and the latter case will be called the rowwise representation. In both cases, a basis is a set of vectors forming a non-singular matrix. The dimension of the vectors is referred to as the basis' dimension, whereas the number of vectors belonging to the LP is called the basis' codimension. More...
class	Statistics
	Class for collecting statistical information. More...
class	SoPlex
	Preconfigured SoPlex LP-solver. More...

Detailed Description

Implementation of numerical algorithms.

Algorithmic classes serve for implementing a variety of algorithms for solving numerical (sub-)problems.