CoinPrePostsolveMatrix Class Reference

Collects all the information about the problem that is needed in both presolve and postsolve. More...

#include <CoinPresolveMatrix.hpp>

Inheritance diagram for CoinPrePostsolveMatrix:
Inheritance graph
[legend]
Collaboration diagram for CoinPrePostsolveMatrix:
Collaboration graph
[legend]

List of all members.

Public Types

enum  Status {
  isFree = 0x00, basic = 0x01, atUpperBound = 0x02, atLowerBound = 0x03,
  superBasic = 0x04
}
 

Enum for status of various sorts.

More...

Public Member Functions

Constructors & Destructors



 CoinPrePostsolveMatrix (int ncols_alloc, int nrows_alloc, CoinBigIndex nelems_alloc)
 `Native' constructor
 CoinPrePostsolveMatrix (const OsiSolverInterface *si, int ncols_, int nrows_, CoinBigIndex nelems_)
 Generic OSI constructor.
 CoinPrePostsolveMatrix (const ClpSimplex *si, int ncols_, int nrows_, CoinBigIndex nelems_, double bulkRatio)
 ~CoinPrePostsolveMatrix ()
 Destructor.
Functions to work with variable status

Functions to work with the CoinPrePostsolveMatrix::Status enum and related vectors.



void setRowStatus (int sequence, Status status)
 Set row status (i.e., status of artificial for this row).
Status getRowStatus (int sequence) const
 Get row status.
bool rowIsBasic (int sequence) const
 Check if artificial for this row is basic.
void setColumnStatus (int sequence, Status status)
 Set column status (i.e., status of primal variable).
Status getColumnStatus (int sequence) const
 Get column (structural variable) status.
bool columnIsBasic (int sequence) const
 Check if column (structural variable) is basic.
void setRowStatusUsingValue (int iRow)
 Set status of row (artificial variable) to the correct nonbasic status given bounds and current value.
void setColumnStatusUsingValue (int iColumn)
 Set status of column (structural variable) to the correct nonbasic status given bounds and current value.
void setStructuralStatus (const char *strucStatus, int lenParam)
 Set column (structural variable) status vector.
void setArtificialStatus (const char *artifStatus, int lenParam)
 Set row (artificial variable) status vector.
void setStatus (const CoinWarmStartBasis *basis)
 Set the status of all variables from a basis.
CoinWarmStartBasisgetStatus ()
 Get status in the form of a CoinWarmStartBasis.
const char * columnStatusString (int j) const
 Return a print string for status of a column (structural variable).
const char * rowStatusString (int i) const
 Return a print string for status of a row (artificial variable).
Functions to load problem and solution information

These functions can be used to load portions of the problem definition and solution. See also the CoinPresolveMatrix and CoinPostsolveMatrix classes.



void setObjOffset (double offset)
 Set the objective function offset for the original system.
void setObjSense (double objSense)
 Set the objective sense (max/min).
void setPrimalTolerance (double primTol)
 Set the primal feasibility tolerance.
void setDualTolerance (double dualTol)
 Set the dual feasibility tolerance.
void setColLower (const double *colLower, int lenParam)
 Set column lower bounds.
void setColUpper (const double *colUpper, int lenParam)
 Set column upper bounds.
void setColSolution (const double *colSol, int lenParam)
 Set column solution.
void setCost (const double *cost, int lenParam)
 Set objective coefficients.
void setReducedCost (const double *redCost, int lenParam)
 Set reduced costs.
void setRowLower (const double *rowLower, int lenParam)
 Set row lower bounds.
void setRowUpper (const double *rowUpper, int lenParam)
 Set row upper bounds.
void setRowPrice (const double *rowSol, int lenParam)
 Set row solution.
void setRowActivity (const double *rowAct, int lenParam)
 Set row activity.
Functions to retrieve problem and solution information



int getNumCols ()
 Get current number of columns.
int getNumRows ()
 Get current number of rows.
int getNumElems ()
 Get current number of non-zero coefficients.
const CoinBigIndexgetColStarts () const
 Get column start vector for column-major packed matrix.
const int * getColLengths () const
 Get column length vector for column-major packed matrix.
const int * getRowIndicesByCol () const
 Get vector of row indices for column-major packed matrix.
const double * getElementsByCol () const
 Get vector of elements for column-major packed matrix.
const double * getColLower () const
 Get column lower bounds.
const double * getColUpper () const
 Get column upper bounds.
const double * getCost () const
 Get objective coefficients.
const double * getRowLower () const
 Get row lower bounds.
const double * getRowUpper () const
 Get row upper bounds.
const double * getColSolution () const
 Get column solution (primal variable values).
const double * getRowActivity () const
 Get row activity (constraint lhs values).
const double * getRowPrice () const
 Get row solution (dual variables).
const double * getReducedCost () const
 Get reduced costs.
int countEmptyCols ()
 Count empty columns.

Public Attributes

Current and Allocated Size

During pre- and postsolve, the matrix will change in size. During presolve it will shrink; during postsolve it will grow. Hence there are two sets of size variables, one for the current size and one for the allocated size. (See the general comments for the CoinPrePostsolveMatrix class for more information.)



int ncols_
 current number of columns
int nrows_
 current number of rows
CoinBigIndex nelems_
 current number of coefficients
int ncols0_
 Allocated number of columns.
int nrows0_
 Allocated number of rows.
CoinBigIndex nelems0_
 Allocated number of coefficients.
CoinBigIndex bulk0_
 Allocated size of bulk storage for row indices and coefficients.
double bulkRatio_
 Ratio of bulk0- to nelems0_.
Problem representation

The matrix is the common column-major format: A pair of vectors with positional correspondence to hold coefficients and row indices, and a second pair of vectors giving the starting position and length of each column in the first pair.



CoinBigIndexmcstrt_
 Vector of column start positions in hrow_, colels_.
int * hincol_
 Vector of column lengths.
int * hrow_
 Row indices (positional correspondence with colels_).
double * colels_
 Coefficients (positional correspondence with hrow_).
double * cost_
 Objective coefficients.
double originalOffset_
 Original objective offset.
double * clo_
 Column (primal variable) lower bounds.
double * cup_
 Column (primal variable) upper bounds.
double * rlo_
 Row (constraint) lower bounds.
double * rup_
 Row (constraint) upper bounds.
int * originalColumn_
 Original column numbers.
int * originalRow_
 Original row numbers.
double ztolzb_
 Primal feasibility tolerance.
double ztoldj_
 Dual feasibility tolerance.
double maxmin_
 Maximization/minimization.
Problem solution information

The presolve phase will work without any solution information (appropriate for initial optimisation) or with solution information (appropriate for reoptimisation). When solution information is supplied, presolve will maintain it to the best of its ability. colstat_ is checked to determine the presence/absence of status information. sol_ is checked for primal solution information, and rowduals_ for dual solution information.

The postsolve phase requires the complete solution information from the presolved problem (status, primal and dual solutions). It will be transformed into a correct solution for the original problem.



double * sol_
 Vector of primal variable values.
double * rowduals_
 Vector of dual variable values.
double * acts_
 Vector of constraint left-hand-side values (row activity).
double * rcosts_
 Vector of reduced costs.
unsigned char * colstat_
 Status of primal variables.
unsigned char * rowstat_
 Status of constraints.

Related Functions

(Note that these are not member functions.)



void presolve_make_memlists (CoinBigIndex *starts, int *lengths, presolvehlink *link, int n)
 Initialise linked list for major vector order in bulk storage.
bool presolve_expand_major (CoinBigIndex *majstrts, double *majels, int *minndxs, int *majlens, presolvehlink *majlinks, int nmaj, int k)
 Make sure a major-dimension vector k has room for one more coefficient.
bool presolve_expand_col (CoinBigIndex *mcstrt, double *colels, int *hrow, int *hincol, presolvehlink *clink, int ncols, int colx)
 Make sure a column (colx) in a column-major matrix has room for one more coefficient.
bool presolve_expand_row (CoinBigIndex *mrstrt, double *rowels, int *hcol, int *hinrow, presolvehlink *rlink, int nrows, int rowx)
 Make sure a row (rowx) in a row-major matrix has room for one more coefficient.
CoinBigIndex presolve_find_minor (int tgt, CoinBigIndex ks, CoinBigIndex ke, const int *minndxs)
 Find position of a minor index in a major vector.
CoinBigIndex presolve_find_row (int row, CoinBigIndex kcs, CoinBigIndex kce, const int *hrow)
 Find position of a row in a column in a column-major matrix.
CoinBigIndex presolve_find_minor1 (int tgt, CoinBigIndex ks, CoinBigIndex ke, const int *minndxs)
 Find position of a minor index in a major vector.
CoinBigIndex presolve_find_row1 (int row, CoinBigIndex kcs, CoinBigIndex kce, const int *hrow)
 Find position of a row in a column in a column-major matrix.
CoinBigIndex presolve_find_col1 (int col, CoinBigIndex krs, CoinBigIndex kre, const int *hcol)
 Find position of a column in a row in a row-major matrix.
void presolve_delete_from_major (int majndx, int minndx, const CoinBigIndex *majstrts, int *majlens, int *minndxs, double *els)
 Delete the entry for a minor index from a major vector.
void presolve_delete_from_col (int row, int col, const CoinBigIndex *mcstrt, int *hincol, int *hrow, double *colels)
 Delete the entry for row row from column col in a column-major matrix.
void presolve_delete_from_row (int row, int col, const CoinBigIndex *mrstrt, int *hinrow, int *hcol, double *rowels)
 Delete the entry for column col from row row in a row-major matrix.

Message handling

Uses the standard COIN approach: a default handler is installed, and the CoinPrePostsolveMatrix object takes responsibility for it. If the client replaces the handler with one of their own, it becomes their responsibility.



CoinMessageHandlerhandler_
 Message handler.
bool defaultHandler_
 Indicates if the current handler_ is default (true) or not (false).
CoinMessage messages_
 Standard COIN messages.
CoinMessageHandlermessageHandler () const
 Return message handler.
void setMessageHandler (CoinMessageHandler *handler)
 Set message handler.
CoinMessages messages () const
 Return messages.

Detailed Description

Collects all the information about the problem that is needed in both presolve and postsolve.

In a bit more detail, a column-major representation of the constraint matrix and upper and lower bounds on variables and constraints, plus row and column solutions, reduced costs, and status. There's also a set of arrays holding the original row and column numbers.

As presolve and postsolve transform the matrix, it will occasionally be necessary to expand the number of entries in a column. There are two aspects:

The first is addressed by the members ncols0_, nrows0_, and nelems0_. These should be set (via constructor parameters) to values large enough for the largest size taken on by the constraint system. Typically, this will be the size of the original constraint system.

The second is addressed by a generous allocation of extra (empty) space for the arrays used to hold coefficients and row indices. When columns must be expanded, they are moved into the empty space. When it is used up, the arrays are compacted. When compaction fails to produce sufficient space, presolve/postsolve will fail.

CoinPrePostsolveMatrix isn't really intended to be used `bare' --- the expectation is that it'll be used through CoinPresolveMatrix or CoinPostsolveMatrix. Some of the functions needed to load a problem are defined in the derived classes.

When CoinPresolve is applied when reoptimising, we need to be prepared to accept a basis and modify it to match the presolved problem (otherwise we throw away all the advantages of warm start for reoptimization). But I'm pretty well certain that the other solution components (acts_, rowduals_, sol_, and rcosts_) are only useful for postsolve (to save a final no-pivot call to the solver to regenerate the solution). But moving them from CoinPrePostsolveMatrix to CoinPostsolveMatrix would break a lot of code. It's not clear that it's worth it, and it would preclude upgrades to the presolve side that might make use of any of these. -- lh, 040806 --

Definition at line 232 of file CoinPresolveMatrix.hpp.


Member Enumeration Documentation

Enum for status of various sorts.

Matches CoinWarmStartBasis::Status and adds superBasic. Most code that converts between CoinPrePostsolveMatrix::Status and CoinWarmStartBasis::Status will break if this correspondence is broken.

superBasic is an unresolved problem: there's no analogue in CoinWarmStartBasis::Status.

Enumerator:
isFree 
basic 
atUpperBound 
atLowerBound 
superBasic 

Definition at line 280 of file CoinPresolveMatrix.hpp.


Constructor & Destructor Documentation

CoinPrePostsolveMatrix::CoinPrePostsolveMatrix ( int  ncols_alloc,
int  nrows_alloc,
CoinBigIndex  nelems_alloc 
)

`Native' constructor

This constructor creates an empty object which must then be loaded. On the other hand, it doesn't assume that the client is an OsiSolverInterface.

CoinPrePostsolveMatrix::CoinPrePostsolveMatrix ( const OsiSolverInterface si,
int  ncols_,
int  nrows_,
CoinBigIndex  nelems_ 
)

Generic OSI constructor.

See OSI code for the definition.

CoinPrePostsolveMatrix::CoinPrePostsolveMatrix ( const ClpSimplex si,
int  ncols_,
int  nrows_,
CoinBigIndex  nelems_,
double  bulkRatio 
)

ClpOsi constructor

See Clp code for the definition.

CoinPrePostsolveMatrix::~CoinPrePostsolveMatrix (  ) 

Destructor.


Member Function Documentation

void CoinPrePostsolveMatrix::setRowStatus ( int  sequence,
Status  status 
) [inline]

Set row status (i.e., status of artificial for this row).

Definition at line 296 of file CoinPresolveMatrix.hpp.

Status CoinPrePostsolveMatrix::getRowStatus ( int  sequence  )  const [inline]

Get row status.

Definition at line 303 of file CoinPresolveMatrix.hpp.

bool CoinPrePostsolveMatrix::rowIsBasic ( int  sequence  )  const [inline]

Check if artificial for this row is basic.

Definition at line 306 of file CoinPresolveMatrix.hpp.

void CoinPrePostsolveMatrix::setColumnStatus ( int  sequence,
Status  status 
) [inline]

Set column status (i.e., status of primal variable).

Definition at line 309 of file CoinPresolveMatrix.hpp.

Status CoinPrePostsolveMatrix::getColumnStatus ( int  sequence  )  const [inline]

Get column (structural variable) status.

Definition at line 349 of file CoinPresolveMatrix.hpp.

bool CoinPrePostsolveMatrix::columnIsBasic ( int  sequence  )  const [inline]

Check if column (structural variable) is basic.

Definition at line 352 of file CoinPresolveMatrix.hpp.

void CoinPrePostsolveMatrix::setRowStatusUsingValue ( int  iRow  ) 

Set status of row (artificial variable) to the correct nonbasic status given bounds and current value.

void CoinPrePostsolveMatrix::setColumnStatusUsingValue ( int  iColumn  ) 

Set status of column (structural variable) to the correct nonbasic status given bounds and current value.

void CoinPrePostsolveMatrix::setStructuralStatus ( const char *  strucStatus,
int  lenParam 
)

Set column (structural variable) status vector.

void CoinPrePostsolveMatrix::setArtificialStatus ( const char *  artifStatus,
int  lenParam 
)

Set row (artificial variable) status vector.

void CoinPrePostsolveMatrix::setStatus ( const CoinWarmStartBasis basis  ) 

Set the status of all variables from a basis.

CoinWarmStartBasis* CoinPrePostsolveMatrix::getStatus (  ) 

Get status in the form of a CoinWarmStartBasis.

const char* CoinPrePostsolveMatrix::columnStatusString ( int  j  )  const

Return a print string for status of a column (structural variable).

const char* CoinPrePostsolveMatrix::rowStatusString ( int  i  )  const

Return a print string for status of a row (artificial variable).

void CoinPrePostsolveMatrix::setObjOffset ( double  offset  ) 

Set the objective function offset for the original system.

void CoinPrePostsolveMatrix::setObjSense ( double  objSense  ) 

Set the objective sense (max/min).

Coded as 1.0 for min, -1.0 for max.

void CoinPrePostsolveMatrix::setPrimalTolerance ( double  primTol  ) 

Set the primal feasibility tolerance.

void CoinPrePostsolveMatrix::setDualTolerance ( double  dualTol  ) 

Set the dual feasibility tolerance.

void CoinPrePostsolveMatrix::setColLower ( const double *  colLower,
int  lenParam 
)

Set column lower bounds.

void CoinPrePostsolveMatrix::setColUpper ( const double *  colUpper,
int  lenParam 
)

Set column upper bounds.

void CoinPrePostsolveMatrix::setColSolution ( const double *  colSol,
int  lenParam 
)

Set column solution.

void CoinPrePostsolveMatrix::setCost ( const double *  cost,
int  lenParam 
)

Set objective coefficients.

void CoinPrePostsolveMatrix::setReducedCost ( const double *  redCost,
int  lenParam 
)

Set reduced costs.

void CoinPrePostsolveMatrix::setRowLower ( const double *  rowLower,
int  lenParam 
)

Set row lower bounds.

void CoinPrePostsolveMatrix::setRowUpper ( const double *  rowUpper,
int  lenParam 
)

Set row upper bounds.

void CoinPrePostsolveMatrix::setRowPrice ( const double *  rowSol,
int  lenParam 
)

Set row solution.

void CoinPrePostsolveMatrix::setRowActivity ( const double *  rowAct,
int  lenParam 
)

Set row activity.

int CoinPrePostsolveMatrix::getNumCols (  )  [inline]

Get current number of columns.

Definition at line 421 of file CoinPresolveMatrix.hpp.

int CoinPrePostsolveMatrix::getNumRows (  )  [inline]

Get current number of rows.

Definition at line 424 of file CoinPresolveMatrix.hpp.

int CoinPrePostsolveMatrix::getNumElems (  )  [inline]

Get current number of non-zero coefficients.

Definition at line 427 of file CoinPresolveMatrix.hpp.

const CoinBigIndex* CoinPrePostsolveMatrix::getColStarts (  )  const [inline]

Get column start vector for column-major packed matrix.

Definition at line 430 of file CoinPresolveMatrix.hpp.

const int* CoinPrePostsolveMatrix::getColLengths (  )  const [inline]

Get column length vector for column-major packed matrix.

Definition at line 433 of file CoinPresolveMatrix.hpp.

const int* CoinPrePostsolveMatrix::getRowIndicesByCol (  )  const [inline]

Get vector of row indices for column-major packed matrix.

Definition at line 436 of file CoinPresolveMatrix.hpp.

const double* CoinPrePostsolveMatrix::getElementsByCol (  )  const [inline]

Get vector of elements for column-major packed matrix.

Definition at line 439 of file CoinPresolveMatrix.hpp.

const double* CoinPrePostsolveMatrix::getColLower (  )  const [inline]

Get column lower bounds.

Definition at line 442 of file CoinPresolveMatrix.hpp.

const double* CoinPrePostsolveMatrix::getColUpper (  )  const [inline]

Get column upper bounds.

Definition at line 445 of file CoinPresolveMatrix.hpp.

const double* CoinPrePostsolveMatrix::getCost (  )  const [inline]

Get objective coefficients.

Definition at line 448 of file CoinPresolveMatrix.hpp.

const double* CoinPrePostsolveMatrix::getRowLower (  )  const [inline]

Get row lower bounds.

Definition at line 451 of file CoinPresolveMatrix.hpp.

const double* CoinPrePostsolveMatrix::getRowUpper (  )  const [inline]

Get row upper bounds.

Definition at line 454 of file CoinPresolveMatrix.hpp.

const double* CoinPrePostsolveMatrix::getColSolution (  )  const [inline]

Get column solution (primal variable values).

Definition at line 457 of file CoinPresolveMatrix.hpp.

const double* CoinPrePostsolveMatrix::getRowActivity (  )  const [inline]

Get row activity (constraint lhs values).

Definition at line 460 of file CoinPresolveMatrix.hpp.

const double* CoinPrePostsolveMatrix::getRowPrice (  )  const [inline]

Get row solution (dual variables).

Definition at line 463 of file CoinPresolveMatrix.hpp.

const double* CoinPrePostsolveMatrix::getReducedCost (  )  const [inline]

Get reduced costs.

Definition at line 466 of file CoinPresolveMatrix.hpp.

int CoinPrePostsolveMatrix::countEmptyCols (  )  [inline]

Count empty columns.

Definition at line 469 of file CoinPresolveMatrix.hpp.

CoinMessageHandler* CoinPrePostsolveMatrix::messageHandler (  )  const [inline]

Return message handler.

Definition at line 479 of file CoinPresolveMatrix.hpp.

void CoinPrePostsolveMatrix::setMessageHandler ( CoinMessageHandler handler  )  [inline]

Set message handler.

The client retains responsibility for the handler --- it will not be destroyed with the CoinPrePostsolveMatrix object.

Definition at line 486 of file CoinPresolveMatrix.hpp.

CoinMessages CoinPrePostsolveMatrix::messages (  )  const [inline]

Return messages.

Definition at line 492 of file CoinPresolveMatrix.hpp.


Member Data Documentation

current number of columns

Definition at line 507 of file CoinPresolveMatrix.hpp.

current number of rows

Definition at line 509 of file CoinPresolveMatrix.hpp.

current number of coefficients

Definition at line 511 of file CoinPresolveMatrix.hpp.

Allocated number of columns.

Definition at line 514 of file CoinPresolveMatrix.hpp.

Allocated number of rows.

Definition at line 516 of file CoinPresolveMatrix.hpp.

Allocated number of coefficients.

Definition at line 518 of file CoinPresolveMatrix.hpp.

Allocated size of bulk storage for row indices and coefficients.

This is the space allocated for hrow_ and colels_. This must be large enough to allow columns to be copied into empty space when they need to be expanded. For efficiency (to minimize the number of times the representation must be compressed) it's recommended that this be at least 2*nelems0_.

Definition at line 527 of file CoinPresolveMatrix.hpp.

Ratio of bulk0- to nelems0_.

Definition at line 529 of file CoinPresolveMatrix.hpp.

Vector of column start positions in hrow_, colels_.

Definition at line 541 of file CoinPresolveMatrix.hpp.

Vector of column lengths.

Definition at line 543 of file CoinPresolveMatrix.hpp.

Row indices (positional correspondence with colels_).

Definition at line 545 of file CoinPresolveMatrix.hpp.

Coefficients (positional correspondence with hrow_).

Definition at line 547 of file CoinPresolveMatrix.hpp.

Objective coefficients.

Definition at line 550 of file CoinPresolveMatrix.hpp.

Original objective offset.

Definition at line 552 of file CoinPresolveMatrix.hpp.

Column (primal variable) lower bounds.

Definition at line 555 of file CoinPresolveMatrix.hpp.

Column (primal variable) upper bounds.

Definition at line 557 of file CoinPresolveMatrix.hpp.

Row (constraint) lower bounds.

Definition at line 560 of file CoinPresolveMatrix.hpp.

Row (constraint) upper bounds.

Definition at line 562 of file CoinPresolveMatrix.hpp.

Original column numbers.

Definition at line 565 of file CoinPresolveMatrix.hpp.

Original row numbers.

Definition at line 567 of file CoinPresolveMatrix.hpp.

Primal feasibility tolerance.

Definition at line 570 of file CoinPresolveMatrix.hpp.

Dual feasibility tolerance.

Definition at line 572 of file CoinPresolveMatrix.hpp.

Maximization/minimization.

Definition at line 575 of file CoinPresolveMatrix.hpp.

Vector of primal variable values.

If sol_ exists, it is assumed that primal solution information should be updated and that acts_ also exists.

Definition at line 598 of file CoinPresolveMatrix.hpp.

Vector of dual variable values.

If rowduals_ exists, it is assumed that dual solution information should be updated and that rcosts_ also exists.

Definition at line 604 of file CoinPresolveMatrix.hpp.

Vector of constraint left-hand-side values (row activity).

Produced by evaluating constraints according to sol_. Updated iff sol_ exists.

Definition at line 610 of file CoinPresolveMatrix.hpp.

Vector of reduced costs.

Produced by evaluating dual constraints according to rowduals_. Updated iff rowduals_ exists.

Definition at line 616 of file CoinPresolveMatrix.hpp.

Status of primal variables.

Coded with CoinPrePostSolveMatrix::Status, one code per char. colstat_ and rowstat_ MUST be allocated as a single vector. This is to maintain compatibility with ClpPresolve and OsiPresolve, which do it this way.

Definition at line 624 of file CoinPresolveMatrix.hpp.

Status of constraints.

More accurately, the status of the logical variable associated with the constraint. Coded with CoinPrePostSolveMatrix::Status, one code per char. Note that this must be allocated as a single vector with colstat_.

Definition at line 632 of file CoinPresolveMatrix.hpp.

Message handler.

Definition at line 644 of file CoinPresolveMatrix.hpp.

Indicates if the current handler_ is default (true) or not (false).

Definition at line 646 of file CoinPresolveMatrix.hpp.

Standard COIN messages.

Definition at line 648 of file CoinPresolveMatrix.hpp.


The documentation for this class was generated from the following file:

Generated on 15 Mar 2015 for Coin-All by  doxygen 1.6.1