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

#include <spxbasis.h>

Classes
class	Desc
	Basis descriptor. More...

Public Types
enum	SPxStatus { NO_PROBLEM = -2, SINGULAR = -1, REGULAR = 0, DUAL = 1, PRIMAL = 2, OPTIMAL = 3, UNBOUNDED = 4, INFEASIBLE = 5 }
	basis status. More...

Public Member Functions
Status and Descriptor related Methods
SPxStatus	status () const
	returns current SPxStatus. More...

void	setStatus (SPxStatus stat)
	sets basis SPxStatus to `stat`. More...

void	setMaxUpdates (int maxUp)
	change maximum number of iterations until a refactorization is performed More...

int	getMaxUpdates () const
	returns maximum number of updates before a refactorization is performed More...

const Desc &	desc () const

Desc &	desc ()
	returns current basis Descriptor. More...

Desc::Status	dualColStatus (int i) const
	dual Status for the `i'th` column variable of the loaded LP. More...

Desc::Status	dualStatus (const SPxColId &id) const
	dual Status for the column variable with ID `id` of the loaded LP. More...

Desc::Status	dualRowStatus (int i) const
	dual Status for the `i'th` row variable of the loaded LP. More...

Desc::Status	dualStatus (const SPxRowId &id) const
	dual Status for the row variable with ID `id` of the loaded LP. More...

Desc::Status	dualStatus (const SPxId &id) const
	dual Status for the variable with ID `id` of the loaded LP. More...

Inquiry Methods
SPxId &	baseId (int i)

SPxId	baseId (int i) const
	returns the Id of the `i'th` basis vector. More...

const SVectorBase< R > &	baseVec (int i) const
	returns the `i'th` basic vector. More...

SPxId	lastEntered () const
	returns SPxId of last VectorBase<R> included to the basis. More...

SPxId	lastLeft () const
	returns SPxId of last vector that left the basis. More...

int	lastIndex () const
	returns index in basis where last update was done. More...

int	lastUpdate () const
	returns number of basis changes since last refactorization. More...

int	iteration () const
	returns number of basis changes since last load(). More...

int	prevIteration () const
	returns the number of iterations prior to the last break in execution More...

int	lastDegenCheck () const
	returns the number of iterations since the last degeneracy check More...

SPxSolverBase< R > *	solver () const
	returns loaded solver. More...

Linear Algebra
VectorBase< R > &	multBaseWith (VectorBase< R > &x) const
	Basis-vector product. More...

void	multBaseWith (SSVectorBase< R > &x, SSVectorBase< R > &result) const
	Basis-vector product. More...

VectorBase< R > &	multWithBase (VectorBase< R > &x) const
	Vector-basis product. More...

void	multWithBase (SSVectorBase< R > &x, SSVectorBase< R > &result) const
	VectorBase<R>-basis product. More...

R	condition (int maxiters=10, R tolerance=1e-6)

R	getEstimatedCondition ()

R	getExactCondition ()

R	getMatrixMetric (int type=0)

R	stability () const
	returns the stability of the basis matrix. More...

void	solve (VectorBase< R > &x, const VectorBase< R > &rhs)

void	solve (SSVectorBase< R > &x, const SVectorBase< R > &rhs)

void	solve4update (SSVectorBase< R > &x, const SVectorBase< R > &rhs)
	solves linear system with basis matrix. More...

void	solve4update (SSVectorBase< R > &x, VectorBase< R > &y, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy)
	solves two systems in one call. More...

void	solve4update (SSVectorBase< R > &x, SSVectorBase< R > &y, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy)
	solves two systems in one call using only sparse data structures More...

void	solve4update (SSVectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &y2, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy, SSVectorBase< R > &rhsy2)
	solves three systems in one call. More...

void	solve4update (SSVectorBase< R > &x, SSVectorBase< R > &y, SSVectorBase< R > &y2, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy, SSVectorBase< R > &rhsy2)
	solves three systems in one call using only sparse data structures More...

void	coSolve (VectorBase< R > &x, const VectorBase< R > &rhs)
	Cosolves linear system with basis matrix. More...

void	coSolve (SSVectorBase< R > &x, const SVectorBase< R > &rhs)
	Sparse version of coSolve. More...

void	coSolve (SSVectorBase< R > &x, VectorBase< R > &y, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy)
	solves two systems in one call. More...

void	coSolve (SSVectorBase< R > &x, SSVectorBase< R > &y, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy)
	Sparse version of solving two systems in one call. More...

void	coSolve (SSVectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &z, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy, SSVectorBase< R > &rhsz)
	solves three systems in one call. May be improved by using just one pass through the basis. More...

void	coSolve (SSVectorBase< R > &x, SSVectorBase< R > &y, SSVectorBase< R > &z, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy, SSVectorBase< R > &rhsz)
	Sparse version of solving three systems in one call. More...

Modification notification.
These methods must be called after the loaded LP has been modified.
void	addedRows (int n)
	inform SPxBasisBase, that `n` new rows had been added. More...

void	removedRow (int i)
	inform SPxBasisBase that row `i` had been removed. More...

void	removedRows (const int perm[])
	inform SPxBasisBase that rows in `perm` with negative entry were removed. More...

void	addedCols (int n)
	inform SPxBasisBase that `n` new columns had been added. More...

void	removedCol (int i)
	inform SPxBasisBase that column `i` had been removed. More...

void	removedCols (const int perm[])
	inform SPxBasisBase that columns in `perm` with negative entry were removed. More...

void	changedRow (int)
	inform SPxBasisBase that a row had been changed. More...

void	changedCol (int)
	inform SPxBasisBase that a column had been changed. More...

void	changedElement (int, int)
	inform SPxBasisBase that a matrix entry had been changed. More...

Miscellaneous
virtual void	change (int i, SPxId &id, const SVectorBase< R > enterVec, const SSVectorBase< R > eta=0)
	performs basis update. More...

virtual bool	readBasis (std::istream &in, const NameSet rowNames, const NameSet colNames)

virtual void	writeBasis (std::ostream &os, const NameSet rownames, const NameSet colnames, const bool cpxFormat=false) const

virtual void	printMatrix () const

void	printMatrixMTX (int number)

virtual bool	isDescValid (const Desc &ds)
	checks if a Descriptor is valid for the current LP w.r.t. its bounds More...

virtual void	loadDesc (const Desc &)
	sets up basis. More...

virtual void	loadBasisSolver (SLinSolver< R > *solver, const bool destroy=false)
	sets up linear solver to use. More...

virtual void	load (SPxSolverBase< R > *lp, bool initSlackBasis=true)
	loads the LP `lp` to the basis. More...

virtual void	unLoad ()
	unloads the LP from the basis. More...

void	invalidate ()
	invalidates actual basis. More...

void	restoreInitialBasis ()
	Restores initial basis. More...

void	dump ()
	output basis entries. More...

bool	isConsistent () const
	consistency check. More...

Real	getTotalUpdateTime () const
	time spent in updates More...

int	getTotalUpdateCount () const
	number of updates performed More...

std::string	statistics () const
	returns statistical information in form of a string. More...

void	setOutstream (SPxOut &newOutstream)

Constructors / Destructors
	SPxBasisBase (Timer::TYPE ttype=Timer::USER_TIME)
	default constructor. More...

	SPxBasisBase (const SPxBasisBase< R > &old)
	copy constructor More...

SPxBasisBase< R > &	operator= (const SPxBasisBase< R > &rhs)
	assignment operator More...

virtual	~SPxBasisBase ()
	destructor. More...

Protected Member Functions
Protected helpers
void	loadMatrixVecs ()
	loads matrix according to the SPxIds stored in theBaseId. More...

void	reDim ()
	resizes internal arrays. More...

virtual void	factorize ()
	factorizes the basis matrix. More...

void	setRep ()
	sets descriptor representation according to loaded LP. More...

Protected Attributes

SPxSolverBase< R > *	theLP
	the LP More...

DataArray< SPxId >	theBaseId
	SPxIds of basic vectors. More...

DataArray< const SVectorBase< R > *>	matrix
	pointers to the vectors of the basis matrix. More...

bool	matrixIsSetup
	`true` iff the pointers in matrix are set up correctly. More...

SLinSolver< R > *	factor

bool	factorized
	`true` iff factor = matrix \(^{-1}\). More...

int	maxUpdates
	number of updates before refactorization. More...

R	nonzeroFactor
	allowed increase of nonzeros before refactorization. More...

R	fillFactor
	allowed increase in relative fill before refactorization More...

R	memFactor
	allowed total increase in memory consumption before refactorization More...

int	iterCount
	number of calls to change() since last manipulation More...

int	lastIterCount
	number of calls to change() before halting the simplex More...

int	iterDegenCheck
	number of calls to change() since last degeneracy check More...

int	updateCount
	number of calls to change() since last factorize() More...

int	totalUpdateCount
	number of updates More...

int	nzCount
	number of nonzeros in basis matrix More...

int	lastMem
	memory needed after last fresh factorization More...

R	lastFill
	fill ratio that occured during last factorization More...

int	lastNzCount
	number of nonzeros in basis matrix after last fresh factorization More...

Timer *	theTime
	time spent in updates More...

Timer::TYPE	timerType
	type of timer (user or wallclock) More...

SPxId	lastin
	lastEntered(): variable entered the base last More...

SPxId	lastout
	lastLeft(): variable left the base last More...

int	lastidx
	lastIndex(): basis index where last update was done More...

R	minStab
	minimum stability More...

Private Attributes

SPxStatus	thestatus
	current status of the basis. More...

Desc	thedesc
	the basis' Descriptor More...

bool	freeSlinSolver
	true iff factor should be freed inside of this object More...

SPxOut *	spxout
	message handler More...

Detailed Description

template<class R>
class soplex::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.

Class SPxBasisBase is designed to represent a generic simplex basis, suitable for both representations. At any time the representation can be changed by calling method setRep().

Class SPxBasisBase provides methods for solving linear systems with the basis matrix. However, SPxBasisBase does not provide a linear solver by its own. Instead, a SLinSolver object must be loaded to a SPxBasisBase which will be called for solving linear systems.

Definition at line 84 of file spxbasis.h.

Member Enumeration Documentation

◆ SPxStatus

enum SPxStatus

basis status.

Each SPxBasisBase is assigned a status flag, which can take on of the above values.

Enumerator
NO_PROBLEM	No Problem has been loaded to the basis.
SINGULAR	Basis is singular.
REGULAR	Basis is not known to be dual nor primal feasible.
DUAL	Basis is dual feasible.
PRIMAL	Basis is primal feasible.
OPTIMAL	Basis is optimal, i.e. dual and primal feasible.
UNBOUNDED	LP has been proven to be primal unbounded.
INFEASIBLE	LP has been proven to be primal infeasible.

Definition at line 92 of file spxbasis.h.

Constructor & Destructor Documentation

◆ SPxBasisBase() [1/2]

SPxBasisBase ( Timer::TYPE ttype = Timer::USER_TIME )

default constructor.

◆ SPxBasisBase() [2/2]

SPxBasisBase ( const SPxBasisBase< R > & old )

copy constructor

◆ ~SPxBasisBase()

virtual ~SPxBasisBase ( )

virtual

destructor.

Member Function Documentation

◆ addedCols()

void addedCols ( int n )

inform SPxBasisBase that n new columns had been added.

Referenced by SPxBasisBase< R >::coSolve().

◆ addedRows()

void addedRows ( int n )

inform SPxBasisBase, that n new rows had been added.

Referenced by SPxBasisBase< R >::coSolve().

◆ baseId() [1/2]

SPxId& baseId ( int i )

Definition at line 507 of file spxbasis.h.

◆ baseId() [2/2]

SPxId baseId ( int i ) const

returns the Id of the i'th basis vector.

Definition at line 512 of file spxbasis.h.

◆ baseVec()

const SVectorBase<R>& baseVec ( int i ) const

returns the i'th basic vector.

Definition at line 518 of file spxbasis.h.

◆ change()

virtual void change	(	int	i,
		SPxId &	id,
		const SVectorBase< R > *	enterVec,
		const SSVectorBase< R > *	eta = `0`
	)

virtual

performs basis update.

Changes the i 'th vector of the basis with the vector associated to id. This includes:

updating the factorization, or recomputing it from scratch by calling factorize(),
resetting lastEntered(),
resetting lastIndex(),
resetting lastLeft(),
resetting lastUpdate(),
resetting iterations().

The basis descriptor is not modified, since factor() cannot know about how to set up the status of the involved variables correctly.

A vector enterVec may be passed for a fast ETA update of the LU factorization associated to the basis. It must be initialized with the solution vector \(x\) of the right linear system \(Bx = b\) with the entering vector as right-hand side vector \(b\), where \(B\) denotes the basis matrix. This can be computed using method solve(). When using FAST updates, a vector eta may be passed for improved performance. It must be initialized by a call to factor->solveRightUpdate() as described in SLinSolver. The implementation hidden behind FAST updates depends on the SLinSolver implementation class.

Referenced by SPxBasisBase< R >::coSolve().

◆ changedCol()

void changedCol ( int )

inform SPxBasisBase that a column had been changed.

Referenced by SPxBasisBase< R >::coSolve().

◆ changedElement()

void changedElement	(	int	,
		int
	)

inform SPxBasisBase that a matrix entry had been changed.

Referenced by SPxBasisBase< R >::coSolve().

◆ changedRow()

void changedRow ( int )

inform SPxBasisBase that a row had been changed.

Referenced by SPxBasisBase< R >::coSolve().

◆ condition()

R condition	(	int	maxiters = `10`,
		R	tolerance = `1e-6`
	)

Referenced by SPxBasisBase< R >::getEstimatedCondition(), SPxBasisBase< R >::getExactCondition(), and SPxBasisBase< R >::solver().

◆ coSolve() [1/6]

void coSolve	(	VectorBase< R > &	x,
		const VectorBase< R > &	rhs
	)

Cosolves linear system with basis matrix.

Depending on the representation, for a SPxBasisBase B, B.coSolve(x) computes

\(x \leftarrow rhs^TB^{-1}\) in the columnwise case and
\(x \leftarrow B^{-1}rhs\) in the rowwise case.

Both can be seen uniformly as solving a linear system with the basis matrix B and a right handside vector x aligned the same way as the covectors of B.

Definition at line 735 of file spxbasis.h.

References VectorBase< R >::clear(), VectorBase< R >::dim(), SPxBasisBase< R >::factorize(), and SLinSolver< R >::solveLeft().

◆ coSolve() [2/6]

void coSolve	(	SSVectorBase< R > &	x,
		const SVectorBase< R > &	rhs
	)

Sparse version of coSolve.

Definition at line 749 of file spxbasis.h.

References SSVectorBase< R >::clear(), SPxBasisBase< R >::factorize(), SVectorBase< R >::size(), and SLinSolver< R >::solveLeft().

◆ coSolve() [3/6]

void coSolve	(	SSVectorBase< R > &	x,
		VectorBase< R > &	y,
		const SVectorBase< R > &	rhsx,
		SSVectorBase< R > &	rhsy
	)

solves two systems in one call.

Definition at line 763 of file spxbasis.h.

References SPxBasisBase< R >::factorize(), and SLinSolver< R >::solveLeft().

◆ coSolve() [4/6]

void coSolve	(	SSVectorBase< R > &	x,
		SSVectorBase< R > &	y,
		const SVectorBase< R > &	rhsx,
		SSVectorBase< R > &	rhsy
	)

Sparse version of solving two systems in one call.

Definition at line 772 of file spxbasis.h.

References SPxBasisBase< R >::factorize(), and SLinSolver< R >::solveLeft().

◆ coSolve() [5/6]

void coSolve	(	SSVectorBase< R > &	x,
		VectorBase< R > &	y,
		VectorBase< R > &	z,
		const SVectorBase< R > &	rhsx,
		SSVectorBase< R > &	rhsy,
		SSVectorBase< R > &	rhsz
	)

solves three systems in one call. May be improved by using just one pass through the basis.

Definition at line 781 of file spxbasis.h.

References SPxBasisBase< R >::factorize(), and SLinSolver< R >::solveLeft().

◆ coSolve() [6/6]

void coSolve	(	SSVectorBase< R > &	x,
		SSVectorBase< R > &	y,
		SSVectorBase< R > &	z,
		const SVectorBase< R > &	rhsx,
		SSVectorBase< R > &	rhsy,
		SSVectorBase< R > &	rhsz
	)

◆ desc() [1/2]

const Desc& desc ( ) const

Definition at line 467 of file spxbasis.h.

References SPxBasisBase< R >::thedesc.

◆ desc() [2/2]

Desc& desc ( )

returns current basis Descriptor.

Definition at line 472 of file spxbasis.h.

References SPxBasisBase< R >::dualColStatus(), SPxBasisBase< R >::dualRowStatus(), SPxBasisBase< R >::dualStatus(), and SPxBasisBase< R >::thedesc.

◆ dualColStatus()

Desc::Status dualColStatus ( int i ) const

dual Status for the i'th column variable of the loaded LP.

Referenced by SPxBasisBase< R >::desc().

◆ dualRowStatus()

Desc::Status dualRowStatus ( int i ) const

dual Status for the i'th row variable of the loaded LP.

Referenced by SPxBasisBase< R >::desc().

◆ dualStatus() [1/3]

Desc::Status dualStatus ( const SPxColId & id ) const

dual Status for the column variable with ID id of the loaded LP.

Referenced by SPxBasisBase< R >::desc(), and SPxBasisBase< R >::dualStatus().

◆ dualStatus() [2/3]

Desc::Status dualStatus ( const SPxRowId & id ) const

dual Status for the row variable with ID id of the loaded LP.

◆ dualStatus() [3/3]

Desc::Status dualStatus ( const SPxId & id ) const

dual Status for the variable with ID id of the loaded LP.

It is automatically detected, whether the id is one of a row or a column variable, and the correct row or column status is returned.

Definition at line 494 of file spxbasis.h.

References SPxBasisBase< R >::dualStatus().

◆ dump()

void dump ( )

output basis entries.

◆ factorize()

virtual void factorize ( )

protectedvirtual

factorizes the basis matrix.

Reimplemented in SPxSolverBase< R >.

Referenced by SPxBasisBase< R >::coSolve(), SPxBasisBase< R >::setOutstream(), SPxBasisBase< R >::solve(), and SPxBasisBase< R >::solve4update().

◆ getEstimatedCondition()

R getEstimatedCondition ( )

Definition at line 611 of file spxbasis.h.

References SPxBasisBase< R >::condition().

◆ getExactCondition()

R getExactCondition ( )

Definition at line 617 of file spxbasis.h.

References SPxBasisBase< R >::condition(), and SPxBasisBase< R >::getMatrixMetric().

◆ getMatrixMetric()

R getMatrixMetric ( int type = 0 )

compute one of several matrix metrics based on the diagonal of the LU factorization type = 0: max/min ratio type = 1: trace of U (sum of diagonal elements) type = 2: determinant (product of diagonal elements)

Referenced by SPxBasisBase< R >::getExactCondition().

◆ getMaxUpdates()

int getMaxUpdates ( ) const

returns maximum number of updates before a refactorization is performed

Definition at line 461 of file spxbasis.h.

References SPxBasisBase< R >::maxUpdates.

◆ getTotalUpdateCount()

int getTotalUpdateCount ( ) const

number of updates performed

Definition at line 932 of file spxbasis.h.

References SPxBasisBase< R >::totalUpdateCount.

Referenced by SPxBasisBase< R >::statistics().

◆ getTotalUpdateTime()

Real getTotalUpdateTime ( ) const

time spent in updates

Definition at line 927 of file spxbasis.h.

References Timer::time().

Referenced by SPxBasisBase< R >::statistics().

◆ invalidate()

void invalidate ( )

invalidates actual basis.

This method makes the basis matrix and vectors invalid. The basis will be reinitialized if needed.

Referenced by SPxBasisBase< R >::setStatus(), and SPxBasisBase< R >::unLoad().

◆ isConsistent()

bool isConsistent ( ) const

consistency check.

◆ isDescValid()

virtual bool isDescValid ( const Desc & ds )

virtual

checks if a Descriptor is valid for the current LP w.r.t. its bounds

Referenced by SPxBasisBase< R >::coSolve().

◆ iteration()

int iteration ( ) const

returns number of basis changes since last load().

Definition at line 549 of file spxbasis.h.

References SPxBasisBase< R >::iterCount.

◆ lastDegenCheck()

int lastDegenCheck ( ) const

returns the number of iterations since the last degeneracy check

Definition at line 561 of file spxbasis.h.

References SPxBasisBase< R >::iterDegenCheck.

◆ lastEntered()

SPxId lastEntered ( ) const

returns SPxId of last VectorBase<R> included to the basis.

Definition at line 525 of file spxbasis.h.

References SPxBasisBase< R >::lastin.

◆ lastIndex()

int lastIndex ( ) const

returns index in basis where last update was done.

Definition at line 537 of file spxbasis.h.

References SPxBasisBase< R >::lastidx.

◆ lastLeft()

SPxId lastLeft ( ) const

returns SPxId of last vector that left the basis.

Definition at line 531 of file spxbasis.h.

References SPxBasisBase< R >::lastout.

◆ lastUpdate()

int lastUpdate ( ) const

returns number of basis changes since last refactorization.

Definition at line 543 of file spxbasis.h.

References SPxBasisBase< R >::updateCount.

◆ load()

virtual void load	(	SPxSolverBase< R > *	lp,
		bool	initSlackBasis = `true`
	)

virtual

loads the LP lp to the basis.

This involves resetting all counters to 0 and setting up a regular default basis consisting of slacks, artificial variables or bounds.

Referenced by SPxBasisBase< R >::coSolve().

◆ loadBasisSolver()

virtual void loadBasisSolver	(	SLinSolver< R > *	solver,
		const bool	destroy = `false`
	)

virtual

sets up linear solver to use.

If destroy is true, solver will be freed inside this object, e.g. in the destructor.

Referenced by SPxBasisBase< R >::coSolve().

◆ loadDesc()

virtual void loadDesc ( const Desc & )

virtual

sets up basis.

Loads a Descriptor to the basis and sets up the basis matrix and all vectors accordingly. The Descriptor must have the same number of rows and columns as the currently loaded LP.

Referenced by SPxBasisBase< R >::coSolve().

◆ loadMatrixVecs()

void loadMatrixVecs ( )

protected

loads matrix according to the SPxIds stored in theBaseId.

This method must be called whenever there is a chance, that the vector pointers may have changed due to manipulations of the LP.

Referenced by SPxBasisBase< R >::setOutstream().

◆ multBaseWith() [1/2]

VectorBase<R>& multBaseWith ( VectorBase< R > & x ) const

Basis-vector product.

Depending on the representation, for an SPxBasisBase B, B.multBaseWith(x) computes

\(x \leftarrow Bx\) in the columnwise case, and
\(x \leftarrow x^TB\) in the rowwise case.

Both can be seen uniformly as multiplying the basis matrix B with a vector x aligned the same way as the vectors of B.

Referenced by SPxBasisBase< R >::solver().

◆ multBaseWith() [2/2]

void multBaseWith	(	SSVectorBase< R > &	x,
		SSVectorBase< R > &	result
	)		const

Basis-vector product.

◆ multWithBase() [1/2]

VectorBase<R>& multWithBase ( VectorBase< R > & x ) const

Vector-basis product.

Depending on the representation, for a SPxBasisBase B, B.multWithBase(x) computes

\(x \leftarrow x^TB\) in the columnwise case and
\(x \leftarrow Bx\) in the rowwise case.

Both can be seen uniformly as multiplying the basis matrix B with a vector x aligned the same way as the covectors of B.

Referenced by SPxBasisBase< R >::solver().

◆ multWithBase() [2/2]

void multWithBase	(	SSVectorBase< R > &	x,
		SSVectorBase< R > &	result
	)		const

VectorBase<R>-basis product.

◆ operator=()

SPxBasisBase<R>& operator= ( const SPxBasisBase< R > & rhs )

assignment operator

◆ prevIteration()

int prevIteration ( ) const

returns the number of iterations prior to the last break in execution

Definition at line 555 of file spxbasis.h.

References SPxBasisBase< R >::lastIterCount.

◆ printMatrix()

virtual void printMatrix ( ) const

virtual

Referenced by SPxBasisBase< R >::coSolve().

◆ printMatrixMTX()

void printMatrixMTX ( int number )

Prints current basis matrix to a file using the MatrixMarket format: row col value The filename is basis/basis[number].mtx where number is a parameter.

Referenced by SPxBasisBase< R >::coSolve().

◆ readBasis()

virtual bool readBasis	(	std::istream &	in,
		const NameSet *	rowNames,
		const NameSet *	colNames
	)

virtual

Load basis from in in MPS format. If rowNames and colNames are NULL, default names are used for the constraints and variables.

Referenced by SPxBasisBase< R >::coSolve().

◆ reDim()

void reDim ( )

protected

resizes internal arrays.

When a new LP is loaded, the basis matrix and vectors become invalid and possibly also of the wrong dimension. Hence, after loading an LP, reDim() is called to reset all arrays etc. accoriding to the dimensions of the loaded LP.

Referenced by SPxBasisBase< R >::setOutstream().

◆ removedCol()

void removedCol ( int i )

inform SPxBasisBase that column i had been removed.

Referenced by SPxBasisBase< R >::coSolve().

◆ removedCols()

void removedCols ( const int perm[] )

inform SPxBasisBase that columns in perm with negative entry were removed.

Referenced by SPxBasisBase< R >::coSolve().

◆ removedRow()

void removedRow ( int i )

inform SPxBasisBase that row i had been removed.

Referenced by SPxBasisBase< R >::coSolve().

◆ removedRows()

void removedRows ( const int perm[] )

inform SPxBasisBase that rows in perm with negative entry were removed.

Referenced by SPxBasisBase< R >::coSolve().

◆ restoreInitialBasis()

void restoreInitialBasis ( )

Restores initial basis.

This method changes the basis to that present just after loading the LP (see addedRows() and addedCols()). This may be necessary if a row or a column is changed, since then the current basis may become singular.

Referenced by SPxBasisBase< R >::unLoad().

◆ setMaxUpdates()

void setMaxUpdates ( int maxUp )

change maximum number of iterations until a refactorization is performed

Definition at line 454 of file spxbasis.h.

◆ setOutstream()

void setOutstream ( SPxOut & newOutstream )

Definition at line 951 of file spxbasis.h.

References SPxBasisBase< R >::factorize(), SPxBasisBase< R >::loadMatrixVecs(), SPxBasisBase< R >::Desc::operator<<, SPxBasisBase< R >::Desc::operator=(), SPxBasisBase< R >::reDim(), SPxBasisBase< R >::setRep(), SPxBasisBase< R >::Desc::status(), and Timer::USER_TIME.

◆ setRep()

void setRep ( )

protected

sets descriptor representation according to loaded LP.

Referenced by SPxBasisBase< R >::setOutstream().

◆ setStatus()

void setStatus ( SPxStatus stat )

sets basis SPxStatus to stat.

Definition at line 434 of file spxbasis.h.

References SPxBasisBase< R >::invalidate(), MSG_DEBUG, and SPxBasisBase< R >::NO_PROBLEM.

Referenced by SPxBasisBase< R >::unLoad().

◆ solve() [1/2]

void solve	(	VectorBase< R > &	x,
		const VectorBase< R > &	rhs
	)

Definition at line 635 of file spxbasis.h.

References VectorBase< R >::clear(), VectorBase< R >::dim(), SPxBasisBase< R >::factorize(), and SLinSolver< R >::solveRight().

◆ solve() [2/2]

void solve	(	SSVectorBase< R > &	x,
		const SVectorBase< R > &	rhs
	)

Definition at line 649 of file spxbasis.h.

References SSVectorBase< R >::clear(), SPxBasisBase< R >::factorize(), SVectorBase< R >::size(), and SLinSolver< R >::solveRight().

◆ solve4update() [1/5]

void solve4update	(	SSVectorBase< R > &	x,
		const SVectorBase< R > &	rhs
	)

solves linear system with basis matrix.

Depending on the representation, for a SPxBasisBase B, B.solve(x) computes

\(x \leftarrow B^{-1}rhs\) in the columnwise case and
\(x \leftarrow rhs^TB^{-1}\) in the rowwise case.

Both can be seen uniformly as solving a linear system with the basis matrix B and a right handside vector x aligned the same way as the vectors of B.

Definition at line 672 of file spxbasis.h.

References SSVectorBase< R >::clear(), SPxBasisBase< R >::factorize(), SVectorBase< R >::size(), and SLinSolver< R >::solveRight4update().

◆ solve4update() [2/5]

void solve4update	(	SSVectorBase< R > &	x,
		VectorBase< R > &	y,
		const SVectorBase< R > &	rhsx,
		SSVectorBase< R > &	rhsy
	)

solves two systems in one call.

Definition at line 686 of file spxbasis.h.

References SPxBasisBase< R >::factorize(), and SLinSolver< R >::solve2right4update().

◆ solve4update() [3/5]

void solve4update	(	SSVectorBase< R > &	x,
		SSVectorBase< R > &	y,
		const SVectorBase< R > &	rhsx,
		SSVectorBase< R > &	rhsy
	)

solves two systems in one call using only sparse data structures

Definition at line 695 of file spxbasis.h.

References SPxBasisBase< R >::factorize(), and SLinSolver< R >::solve2right4update().

◆ solve4update() [4/5]

void solve4update	(	SSVectorBase< R > &	x,
		VectorBase< R > &	y,
		VectorBase< R > &	y2,
		const SVectorBase< R > &	rhsx,
		SSVectorBase< R > &	rhsy,
		SSVectorBase< R > &	rhsy2
	)

solves three systems in one call.

Definition at line 704 of file spxbasis.h.

References SPxBasisBase< R >::factorize(), SSVectorBase< R >::isSetup(), and SLinSolver< R >::solve3right4update().

◆ solve4update() [5/5]

void solve4update	(	SSVectorBase< R > &	x,
		SSVectorBase< R > &	y,
		SSVectorBase< R > &	y2,
		const SVectorBase< R > &	rhsx,
		SSVectorBase< R > &	rhsy,
		SSVectorBase< R > &	rhsy2
	)

solves three systems in one call using only sparse data structures

Definition at line 715 of file spxbasis.h.

References SPxBasisBase< R >::factorize(), SSVectorBase< R >::isSetup(), and SLinSolver< R >::solve3right4update().

◆ solver()

SPxSolverBase<R>* solver ( ) const

returns loaded solver.

Definition at line 567 of file spxbasis.h.

References SPxBasisBase< R >::condition(), SPxBasisBase< R >::multBaseWith(), SPxBasisBase< R >::multWithBase(), and SPxBasisBase< R >::theLP.

Referenced by SPxBasisBase< R >::coSolve().

◆ stability()

R stability ( ) const

returns the stability of the basis matrix.

Definition at line 630 of file spxbasis.h.

References SLinSolver< R >::stability().

◆ statistics()

std::string statistics ( ) const

returns statistical information in form of a string.

Definition at line 938 of file spxbasis.h.

References SPxBasisBase< R >::getTotalUpdateCount(), SPxBasisBase< R >::getTotalUpdateTime(), and SLinSolver< R >::statistics().

◆ status()

SPxStatus status ( void ) const

returns current SPxStatus.

Definition at line 428 of file spxbasis.h.

References SPxBasisBase< R >::thestatus.

◆ unLoad()

virtual void unLoad ( )

virtual

unloads the LP from the basis.

Definition at line 901 of file spxbasis.h.

References SPxBasisBase< R >::Desc::dump(), SPxBasisBase< R >::invalidate(), SPxBasisBase< R >::Desc::isConsistent(), SPxBasisBase< R >::NO_PROBLEM, SPxBasisBase< R >::restoreInitialBasis(), and SPxBasisBase< R >::setStatus().

◆ writeBasis()

virtual void writeBasis	(	std::ostream &	os,
		const NameSet *	rownames,
		const NameSet *	colnames,
		const bool	cpxFormat = `false`
	)		const

virtual

Write basis to os in MPS format. If rowNames and colNames are NULL, default names are used for the constraints and variables.

Referenced by SPxBasisBase< R >::coSolve().

Member Data Documentation

◆ factor

SLinSolver<R>* factor

protected

Definition at line 358 of file spxbasis.h.

◆ factorized

bool factorized

protected

true iff factor = matrix \(^{-1}\).

Definition at line 360 of file spxbasis.h.

◆ fillFactor

R fillFactor

protected

allowed increase in relative fill before refactorization

When the real relative fill is bigger than fillFactor times lastFill the Basis will be refactorized.

Definition at line 382 of file spxbasis.h.

◆ freeSlinSolver

bool freeSlinSolver

private

true iff factor should be freed inside of this object

Definition at line 417 of file spxbasis.h.

◆ iterCount

int iterCount

protected

number of calls to change() since last manipulation

Definition at line 391 of file spxbasis.h.

Referenced by SPxBasisBase< R >::iteration().

◆ iterDegenCheck

int iterDegenCheck

protected

number of calls to change() since last degeneracy check

Definition at line 393 of file spxbasis.h.

Referenced by SPxBasisBase< R >::lastDegenCheck().

◆ lastFill

R lastFill

protected

fill ratio that occured during last factorization

Definition at line 398 of file spxbasis.h.

◆ lastidx

int lastidx

protected

lastIndex(): basis index where last update was done

Definition at line 406 of file spxbasis.h.

Referenced by SPxBasisBase< R >::lastIndex().

◆ lastin

SPxId lastin

protected

lastEntered(): variable entered the base last

Definition at line 404 of file spxbasis.h.

Referenced by SPxBasisBase< R >::lastEntered().

◆ lastIterCount

int lastIterCount

protected

number of calls to change() before halting the simplex

Definition at line 392 of file spxbasis.h.

Referenced by SPxBasisBase< R >::prevIteration().

◆ lastMem

int lastMem

protected

memory needed after last fresh factorization

Definition at line 397 of file spxbasis.h.

◆ lastNzCount

int lastNzCount

protected

number of nonzeros in basis matrix after last fresh factorization

Definition at line 399 of file spxbasis.h.

◆ lastout

SPxId lastout

protected

lastLeft(): variable left the base last

Definition at line 405 of file spxbasis.h.

Referenced by SPxBasisBase< R >::lastLeft().

◆ matrix

DataArray< const SVectorBase<R>* > matrix

protected

pointers to the vectors of the basis matrix.

Definition at line 350 of file spxbasis.h.

◆ matrixIsSetup

bool matrixIsSetup

protected

true iff the pointers in matrix are set up correctly.

Definition at line 352 of file spxbasis.h.

◆ maxUpdates

int maxUpdates

protected

number of updates before refactorization.

When a vector of the basis matrix is exchanged by a call to method change(), the LU factorization of the matrix is updated accordingly. However, after atmost maxUpdates updates of the factorization, it is recomputed in order to regain numerical stability and reduce fill in.

Definition at line 369 of file spxbasis.h.

Referenced by SPxBasisBase< R >::getMaxUpdates().

◆ memFactor

R memFactor

protected

allowed total increase in memory consumption before refactorization

Definition at line 385 of file spxbasis.h.

◆ minStab

R minStab

protected

minimum stability

Definition at line 407 of file spxbasis.h.

◆ nonzeroFactor

R nonzeroFactor

protected

allowed increase of nonzeros before refactorization.

When the number of nonzeros in LU factorization exceeds nonzeroFactor times the number of nonzeros in B, the basis matrix is refactorized.

Definition at line 376 of file spxbasis.h.

◆ nzCount

int nzCount

protected

number of nonzeros in basis matrix

Definition at line 396 of file spxbasis.h.

◆ spxout

SPxOut* spxout

private

message handler

Definition at line 418 of file spxbasis.h.

◆ theBaseId

DataArray< SPxId > theBaseId

protected

SPxIds of basic vectors.

Definition at line 348 of file spxbasis.h.

◆ thedesc

Desc thedesc

private

the basis' Descriptor

Definition at line 416 of file spxbasis.h.

Referenced by SPxBasisBase< R >::desc().

◆ theLP

SPxSolverBase<R>* theLP

protected

the LP

For storing the basis matrix we keep two arrays: Array theBaseId contains the SPxIds of the basis vectors, and matrix the pointers to the vectors themselfes. Method loadMatrixVecs() serves for loading matrix according to the SPxIds stored in theBaseId. This method must be called whenever the VectorBase<R> pointers may have changed due to manipulations of the LP.

Definition at line 346 of file spxbasis.h.

Referenced by SPxBasisBase< R >::solver().

◆ thestatus

SPxStatus thestatus

private

current status of the basis.

Definition at line 415 of file spxbasis.h.

Referenced by SPxBasisBase< R >::status().

◆ theTime

Timer* theTime

protected

time spent in updates

Definition at line 401 of file spxbasis.h.

◆ timerType

Timer::TYPE timerType

protected

type of timer (user or wallclock)

Definition at line 402 of file spxbasis.h.

◆ totalUpdateCount

int totalUpdateCount

protected

number of updates

Definition at line 395 of file spxbasis.h.

Referenced by SPxBasisBase< R >::getTotalUpdateCount().

◆ updateCount

int updateCount

protected

number of calls to change() since last factorize()

Definition at line 394 of file spxbasis.h.

Referenced by SPxBasisBase< R >::lastUpdate().

SoPlex

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Private Attributes

Detailed Description

template<class R> class soplex::SPxBasisBase< R >

Member Enumeration Documentation

◆ SPxStatus

Constructor & Destructor Documentation

◆ SPxBasisBase() [1/2]

◆ SPxBasisBase() [2/2]

◆ ~SPxBasisBase()

Member Function Documentation

◆ addedCols()

◆ addedRows()

◆ baseId() [1/2]

◆ baseId() [2/2]

◆ baseVec()

◆ change()

◆ changedCol()

◆ changedElement()

◆ changedRow()

◆ condition()

◆ coSolve() [1/6]

◆ coSolve() [2/6]

◆ coSolve() [3/6]

◆ coSolve() [4/6]

◆ coSolve() [5/6]

◆ coSolve() [6/6]

◆ desc() [1/2]

◆ desc() [2/2]

◆ dualColStatus()

◆ dualRowStatus()

◆ dualStatus() [1/3]

◆ dualStatus() [2/3]

◆ dualStatus() [3/3]

◆ dump()

◆ factorize()

◆ getEstimatedCondition()

◆ getExactCondition()

◆ getMatrixMetric()

◆ getMaxUpdates()

◆ getTotalUpdateCount()

◆ getTotalUpdateTime()

◆ invalidate()

◆ isConsistent()

◆ isDescValid()

◆ iteration()

◆ lastDegenCheck()

◆ lastEntered()

◆ lastIndex()

◆ lastLeft()

◆ lastUpdate()

◆ load()

◆ loadBasisSolver()

◆ loadDesc()

◆ loadMatrixVecs()

◆ multBaseWith() [1/2]

◆ multBaseWith() [2/2]

◆ multWithBase() [1/2]

◆ multWithBase() [2/2]

◆ operator=()

◆ prevIteration()

◆ printMatrix()

◆ printMatrixMTX()

◆ readBasis()

◆ reDim()

◆ removedCol()

◆ removedCols()

◆ removedRow()

◆ removedRows()

◆ restoreInitialBasis()

◆ setMaxUpdates()

◆ setOutstream()

◆ setRep()

◆ setStatus()

◆ solve() [1/2]

template<class R>
class soplex::SPxBasisBase< R >