- During postsolve, the constraint system is expected to grow as the smaller presolved system is transformed back to the original system.
- During both pre- and postsolve, transforms can increase the number of coefficients in a row or column. (See the variable substitution, doubleton, and tripleton transforms.)

int pre = link[i].pre; PRESOLVE_REMOVE_LINK(link,i); PRESOLVE_INSERT_LINK(link,j,pre);But, this routine will work even if i happens to be first in the order. */ inline void PRESOLVE_MOVE_LINK(presolvehlink *link, int i, int j) { int ipre = link[i].pre; int isuc = link[i].suc; if (ipre >= 0) { link[ipre].suc = j; } if (isuc >= 0) { link[isuc].pre = j; } link[i].pre = NO_LINK, link[i].suc = NO_LINK; } /*! \class CoinPresolveMatrix \brief Augments CoinPrePostsolveMatrix with information about the problem that is only needed during presolve. For problem manipulation, this class adds a row-major matrix representation, linked lists that allow for easy manipulation of the matrix when applying presolve transforms, and vectors to track row and column processing status (changed, needs further processing, change prohibited) For problem representation, this class adds information about variable type (integer or continuous), an objective offset, and a feasibility tolerance.

- 0x01: Column has changed
- 0x02: preprocessing prohibited
- 0x04: Column has been used
- 0x08: Column originally had infinite ub

- 0x01: Row has changed
- 0x02: preprocessing prohibited
- 0x04: Row has been used

occupy position kp in their arrays, then the position of
the next coefficient a is found as kq = link[kp].
This threaded representation allows for efficient expansion of columns as
rows are reintroduced during postsolve transformations. The basic packed
structures are allocated to the expected size of the postsolved matrix,
and as new coefficients are added, their location is simply added to the
thread for the column.
There is no provision to convert the threaded representation to a packed
representation. In the context of postsolve, it's not required. (You did
keep a copy of the original matrix, eh?)
The constructors that take an OSI or ClpSimplex as a parameter really should
not be here, but for historical reasons they will likely remain for the
forseeable future. -- lh, 111202 --
*/
class CoinPostsolveMatrix : public CoinPrePostsolveMatrix
{
public:
/*! \brief `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.
*/
CoinPostsolveMatrix(int ncols_alloc, int nrows_alloc,
CoinBigIndex nelems_alloc) ;
/*! \brief Clp OSI constructor
See Clp code for the definition.
*/
CoinPostsolveMatrix(ClpSimplex * si,
int ncols0,
int nrows0,
CoinBigIndex nelems0,
double maxmin_,
// end prepost members
double *sol,
double *acts,
unsigned char *colstat,
unsigned char *rowstat);
/*! \brief Generic OSI constructor
See OSI code for the definition.
*/
CoinPostsolveMatrix(OsiSolverInterface * si,
int ncols0,
int nrows0,
CoinBigIndex nelems0,
double maxmin_,
// end prepost members
double *sol,
double *acts,
unsigned char *colstat,
unsigned char *rowstat);
/*! \brief Load an empty CoinPostsolveMatrix from a CoinPresolveMatrix
This routine transfers the contents of the CoinPrePostsolveMatrix
object from the CoinPresolveMatrix object to the CoinPostsolveMatrix
object and completes initialisation of the CoinPostsolveMatrix object.
The empty shell of the CoinPresolveMatrix object is destroyed.
The routine expects an empty CoinPostsolveMatrix object. If handed a loaded
object, a lot of memory will leak.
*/
void assignPresolveToPostsolve (CoinPresolveMatrix *&preObj) ;
/// Destructor
~CoinPostsolveMatrix();
/*! \name Column thread structures
As mentioned in the class documentation, the entries for a given column
do not necessarily occupy a contiguous block of space. The #link_ array
is used to maintain the threading. There is one thread for each column,
and a single thread for all free entries in #hrow_ and #colels_.
The allocated size of #link_ must be at least as large as the allocated
size of #hrow_ and #colels_.
*/
//@{
/*! \brief First entry in free entries thread */
CoinBigIndex free_list_;
/// Allocated size of #link_
int maxlink_;
/*! \brief Thread array
Within a thread, link_[k] points to the next entry in the thread.
*/
CoinBigIndex *link_;
//@}
/*! \name Debugging aids
These arrays are allocated only when CoinPresolve is compiled with
PRESOLVE_DEBUG defined. They hold codes which track the reason that
a column or row is added to the problem during postsolve.
*/
//@{
char *cdone_;
char *rdone_;
//@}
/// debug
void check_nbasic();
};
/*! \defgroup MtxManip Presolve Matrix Manipulation Functions
Functions to work with the loosely packed and threaded packed matrix
structures used during presolve and postsolve.
*/
//@{
/*! \relates CoinPrePostsolveMatrix
\brief Initialise linked list for major vector order in bulk storage
*/
void presolve_make_memlists(/*CoinBigIndex *starts,*/ int *lengths,
presolvehlink *link, int n);
/*! \relates CoinPrePostsolveMatrix
\brief Make sure a major-dimension vector k has room for one more
coefficient.
You can use this directly, or use the inline wrappers presolve_expand_col
and presolve_expand_row
*/
bool presolve_expand_major(CoinBigIndex *majstrts, double *majels,
int *minndxs, int *majlens,
presolvehlink *majlinks, int nmaj, int k) ;
/*! \relates CoinPrePostsolveMatrix
\brief Make sure a column (colx) in a column-major matrix has room for
one more coefficient
*/
inline bool presolve_expand_col(CoinBigIndex *mcstrt, double *colels,
int *hrow, int *hincol,
presolvehlink *clink, int ncols, int colx)
{ return presolve_expand_major(mcstrt,colels,
hrow,hincol,clink,ncols,colx) ; }
/*! \relates CoinPrePostsolveMatrix
\brief Make sure a row (rowx) in a row-major matrix has room for one
more coefficient
*/
inline bool presolve_expand_row(CoinBigIndex *mrstrt, double *rowels,
int *hcol, int *hinrow,
presolvehlink *rlink, int nrows, int rowx)
{ return presolve_expand_major(mrstrt,rowels,
hcol,hinrow,rlink,nrows,rowx) ; }
/*! \relates CoinPrePostsolveMatrix
\brief Find position of a minor index in a major vector.
The routine returns the position \c k in \p minndxs for the specified
minor index \p tgt. It will abort if the entry does not exist. Can be
used directly or via the inline wrappers presolve_find_row and
presolve_find_col.
*/
inline CoinBigIndex presolve_find_minor(int tgt,
CoinBigIndex ks, CoinBigIndex ke,
const int *minndxs)
{ CoinBigIndex k ;
for (k = ks ; k < ke ; k++)
#ifndef NDEBUG
{ if (minndxs[k] == tgt)
return (k) ; }
DIE("FIND_MINOR") ;
abort () ; return -1;
#else
{ if (minndxs[k] == tgt)
break ; }
return (k) ;
#endif
}
/*! \relates CoinPrePostsolveMatrix
\brief Find position of a row in a column in a column-major matrix.
The routine returns the position \c k in \p hrow for the specified \p row.
It will abort if the entry does not exist.
*/
inline CoinBigIndex presolve_find_row(int row, CoinBigIndex kcs,
CoinBigIndex kce, const int *hrow)
{ return presolve_find_minor(row,kcs,kce,hrow) ; }
/*! \relates CoinPostsolveMatrix
\brief Find position of a column in a row in a row-major matrix.
The routine returns the position \c k in \p hcol for the specified \p col.
It will abort if the entry does not exist.
*/
inline CoinBigIndex presolve_find_col(int col, CoinBigIndex krs,
CoinBigIndex kre, const int *hcol)
{ return presolve_find_minor(col,krs,kre,hcol) ; }
/*! \relates CoinPrePostsolveMatrix
\brief Find position of a minor index in a major vector.
The routine returns the position \c k in \p minndxs for the specified
minor index \p tgt. A return value of \p ke means the entry does not
exist. Can be used directly or via the inline wrappers
presolve_find_row1 and presolve_find_col1.
*/
CoinBigIndex presolve_find_minor1(int tgt, CoinBigIndex ks, CoinBigIndex ke,
const int *minndxs);
/*! \relates CoinPrePostsolveMatrix
\brief Find position of a row in a column in a column-major matrix.
The routine returns the position \c k in \p hrow for the specified \p row.
A return value of \p kce means the entry does not exist.
*/
inline CoinBigIndex presolve_find_row1(int row, CoinBigIndex kcs,
CoinBigIndex kce, const int *hrow)
{ return presolve_find_minor1(row,kcs,kce,hrow) ; }
/*! \relates CoinPrePostsolveMatrix
\brief Find position of a column in a row in a row-major matrix.
The routine returns the position \c k in \p hcol for the specified \p col.
A return value of \p kre means the entry does not exist.
*/
inline CoinBigIndex presolve_find_col1(int col, CoinBigIndex krs,
CoinBigIndex kre, const int *hcol)
{ return presolve_find_minor1(col,krs,kre,hcol) ; }
/*! \relates CoinPostsolveMatrix
\brief Find position of a minor index in a major vector in a threaded
matrix.
The routine returns the position \c k in \p minndxs for the specified
minor index \p tgt. It will abort if the entry does not exist. Can be
used directly or via the inline wrapper presolve_find_row2.
*/
CoinBigIndex presolve_find_minor2(int tgt, CoinBigIndex ks, int majlen,
const int *minndxs,
const CoinBigIndex *majlinks) ;
/*! \relates CoinPostsolveMatrix
\brief Find position of a row in a column in a column-major threaded
matrix.
The routine returns the position \c k in \p hrow for the specified \p row.
It will abort if the entry does not exist.
*/
inline CoinBigIndex presolve_find_row2(int row, CoinBigIndex kcs, int collen,
const int *hrow,
const CoinBigIndex *clinks)
{ return presolve_find_minor2(row,kcs,collen,hrow,clinks) ; }
/*! \relates CoinPostsolveMatrix
\brief Find position of a minor index in a major vector in a threaded
matrix.
The routine returns the position \c k in \p minndxs for the specified
minor index \p tgt. It will return -1 if the entry does not exist.
Can be used directly or via the inline wrappers presolve_find_row3.
*/
CoinBigIndex presolve_find_minor3(int tgt, CoinBigIndex ks, int majlen,
const int *minndxs,
const CoinBigIndex *majlinks) ;
/*! \relates CoinPostsolveMatrix
\brief Find position of a row in a column in a column-major threaded
matrix.
The routine returns the position \c k in \p hrow for the specified \p row.
It will return -1 if the entry does not exist.
*/
inline CoinBigIndex presolve_find_row3(int row, CoinBigIndex kcs, int collen,
const int *hrow,
const CoinBigIndex *clinks)
{ return presolve_find_minor3(row,kcs,collen,hrow,clinks) ; }
/*! \relates CoinPrePostsolveMatrix
\brief Delete the entry for a minor index from a major vector.
Deletes the entry for \p minndx from the major vector \p majndx.
Specifically, the relevant entries are removed from the minor index
(\p minndxs) and coefficient (\p els) arrays and the vector length (\p
majlens) is decremented. Loose packing is maintained by swapping the last
entry in the row into the position occupied by the deleted entry.
*/
inline void presolve_delete_from_major(int majndx, int minndx,
const CoinBigIndex *majstrts,
int *majlens, int *minndxs, double *els)
{
const CoinBigIndex ks = majstrts[majndx] ;
const CoinBigIndex ke = ks+majlens[majndx] ;
const CoinBigIndex kmi = presolve_find_minor(minndx,ks,ke,minndxs) ;
minndxs[kmi] = minndxs[ke-1] ;
els[kmi] = els[ke-1] ;
majlens[majndx]-- ;
return ;
}
/*! \relates CoinPrePostsolveMatrix
\brief Delete marked entries
Removes the entries specified in \p marked, compressing the major vector
to maintain loose packing. \p marked is cleared in the process.
*/
inline void presolve_delete_many_from_major(int majndx, char *marked,
const CoinBigIndex *majstrts,
int *majlens, int *minndxs, double *els)
{
const CoinBigIndex ks = majstrts[majndx] ;
const CoinBigIndex ke = ks+majlens[majndx] ;
CoinBigIndex put = ks ;
for (CoinBigIndex k = ks ; k < ke ; k++) {
int iMinor = minndxs[k] ;
if (!marked[iMinor]) {
minndxs[put] = iMinor ;
els[put++] = els[k] ;
} else {
marked[iMinor] = 0 ;
}
}
majlens[majndx] = put-ks ;
return ;
}
/*! \relates CoinPrePostsolveMatrix
\brief Delete the entry for row \p row from column \p col in a
column-major matrix
Deletes the entry for \p row from the major vector for \p col.
Specifically, the relevant entries are removed from the row index (\p
hrow) and coefficient (\p colels) arrays and the vector length (\p
hincol) is decremented. Loose packing is maintained by swapping the last
entry in the row into the position occupied by the deleted entry.
*/
inline void presolve_delete_from_col(int row, int col,
const CoinBigIndex *mcstrt,
int *hincol, int *hrow, double *colels)
{ presolve_delete_from_major(col,row,mcstrt,hincol,hrow,colels) ; }
/*! \relates CoinPrePostsolveMatrix
\brief Delete the entry for column \p col from row \p row in a
row-major matrix
Deletes the entry for \p col from the major vector for \p row.
Specifically, the relevant entries are removed from the column index (\p
hcol) and coefficient (\p rowels) arrays and the vector length (\p
hinrow) is decremented. Loose packing is maintained by swapping the last
entry in the column into the position occupied by the deleted entry.
*/
inline void presolve_delete_from_row(int row, int col,
const CoinBigIndex *mrstrt,
int *hinrow, int *hcol, double *rowels)
{ presolve_delete_from_major(row,col,mrstrt,hinrow,hcol,rowels) ; }
/*! \relates CoinPostsolveMatrix
\brief Delete the entry for a minor index from a major vector in a
threaded matrix.
Deletes the entry for \p minndx from the major vector \p majndx.
Specifically, the relevant entries are removed from the minor index (\p
minndxs) and coefficient (\p els) arrays and the vector length (\p
majlens) is decremented. The thread for the major vector is relinked
around the deleted entry and the space is returned to the free list.
*/
void presolve_delete_from_major2 (int majndx, int minndx,
CoinBigIndex *majstrts, int *majlens,
int *minndxs, int *majlinks,
CoinBigIndex *free_listp) ;
/*! \relates CoinPostsolveMatrix
\brief Delete the entry for row \p row from column \p col in a
column-major threaded matrix
Deletes the entry for \p row from the major vector for \p col.
Specifically, the relevant entries are removed from the row index (\p
hrow) and coefficient (\p colels) arrays and the vector length (\p
hincol) is decremented. The thread for the major vector is relinked
around the deleted entry and the space is returned to the free list.
*/
inline void presolve_delete_from_col2(int row, int col, CoinBigIndex *mcstrt,
int *hincol, int *hrow,
int *clinks, CoinBigIndex *free_listp)
{ presolve_delete_from_major2(col,row,mcstrt,hincol,hrow,clinks,free_listp) ; }
//@}
/*! \defgroup PresolveUtilities Presolve Utility Functions
Utilities used by multiple presolve transform objects.
*/
//@{
/*! \brief Duplicate a major-dimension vector; optionally omit the entry
with minor index \p tgt.
Designed to copy a major-dimension vector from the paired coefficient
(\p elems) and minor index (\p indices) arrays used in the standard
packed matrix representation. Copies \p length entries starting at
\p offset.
If \p tgt is specified, the entry with minor index == \p tgt is
omitted from the copy.
*/
double *presolve_dupmajor(const double *elems, const int *indices,
int length, CoinBigIndex offset, int tgt = -1);
/// Initialize a vector with random numbers
void coin_init_random_vec(double *work, int n);
//@}
#endif