Go to the documentation of this file.
6 #ifndef CoinPresolveMatrix_H
7 #define CoinPresolveMatrix_H
20 #if PRESOLVE_DEBUG > 0
36 #define deleteAction(array,type) delete [] ((type) array)
38 #define deleteAction(array,type) delete [] array
45 #if PRESOLVE_DEBUG > 0 || PRESOLVE_CONSISTENCY > 0
47 #define PRESOLVE_STMT(s) s
49 #define PRESOLVEASSERT(x) \
50 ((x) ? 1 : ((std::cerr << "FAILED ASSERTION at line " \
51 << __LINE__ << ": " #x "\n"), abort(), 0))
53 inline void DIE(
const char *s) { std::cout << s ; abort() ; }
65 #define PRESENT_IN_REDUCED '\377'
69 #define PRESOLVEASSERT(x) {}
70 #define PRESOLVE_STMT(s) {}
72 inline void DIE(
const char *) {}
79 #ifndef PRESOLVE_DETAIL
80 #define PRESOLVE_DETAIL_PRINT(s) {}
82 #define PRESOLVE_DETAIL_PRINT(s) s
97 #define PRESOLVE_INF COIN_DBL_MAX
98 #define PRESOLVE_SMALL_INF 1.0e20
100 #define PRESOLVEFINITE(n) (-PRESOLVE_INF < (n) && (n) < PRESOLVE_INF)
165 {
throw CoinError(error, ps_routine,
"CoinPresolve"); }
181 {
next = nextAction;}
187 virtual const char *
name()
const = 0;
203 class OsiSolverInterface;
337 unsigned char & st_byte =
rowstat_[sequence];
338 st_byte =
static_cast<unsigned char>(st_byte & (~7)) ;
339 st_byte =
static_cast<unsigned char>(st_byte | status) ;
350 unsigned char & st_byte =
colstat_[sequence];
351 st_byte =
static_cast<unsigned char>(st_byte & (~7)) ;
352 st_byte =
static_cast<unsigned char>(st_byte | status) ;
354 # ifdef PRESOLVE_DEBUG
358 { std::cout <<
"Bad status: Var " << sequence
359 <<
" isFree, lb = " <<
clo_[sequence]
360 <<
", ub = " <<
cup_[sequence] << std::endl ; }
366 { std::cout <<
"Bad status: Var " << sequence
367 <<
" atUpperBound, lb = " <<
clo_[sequence]
368 <<
", ub = " <<
cup_[sequence] << std::endl ; }
372 { std::cout <<
"Bad status: Var " << sequence
373 <<
" atLowerBound, lb = " <<
clo_[sequence]
374 <<
", ub = " <<
cup_[sequence] << std::endl ; }
378 { std::cout <<
"Bad status: Var " << sequence
379 <<
" superBasic, lb = " <<
clo_[sequence]
380 <<
", ub = " <<
cup_[sequence] << std::endl ; }
446 void setCost(
const double *cost,
int lenParam) ;
512 for (
int i = 0 ; i <
ncols_ ; i++)
if (
hincol_[i] == 0) empty++ ;
743 #define NO_LINK -66666666
752 int ipre = link[i].
pre;
753 int isuc = link[i].
suc;
755 link[ipre].
suc = isuc;
758 link[isuc].
pre = ipre;
770 int isuc = link[j].
suc;
792 int ipre = link[i].
pre;
793 int isuc = link[i].
suc;
862 double nonLinearVariable,
877 OsiSolverInterface * si,
882 double nonLinearVariable,
883 const char * prohibited,
915 for (
int i = 0 ; i <
nrows_ ; i++)
if (
hinrow_[i] == 0) empty++ ;
925 integerType_[i] =
static_cast<unsigned char>(variableType) ; }
972 {
return (
false) ; } }
1008 # if PRESOLVE_DEBUG > 2
1009 assert(fabs(change_amount)<1.0e50) ;
1451 unsigned char *colstat,
1452 unsigned char *rowstat);
1470 unsigned char *colstat,
1471 unsigned char *rowstat);
1551 int *minndxs,
int *majlens,
1560 int *hrow,
int *hincol,
1563 hrow,hincol,clink,ncols,colx) ; }
1571 int *hcol,
int *hinrow,
1574 hcol,hinrow,rlink,nrows,rowx) ; }
1589 for (k = ks ; k < ke ; k++)
1591 {
if (minndxs[k] == tgt)
1595 abort () ;
return -1;
1597 {
if (minndxs[k] == tgt)
1633 const int *minndxs);
1714 int *majlens,
int *minndxs,
double *els)
1721 minndxs[kmi] = minndxs[ke-1] ;
1722 els[kmi] = els[ke-1] ;
1736 int *majlens,
int *minndxs,
double *els)
1742 int iMinor = minndxs[k] ;
1743 if (!marked[iMinor]) {
1744 minndxs[put] = iMinor ;
1745 els[put++] = els[k] ;
1747 marked[iMinor] = 0 ;
1750 majlens[majndx] = put-ks ;
1766 int *hincol,
int *hrow,
double *colels)
1781 int *hinrow,
int *hcol,
double *rowels)
1796 int *minndxs,
int *majlinks,
1810 int *hincol,
int *hrow,
int getNumRows() const
Get current number of rows.
void unsetRowUsed(int i)
Mark row as unused.
void setVariableType(bool allIntegers, int lenParam)
Set the type of all variables.
void PRESOLVE_INSERT_LINK(presolvehlink *link, int i, int j)
insert vector i after vector j
void setColChanged(int i)
Mark column as changed.
int * hinrow_
Vector of row lengths.
void setColumnStatusUsingValue(int iColumn)
Set status of column (structural variable) to the correct nonbasic status given bounds and current va...
void setRowStatus(int sequence, Status status)
Set row status (i.e., status of artificial for this row)
bool colProhibited(int i) const
Test if column is eligible for preprocessing.
int * rowsToDo_
Input list of rows to process.
void statistics()
Say we want statistics - also set time.
const int * getRowIndicesByCol() const
Get vector of row indices for column-major packed matrix.
bool colInfinite(int i) const
Has column infinite ub (originally)
const double * getRowActivity() const
Get row activity (constraint lhs values)
const double * getRowLower() const
Get row lower bounds.
const double * getElementsByRow() const
Get vector of elements for row-major packed matrix.
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.
void setArtificialStatus(const char *artifStatus, int lenParam)
Set row (artificial variable) status vector.
double ztoldj_
Dual feasibility tolerance.
void initializeStuff()
Allocate scratch arrays.
void initRowsToDo()
Initialise the row ToDo lists.
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.
double * sumDown_
Work array for sum of finite contributions to row lhs lower bound.
presolvehlink * clink_
Linked list for the column-major representation.
void setPrimalTolerance(double primTol)
Set the primal feasibility tolerance.
const double * getColLower() const
Get column lower bounds.
void initColsToDo()
Initialise the column ToDo lists.
void setVariableType(int i, int variableType)
Set variable type information for a single variable.
void presolve_delete_many_from_major(int majndx, char *marked, const CoinBigIndex *majstrts, int *majlens, int *minndxs, double *els)
Delete marked entries.
int numberColsToDo()
Return the number of columns on the colsToDo_ list.
double * clo_
Column (primal variable) lower bounds.
This file contains the enum for the standard set of Coin messages and a class definition whose sole p...
virtual ~CoinPresolveAction()
Virtual destructor.
CoinMessages messages() const
Return messages.
void setStatus(const CoinWarmStartBasis *basis)
Set the status of all variables from a basis.
int * colsToDo_
Input list of columns to process.
int * usefulColumnInt_
Preallocated scratch work array, 2*ncols_.
double * acts_
Vector of constraint left-hand-side values (row activity)
CoinBigIndex presolve_find_col(int col, CoinBigIndex krs, CoinBigIndex kre, const int *hcol)
Find position of a column in a row in a row-major matrix.
void presolve_make_memlists(int *lengths, presolvehlink *link, int n)
Initialise linked list for major vector order in bulk storage.
const double * getReducedCost() const
Get reduced costs.
void setColLower(const double *colLower, int lenParam)
Set column lower bounds.
bool anyProhibited_
Flag to say if any rows or columns are marked as prohibited.
CoinMessageHandler * messageHandler() const
Return message handler.
void coin_init_random_vec(double *work, int n)
Initialize a vector with random numbers.
~CoinPostsolveMatrix()
Destructor.
double startTime_
Start time of presolve.
CoinPresolveAction(const CoinPresolveAction *next)
Construct a postsolve object and add it to the transformation list.
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.
const int * getColIndicesByRow() const
Get vector of column indices for row-major packed matrix.
void setAnyInteger(bool anyInteger=true)
Set a flag for presence (true) or absence (false) of integer variables.
CoinBigIndex * link_
Thread array.
Class to hold and manipulate an array of massaged messages.
const double * getRowPrice() const
Get row solution (dual variables)
unsigned char * integerType_
Tracks integrality of columns (1 for integer, 0 for continuous)
bool anyInteger_
Flag to say if any variables are integer.
void setRowUpper(const double *rowUpper, int lenParam)
Set row upper bounds.
double * usefulColumnDouble_
Preallocated scratch work array, ncols_.
The standard set of Coin messages.
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.
#define PRESOLVE_INF
The usual finite infinity.
unsigned char * colChanged_
Column change status information.
void setRowLower(const double *rowLower, int lenParam)
Set row lower bounds.
void setRowPrice(const double *rowSol, int lenParam)
Set row solution.
double * randomNumber_
Array of random numbers (max row,column)
CoinBigIndex presolve_find_minor3(int tgt, CoinBigIndex ks, int majlen, const int *minndxs, const CoinBigIndex *majlinks)
Find position of a minor index in a major vector in a threaded matrix.
void addCol(int i)
Mark column as changed and add to list of columns to process next.
bool defaultHandler_
Indicates if the current handler_ is default (true) or not (false).
unsigned char * colstat_
Status of primal variables.
int status_
Output status: 0 = feasible, 1 = infeasible, 2 = unbounded.
bool anyInteger() const
Check if there are any integer variables.
void setColUpper(const double *colUpper, int lenParam)
Set column upper bounds.
The default COIN simplex (basis-oriented) warm start class.
void setPresolveOptions(int value)
Sets any special options (see presolveOptions_)
double dobias_
Objective function offset introduced during presolve.
Links to aid in packed matrix modification.
double originalOffset_
Original objective offset.
int presolveOptions() const
Picks up any special options.
int ncols_
current number of columns
CoinPrePostsolveMatrix(const OsiSolverInterface *si, int ncols_, int nrows_, CoinBigIndex nelems_)
Generic OSI constructor.
double feasibilityTolerance()
Return feasibility tolerance.
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.
int * originalRow_
Original row numbers.
double * rlo_
Row (constraint) lower bounds.
void setObjOffset(double offset)
Set the objective function offset for the original system.
void unsetColUsed(int i)
Mark column as unused.
int stepRowsToDo()
Step row ToDo lists.
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.
const CoinPresolveAction * next
The next presolve transformation.
presolvehlink * rlink_
Linked list for the row-major representation.
CoinMessageHandler * handler_
Message handler.
bool rowIsBasic(int sequence) const
Check if artificial for this row is basic.
void setRowActivity(const double *rowAct, int lenParam)
Set row activity.
unsigned char * rowChanged_
Row change status information.
const double * getCost() const
Get objective coefficients.
bool colProhibited2(int i) const
Test if column is eligible for preprocessing.
double * rowduals_
Vector of dual variable values.
double * presolve_dupmajor(const double *elems, const int *indices, int length, CoinBigIndex offset, int tgt=-1)
Duplicate a major-dimension vector; optionally omit the entry with minor index tgt.
~CoinPresolveMatrix()
Destructor.
int pass_
Presolve pass number.
bool columnIsBasic(int sequence) const
Check if column (structural variable) is basic.
void setColInfinite(int i)
Mark column as infinite ub (originally)
friend void assignPresolveToPostsolve(CoinPresolveMatrix *&preObj)
Initialize a CoinPostsolveMatrix object, destroying the CoinPresolveMatrix object.
int getNumCols() const
Get current number of columns.
CoinBigIndex presolve_find_row2(int row, CoinBigIndex kcs, int collen, const int *hrow, const CoinBigIndex *clinks)
Find position of a row in a column in a column-major threaded matrix.
Augments CoinPrePostsolveMatrix with information about the problem that is only needed during postsol...
CoinPostsolveMatrix(ClpSimplex *si, int ncols0, int nrows0, CoinBigIndex nelems0, double maxmin_, double *sol, double *acts, unsigned char *colstat, unsigned char *rowstat)
Clp OSI constructor.
void deleteStuff()
Free scratch arrays.
void setStatus(int status)
Set problem status.
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 setAnyProhibited(bool val=true)
Set a flag for presence of prohibited rows or columns.
int nrows0_
Allocated number of rows.
void setColProhibited(int i)
Mark column as ineligible for preprocessing.
void addRow(int i)
Mark row as changed and add to list of rows to process next.
CoinWarmStartBasis * getStatus()
Get status in the form of a CoinWarmStartBasis.
void setRowStatusUsingValue(int iRow)
Set status of row (artificial variable) to the correct nonbasic status given bounds and current value...
double * usefulRowDouble_
Preallocated scratch work array, 2*nrows_.
double * sol_
Vector of primal variable values.
void setFeasibilityTolerance(double val)
Set feasibility tolerance.
CoinPresolveMatrix(int ncols0, double maxmin, ClpSimplex *si, int nrows, CoinBigIndex nelems, bool doStatus, double nonLinearVariable, double bulkRatio)
Clp OSI constructor.
CoinPrePostsolveMatrix(int ncols_alloc, int nrows_alloc, CoinBigIndex nelems_alloc)
‘Native’ constructor
unsigned char * rowstat_
Status of constraints.
Base class for message handling.
int stepColsToDo()
Step column ToDo lists.
void setVariableType(const unsigned char *variableType, int lenParam)
Set variable type information for all variables.
bool rowProhibited2(int i) const
Test if row is eligible for preprocessing.
double * sumUp_
Work array for sum of finite contributions to row lhs upper bound.
void presolve_delete_from_major2(int majndx, int minndx, CoinBigIndex *majstrts, int *majlens, int *minndxs, int *majlinks, CoinBigIndex *free_listp)
Delete the entry for a minor index from a major vector in a threaded matrix.
double * rcosts_
Vector of reduced costs.
void PRESOLVE_REMOVE_LINK(presolvehlink *link, int i)
unlink vector i
double * colels_
Coefficients (positional correspondence with hrow_)
int * nextRowsToDo_
Output list of rows to process next.
const double * getRowUpper() const
Get row upper bounds.
void setRowProhibited(int i)
Mark row as ineligible for preprocessing.
int numberNextColsToDo_
Length of nextColsToDo_.
Status getColumnStatus(int sequence) const
Get column (structural variable) status.
int * infiniteUp_
Work array for count of infinite contributions to row lhs upper bound.
CoinBigIndex * mrstrt_
Vector of row start positions in #hcol, rowels_.
virtual const char * name() const =0
A name for debug printing.
int maxlink_
Allocated size of link_.
int * infiniteDown_
Work array for count of infinite contributions to row lhs lower bound.
Abstract base class of all presolve routines.
Collects all the information about the problem that is needed in both presolve and postsolve.
void setReducedCost(const double *redCost, int lenParam)
Set reduced costs.
const CoinBigIndex * getRowStarts() const
Get row start vector for row-major packed matrix.
void setMessageHandler(CoinMessageHandler *handler)
Set message handler.
CoinBigIndex * mcstrt_
Vector of column start positions in hrow_, colels_.
void setDualTolerance(double dualTol)
Set the dual feasibility tolerance.
CoinBigIndex nelems0_
Allocated number of coefficients.
static void throwCoinError(const char *error, const char *ps_routine)
Stub routine to throw exceptions.
int getNumElems() const
Get current number of non-zero coefficients.
int numberRowsToDo_
Length of rowsToDo_.
const double * getColUpper() const
Get column upper bounds.
bool colUsed(int i) const
Test if column is marked as used.
const char * statusName(CoinPrePostsolveMatrix::Status status)
Generate a print string for a status code.
void setObjSense(double objSense)
Set the objective sense (max/min)
Status
Enum for status of various sorts.
const double * getColSolution() const
Get column solution (primal variable values)
void setCost(const double *cost, int lenParam)
Set objective coefficients.
void setColUsed(int i)
Mark column as used.
const char * columnStatusString(int j) const
Return a print string for status of a column (structural variable)
int status()
Returns problem status (0 = feasible, 1 = infeasible, 2 = unbounded)
bool anyProhibited() const
Check if there are any prohibited rows or columns.
double * cost_
Objective coefficients.
double maxmin_
Maximization/minimization.
Sparse Matrix Base Class.
void PRESOLVE_MOVE_LINK(presolvehlink *link, int i, int j)
relink vector j in place of vector i
CoinMessage messages_
Standard COIN messages.
CoinPresolveMatrix(int ncols_alloc, int nrows_alloc, CoinBigIndex nelems_alloc)
‘Native’ constructor
int countEmptyRows()
Count number of empty rows.
void unsetColChanged(int i)
Mark column as not changed.
CoinPrePostsolveMatrix(const ClpSimplex *si, int ncols_, int nrows_, CoinBigIndex nelems_, double bulkRatio)
ClpOsi constructor.
void assignPresolveToPostsolve(CoinPresolveMatrix *&preObj)
Load an empty CoinPostsolveMatrix from a CoinPresolveMatrix.
int * hcol_
Column indices (positional correspondence with rowels_)
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.
int presolveOptions_
Fine control over presolve actions.
Status getRowStatus(int sequence) const
Get row status.
void update_model(OsiSolverInterface *si, int nrows0, int ncols0, CoinBigIndex nelems0)
Update the model held by a generic OSI.
double ztolzb_
Primal feasibility tolerance.
const double ZTOLDP2
Alternate zero tolerance.
CoinPresolveMatrix(int ncols0, double maxmin, OsiSolverInterface *si, int nrows, CoinBigIndex nelems, bool doStatus, double nonLinearVariable, const char *prohibited, const char *rowProhibited=NULL)
Generic OSI constructor.
double * rup_
Row (constraint) upper bounds.
const char * rowStatusString(int i) const
Return a print string for status of a row (artificial variable)
double * rowels_
Coefficients (positional correspondence with hcol_)
void setMaximumSubstitutionLevel(int level)
Set Maximum substitution level (normally 3)
const int * getColLengths() const
Get column length vector for column-major packed matrix.
int * originalColumn_
Original column numbers.
bool colChanged(int i) const
Has column been changed?
CoinBigIndex presolve_find_minor2(int tgt, CoinBigIndex ks, int majlen, const int *minndxs, const CoinBigIndex *majlinks)
Find position of a minor index in a major vector in a threaded matrix.
void setStructuralStatus(const char *strucStatus, int lenParam)
Set column (structural variable) status vector.
void setColSolution(const double *colSol, int lenParam)
Set column solution.
bool tuning_
Print statistics for tuning.
int * nextColsToDo_
Output list of columns to process next.
int numberNextRowsToDo_
Length of nextRowsToDo_.
void unsetColInfinite(int i)
Mark column as not infinite ub (originally)
Error Class thrown by an exception.
void unsetRowChanged(int i)
Mark row as not changed.
void change_bias(double change_amount)
Adjust objective function constant offset.
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.
void setMatrix(const CoinPackedMatrix *mtx)
Load the cofficient matrix.
const CoinBigIndex * getColStarts() const
Get column start vector for column-major packed matrix.
CoinBigIndex presolve_find_minor(int tgt, CoinBigIndex ks, CoinBigIndex ke, const int *minndxs)
Find position of a minor index in a major vector.
int recomputeSums(int whichRow)
Recompute row lhs bounds.
int ncols0_
Allocated number of columns.
CoinBigIndex nelems_
current number of coefficients
CoinPostsolveMatrix(int ncols_alloc, int nrows_alloc, CoinBigIndex nelems_alloc)
‘Native’ constructor
int maxSubstLevel_
Maximum substitution level.
Augments CoinPrePostsolveMatrix with information about the problem that is only needed during presolv...
double * cup_
Column (primal variable) upper bounds.
CoinBigIndex presolve_find_row3(int row, CoinBigIndex kcs, int collen, const int *hrow, const CoinBigIndex *clinks)
Find position of a row in a column in a column-major threaded matrix.
int countEmptyCols()
Count empty columns.
void setRowChanged(int i)
Mark row as changed.
double feasibilityTolerance_
Bounds can be moved by this to retain feasibility.
CoinBigIndex free_list_
First entry in free entries thread.
double bulkRatio_
Ratio of bulk0_ to nelems0_; default is 2.
void presolve_delete_from_col2(int row, int col, CoinBigIndex *mcstrt, int *hincol, int *hrow, int *clinks, CoinBigIndex *free_listp)
Delete the entry for row row from column col in a column-major threaded matrix.
int nrows_
current number of rows
bool rowChanged(int i) const
Has row been changed?
int numberColsToDo_
Length of colsToDo_.
bool rowUsed(int i) const
Test if row is marked as used.
void setColumnStatus(int sequence, Status status)
Set column status (i.e., status of primal variable)
int * hincol_
Vector of column lengths.
void setNext(const CoinPresolveAction *nextAction)
modify next (when building rather than passing)
virtual void postsolve(CoinPostsolveMatrix *prob) const =0
Apply the postsolve transformation for this particular presolve action.
const double ZTOLDP
Zero tolerance.
int numberRowsToDo()
Return the number of rows on the rowsToDo_ list.
CoinBigIndex bulk0_
Allocated size of bulk storage for row indices and coefficients.
bool isInteger(int i) const
Check for integrality of the specified variable.
int * hrow_
Row indices (positional correspondence with colels_)
CoinBigIndex presolve_find_minor1(int tgt, CoinBigIndex ks, CoinBigIndex ke, const int *minndxs)
Find position of a minor index in a major vector.
CoinPostsolveMatrix(OsiSolverInterface *si, int ncols0, int nrows0, CoinBigIndex nelems0, double maxmin_, double *sol, double *acts, unsigned char *colstat, unsigned char *rowstat)
Generic OSI constructor.
void update_model(ClpSimplex *si, int nrows0, int ncols0, CoinBigIndex nelems0)
Update the model held by a Clp OSI.
void setPass(int pass=0)
Set pass number.
~CoinPrePostsolveMatrix()
Destructor.
int * usefulRowInt_
Preallocated scratch work array, 3*nrows_.
const double * getElementsByCol() const
Get vector of elements for column-major packed matrix.
bool rowProhibited(int i) const
Test if row is eligible for preprocessing.
void setRowUsed(int i)
Mark row as used.