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) ;
343 {
return static_cast<Status> (rowstat_[sequence]&7);}
346 {
return (static_cast<Status> (rowstat_[sequence]&7)==basic);}
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 ; }
389 {
return static_cast<Status> (colstat_[sequence]&7);}
392 {
return (static_cast<Status> (colstat_[sequence]&7)==basic);}
396 void setRowStatusUsingValue(
int iRow);
400 void setColumnStatusUsingValue(
int iColumn);
402 void setStructuralStatus(
const char *strucStatus,
int lenParam) ;
404 void setArtificialStatus(
const char *artifStatus,
int lenParam) ;
412 const char *columnStatusString(
int j)
const ;
416 const char *rowStatusString(
int i)
const ;
426 void setObjOffset(
double offset) ;
434 void setObjSense(
double objSense) ;
436 void setPrimalTolerance(
double primTol) ;
438 void setDualTolerance(
double dualTol) ;
440 void setColLower(
const double *colLower,
int lenParam) ;
442 void setColUpper(
const double *colUpper,
int lenParam) ;
444 void setColSolution(
const double *colSol,
int lenParam) ;
446 void setCost(
const double *cost,
int lenParam) ;
448 void setReducedCost(
const double *redCost,
int lenParam) ;
450 void setRowLower(
const double *rowLower,
int lenParam) ;
452 void setRowUpper(
const double *rowUpper,
int lenParam) ;
454 void setRowPrice(
const double *rowSol,
int lenParam) ;
456 void setRowActivity(
const double *rowAct,
int lenParam) ;
461 inline int getNumCols()
const 463 {
return (ncols_) ; }
466 {
return (nrows_) ; }
469 {
return (nelems_) ; }
472 {
return (mcstrt_) ; }
475 {
return (hincol_) ; }
481 {
return (colels_) ; }
505 {
return (rowduals_) ; }
508 {
return (rcosts_) ; }
512 for (
int i = 0 ; i < ncols_ ; i++)
if (hincol_[i] == 0) empty++ ;
528 {
if (defaultHandler_ ==
true)
530 defaultHandler_ = false ; }
531 handler_ = handler ; }
534 {
return messages_; }
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,
866 void update_model(ClpSimplex * si,
877 OsiSolverInterface * si,
882 double nonLinearVariable,
883 const char * prohibited,
884 const char * rowProhibited=NULL);
887 void update_model(OsiSolverInterface * si,
915 for (
int i = 0 ; i < nrows_ ; i++)
if (hinrow_[i] == 0) empty++ ;
924 {
if (integerType_ == 0) integerType_ =
new unsigned char [ncols0_] ;
925 integerType_[i] =
static_cast<unsigned char>(variableType) ; }
932 void setVariableType(
const unsigned char *variableType,
int lenParam) ;
939 void setVariableType (
bool allIntegers,
int lenParam) ;
943 { anyInteger_ = anyInteger ; }
952 {
return (mrstrt_) ; }
958 {
return (rowels_) ; }
966 {
if (integerType_ == 0)
967 {
return (anyInteger_) ; }
969 if (integerType_[i] == 1)
972 {
return (
false) ; } }
979 {
return (anyInteger_) ; }
982 {
return presolveOptions_;}
985 { presolveOptions_=value;}
1007 dobias_ += change_amount ;
1008 # if PRESOLVE_DEBUG > 2 1009 assert(fabs(change_amount)<1.0e50) ;
1012 change_amount, dobias_)) ;
1053 {
return (feasibilityTolerance_) ; }
1056 { feasibilityTolerance_ = val ; }
1066 {
return (status_) ; }
1069 { status_ = (status&0x3) ; }
1090 { maxSubstLevel_ = level ; }
1180 int *usefulRowInt_ ;
1212 int recomputeSums(
int whichRow) ;
1215 void initializeStuff() ;
1217 void deleteStuff() ;
1227 void initColsToDo () ;
1234 int stepColsToDo () ;
1238 {
return (numberColsToDo_) ; }
1242 return (colChanged_[i]&1)!=0;
1246 colChanged_[i] =
static_cast<unsigned char>(colChanged_[i] & (~1)) ;
1250 colChanged_[i] =
static_cast<unsigned char>(colChanged_[i] | (1)) ;
1254 if ((colChanged_[i]&1)==0) {
1255 colChanged_[i] =
static_cast<unsigned char>(colChanged_[i] | (1)) ;
1256 nextColsToDo_[numberNextColsToDo_++] = i;
1261 return (colChanged_[i]&2)!=0;
1270 if (!anyProhibited_)
1273 return (colChanged_[i]&2)!=0;
1277 colChanged_[i] =
static_cast<unsigned char>(colChanged_[i] | (2)) ;
1285 return (colChanged_[i]&4)!=0;
1289 colChanged_[i] =
static_cast<unsigned char>(colChanged_[i] | (4)) ;
1293 colChanged_[i] =
static_cast<unsigned char>(colChanged_[i] & (~4)) ;
1297 return (colChanged_[i]&8)!=0;
1301 colChanged_[i] =
static_cast<unsigned char>(colChanged_[i] & (~8)) ;
1305 colChanged_[i] =
static_cast<unsigned char>(colChanged_[i] | (8)) ;
1313 void initRowsToDo () ;
1320 int stepRowsToDo () ;
1324 {
return (numberRowsToDo_) ; }
1328 return (rowChanged_[i]&1)!=0;
1332 rowChanged_[i] =
static_cast<unsigned char>(rowChanged_[i] & (~1)) ;
1336 rowChanged_[i] =
static_cast<unsigned char>(rowChanged_[i] | (1)) ;
1340 if ((rowChanged_[i]&1)==0) {
1341 rowChanged_[i] =
static_cast<unsigned char>(rowChanged_[i] | (1)) ;
1342 nextRowsToDo_[numberNextRowsToDo_++] = i;
1347 return (rowChanged_[i]&2)!=0;
1356 if (!anyProhibited_)
1359 return (rowChanged_[i]&2)!=0;
1363 rowChanged_[i] =
static_cast<unsigned char>(rowChanged_[i] | (2)) ;
1371 return (rowChanged_[i]&4)!=0;
1375 rowChanged_[i] =
static_cast<unsigned char>(rowChanged_[i] | (4)) ;
1379 rowChanged_[i] =
static_cast<unsigned char>(rowChanged_[i] & (~4)) ;
1385 {
return anyProhibited_;}
1388 { anyProhibited_ = val ; }
1451 unsigned char *colstat,
1452 unsigned char *rowstat);
1470 unsigned char *colstat,
1471 unsigned char *rowstat);
1524 void check_nbasic();
1540 void presolve_make_memlists(
int *lengths,
1550 bool presolve_expand_major(
CoinBigIndex *majstrts,
double *majels,
1551 int *minndxs,
int *majlens,
1560 int *hrow,
int *hincol,
1562 {
return presolve_expand_major(mcstrt,colels,
1563 hrow,hincol,clink,ncols,colx) ; }
1571 int *hcol,
int *hinrow,
1573 {
return presolve_expand_major(mrstrt,rowels,
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)
1611 {
return presolve_find_minor(row,kcs,kce,hrow) ; }
1621 {
return presolve_find_minor(col,krs,kre,hcol) ; }
1633 const int *minndxs);
1643 {
return presolve_find_minor1(row,kcs,kce,hrow) ; }
1653 {
return presolve_find_minor1(col,krs,kre,hcol) ; }
1677 {
return presolve_find_minor2(row,kcs,collen,hrow,clinks) ; }
1701 {
return presolve_find_minor3(row,kcs,collen,hrow,clinks) ; }
1714 int *majlens,
int *minndxs,
double *els)
1719 const CoinBigIndex kmi = presolve_find_minor(minndx,ks,ke,minndxs) ;
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)
1767 { presolve_delete_from_major(col,row,mcstrt,hincol,hrow,colels) ; }
1781 int *hinrow,
int *hcol,
double *rowels)
1782 { presolve_delete_from_major(row,col,mrstrt,hinrow,hcol,rowels) ; }
1794 void presolve_delete_from_major2 (
int majndx,
int minndx,
1796 int *minndxs,
int *majlinks,
1810 int *hincol,
int *hrow,
1812 { presolve_delete_from_major2(col,row,mcstrt,hincol,hrow,clinks,free_listp) ; }
unsigned char * rowChanged_
Row change status information.
void setColChanged(int i)
Mark column as changed.
int * originalRow_
Original row numbers.
bool rowIsBasic(int sequence) const
Check if artificial for this row is basic.
Error Class thrown by an exception.
void setPass(int pass=0)
Set pass number.
int * colsToDo_
Input list of columns to process.
int getNumRows() const
Get current number of rows.
void setMessageHandler(CoinMessageHandler *handler)
Set message handler.
virtual void postsolve(CoinPostsolveMatrix *prob) const =0
Apply the postsolve transformation for this particular presolve action.
double ztolzb_
Primal feasibility tolerance.
void PRESOLVE_REMOVE_LINK(presolvehlink *link, int i)
unlink vector i
void setFeasibilityTolerance(double val)
Set feasibility tolerance.
Collects all the information about the problem that is needed in both presolve and postsolve...
int * originalColumn_
Original column numbers.
bool anyInteger_
Flag to say if any variables are integer.
Status getRowStatus(int sequence) const
Get row status.
double * sumDown_
Work array for sum of finite contributions to row lhs lower bound.
int nrows0_
Allocated number of rows.
double * colels_
Coefficients (positional correspondence with hrow_)
CoinMessage messages_
Standard COIN messages.
Status getColumnStatus(int sequence) const
Get column (structural variable) status.
const CoinBigIndex * getColStarts() const
Get column start vector for column-major packed matrix.
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.
CoinBigIndex nelems0_
Allocated number of coefficients.
int * infiniteUp_
Work array for count of infinite contributions to row lhs upper bound.
double * usefulColumnDouble_
Preallocated scratch work array, ncols_.
unsigned char * rowstat_
Status of constraints.
bool columnIsBasic(int sequence) const
Check if column (structural variable) is basic.
double * rup_
Row (constraint) upper bounds.
void unsetRowChanged(int i)
Mark row as not changed.
double * randomNumber_
Array of random numbers (max row,column)
int * hcol_
Column indices (positional correspondence with rowels_)
const int * getColLengths() const
Get column length vector for column-major packed matrix.
const double ZTOLDP2
Alternate zero tolerance.
int presolveOptions_
Fine control over presolve actions.
double * rcosts_
Vector of reduced costs.
CoinBigIndex nelems_
current number of coefficients
Links to aid in packed matrix modification.
int * nextColsToDo_
Output list of columns to process next.
int ncols0_
Allocated number of columns.
int * rowsToDo_
Input list of rows to process.
Abstract base class of all presolve routines.
double maxmin_
Maximization/minimization.
double bulkRatio_
Ratio of bulk0_ to nelems0_; default is 2.
static void throwCoinError(const char *error, const char *ps_routine)
Stub routine to throw exceptions.
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 countEmptyCols()
Count empty columns.
int numberNextColsToDo_
Length of nextColsToDo_.
bool anyInteger() const
Check if there are any integer variables.
int status()
Returns problem status (0 = feasible, 1 = infeasible, 2 = unbounded)
void unsetColUsed(int i)
Mark column as unused.
void setStatus(int status)
Set problem status.
The default COIN simplex (basis-oriented) warm start class.
int numberColsToDo_
Length of colsToDo_.
CoinBigIndex presolve_find_minor(int tgt, CoinBigIndex ks, CoinBigIndex ke, const int *minndxs)
Find position of a minor index in a major vector.
int numberColsToDo()
Return the number of columns on the colsToDo_ list.
void setPresolveOptions(int value)
Sets any special options (see presolveOptions_)
Status
Enum for status of various sorts.
Base class for message handling.
double * cost_
Objective coefficients.
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.
bool rowProhibited2(int i) const
Test if row is eligible for preprocessing.
bool anyProhibited_
Flag to say if any rows or columns are marked as prohibited.
double startTime_
Start time of presolve.
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.
void setVariableType(int i, int variableType)
Set variable type information for a single variable.
void PRESOLVE_MOVE_LINK(presolvehlink *link, int i, int j)
relink vector j in place of vector i
The standard set of Coin messages.
void setNext(const CoinPresolveAction *nextAction)
modify next (when building rather than passing)
void addCol(int i)
Mark column as changed and add to list of columns to process next.
void setRowStatus(int sequence, Status status)
Set row status (i.e., status of artificial for this row)
unsigned char * integerType_
Tracks integrality of columns (1 for integer, 0 for continuous)
void coin_init_random_vec(double *work, int n)
Initialize a vector with random numbers.
int nrows_
current number of rows
const double * getCost() const
Get objective coefficients.
const double * getElementsByCol() const
Get vector of elements for column-major packed matrix.
virtual ~CoinPresolveAction()
Virtual destructor.
void setAnyInteger(bool anyInteger=true)
Set a flag for presence (true) or absence (false) of integer variables.
bool rowChanged(int i) const
Has row been changed?
bool isInteger(int i) const
Check for integrality of the specified variable.
double * usefulRowDouble_
Preallocated scratch work array, 2*nrows_.
double * cup_
Column (primal variable) upper bounds.
void setColumnStatus(int sequence, Status status)
Set column status (i.e., status of primal variable)
int status_
Output status: 0 = feasible, 1 = infeasible, 2 = unbounded.
void setAnyProhibited(bool val=true)
Set a flag for presence of prohibited rows or columns.
int * hincol_
Vector of column lengths.
bool rowUsed(int i) const
Test if row is marked as used.
double * acts_
Vector of constraint left-hand-side values (row activity)
int * hrow_
Row indices (positional correspondence with colels_)
CoinPresolveAction(const CoinPresolveAction *next)
Construct a postsolve object and add it to the transformation list.
int getNumElems() const
Get current number of non-zero coefficients.
void presolve_delete_many_from_major(int majndx, char *marked, const CoinBigIndex *majstrts, int *majlens, int *minndxs, double *els)
Delete marked entries.
bool anyProhibited() const
Check if there are any prohibited rows or columns.
int numberNextRowsToDo_
Length of nextRowsToDo_.
void setColProhibited(int i)
Mark column as ineligible for preprocessing.
double ztoldj_
Dual feasibility tolerance.
const double ZTOLDP
Zero tolerance.
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.
bool rowProhibited(int i) const
Test if row is eligible for preprocessing.
const double * getColSolution() const
Get column solution (primal variable values)
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 double * getRowPrice() const
Get row solution (dual variables)
Augments CoinPrePostsolveMatrix with information about the problem that is only needed during postsol...
void setRowProhibited(int i)
Mark row as ineligible for preprocessing.
CoinBigIndex bulk0_
Allocated size of bulk storage for row indices and coefficients.
void setMaximumSubstitutionLevel(int level)
Set Maximum substitution level (normally 3)
void unsetColInfinite(int i)
Mark column as not infinite ub (originally)
const double * getRowUpper() const
Get row upper bounds.
unsigned char * colChanged_
Column change status information.
bool colUsed(int i) const
Test if column is marked as used.
const double * getRowActivity() const
Get row activity (constraint lhs values)
bool defaultHandler_
Indicates if the current handler_ is default (true) or not (false).
Sparse Matrix Base Class.
void setRowChanged(int i)
Mark row as changed.
void change_bias(double change_amount)
Adjust objective function constant offset.
double originalOffset_
Original objective offset.
int countEmptyRows()
Count number of empty rows.
Augments CoinPrePostsolveMatrix with information about the problem that is only needed during presolv...
const CoinBigIndex * getRowStarts() const
Get row start vector for row-major packed matrix.
int * hinrow_
Vector of row lengths.
void setColInfinite(int i)
Mark column as infinite ub (originally)
int * nextRowsToDo_
Output list of rows to process next.
int numberRowsToDo_
Length of rowsToDo_.
const double * getColLower() const
Get column lower bounds.
double * sumUp_
Work array for sum of finite contributions to row lhs upper bound.
int ncols_
current number of columns
void addRow(int i)
Mark row as changed and add to list of rows to process next.
double dobias_
Objective function offset introduced during presolve.
void PRESOLVE_INSERT_LINK(presolvehlink *link, int i, int j)
insert vector i after vector j
CoinMessages messages() const
Return messages.
double * rowels_
Coefficients (positional correspondence with hcol_)
bool tuning_
Print statistics for tuning.
#define PRESOLVE_INF
The usual finite infinity.
int * infiniteDown_
Work array for count of infinite contributions to row lhs lower bound.
int numberRowsToDo()
Return the number of rows on the rowsToDo_ list.
bool colInfinite(int i) const
Has column infinite ub (originally)
int * usefulColumnInt_
Preallocated scratch work array, 2*ncols_.
double feasibilityTolerance()
Return feasibility tolerance.
CoinBigIndex free_list_
First entry in free entries thread.
const double * getElementsByRow() const
Get vector of elements for row-major packed matrix.
bool colChanged(int i) const
Has column been changed?
const double * getRowLower() const
Get row lower bounds.
double * clo_
Column (primal variable) lower bounds.
const double * getReducedCost() const
Get reduced costs.
double feasibilityTolerance_
Bounds can be moved by this to retain feasibility.
void unsetColChanged(int i)
Mark column as not changed.
This file contains the enum for the standard set of Coin messages and a class definition whose sole p...
presolvehlink * rlink_
Linked list for the row-major representation.
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.
bool colProhibited2(int i) const
Test if column is eligible for preprocessing.
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.
unsigned char * colstat_
Status of primal variables.
const int * getRowIndicesByCol() const
Get vector of row indices for column-major packed matrix.
double * sol_
Vector of primal variable values.
double * rowduals_
Vector of dual variable values.
CoinBigIndex * link_
Thread array.
void setColUsed(int i)
Mark column as used.
virtual const char * name() const =0
A name for debug printing.
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.
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_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.
void setRowUsed(int i)
Mark row as used.
int maxlink_
Allocated size of link_.
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 pass_
Presolve pass number.
const int * getColIndicesByRow() const
Get vector of column indices for row-major packed matrix.
Class to hold and manipulate an array of massaged messages.
int maxSubstLevel_
Maximum substitution level.
void unsetRowUsed(int i)
Mark row as unused.
const double * getColUpper() const
Get column upper bounds.
double * rlo_
Row (constraint) lower bounds.
bool colProhibited(int i) const
Test if column is eligible for preprocessing.
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.
int presolveOptions() const
Picks up any special options.