Scippy

SoPlex

Sequential object-oriented simPlex

Algorithmic Classes

Implementation of numerical algorithms. More...

Classes

class  CLUFactor
 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\) infinity. This static member is predefined, but may be overridden to meet the needs of the LP solver to be used. More...

 
class  SLinSolver
 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
 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
 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
 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
 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
 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
 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
 Equilibrium row/column scaling.This SPxScaler implementation performs equilibrium scaling of the LPs rows and columns. More...
 
class  SPxFastRT
 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
 Geometric mean row/column scaling.This SPxScaler implementation performs geometric mean scaling of the LPs rows and columns. More...
 
class  SPxHarrisRT
 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
 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
 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::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::RowObjPS
 Postsolves row objectives. More...
 
class  SPxMainSM::FreeConstraintPS
 Postsolves unconstraint constraints. More...
 
class  SPxMainSM::EmptyConstraintPS
 Postsolves empty constraints. More...
 
class  SPxMainSM::RowSingletonPS
 Postsolves row singletons. More...
 
class  SPxMainSM::ForceConstraintPS
 Postsolves forcing constraints. More...
 
class  SPxMainSM::FixVariablePS
 Postsolves variable fixing. More...
 
class  SPxMainSM::FixBoundsPS
 Postsolves variable bound fixing. More...
 
class  SPxMainSM::FreeZeroObjVariablePS
 Postsolves the case when constraints are removed due to a variable with zero objective that is free in one direction. More...
 
class  SPxMainSM::ZeroObjColSingletonPS
 Postsolves column singletons with zero objective. More...
 
class  SPxMainSM::FreeColSingletonPS
 Postsolves free column singletons. More...
 
class  SPxMainSM::DoubletonEquationPS
 Postsolves doubleton equations combined with a column singleton. More...
 
class  SPxMainSM::DuplicateRowsPS
 Postsolves duplicate rows. More...
 
class  SPxMainSM::DuplicateColsPS
 Postsolves duplicate columns. More...
 
class  SPxMainSM::AggregationPS
 Postsolves aggregation. More...
 
class  SPxMainSM::MultiAggregationPS
 Postsolves multi aggregation. More...
 
class  SPxMainSM::TightenBoundsPS
 Postsolves variable bound tightening from pseudo objective propagation. More...
 
class  SPxMainSM
 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
 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
 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
 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
 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
 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  SPxSolver
 Sequential object-oriented SimPlex.SPxSolver 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
 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
 Steepest edge pricer.Class SPxSteepExPR implements a steepest edge pricer to be used with SoPlex. Exact initialization of weights is used. More...
 
class  SPxSteepPR
 Steepest edge pricer.Class SPxSteepPR implements a steepest edge pricer to be used with SoPlex. More...
 
class  SPxSumST
 Simple heuristic SPxStarter.Testing version of an SPxVectorST using a very simplistic heuristic to build up an approximated solution vector. More...
 
class  SPxVectorST
 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
 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
 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  SPxBasis
 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.