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 nonsingular 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 nonsigular matrix. The dimension of the vectors is refered to as the basis' dimension, whereas the number of vectors belonging to the LP is called the basis' codimension. More...

#include <spxbasis.h>

Inheritance diagram for SPxBasis:

[legend]

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.

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

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

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

const Desc &	desc () const

Desc &	desc ()
	returns current basis Descriptor.

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

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

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

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

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

Inquiry Methods
SPxId &	baseId (int i)

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

const SVector &	baseVec (int i) const
	returns the `i'th` basic vector.

SPxId	lastEntered () const
	returns SPxId of last vector included to the basis.

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

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

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

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

SPxSolver *	solver () const
	returns loaded solver.

Linear Algebra
Vector &	multBaseWith (Vector &x) const
	Basis-vector product.

Vector &	multWithBase (Vector &x) const
	Vector-basis product.

Real	stability () const
	returns the stability of the basis matrix.

void	solve (Vector &x, const Vector &rhs)

void	solve (SSVector &x, const SVector &rhs)

void	solve4update (SSVector &x, const SVector &rhs)
	solves linear system with basis matrix.

void	solve4update (SSVector &x, Vector &y, const SVector &rhsx, SSVector &rhsy)
	solves two systems in one call.

void	solve4update (SSVector &x, Vector &y, Vector &y2, const SVector &rhsx, SSVector &rhsy, SSVector &rhsy2)
	solves three systems in one call.

void	coSolve (Vector &x, const Vector &rhs)
	Cosolves linear system with basis matrix.

void	coSolve (SSVector &x, const SVector &rhs)

void	coSolve (SSVector &x, Vector &y, const SVector &rhsx, SSVector &rhsy)
	solves two systems in one call.

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

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

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

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

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

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

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

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

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

Miscellaneous
virtual void	change (int i, SPxId &id, const SVector enterVec, const SSVector eta=0)
	performs basis update.

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

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

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

virtual void	loadSolver (SLinSolver *solver, const bool destroy=false)
	sets up linear solver to use.

virtual void	load (SPxSolver *lp)
	loads the LP `lp` to the basis.

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

void	invalidate ()
	invalidates actual basis.

void	restoreInitialBasis ()
	Restores initial basis.

void	dump ()
	output basis entries.

bool	isConsistent () const
	consistency check.

Real	getTotalUpdateTime () const
	time spent in updates

int	getTotalUpdateCount () const
	number of updates performed

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

Constructors / Destructors
	SPxBasis ()
	default constructor.

	SPxBasis (const SPxBasis &old)
	copy constructor

SPxBasis &	operator= (const SPxBasis &rhs)
	assignment operator

virtual	~SPxBasis ()
	destructor.

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

void	reDim ()
	resizes internal arrays.

virtual void	factorize ()
	factorizes the basis matrix.

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

Protected Attributes

SPxSolver *	theLP
	the LP

DataArray< SPxId >	theBaseId
	SPxIds of basic vectors.

DataArray< const SVector * >	matrix
	pointers to the vectors of the basis matrix.

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

SLinSolver *	factor

bool	factorized
	`true` iff factor = matrix $^{-1}$ .

int	maxUpdates
	number of updates before refactorization.

Real	nonzeroFactor
	allowed increase of nonzeros before refactorization.

Real	fillFactor
	allowed increase in realtive fill before refactorization

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

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

int	totalUpdateCount
	number of updates

Timer	totalUpdateTime
	time spent in updates

int	nzCount
	number of nonzeros in basis matrix

int	lastMem
	memory needed after last fresh factorization

Real	lastFill
	fill ratio that occured during last factorization

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

SPxId	lastin
	lastEntered(): variable entered the base last

SPxId	lastout
	lastLeft(): variable left the base last

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

Real	minStab
	minimum stability

Private Attributes

SPxStatus	thestatus
	current status of the basis.

Desc	thedesc
	the basis' Descriptor

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

Detailed Description

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 nonsingular 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 nonsigular matrix. The dimension of the vectors is refered to as the basis' dimension, whereas the number of vectors belonging to the LP is called the basis' codimension.

Class SPxBasis 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 SPxBasis provides methods for solving linear systems with the basis matrix. However, SPxBasis does not provide a linear solver by its own. Instead, a SLinSolver object must be loaded to a SPxBasis which will be called for solving linear systems.

Definition at line 76 of file spxbasis.h.

Member Enumeration Documentation

enum SPxStatus

basis status.

Each SPxBasis 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 84 of file spxbasis.h.

Constructor & Destructor Documentation

SPxBasis ( )

default constructor.

Definition at line 1019 of file spxbasis.cpp.

References METHOD.

SPxBasis ( const SPxBasis & old )

copy constructor

Warning: Do not change the LP object. Only pointer to that object is copied. Hint: no problem, we use this function for copy constructor of SPxSolver

Definition at line 1043 of file spxbasis.cpp.

References SLinSolver::clone(), SPxBasis::factor, SPxBasis::freeSlinSolver, SPxBasis::isConsistent(), and METHOD.

~SPxBasis ( )

virtual

destructor.

Definition at line 1072 of file spxbasis.cpp.

References SPxBasis::factor, SPxBasis::freeSlinSolver, and METHOD.

Member Function Documentation

void addedCols ( int n )

inform SPxBasis that n new columns had been added.

Definition at line 266 of file spxchangebasis.cpp.

References SPxBasis::baseId(), SPxBasis::Desc::colStatus(), SPxSolver::COLUMN, SPxBasis::DUAL, SPxBasis::factorized, SPxBasis::INFEASIBLE, SPxBasis::loadMatrixVecs(), SPxBasis::matrixIsSetup, METHOD, MSG_ERROR, SPxLP::nCols(), SPxBasis::NO_PROBLEM, SPxBasis::OPTIMAL, SPxBasis::PRIMAL, soplex::primalColStatus(), SPxBasis::reDim(), SPxBasis::REGULAR, SPxSolver::rep(), SPxSolver::ROW, SPxBasis::setStatus(), SPxBasis::SINGULAR, soplex::spxout, SPxBasis::status(), SPxBasis::thedesc, SPxBasis::theLP, and SPxBasis::UNBOUNDED.

Referenced by SPxSolver::addedCols(), and SPxBasis::load().

void addedRows ( int n )

inform SPxBasis, that n new rows had been added.

Definition at line 62 of file spxchangebasis.cpp.

References SPxBasis::baseId(), SPxSolver::COLUMN, SPxBasis::DUAL, SPxBasis::dualRowStatus(), SPxBasis::factorized, SPxBasis::INFEASIBLE, SPxBasis::loadMatrixVecs(), SPxBasis::matrixIsSetup, METHOD, MSG_ERROR, SPxBasis::NO_PROBLEM, SPxLP::nRows(), SPxBasis::OPTIMAL, SPxBasis::PRIMAL, SPxBasis::reDim(), SPxBasis::REGULAR, SPxSolver::rep(), SPxSolver::ROW, SPxBasis::Desc::rowStatus(), SPxBasis::setStatus(), SPxBasis::SINGULAR, soplex::spxout, SPxBasis::status(), SPxBasis::thedesc, SPxBasis::theLP, and SPxBasis::UNBOUNDED.

Referenced by SPxSolver::addedRows(), and SPxBasis::load().

SPxId& baseId ( int i )

Definition at line 486 of file spxbasis.h.

References SPxBasis::theBaseId.

Referenced by SPxBasis::addedCols(), SPxBasis::addedRows(), SPxSolver::computeEnterCoPrhs(), SPxSolver::computeEnterCoPrhs4Col(), SPxSolver::computeEnterCoPrhs4Row(), SPxSolver::computeLeaveCoPrhs(), SPxSolver::computeLeaveCoPrhs4Col(), SPxSolver::computeLeaveCoPrhs4Row(), SPxWeightPR::computeLeavePenalty(), SPxSolver::enter(), SPxSolver::fpsolve(), SPxSolver::getDual(), SPxSolver::getLeaveVals(), SPxSolver::getPrimal(), SPxSolver::getRedCost(), SPxSolver::getSlacks(), SPxSolver::leave(), SPxBasis::loadMatrixVecs(), SPxBasis::removedCol(), SPxBasis::removedRow(), SPxBasis::restoreInitialBasis(), SPxFastRT::selectLeave(), SPxSolver::setDual(), SPxSolver::setEnterBound4Col(), SPxSolver::setEnterBound4Row(), SPxSolver::setEnterBounds(), SPxSolver::setLeaveBound4Col(), SPxSolver::setLeaveBound4Row(), SPxSolver::setLeaveBounds(), SPxSolver::setPrimal(), SPxSolver::setRedCost(), SPxSolver::setSlacks(), SPxSteepPR::setupWeights(), and SPxSolver::unShift().

SPxId baseId ( int i ) const

returns the Id of the i'th basis vector.

Definition at line 491 of file spxbasis.h.

References SPxBasis::theBaseId.

const SVector& baseVec ( int i ) const

returns the i'th basic vector.

Definition at line 497 of file spxbasis.h.

References SPxBasis::matrix, and SPxBasis::matrixIsSetup.

Referenced by SPxSolver::enter(), SPxSolver::leave(), and SPxBasis::printMatrixMTX().

void change	(	int	i,
		SPxId &	id,
		const SVector *	enterVec,
		const SSVector *	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.

Definition at line 704 of file spxbasis.cpp.

References SLinSolver::change(), SPxBasis::factor, SPxBasis::factorize(), SPxBasis::factorized, SPxBasis::iterCount, SPxBasis::lastFill, SPxBasis::lastidx, SPxBasis::lastin, SPxBasis::lastNzCount, SPxBasis::lastout, SPxBasis::matrix, SPxBasis::matrixIsSetup, SPxBasis::maxUpdates, SLinSolver::memory(), METHOD, SPxBasis::minStab, MSG_INFO3, SPxBasis::nonzeroFactor, SPxBasis::nzCount, SLinSolver::OK, SPxBasis::REGULAR, SVector::size(), soplex::spxout, SLinSolver::stability(), Timer::start(), SLinSolver::status(), SPxBasis::status(), Timer::stop(), SPxBasis::theBaseId, SPxBasis::totalUpdateCount, SPxBasis::totalUpdateTime, and SPxBasis::updateCount.

Referenced by SPxSolver::enter(), and SPxSolver::leave().

void changedCol ( int )

inform SPxBasis that a column had been changed.

Todo:: is this correctly implemented?

Definition at line 501 of file spxchangebasis.cpp.

References SPxBasis::invalidate(), METHOD, and SPxBasis::restoreInitialBasis().

Referenced by SPxSolver::changeCol().

void changedElement	(	int	,
		int
	)

inform SPxBasis that a matrix entry had been changed.

Todo:: is this correctly implemented?

Definition at line 510 of file spxchangebasis.cpp.

References SPxBasis::invalidate(), METHOD, and SPxBasis::restoreInitialBasis().

Referenced by SPxSolver::changeElement().

void changedRow ( int )

inform SPxBasis that a row had been changed.

Todo:: Implement changedRow(), changedCol(), changedElement() in a more clever way. For instance, the basis won't be singular (but maybe infeasible) if the change doesn't affect the basis rows/columns.

The following methods (changedRow(), changedCol(), changedElement()) radically change the current basis to the original (slack) basis also present after loading the LP. The reason is that through the changes, the current basis may become singular. Going back to the initial basis is quite inefficient, but correct.

Todo:: is this correctly implemented?

Definition at line 492 of file spxchangebasis.cpp.

References SPxBasis::invalidate(), METHOD, and SPxBasis::restoreInitialBasis().

Referenced by SPxSolver::changeRow().

void coSolve	(	Vector &	x,
		const Vector &	rhs
	)

Cosolves linear system with basis matrix.

Depending on the representation, for a SPxBasis 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 632 of file spxbasis.h.

References SPxBasis::factor, SPxBasis::factorize(), SPxBasis::factorized, METHOD, and SLinSolver::solveLeft().

Referenced by SPxSolver::enter(), SPxSolver::factorize(), SPxSolver::init(), SPxSteepPR::isConsistent(), SPxSolver::leave(), SPxSolver::reinitializeVecs(), SPxSteepPR::selectLeave(), SPxSteepPR::selectLeavePart(), SPxSteepPR::selectLeaveSparse(), SPxSteepPR::setupWeights(), SPxSolver::terminate(), and SPxSolver::testVecs().

void coSolve	(	SSVector &	x,
		const SVector &	rhs
	)

Definition at line 640 of file spxbasis.h.

References SPxBasis::factor, SPxBasis::factorize(), SPxBasis::factorized, METHOD, and SLinSolver::solveLeft().

void coSolve	(	SSVector &	x,
		Vector &	y,
		const SVector &	rhsx,
		SSVector &	rhsy
	)

solves two systems in one call.

Definition at line 648 of file spxbasis.h.

References SPxBasis::factor, SPxBasis::factorize(), SPxBasis::factorized, METHOD, and SLinSolver::solveLeft().

const Desc& desc ( ) const

Definition at line 446 of file spxbasis.h.

References SPxBasis::thedesc.

Desc& desc ( )

returns current basis Descriptor.

Definition at line 451 of file spxbasis.h.

References SPxBasis::thedesc.

SPxBasis::Desc::Status dualColStatus ( int i ) const

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

Definition at line 74 of file spxbasis.cpp.

References SPxBasis::Desc::D_FREE, SPxBasis::Desc::D_ON_BOTH, SPxBasis::Desc::D_ON_LOWER, SPxBasis::Desc::D_ON_UPPER, SPxBasis::Desc::D_UNDEFINED, soplex::infinity, METHOD, and SPxBasis::theLP.

Referenced by soplex::changeLowerStatus(), soplex::changeUpperStatus(), SPxBasis::dualStatus(), SPxSolver::getLeaveVals(), SPxSolver::getLeaveVals2(), SPxBasis::isConsistent(), SPxBasis::isDescValid(), SPxBasis::loadDesc(), SPxBasis::readBasis(), SPxSolver::setDualRowBounds(), soplex::setDualStatus(), and SPxSolver::varStatusToBasisStatusCol().

SPxBasis::Desc::Status dualRowStatus ( int i ) const

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

Definition at line 50 of file spxbasis.cpp.

References SPxBasis::Desc::D_FREE, SPxBasis::Desc::D_ON_BOTH, SPxBasis::Desc::D_ON_LOWER, SPxBasis::Desc::D_ON_UPPER, SPxBasis::Desc::D_UNDEFINED, soplex::infinity, SPxLP::lhs(), METHOD, SPxLP::rhs(), and SPxBasis::theLP.

Referenced by SPxBasis::addedRows(), soplex::changeLhsStatus(), soplex::changeRhsStatus(), SPxBasis::dualStatus(), SPxSolver::getLeaveVals(), SPxSolver::getLeaveVals2(), SPxBasis::isConsistent(), SPxBasis::isDescValid(), SPxBasis::loadDesc(), SPxBasis::readBasis(), SPxBasis::restoreInitialBasis(), SPxSolver::setDualRowBounds(), soplex::setDualStatus(), and SPxSolver::varStatusToBasisStatusRow().

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

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

Definition at line 36 of file spxbasis.cpp.

References SPxBasis::dualColStatus(), METHOD, and SPxBasis::theLP.

Referenced by SPxBasis::dualStatus().

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

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

Definition at line 43 of file spxbasis.cpp.

References SPxBasis::dualRowStatus(), METHOD, and SPxBasis::theLP.

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 473 of file spxbasis.h.

References SPxBasis::dualStatus().

void dump ( )

output basis entries.

Definition at line 923 of file spxbasis.cpp.

References SPxBasis::Desc::colStatus(), SPxOut::DEBUG, SPxSolver::dim(), SPxOut::getVerbosity(), SPxSolver::isBasic(), SPxBasis::matrix, METHOD, SPxLP::nCols(), SPxBasis::Desc::nCols(), SPxBasis::NO_PROBLEM, SPxLP::nRows(), SPxBasis::Desc::nRows(), SPxLP::number(), SPxBasis::Desc::rowStatus(), SPxOut::setVerbosity(), soplex::spxout, SPxBasis::status(), SPxBasis::thedesc, and SPxBasis::theLP.

void factorize ( )

protectedvirtual

factorizes the basis matrix.

Reimplemented in SPxSolver.

Definition at line 835 of file spxbasis.cpp.

References SPxBasis::factor, SPxBasis::factorized, SPxBasis::fillFactor, SPxBasis::lastFill, SPxBasis::lastMem, SPxBasis::lastNzCount, SLinSolver::load(), SPxBasis::loadDesc(), SPxBasis::matrix, SPxBasis::matrixIsSetup, SLinSolver::memory(), METHOD, SPxBasis::minStab, MSG_ERROR, SPxBasis::nonzeroFactor, SPxBasis::nzCount, SLinSolver::OK, SPxBasis::REGULAR, SPxBasis::setStatus(), SLinSolver::SINGULAR, SPxBasis::SINGULAR, soplex::spxout, SLinSolver::stability(), SPxBasis::status(), SPxBasis::thedesc, and SPxBasis::updateCount.

Referenced by SPxBasis::change(), SPxBasis::coSolve(), SPxSolver::factorize(), SPxBasis::solve(), and SPxBasis::solve4update().

int getMaxUpdates ( )

returns maximum number of updates before a refactorization is performed

Definition at line 440 of file spxbasis.h.

References SPxBasis::maxUpdates.

int getTotalUpdateCount ( ) const

number of updates performed

Definition at line 790 of file spxbasis.h.

References SPxBasis::totalUpdateCount.

Referenced by SPxBasis::statistics().

Real getTotalUpdateTime ( ) const

time spent in updates

Definition at line 785 of file spxbasis.h.

References SPxBasis::totalUpdateTime, and Timer::userTime().

Referenced by SPxBasis::statistics().

void invalidate ( )

invalidates actual basis.

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

Todo:: is this correctly implemented?

Definition at line 417 of file spxchangebasis.cpp.

References SPxBasis::factorized, SPxBasis::matrixIsSetup, METHOD, MSG_INFO3, and soplex::spxout.

Referenced by SPxBasis::changedCol(), SPxBasis::changedElement(), SPxBasis::changedRow(), and SPxBasis::setStatus().

bool isConsistent ( ) const

consistency check.

Definition at line 970 of file spxbasis.cpp.

References SPxBasis::Desc::colStatus(), SPxSolver::dim(), SPxBasis::dualColStatus(), SPxBasis::dualRowStatus(), SPxBasis::factor, SLinSolver::isConsistent(), SPxBasis::Desc::isConsistent(), SPxBasis::matrix, METHOD, MSGinconsistent, SPxLP::nCols(), SPxBasis::Desc::nCols(), SPxBasis::NO_PROBLEM, SPxLP::nRows(), SPxBasis::Desc::nRows(), SPxBasis::Desc::rowStatus(), SPxBasis::status(), SPxBasis::theBaseId, SPxBasis::thedesc, and SPxBasis::theLP.

Referenced by SPxSolver::isConsistent(), SPxBasis::operator=(), and SPxBasis::SPxBasis().

bool isDescValid ( const Desc & ds )

virtual

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

Definition at line 119 of file spxbasis.cpp.

References SPxBasis::Desc::colstat, SPxBasis::dualColStatus(), SPxBasis::dualRowStatus(), soplex::infinity, METHOD, MSG_DEBUG, SPxLP::nCols(), SPxBasis::Desc::nCols(), SPxBasis::NO_PROBLEM, SPxLP::nRows(), SPxBasis::Desc::nRows(), SPxBasis::Desc::P_FIXED, SPxBasis::Desc::P_ON_LOWER, SPxBasis::Desc::P_ON_UPPER, SPxBasis::Desc::rowstat, soplex::spxout, SPxBasis::status(), and SPxBasis::theLP.

Referenced by SPxBasis::loadDesc(), SPxSolver::refine(), SoPlex::solve(), and SPxSolver::solve().

int iteration ( ) const

returns number of basis changes since last load().

Definition at line 528 of file spxbasis.h.

References SPxBasis::iterCount.

Referenced by SPxSteepPR::entered4(), SPxSolver::factorize(), SPxSolver::fpsolve(), SoPlex::iteration(), SPxSolver::leave(), SPxSteepPR::left4(), SPxSolver::perturbMaxEnter(), SPxSolver::perturbMaxLeave(), SPxSolver::perturbMinEnter(), SPxSolver::perturbMinLeave(), SPxFastRT::selectEnter(), SPxBoundFlippingRT::selectEnter(), SPxFastRT::selectLeave(), SPxSolver::terminate(), and SPxSolver::testVecs().

SPxId lastEntered ( ) const

returns SPxId of last vector included to the basis.

Definition at line 504 of file spxbasis.h.

References SPxBasis::lastin.

Referenced by SPxSolver::fpsolve().

int lastIndex ( ) const

returns index in basis where last update was done.

Definition at line 516 of file spxbasis.h.

References SPxBasis::lastidx.

Referenced by SPxSolver::fpsolve().

SPxId lastLeft ( ) const

returns SPxId of last vector that left the basis.

Definition at line 510 of file spxbasis.h.

References SPxBasis::lastout.

Referenced by SPxSolver::fpsolve().

int lastUpdate ( ) const

returns number of basis changes since last refactorization.

Definition at line 522 of file spxbasis.h.

References SPxBasis::updateCount.

Referenced by SPxSolver::enter(), SPxSolver::factorize(), SPxSolver::fpsolve(), SPxSolver::leave(), and SPxSolver::qualRedCostViolation().

void load ( SPxSolver * lp )

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.

Definition at line 310 of file spxbasis.cpp.

References SPxBasis::addedCols(), SPxBasis::addedRows(), SPxBasis::loadDesc(), METHOD, SPxLP::nCols(), SPxLP::nRows(), SPxBasis::REGULAR, SPxBasis::setRep(), SPxBasis::setStatus(), SPxBasis::thedesc, and SPxBasis::theLP.

Referenced by SPxSolver::fpsolve(), SPxSolver::init(), SPxSolver::loadBasis(), SPxSolver::loadLP(), SPxSolver::read(), SPxBasis::readBasis(), SPxSolver::setBasis(), and SPxSolver::setType().

void loadDesc ( const Desc & ds )

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.

Definition at line 197 of file spxbasis.cpp.

References SLinSolver::clear(), SPxBasis::Desc::colStatus(), SPxSolver::dim(), SPxBasis::dualColStatus(), SPxBasis::dualRowStatus(), SPxBasis::factor, SPxBasis::factorized, soplex::infinity, SPxSolver::isBasic(), SPxBasis::isDescValid(), SPxBasis::iterCount, SPxBasis::lastidx, SPxBasis::lastin, SPxBasis::lastout, SPxBasis::matrix, SPxBasis::matrixIsSetup, METHOD, MSG_INFO3, SPxLP::nCols(), SPxBasis::Desc::nCols(), SPxBasis::NO_PROBLEM, SPxLP::nRows(), SPxBasis::Desc::nRows(), SPxBasis::nzCount, SPxBasis::Desc::P_FIXED, SPxBasis::Desc::P_FREE, SPxBasis::Desc::P_ON_LOWER, SPxBasis::Desc::P_ON_UPPER, SPxBasis::Desc::rowStatus(), SPxBasis::setRep(), soplex::spxout, SPxBasis::status(), SPxBasis::theBaseId, SPxBasis::thedesc, SPxBasis::theLP, SPxBasis::updateCount, and SPxSolver::vector().

Referenced by SPxBasis::factorize(), SPxSolver::init(), SPxSolver::initRep(), SPxBasis::load(), SPxSolver::loadBasis(), and SPxBasis::readBasis().

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.

Definition at line 97 of file spxbasis.cpp.

References SPxBasis::baseId(), SLinSolver::clear(), SPxSolver::dim(), SPxBasis::factor, SPxBasis::factorized, SPxBasis::matrix, SPxBasis::matrixIsSetup, METHOD, MSG_INFO3, SPxBasis::nzCount, soplex::spxout, SPxBasis::theLP, and SPxSolver::vector().

Referenced by SPxBasis::addedCols(), SPxBasis::addedRows(), and SPxBasis::restoreInitialBasis().

void loadSolver	(	SLinSolver *	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.

Definition at line 326 of file spxbasis.cpp.

References SLinSolver::clear(), SPxBasis::factor, SPxBasis::factorized, SPxBasis::freeSlinSolver, METHOD, MSG_INFO3, and soplex::spxout.

Referenced by SPxSolver::setSolver().

Vector & multBaseWith ( Vector & x ) const

Basis-vector product.

Depending on the representation, for an SPxBasis 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.

Definition at line 899 of file spxbasis.cpp.

References Vector::clear(), Vector::dim(), SPxSolver::dim(), SPxBasis::matrix, SPxBasis::matrixIsSetup, METHOD, Vector::multAdd(), SPxBasis::SINGULAR, SPxBasis::status(), SPxBasis::thedesc, and SPxBasis::theLP.

Referenced by SPxSolver::enter(), SPxSolver::factorize(), SPxSolver::leave(), and SPxSolver::testVecs().

Vector & multWithBase ( Vector & x ) const

Vector-basis product.

Depending on the representation, for a SPxBasis 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.

Definition at line 879 of file spxbasis.cpp.

References Vector::dim(), SPxSolver::dim(), SPxBasis::matrix, SPxBasis::matrixIsSetup, METHOD, SPxBasis::SINGULAR, SPxBasis::status(), SPxBasis::thedesc, and SPxBasis::theLP.

Referenced by SPxSolver::factorize(), and SPxSolver::testVecs().

SPxBasis & operator= ( const SPxBasis & rhs )

assignment operator

Warning: Note that we do not create a deep copy of the corresponding SPxSolver object. Only the reference to that object is copied.

Definition at line 1089 of file spxbasis.cpp.

References SLinSolver::clone(), SPxBasis::factor, SPxBasis::factorized, SPxBasis::fillFactor, SPxBasis::freeSlinSolver, SPxBasis::isConsistent(), SPxBasis::iterCount, SPxBasis::lastFill, SPxBasis::lastidx, SPxBasis::lastin, SPxBasis::lastNzCount, SPxBasis::lastout, SPxBasis::matrix, SPxBasis::matrixIsSetup, SPxBasis::maxUpdates, METHOD, SPxBasis::minStab, SPxBasis::nonzeroFactor, SPxBasis::nzCount, SPxBasis::theBaseId, SPxBasis::thedesc, SPxBasis::theLP, and SPxBasis::thestatus.

Referenced by SPxSolver::operator=().

void printMatrix ( ) const

virtual

Definition at line 661 of file spxbasis.cpp.

References SPxBasis::matrix, SPxBasis::matrixIsSetup, METHOD, and soplex::spxout.

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.

Definition at line 673 of file spxbasis.cpp.

References SPxBasis::baseVec(), SVector::index(), SPxBasis::matrix, SPxBasis::nzCount, SVector::size(), and SVector::value().

bool readBasis	(	std::istream &	is,
		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.

The specification is taken from the

ILOG CPLEX 7.0 Reference Manual, Appendix E, Page 543.

This routine should read valid BAS format files.

Returns: true if the file was read correctly.

Here is a very brief outline of the format:

The format is in a form similar to an MPS file. The basic assumption is that all (column) variables are nonbasic at their lower bound and all row (variables) are basic; only the differences to this rule are given. Each data line contains an indicator, a variable name and possibly a row/constraint name. The following meaning applies with respect to the indicators:

XU: the variable is basic, the row is nonbasic at its upper bound
XL: the variable is basic, the row is nonbasic at its lower bound
UL: the variable is nonbasic and at its upper bound
LL: the variable is nonbasic and at its lower bound

The CPLEX format contains an additional indicator 'BS', but this is unsupported here.

Nonbasic variables without lower bound have the following default status for SoPlex:

at their upper bound if finite,
at zero if free.

Definition at line 378 of file spxbasis.cpp.

References NameSet::add(), SPxSolver::colId(), SPxBasis::Desc::colstat, SPxBasis::dualColStatus(), SPxBasis::dualRowStatus(), SPxBasis::Desc::dump(), MPSInput::ENDATA, MPSInput::field0(), MPSInput::field1(), MPSInput::field2(), MPSInput::field3(), MPSInput::hasError(), soplex::infinity, SPxBasis::load(), SPxBasis::loadDesc(), METHOD, MSG_DEBUG, SPxLP::nCols(), SPxBasis::NO_PROBLEM, SPxLP::nRows(), NameSet::number(), SPxBasis::Desc::P_FIXED, SPxBasis::Desc::P_FREE, SPxBasis::Desc::P_ON_LOWER, SPxBasis::Desc::P_ON_UPPER, MPSInput::readLine(), SPxBasis::REGULAR, NameSet::reMax(), SPxSolver::rowId(), SPxBasis::Desc::rowstat, MPSInput::section(), MPSInput::setSection(), SPxBasis::setStatus(), SPxBasis::status(), MPSInput::syntaxError(), SPxBasis::thedesc, and SPxBasis::theLP.

Referenced by SPxSolver::readBasisFile().

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.

Definition at line 29 of file spxchangebasis.cpp.

References SPxSolver::dim(), SPxBasis::factorized, SPxBasis::matrix, SPxBasis::matrixIsSetup, METHOD, MSG_DEBUG, MSG_INFO3, SPxLP::nCols(), SPxLP::nRows(), SPxBasis::Desc::reSize(), soplex::spxout, SPxBasis::theBaseId, SPxBasis::thedesc, and SPxBasis::theLP.

Referenced by SPxBasis::addedCols(), SPxBasis::addedRows(), SPxSolver::clear(), SPxBasis::removedCol(), SPxBasis::removedCols(), SPxBasis::removedRow(), SPxBasis::removedRows(), and SPxBasis::setRep().

void removedCol ( int i )

inform SPxBasis that column i had been removed.

Definition at line 331 of file spxchangebasis.cpp.

References SPxBasis::baseId(), SPxBasis::Desc::colStatus(), SPxSolver::COLUMN, SPxSolver::dim(), SPxBasis::factorized, SPxSolver::isBasic(), SPxBasis::matrix, SPxBasis::matrixIsSetup, METHOD, SPxLP::nCols(), SPxBasis::NO_PROBLEM, SPxLP::number(), SPxBasis::reDim(), SPxSolver::rep(), SPxSolver::ROW, SPxBasis::setStatus(), SPxBasis::status(), SPxBasis::thedesc, SPxBasis::theLP, and SPxSolver::vector().

Referenced by SPxSolver::doRemoveCol().

void removedCols ( const int perm[] )

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

Definition at line 370 of file spxchangebasis.cpp.

References SPxBasis::Desc::colStatus(), SPxSolver::COLUMN, SPxBasis::factorized, SPxSolver::isBasic(), SPxBasis::matrixIsSetup, METHOD, SPxBasis::Desc::nCols(), SPxBasis::NO_PROBLEM, SPxBasis::reDim(), SPxSolver::rep(), SPxSolver::ROW, SPxBasis::setStatus(), SPxBasis::status(), SPxBasis::thedesc, and SPxBasis::theLP.

Referenced by SPxSolver::doRemoveCols().

void removedRow ( int i )

inform SPxBasis that row i had been removed.

Definition at line 129 of file spxchangebasis.cpp.

References SPxBasis::baseId(), SPxSolver::COLUMN, SPxSolver::dim(), SPxBasis::factorized, SPxSolver::isBasic(), SPxBasis::matrix, SPxBasis::matrixIsSetup, METHOD, MSG_DEBUG, SPxBasis::NO_PROBLEM, SPxLP::nRows(), SPxLP::number(), SPxBasis::reDim(), SPxSolver::rep(), SPxSolver::ROW, SPxBasis::Desc::rowStatus(), SPxBasis::setStatus(), soplex::spxout, SPxBasis::status(), SPxBasis::thedesc, SPxBasis::theLP, and SPxSolver::vector().

Referenced by SPxSolver::doRemoveRow().

void removedRows ( const int perm[] )

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

Definition at line 176 of file spxchangebasis.cpp.

References SPxSolver::COLUMN, SPxBasis::factorized, SPxSolver::isBasic(), SPxBasis::matrixIsSetup, METHOD, MSG_DEBUG, SPxBasis::NO_PROBLEM, SPxBasis::Desc::nRows(), SPxBasis::reDim(), SPxSolver::rep(), SPxSolver::ROW, SPxBasis::Desc::rowStatus(), SPxBasis::setStatus(), soplex::spxout, SPxBasis::status(), SPxBasis::thedesc, and SPxBasis::theLP.

Referenced by SPxSolver::doRemoveRows().

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.

This code has been adapted from SPxBasis::addedRows() and SPxBasis::addedCols().

Definition at line 433 of file spxchangebasis.cpp.

References SPxBasis::baseId(), SPxBasis::Desc::colStatus(), SPxSolver::COLUMN, SPxBasis::dualRowStatus(), SPxBasis::factorized, SPxBasis::loadMatrixVecs(), SPxBasis::matrixIsSetup, METHOD, SPxLP::nCols(), SPxBasis::NO_PROBLEM, SPxLP::nRows(), soplex::primalColStatus(), SPxBasis::REGULAR, SPxSolver::rep(), SPxSolver::ROW, SPxBasis::Desc::rowStatus(), SPxBasis::setStatus(), SPxBasis::status(), SPxBasis::thedesc, and SPxBasis::theLP.

Referenced by SPxBasis::changedCol(), SPxBasis::changedElement(), and SPxBasis::changedRow().

void setMaxUpdates ( int maxUp )

change maximum number of iterations until a refactorization is performed

Definition at line 433 of file spxbasis.h.

References SPxBasis::maxUpdates.

void setRep ( )

protected

sets descriptor representation according to loaded LP.

Definition at line 290 of file spxbasis.cpp.

References SPxBasis::Desc::colstat, SPxBasis::Desc::costat, METHOD, SPxBasis::minStab, SPxBasis::reDim(), SPxSolver::rep(), SPxSolver::ROW, SPxBasis::Desc::rowstat, SPxBasis::Desc::stat, SPxBasis::thedesc, and SPxBasis::theLP.

Referenced by SPxSolver::initRep(), SPxBasis::load(), and SPxBasis::loadDesc().

void setStatus ( SPxStatus stat )

sets basis SPxStatus to stat.

Definition at line 415 of file spxbasis.h.

References SPxBasis::invalidate(), METHOD, MSG_DEBUG, SPxBasis::NO_PROBLEM, soplex::spxout, and SPxBasis::thestatus.

Referenced by SPxBasis::addedCols(), SPxBasis::addedRows(), SPxBasis::factorize(), SPxBasis::load(), SPxBasis::readBasis(), SPxBasis::removedCol(), SPxBasis::removedCols(), SPxBasis::removedRow(), SPxBasis::removedRows(), SPxBasis::restoreInitialBasis(), and SPxBasis::unLoad().

void solve	(	Vector &	x,
		const Vector &	rhs
	)

Definition at line 570 of file spxbasis.h.

References SPxBasis::factor, SPxBasis::factorize(), SPxBasis::factorized, METHOD, and SLinSolver::solveRight().

Referenced by SPxSolver::factorize(), SPxSolver::init(), SPxSolver::leave(), SPxSolver::reinitializeVecs(), SPxSolver::terminate(), and SPxSolver::testVecs().

void solve	(	SSVector &	x,
		const SVector &	rhs
	)

Definition at line 578 of file spxbasis.h.

References SPxBasis::factor, SPxBasis::factorize(), SPxBasis::factorized, METHOD, and SLinSolver::solveRight().

void solve4update	(	SSVector &	x,
		const SVector &	rhs
	)

solves linear system with basis matrix.

Depending on the representation, for a SPxBasis 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 595 of file spxbasis.h.

References SPxBasis::factor, SPxBasis::factorize(), SPxBasis::factorized, METHOD, and SLinSolver::solveRight4update().

Referenced by SPxSolver::enter(), SPxSolver::leave(), and SPxSteepPR::selectEnter().

void solve4update	(	SSVector &	x,
		Vector &	y,
		const SVector &	rhsx,
		SSVector &	rhsy
	)

solves two systems in one call.

Definition at line 603 of file spxbasis.h.

References SPxBasis::factor, SPxBasis::factorize(), SPxBasis::factorized, METHOD, and SLinSolver::solve2right4update().

void solve4update	(	SSVector &	x,
		Vector &	y,
		Vector &	y2,
		const SVector &	rhsx,
		SSVector &	rhsy,
		SSVector &	rhsy2
	)

solves three systems in one call.

Definition at line 611 of file spxbasis.h.

References SPxBasis::factor, SPxBasis::factorize(), SPxBasis::factorized, SSVector::isSetup(), METHOD, and SLinSolver::solve3right4update().

SPxSolver* solver ( ) const

returns loaded solver.

Definition at line 533 of file spxbasis.h.

References SPxBasis::theLP.

Referenced by SPxSolver::init().

Real stability ( ) const

returns the stability of the basis matrix.

Definition at line 565 of file spxbasis.h.

References SPxBasis::factor, and SLinSolver::stability().

Referenced by SPxFastRT::selectLeave().

std::string statistics ( ) const

returns statistical information in form of a string.

Definition at line 796 of file spxbasis.h.

References SPxBasis::factor, SPxBasis::getTotalUpdateCount(), SPxBasis::getTotalUpdateTime(), and SLinSolver::statistics().

SPxStatus status ( void ) const

returns current SPxStatus.

Definition at line 409 of file spxbasis.h.

References SPxBasis::thestatus.

virtual void unLoad ( )

virtual

unloads the LP from the basis.

Definition at line 758 of file spxbasis.h.

References METHOD, SPxBasis::NO_PROBLEM, SPxBasis::setStatus(), and SPxBasis::theLP.

Referenced by SPxSolver::loadLP(), SPxSolver::read(), and SPxSolver::reLoad().

void writeBasis	(	std::ostream &	os,
		const NameSet *	rownames,
		const NameSet *	colnames
	)		const

virtual

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

Definition at line 581 of file spxbasis.cpp.

References SPxBasis::Desc::colStatus(), SPxBasis::Desc::dump(), soplex::getColName(), soplex::getRowName(), soplex::infinity, SPxLP::lower(), METHOD, MSG_DEBUG, SPxLP::nCols(), SPxBasis::NO_PROBLEM, SPxLP::nRows(), SPxBasis::Desc::P_FIXED, SPxBasis::Desc::P_FREE, SPxBasis::Desc::P_ON_LOWER, SPxBasis::Desc::P_ON_UPPER, SPxBasis::Desc::rowStatus(), SPxBasis::status(), SPxBasis::thedesc, SPxBasis::theLP, and SPxLP::upper().

Member Data Documentation

SLinSolver* factor

protected

Definition at line 349 of file spxbasis.h.

Referenced by SPxBasis::change(), SPxBasis::coSolve(), SPxBasis::factorize(), SPxBasis::isConsistent(), SPxBasis::loadDesc(), SPxBasis::loadMatrixVecs(), SPxBasis::loadSolver(), SPxBasis::operator=(), SPxBasis::solve(), SPxBasis::solve4update(), SPxBasis::SPxBasis(), SPxBasis::stability(), SPxBasis::statistics(), and SPxBasis::~SPxBasis().

bool factorized

protected

true iff factor = matrix $^{-1}$ .

Definition at line 351 of file spxbasis.h.

Referenced by SPxBasis::addedCols(), SPxBasis::addedRows(), SPxBasis::change(), SPxBasis::coSolve(), SPxBasis::factorize(), SPxBasis::invalidate(), SPxBasis::loadDesc(), SPxBasis::loadMatrixVecs(), SPxBasis::loadSolver(), SPxBasis::operator=(), SPxBasis::reDim(), SPxBasis::removedCol(), SPxBasis::removedCols(), SPxBasis::removedRow(), SPxBasis::removedRows(), SPxBasis::restoreInitialBasis(), SPxSolver::setType(), SPxBasis::solve(), and SPxBasis::solve4update().

Real fillFactor

protected

allowed increase in realtive fill before refactorization

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

Definition at line 373 of file spxbasis.h.

Referenced by SPxBasis::factorize(), and SPxBasis::operator=().

bool freeSlinSolver

private

true iff factor should be freed inside of this object

Definition at line 400 of file spxbasis.h.

Referenced by SPxBasis::loadSolver(), SPxBasis::operator=(), SPxBasis::SPxBasis(), and SPxBasis::~SPxBasis().

int iterCount

protected

number of calls to change() since last manipulation

Definition at line 378 of file spxbasis.h.

Referenced by SPxBasis::change(), SPxSolver::fpsolve(), SPxBasis::iteration(), SPxBasis::loadDesc(), SPxBasis::operator=(), SPxSolver::refine(), SPxSolver::solve(), and SPxSolver::testBounds().

Real lastFill

protected

fill ratio that occured during last factorization

Definition at line 384 of file spxbasis.h.

Referenced by SPxBasis::change(), SPxBasis::factorize(), and SPxBasis::operator=().

int lastidx

protected

lastIndex(): basis index where last update was done

Definition at line 389 of file spxbasis.h.

Referenced by SPxBasis::change(), SPxBasis::lastIndex(), SPxBasis::loadDesc(), and SPxBasis::operator=().

SPxId lastin

protected

lastEntered(): variable entered the base last

Definition at line 387 of file spxbasis.h.

Referenced by SPxBasis::change(), SPxBasis::lastEntered(), SPxBasis::loadDesc(), and SPxBasis::operator=().

int lastMem

protected

memory needed after last fresh factorization

Definition at line 383 of file spxbasis.h.

Referenced by SPxBasis::factorize().

int lastNzCount

protected

number of nonzeros in basis matrix after last fresh factorization

Definition at line 385 of file spxbasis.h.

Referenced by SPxBasis::change(), SPxBasis::factorize(), and SPxBasis::operator=().

SPxId lastout

protected

lastLeft(): variable left the base last

Definition at line 388 of file spxbasis.h.

Referenced by SPxBasis::change(), SPxBasis::lastLeft(), SPxBasis::loadDesc(), and SPxBasis::operator=().

DataArray< const SVector* > matrix

protected

pointers to the vectors of the basis matrix.

Definition at line 341 of file spxbasis.h.

Referenced by SPxBasis::baseVec(), SPxBasis::change(), SPxBasis::dump(), SPxBasis::factorize(), SPxBasis::isConsistent(), SPxBasis::loadDesc(), SPxBasis::loadMatrixVecs(), SPxBasis::multBaseWith(), SPxBasis::multWithBase(), SPxBasis::operator=(), SPxBasis::printMatrix(), SPxBasis::printMatrixMTX(), SPxBasis::reDim(), SPxBasis::removedCol(), and SPxBasis::removedRow().

bool matrixIsSetup

protected

true iff the pointers in matrix are set up correctly.

Definition at line 343 of file spxbasis.h.

Referenced by SPxBasis::addedCols(), SPxBasis::addedRows(), SPxBasis::baseVec(), SPxBasis::change(), SPxBasis::factorize(), SPxSolver::fpsolve(), SPxSolver::init(), SPxBasis::invalidate(), SPxBasis::loadDesc(), SPxBasis::loadMatrixVecs(), SPxBasis::multBaseWith(), SPxBasis::multWithBase(), SPxBasis::operator=(), SPxBasis::printMatrix(), SPxBasis::reDim(), SPxBasis::removedCol(), SPxBasis::removedCols(), SPxBasis::removedRow(), SPxBasis::removedRows(), SPxBasis::restoreInitialBasis(), and SPxSolver::setType().

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 360 of file spxbasis.h.

Referenced by SPxBasis::change(), SPxBasis::getMaxUpdates(), SPxBasis::operator=(), and SPxBasis::setMaxUpdates().

Real minStab

protected

minimum stability

Definition at line 390 of file spxbasis.h.

Referenced by SPxBasis::change(), SPxBasis::factorize(), SPxBasis::operator=(), and SPxBasis::setRep().

Real 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 367 of file spxbasis.h.

Referenced by SPxBasis::change(), SPxBasis::factorize(), and SPxBasis::operator=().

int nzCount

protected

number of nonzeros in basis matrix

Definition at line 382 of file spxbasis.h.

Referenced by SPxBasis::change(), SPxBasis::factorize(), SPxBasis::loadDesc(), SPxBasis::loadMatrixVecs(), SPxBasis::operator=(), and SPxBasis::printMatrixMTX().

DataArray< SPxId > theBaseId

protected

SPxIds of basic vectors.

Definition at line 339 of file spxbasis.h.

Referenced by SPxBasis::baseId(), SPxBasis::change(), SPxBasis::isConsistent(), SPxBasis::loadDesc(), SPxBasis::operator=(), and SPxBasis::reDim().

Desc thedesc

private

the basis' Descriptor

Definition at line 399 of file spxbasis.h.

Referenced by SPxBasis::addedCols(), SPxBasis::addedRows(), SPxBasis::desc(), SPxBasis::dump(), SPxBasis::factorize(), SPxBasis::isConsistent(), SPxBasis::load(), SPxBasis::loadDesc(), SPxBasis::multBaseWith(), SPxBasis::multWithBase(), SPxBasis::operator=(), SPxBasis::readBasis(), SPxBasis::reDim(), SPxBasis::removedCol(), SPxBasis::removedCols(), SPxBasis::removedRow(), SPxBasis::removedRows(), SPxBasis::restoreInitialBasis(), SPxBasis::setRep(), and SPxBasis::writeBasis().

SPxSolver* 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 vector pointers may have changed due to manipulations of the LP.

Definition at line 337 of file spxbasis.h.

Referenced by SPxBasis::addedCols(), SPxBasis::addedRows(), SPxBasis::dualColStatus(), SPxBasis::dualRowStatus(), SPxBasis::dualStatus(), SPxBasis::dump(), SPxBasis::isConsistent(), SPxBasis::isDescValid(), SPxBasis::load(), SPxBasis::loadDesc(), SPxBasis::loadMatrixVecs(), SPxBasis::multBaseWith(), SPxBasis::multWithBase(), SPxBasis::operator=(), SPxSolver::operator=(), SPxBasis::readBasis(), SPxBasis::reDim(), SPxSolver::reLoad(), SPxBasis::removedCol(), SPxBasis::removedCols(), SPxBasis::removedRow(), SPxBasis::removedRows(), SPxBasis::restoreInitialBasis(), SPxBasis::setRep(), SPxBasis::solver(), SPxSolver::SPxSolver(), SPxBasis::unLoad(), and SPxBasis::writeBasis().