CoinPresolveMatrix.hpp
Go to the documentation of this file.
1 /* $Id: CoinPresolveMatrix.hpp 1269 2010-04-02 17:15:06Z forrest $ */
2 // Copyright (C) 2002, International Business Machines
3 // Corporation and others. All Rights Reserved.
4 #ifndef CoinPresolveMatrix_H
5 #define CoinPresolveMatrix_H
6 
7 #include "CoinPragma.hpp"
8 #include "CoinPackedMatrix.hpp"
9 #include "CoinMessage.hpp"
10 #include "CoinTime.hpp"
11 
12 #include <cmath>
13 #include <cassert>
14 #include <cfloat>
15 #include <cassert>
16 
25 #if defined(_MSC_VER)
26 // Avoid MS Compiler problem in recognizing type to delete
27 // by casting to type.
28 #define deleteAction(array,type) delete [] ((type) array)
29 #else
30 #define deleteAction(array,type) delete [] array
31 #endif
32 
37 const double ZTOLDP = 1e-12;
38 // But use a different one if we are doing doubletons etc
39 const double ZTOLDP2 = 1e-10;
40 //#define PRESOLVE_DEBUG 1
41 // Debugging macros/functions
42 
43 #if PRESOLVE_DEBUG || PRESOLVE_CONSISTENCY
44 #define PRESOLVE_STMT(s) s
45 #define PRESOLVEASSERT(x) \
46  ((x) ? 1 : \
47  ((std::cerr << "FAILED ASSERTION at line " \
48  << __LINE__ << ": " #x "\n"), abort(), 0))
49 
50 inline void DIE(const char *s) { std::cout<<s; abort(); }
51 
52 // This code is used in [cr]done for columns and rows that are present in
53 // the presolved system.
54 #define PRESENT_IN_REDUCED '\377'
55 
56 #else
57 
58 #define PRESOLVEASSERT(x) {}
59 #define PRESOLVE_STMT(s) {}
60 
61 inline void DIE(const char *) {}
62 
63 #endif
64 
65 inline int ALIGN(int n, int m) { return (((n + m - 1) / m) * m); }
66 inline int ALIGN_DOUBLE(int n) { return ALIGN(n,sizeof(double)); }
67 
68 // Plus infinity
69 #ifndef COIN_DBL_MAX
70 #define COIN_DBL_MAX DBL_MAX
71 #endif
72 #define PRESOLVE_INF COIN_DBL_MAX
73 
75 
76 // Note 77
77 // "Members and bases are constructed in order of declaration
78 // in the class and destroyed in the reverse order." C++PL 3d Ed. p. 307
79 //
80 // That's why I put integer members (such as ncols) before the array members;
81 // I like to use those integer values during initialization.
82 // NOT ANYMORE
83 
134 {
135  public:
142  static void throwCoinError(const char *error, const char *ps_routine)
143  { throw CoinError(error, ps_routine, "CoinPresolve"); }
144 
145 
151 
159  inline void setNext(const CoinPresolveAction *nextAction)
160  { next = nextAction;}
161 
166  virtual const char *name() const = 0;
167 
171  virtual void postsolve(CoinPostsolveMatrix *prob) const = 0;
172 
174  virtual ~CoinPresolveAction() {}
175 };
176 
177 /*
178  These are needed for OSI-aware constructors associated with
179  CoinPrePostsolveMatrix, CoinPresolveMatrix, and CoinPostsolveMatrix.
180 */
181  class ClpSimplex;
182  class OsiSolverInterface;
183 
184 /*
185  CoinWarmStartBasis is required for methods in CoinPrePostsolveMatrix
186  that accept/return a CoinWarmStartBasis object.
187 */
188  class CoinWarmStartBasis ;
189 
241 {
242  public:
243 
253  CoinPrePostsolveMatrix(int ncols_alloc, int nrows_alloc,
254  CoinBigIndex nelems_alloc) ;
255 
260  CoinPrePostsolveMatrix(const OsiSolverInterface * si,
261  int ncols_,
262  int nrows_,
264 
269  CoinPrePostsolveMatrix(const ClpSimplex * si,
270  int ncols_,
271  int nrows_,
272  CoinBigIndex nelems_,
273  double bulkRatio);
274 
278 
288  enum Status {
289  isFree = 0x00,
290  basic = 0x01,
291  atUpperBound = 0x02,
292  atLowerBound = 0x03,
293  superBasic = 0x04
294  };
295 
302 
304  inline void setRowStatus(int sequence, Status status)
305  {
306  unsigned char & st_byte = rowstat_[sequence];
307  st_byte = static_cast<unsigned char>(st_byte & (~7)) ;
308  st_byte = static_cast<unsigned char>(st_byte | status) ;
309  }
311  inline Status getRowStatus(int sequence) const
312  {return static_cast<Status> (rowstat_[sequence]&7);}
314  inline bool rowIsBasic(int sequence) const
315  {return (static_cast<Status> (rowstat_[sequence]&7)==basic);}
317  inline void setColumnStatus(int sequence, Status status)
318  {
319  unsigned char & st_byte = colstat_[sequence];
320  st_byte = static_cast<unsigned char>(st_byte & (~7)) ;
321  st_byte = static_cast<unsigned char>(st_byte | status) ;
322 
323 # ifdef PRESOLVE_DEBUG
324  switch (status)
325  { case isFree:
326  { if (clo_[sequence] > -PRESOLVE_INF || cup_[sequence] < PRESOLVE_INF)
327  { std::cout << "Bad status: Var " << sequence
328  << " isFree, lb = " << clo_[sequence]
329  << ", ub = " << cup_[sequence] << std::endl ; }
330  break ; }
331  case basic:
332  { break ; }
333  case atUpperBound:
334  { if (cup_[sequence] >= PRESOLVE_INF)
335  { std::cout << "Bad status: Var " << sequence
336  << " atUpperBound, lb = " << clo_[sequence]
337  << ", ub = " << cup_[sequence] << std::endl ; }
338  break ; }
339  case atLowerBound:
340  { if (clo_[sequence] <= -PRESOLVE_INF)
341  { std::cout << "Bad status: Var " << sequence
342  << " atLowerBound, lb = " << clo_[sequence]
343  << ", ub = " << cup_[sequence] << std::endl ; }
344  break ; }
345  case superBasic:
346  { if (clo_[sequence] <= -PRESOLVE_INF && cup_[sequence] >= PRESOLVE_INF)
347  { std::cout << "Bad status: Var " << sequence
348  << " superBasic, lb = " << clo_[sequence]
349  << ", ub = " << cup_[sequence] << std::endl ; }
350  break ; }
351  default:
352  { assert(false) ;
353  break ; } }
354 # endif
355  }
357  inline Status getColumnStatus(int sequence) const
358  {return static_cast<Status> (colstat_[sequence]&7);}
360  inline bool columnIsBasic(int sequence) const
361  {return (static_cast<Status> (colstat_[sequence]&7)==basic);}
365  void setRowStatusUsingValue(int iRow);
369  void setColumnStatusUsingValue(int iColumn);
371  void setStructuralStatus(const char *strucStatus, int lenParam) ;
373  void setArtificialStatus(const char *artifStatus, int lenParam) ;
375  void setStatus(const CoinWarmStartBasis *basis) ;
381  const char *columnStatusString(int j) const ;
385  const char *rowStatusString(int i) const ;
387 
395  void setObjOffset(double offset) ;
401  void setObjSense(double objSense) ;
403  void setPrimalTolerance(double primTol) ;
405  void setDualTolerance(double dualTol) ;
407  void setColLower(const double *colLower, int lenParam) ;
409  void setColUpper(const double *colUpper, int lenParam) ;
411  void setColSolution(const double *colSol, int lenParam) ;
413  void setCost(const double *cost, int lenParam) ;
415  void setReducedCost(const double *redCost, int lenParam) ;
417  void setRowLower(const double *rowLower, int lenParam) ;
419  void setRowUpper(const double *rowUpper, int lenParam) ;
421  void setRowPrice(const double *rowSol, int lenParam) ;
423  void setRowActivity(const double *rowAct, int lenParam) ;
425 
428  inline int getNumCols()
430  { return (ncols_) ; }
432  inline int getNumRows()
433  { return (nrows_) ; }
435  inline int getNumElems()
436  { return (nelems_) ; }
438  inline const CoinBigIndex *getColStarts() const
439  { return (mcstrt_) ; }
441  inline const int *getColLengths() const
442  { return (hincol_) ; }
444  inline const int *getRowIndicesByCol() const
445  { return (hrow_) ; }
447  inline const double *getElementsByCol() const
448  { return (colels_) ; }
450  inline const double *getColLower() const
451  { return (clo_) ; }
453  inline const double *getColUpper() const
454  { return (cup_) ; }
456  inline const double *getCost() const
457  { return (cost_) ; }
459  inline const double *getRowLower() const
460  { return (rlo_) ; }
462  inline const double *getRowUpper() const
463  { return (rup_) ; }
465  inline const double *getColSolution() const
466  { return (sol_) ; }
468  inline const double *getRowActivity() const
469  { return (acts_) ; }
471  inline const double *getRowPrice() const
472  { return (rowduals_) ; }
474  inline const double *getReducedCost() const
475  { return (rcosts_) ; }
477  inline int countEmptyCols()
478  { int empty = 0 ;
479  for (int i = 0 ; i < ncols_ ; i++) if (hincol_[i] == 0) empty++ ;
480  return (empty) ; }
482 
483 
486  inline CoinMessageHandler *messageHandler() const
488  { return handler_; }
494  inline void setMessageHandler(CoinMessageHandler *handler)
495  { if (defaultHandler_ == true)
496  { delete handler_ ;
497  defaultHandler_ = false ; }
498  handler_ = handler ; }
500  inline CoinMessages messages() const
501  { return messages_; }
503 
513 
515  int ncols_;
517  int nrows_;
520 
522  int ncols0_;
524  int nrows0_ ;
537  double bulkRatio_;
539 
551  int *hincol_;
553  int *hrow_;
555  double *colels_;
556 
558  double *cost_;
561 
563  double *clo_;
565  double *cup_;
566 
568  double *rlo_;
570  double *rup_;
571 
576 
578  double ztolzb_;
580  double ztoldj_;
581 
583  double maxmin_;
585 
606  double *sol_;
612  double *rowduals_;
618  double *acts_;
624  double *rcosts_;
625 
632  unsigned char *colstat_;
633 
640  unsigned char *rowstat_;
642 
658 
659 };
660 
661 
687 { public:
688  int pre, suc;
689 } ;
690 
691 #define NO_LINK -66666666
692 
698 inline void PRESOLVE_REMOVE_LINK(presolvehlink *link, int i)
699 {
700  int ipre = link[i].pre;
701  int isuc = link[i].suc;
702  if (ipre >= 0) {
703  link[ipre].suc = isuc;
704  }
705  if (isuc >= 0) {
706  link[isuc].pre = ipre;
707  }
708  link[i].pre = NO_LINK, link[i].suc = NO_LINK;
709 }
710 
716 inline void PRESOLVE_INSERT_LINK(presolvehlink *link, int i, int j)
717 {
718  int isuc = link[j].suc;
719  link[j].suc = i;
720  link[i].pre = j;
721  if (isuc >= 0) {
722  link[isuc].pre = i;
723  }
724  link[i].suc = isuc;
725 }
726 
738 inline void PRESOLVE_MOVE_LINK(presolvehlink *link, int i, int j)
739 {
740  int ipre = link[i].pre;
741  int isuc = link[i].suc;
742  if (ipre >= 0) {
743  link[ipre].suc = j;
744  }
745  if (isuc >= 0) {
746  link[isuc].pre = j;
747  }
748  link[i].pre = NO_LINK, link[i].suc = NO_LINK;
749 }
750 
751 
774 {
775  public:
776 
783  CoinPresolveMatrix(int ncols_alloc, int nrows_alloc,
784  CoinBigIndex nelems_alloc) ;
785 
790  CoinPresolveMatrix(int ncols0,
791  double maxmin,
792  // end prepost members
793 
794  ClpSimplex * si,
795 
796  // rowrep
797  int nrows,
798  CoinBigIndex nelems,
799  bool doStatus,
800  double nonLinearVariable,
801  double bulkRatio);
802 
804  void update_model(ClpSimplex * si,
805  int nrows0,
806  int ncols0,
807  CoinBigIndex nelems0);
812  CoinPresolveMatrix(int ncols0,
813  double maxmin,
814  // end prepost members
815  OsiSolverInterface * si,
816  // rowrep
817  int nrows,
818  CoinBigIndex nelems,
819  bool doStatus,
820  double nonLinearVariable,
821  const char * prohibited,
822  const char * rowProhibited=NULL);
823 
825  void update_model(OsiSolverInterface * si,
826  int nrows0,
827  int ncols0,
828  CoinBigIndex nelems0);
829 
832 
838  friend void assignPresolveToPostsolve (CoinPresolveMatrix *&preObj) ;
839 
848  void setMatrix(const CoinPackedMatrix *mtx) ;
849 
851  inline int countEmptyRows()
852  { int empty = 0 ;
853  for (int i = 0 ; i < nrows_ ; i++) if (hinrow_[i] == 0) empty++ ;
854  return (empty) ; }
855 
861  inline void setVariableType(int i, int variableType)
862  { if (integerType_ == 0) integerType_ = new unsigned char [ncols0_] ;
863  integerType_[i] = static_cast<unsigned char>(variableType) ; }
864 
870  void setVariableType(const unsigned char *variableType, int lenParam) ;
871 
877  void setVariableType (bool allIntegers, int lenParam) ;
878 
880  inline void setAnyInteger (bool anyInteger = true)
881  { anyInteger_ = anyInteger ; }
883 
887 
889  inline const CoinBigIndex *getRowStarts() const
890  { return (mrstrt_) ; }
892  inline const int *getColIndicesByRow() const
893  { return (hcol_) ; }
895  inline const double *getElementsByRow() const
896  { return (rowels_) ; }
897 
903  inline bool isInteger (int i) const
904  { if (integerType_ == 0)
905  { return (anyInteger_) ; }
906  else
907  if (integerType_[i] == 1)
908  { return (true) ; }
909  else
910  { return (false) ; } }
911 
916  inline bool anyInteger () const
917  { return (anyInteger_) ; }
919  inline int presolveOptions() const
920  { return presolveOptions_;}
922  inline void setPresolveOptions(int value)
923  { presolveOptions_=value;}
925 
938 
940  double dobias_;
941 
943  inline void change_bias(double change_amount)
944  {
945  dobias_ += change_amount;
946  #if PRESOLVE_DEBUG
947  assert(fabs(change_amount)<1.0e50);
948  #endif
949  if (change_amount)
950  PRESOLVE_STMT(printf("changing bias by %g to %g\n",
951  change_amount, dobias_));
952  }
953 
965  int *hinrow_;
967  double *rowels_;
969  int *hcol_;
971 
973  unsigned char *integerType_;
979  bool anyInteger_ ;
981  bool tuning_;
983  void statistics();
985  double startTime_;
986 
990  inline double feasibilityTolerance()
991  { return (feasibilityTolerance_) ; }
993  inline void setFeasibilityTolerance (double val)
994  { feasibilityTolerance_ = val ; }
995 
1001  int status_;
1003  inline int status()
1004  { return (status_) ; }
1006  inline void setStatus(int status)
1007  { status_ = (status&0x3) ; }
1008 
1014  int pass_;
1016  inline void setPass (int pass = 0)
1017  { pass_ = pass ; }
1018 
1025  inline void setMaximumSubstitutionLevel (int level)
1026  { maxSubstLevel_ = level ; }
1027 
1028 
1051  unsigned char * colChanged_;
1053  int * colsToDo_;
1060 
1070  unsigned char * rowChanged_;
1072  int * rowsToDo_;
1103  double * randomNumber_;
1107  double * sumUp_;
1111  double * sumDown_;
1113 
1116 
1122  void initColsToDo () ;
1123 
1129  int stepColsToDo () ;
1130 
1132  inline int numberColsToDo()
1133  { return (numberColsToDo_) ; }
1134 
1136  inline bool colChanged(int i) const {
1137  return (colChanged_[i]&1)!=0;
1138  }
1140  inline void unsetColChanged(int i) {
1141  colChanged_[i] = static_cast<unsigned char>(colChanged_[i] & (~1)) ;
1142  }
1144  inline void setColChanged(int i) {
1145  colChanged_[i] = static_cast<unsigned char>(colChanged_[i] | (1)) ;
1146  }
1148  inline void addCol(int i) {
1149  if ((colChanged_[i]&1)==0) {
1150  colChanged_[i] = static_cast<unsigned char>(colChanged_[i] | (1)) ;
1152  }
1153  }
1155  inline bool colProhibited(int i) const {
1156  return (colChanged_[i]&2)!=0;
1157  }
1164  inline bool colProhibited2(int i) const {
1165  if (!anyProhibited_)
1166  return false;
1167  else
1168  return (colChanged_[i]&2)!=0;
1169  }
1171  inline void setColProhibited(int i) {
1172  colChanged_[i] = static_cast<unsigned char>(colChanged_[i] | (2)) ;
1173  }
1179  inline bool colUsed(int i) const {
1180  return (colChanged_[i]&4)!=0;
1181  }
1183  inline void setColUsed(int i) {
1184  colChanged_[i] = static_cast<unsigned char>(colChanged_[i] | (4)) ;
1185  }
1187  inline void unsetColUsed(int i) {
1188  colChanged_[i] = static_cast<unsigned char>(colChanged_[i] & (~4)) ;
1189  }
1190 
1196  void initRowsToDo () ;
1197 
1203  int stepRowsToDo () ;
1204 
1206  inline int numberRowsToDo()
1207  { return (numberRowsToDo_) ; }
1208 
1210  inline bool rowChanged(int i) const {
1211  return (rowChanged_[i]&1)!=0;
1212  }
1214  inline void unsetRowChanged(int i) {
1215  rowChanged_[i] = static_cast<unsigned char>(rowChanged_[i] & (~1)) ;
1216  }
1218  inline void setRowChanged(int i) {
1219  rowChanged_[i] = static_cast<unsigned char>(rowChanged_[i] | (1)) ;
1220  }
1222  inline void addRow(int i) {
1223  if ((rowChanged_[i]&1)==0) {
1224  rowChanged_[i] = static_cast<unsigned char>(rowChanged_[i] | (1)) ;
1226  }
1227  }
1229  inline bool rowProhibited(int i) const {
1230  return (rowChanged_[i]&2)!=0;
1231  }
1238  inline bool rowProhibited2(int i) const {
1239  if (!anyProhibited_)
1240  return false;
1241  else
1242  return (rowChanged_[i]&2)!=0;
1243  }
1245  inline void setRowProhibited(int i) {
1246  rowChanged_[i] = static_cast<unsigned char>(rowChanged_[i] | (2)) ;
1247  }
1253  inline bool rowUsed(int i) const {
1254  return (rowChanged_[i]&4)!=0;
1255  }
1257  inline void setRowUsed(int i) {
1258  rowChanged_[i] = static_cast<unsigned char>(rowChanged_[i] | (4)) ;
1259  }
1261  inline void unsetRowUsed(int i) {
1262  rowChanged_[i] = static_cast<unsigned char>(rowChanged_[i] & (~4)) ;
1263  }
1264 
1265 
1267  inline bool anyProhibited() const
1268  { return anyProhibited_;}
1270  inline void setAnyProhibited(bool val = true)
1271  { anyProhibited_ = val ; }
1274  int recomputeSums(int iRow);
1276  int initializeStuff();
1278  void deleteStuff();
1280 
1281 };
1282 
1308 {
1309  public:
1310 
1317  CoinPostsolveMatrix(int ncols_alloc, int nrows_alloc,
1318  CoinBigIndex nelems_alloc) ;
1319 
1320 
1325  CoinPostsolveMatrix(ClpSimplex * si,
1326 
1327  int ncols0,
1328  int nrows0,
1329  CoinBigIndex nelems0,
1330 
1331  double maxmin_,
1332  // end prepost members
1333 
1334  double *sol,
1335  double *acts,
1336 
1337  unsigned char *colstat,
1338  unsigned char *rowstat);
1339 
1344  CoinPostsolveMatrix(OsiSolverInterface * si,
1345 
1346  int ncols0,
1347  int nrows0,
1348  CoinBigIndex nelems0,
1349 
1350  double maxmin_,
1351  // end prepost members
1352 
1353  double *sol,
1354  double *acts,
1355 
1356  unsigned char *colstat,
1357  unsigned char *rowstat);
1358 
1370 
1373 
1385 
1395 
1397 
1405  char *cdone_;
1406  char *rdone_;
1408 
1410  void check_nbasic();
1411 
1412 };
1413 
1414 
1415 #define PRESOLVEFINITE(n) (-PRESOLVE_INF < (n) && (n) < PRESOLVE_INF)
1416 
1423 
1428 void presolve_make_memlists(/*CoinBigIndex *starts,*/ int *lengths,
1429  presolvehlink *link, int n);
1430 
1438 bool presolve_expand_major(CoinBigIndex *majstrts, double *majels,
1439  int *minndxs, int *majlens,
1440  presolvehlink *majlinks, int nmaj, int k) ;
1441 
1447 inline bool presolve_expand_col(CoinBigIndex *mcstrt, double *colels,
1448  int *hrow, int *hincol,
1449  presolvehlink *clink, int ncols, int colx)
1450 { return presolve_expand_major(mcstrt,colels,
1451  hrow,hincol,clink,ncols,colx) ; }
1452 
1458 inline bool presolve_expand_row(CoinBigIndex *mrstrt, double *rowels,
1459  int *hcol, int *hinrow,
1460  presolvehlink *rlink, int nrows, int rowx)
1461 { return presolve_expand_major(mrstrt,rowels,
1462  hcol,hinrow,rlink,nrows,rowx) ; }
1463 
1464 
1474  const int *minndxs)
1475 { CoinBigIndex k ;
1476  for (k = ks ; k < ke ; k++)
1477 #ifndef NDEBUG
1478  { if (minndxs[k] == tgt)
1479  return (k) ; }
1480  DIE("FIND_MINOR") ;
1481 
1482  abort () ; return -1;
1483 #else
1484  { if (minndxs[k] == tgt)
1485  break ; }
1486  return (k) ;
1487 #endif
1488 }
1489 
1497  CoinBigIndex kce, const int *hrow)
1498 { return presolve_find_minor(row,kcs,kce,hrow) ; }
1499 
1507  CoinBigIndex kre, const int *hcol)
1508 { return presolve_find_minor(col,krs,kre,hcol) ; }
1509 
1510 
1520  const int *minndxs);
1521 
1529  CoinBigIndex kce, const int *hrow)
1530 { return presolve_find_minor1(row,kcs,kce,hrow) ; }
1531 
1539  CoinBigIndex kre, const int *hcol)
1540 { return presolve_find_minor1(col,krs,kre,hcol) ; }
1541 
1550 CoinBigIndex presolve_find_minor2(int tgt, CoinBigIndex ks, int majlen,
1551  const int *minndxs,
1552  const CoinBigIndex *majlinks) ;
1553 
1561 inline CoinBigIndex presolve_find_row2(int row, CoinBigIndex kcs, int collen,
1562  const int *hrow,
1563  const CoinBigIndex *clinks)
1564 { return presolve_find_minor2(row,kcs,collen,hrow,clinks) ; }
1565 
1574 CoinBigIndex presolve_find_minor3(int tgt, CoinBigIndex ks, int majlen,
1575  const int *minndxs,
1576  const CoinBigIndex *majlinks) ;
1577 
1585 inline CoinBigIndex presolve_find_row3(int row, CoinBigIndex kcs, int collen,
1586  const int *hrow,
1587  const CoinBigIndex *clinks)
1588 { return presolve_find_minor3(row,kcs,collen,hrow,clinks) ; }
1589 
1599 inline void presolve_delete_from_major(int majndx, int minndx,
1600  const CoinBigIndex *majstrts,
1601  int *majlens, int *minndxs, double *els)
1602 { CoinBigIndex ks = majstrts[majndx] ;
1603  CoinBigIndex ke = ks + majlens[majndx] ;
1604 
1605  CoinBigIndex kmi = presolve_find_minor(minndx,ks,ke,minndxs) ;
1606 
1607  minndxs[kmi] = minndxs[ke-1] ;
1608  els[kmi] = els[ke-1] ;
1609  majlens[majndx]-- ;
1610 
1611  return ; }
1612 // Delete all marked from major (and zero marked)
1613 inline void presolve_delete_many_from_major(int majndx, char * marked,
1614  const CoinBigIndex *majstrts,
1615  int *majlens, int *minndxs, double *els)
1616 {
1617  CoinBigIndex ks = majstrts[majndx] ;
1618  CoinBigIndex ke = ks + majlens[majndx] ;
1619  CoinBigIndex put=ks;
1620  for (CoinBigIndex k=ks;k<ke;k++) {
1621  int iMinor = minndxs[k];
1622  if (!marked[iMinor]) {
1623  minndxs[put]=iMinor;
1624  els[put++]=els[k];
1625  } else {
1626  marked[iMinor]=0;
1627  }
1628  }
1629  majlens[majndx] = put-ks ;
1630  return ;
1631 }
1632 
1643 inline void presolve_delete_from_col(int row, int col,
1644  const CoinBigIndex *mcstrt,
1645  int *hincol, int *hrow, double *colels)
1646 { presolve_delete_from_major(col,row,mcstrt,hincol,hrow,colels) ; }
1647 
1658 inline void presolve_delete_from_row(int row, int col,
1659  const CoinBigIndex *mrstrt,
1660  int *hinrow, int *hcol, double *rowels)
1661 { presolve_delete_from_major(row,col,mrstrt,hinrow,hcol,rowels) ; }
1662 
1673 void presolve_delete_from_major2 (int majndx, int minndx,
1674  CoinBigIndex *majstrts, int *majlens,
1675  int *minndxs, /*double *els,*/ int *majlinks,
1676  CoinBigIndex *free_listp) ;
1677 
1688 inline void presolve_delete_from_col2(int row, int col, CoinBigIndex *mcstrt,
1689  int *hincol, int *hrow,
1690  /*double *colels,*/ int *clinks,
1691  CoinBigIndex *free_listp)
1692 { presolve_delete_from_major2(col,row,mcstrt,hincol,hrow,/*colels,*/clinks,
1693  free_listp) ; }
1694 
1696 
1702 
1714 double *presolve_dupmajor(const double *elems, const int *indices,
1715  int length, CoinBigIndex offset, int tgt = -1);
1717 void coin_init_random_vec(double *work, int n);
1719 
1720 
1721 #endif
int status()
Returns problem status (0 = feasible, 1 = infeasible, 2 = unbounded)
bool defaultHandler_
Indicates if the current handler_ is default (true) or not (false).
int CoinBigIndex
void setRowStatus(int sequence, Status status)
Set row status (i.e., status of artificial for this row)
bool tuning_
Print statistics for tuning.
~CoinPostsolveMatrix()
Destructor.
void coin_init_random_vec(double *work, int n)
Initialize an array with random numbers.
bool colChanged(int i) const
Has column been changed?
void setReducedCost(const double *redCost, int lenParam)
Set reduced costs.
const char * rowStatusString(int i) const
Return a print string for status of a row (artificial variable)
double startTime_
Start time of presolve.
void update_model(ClpSimplex *si, int nrows0, int ncols0, CoinBigIndex nelems0)
Update the model held by a Clp OSI.
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 dobias_
Objective function offset introduced during presolve.
void setStructuralStatus(const char *strucStatus, int lenParam)
Set column (structural variable) status vector.
int status_
Output status: 0 = feasible, 1 = infeasible, 2 = unbounded.
int * hcol_
Column indices (positional correspondence with rowels_)
void change_bias(double change_amount)
Adjust objective function constant offset.
CoinPresolveMatrix(int ncols_alloc, int nrows_alloc, CoinBigIndex nelems_alloc)
`Native' constructor
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.
void setAnyInteger(bool anyInteger=true)
Set a flag for presence (true) or absence (false) of integer variables.
bool anyInteger_
Flag to say if any variables are integer.
const double * getRowPrice() const
Get row solution (dual variables)
const char * columnStatusString(int j) const
Return a print string for status of a column (structural variable)
const double * getColSolution() const
Get column solution (primal variable values)
double * sumDown_
Array giving sum of non-infinite downs on a row.
void setObjSense(double objSense)
Set the objective sense (max/min)
const double * getElementsByCol() const
Get vector of elements for column-major packed matrix.
int numberColsToDo_
Length of colsToDo_.
void setRowLower(const double *rowLower, int lenParam)
Set row lower bounds.
void setNext(const CoinPresolveAction *nextAction)
modify next (when building rather than passing)
Base class for message handling.
int * hrow_
Row indices (positional correspondence with colels_)
int * rowsToDo_
Input list of rows to process.
void addRow(int i)
Mark row as changed and add to list of rows to process next.
void setStatus(const CoinWarmStartBasis *basis)
Set the status of all variables from a basis.
const double * getRowUpper() const
Get row upper bounds.
const double * getReducedCost() const
Get reduced costs.
Collects all the information about the problem that is needed in both presolve and postsolve...
void setColSolution(const double *colSol, int lenParam)
Set column solution.
int * originalColumn_
Original column numbers.
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.
Status
Enum for status of various sorts.
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.
int numberRowsToDo()
Return the number of rows on the rowsToDo_ list.
CoinMessageHandler * messageHandler() const
Return message handler.
Augments CoinPrePostsolveMatrix with information about the problem that is only needed during postsol...
CoinBigIndex presolve_find_minor1(int tgt, CoinBigIndex ks, CoinBigIndex ke, const int *minndxs)
Find position of a minor index in a major vector.
Augments CoinPrePostsolveMatrix with information about the problem that is only needed during presolv...
void addCol(int i)
Mark column as changed and add to list of columns to process next.
double * sumUp_
Array giving sum of non-infinite ups on a row.
const double * getCost() const
Get objective coefficients.
CoinBigIndex * mcstrt_
Vector of column start positions in hrow_, colels_.
void assignPresolveToPostsolve(CoinPresolveMatrix *&preObj)
Load an empty CoinPostsolveMatrix from a CoinPresolveMatrix.
const double ZTOLDP
Zero tolerance.
int numberNextColsToDo_
Length of nextColsToDo_.
virtual void postsolve(CoinPostsolveMatrix *prob) const =0
Apply the postsolve transformation for this particular presolve action.
unsigned char * rowChanged_
Row change status information.
CoinMessageHandler * handler_
Message handler.
double * cost_
Objective coefficients.
const int * getColIndicesByRow() const
Get vector of column indices for row-major packed matrix.
void setRowActivity(const double *rowAct, int lenParam)
Set row activity.
int * hincol_
Vector of column lengths.
void setDualTolerance(double dualTol)
Set the dual feasibility tolerance.
double * usefulRowDouble_
Useful double array number rows.
~CoinPrePostsolveMatrix()
Destructor.
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.
int ncols_
current number of columns
void setPresolveOptions(int value)
Sets any special options.
int * originalRow_
Original row numbers.
const CoinBigIndex * getColStarts() const
Get column start vector for column-major packed matrix.
void DIE(const char *)
int getNumElems()
Get current number of non-zero coefficients.
CoinPostsolveMatrix(int ncols_alloc, int nrows_alloc, CoinBigIndex nelems_alloc)
`Native' constructor
CoinBigIndex nelems0_
Allocated number of coefficients.
int nrows0_
Allocated number of rows.
int nrows_
current number of rows
void setRowPrice(const double *rowSol, int lenParam)
Set row solution.
double * rowduals_
Vector of dual variable values.
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.
double * usefulColumnDouble_
Useful double array number columns.
double maxmin_
Maximization/minimization.
presolvehlink * clink_
Linked list for the column-major representation.
Sparse Matrix Base Class.
#define PRESOLVE_INF
Status getColumnStatus(int sequence) const
Get column (structural variable) status.
int numberNextRowsToDo_
Length of nextRowsToDo_.
Status getRowStatus(int sequence) const
Get row status.
const double * getRowLower() const
Get row lower bounds.
CoinWarmStartBasis * getStatus()
Get status in the form of a CoinWarmStartBasis.
void presolve_delete_many_from_major(int majndx, char *marked, const CoinBigIndex *majstrts, int *majlens, int *minndxs, double *els)
void setColUpper(const double *colUpper, int lenParam)
Set column upper bounds.
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.
CoinBigIndex free_list_
First entry in free entries thread.
void setRowUsed(int i)
Mark row as used.
void setColUsed(int i)
Mark column as used.
int * infiniteUp_
Array giving number of infinite ups on a row.
int getNumCols()
Get current number of columns.
double bulkRatio_
Ratio of bulk0_ to nelems0_; default is 2.
CoinMessage messages_
Standard COIN messages.
void setRowStatusUsingValue(int iRow)
Set status of row (artificial variable) to the correct nonbasic status given bounds and current value...
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.
#define PRESOLVE_STMT(s)
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.
int * usefulRowInt_
Useful int array 3* number rows.
void setVariableType(int i, int variableType)
Set variable type information for a single variable.
unsigned char * integerType_
Tracks integrality of columns (1 for integer, 0 for continuous)
bool colUsed(int i) const
Test if column is marked as used.
void setRowChanged(int i)
Mark row as changed.
int getNumRows()
Get current number of rows.
void setMessageHandler(CoinMessageHandler *handler)
Set message handler.
CoinMessages messages() const
Return messages.
double * rlo_
Row (constraint) lower bounds.
void unsetRowUsed(int i)
Mark row as unused.
void setColProhibited(int i)
Mark column as ineligible for preprocessing.
void setArtificialStatus(const char *artifStatus, int lenParam)
Set row (artificial variable) status vector.
void setColLower(const double *colLower, int lenParam)
Set column lower bounds.
CoinPresolveAction(const CoinPresolveAction *next)
Construct a postsolve object and add it to the transformation list.
void setAnyProhibited(bool val=true)
Set a flag for presence of prohibited rows or columns.
unsigned char * colChanged_
Column change status information.
int countEmptyCols()
Count empty columns.
void initRowsToDo()
Initialise the row ToDo lists.
void setFeasibilityTolerance(double val)
Set feasibility tolerance.
void setColumnStatus(int sequence, Status status)
Set column status (i.e., status of primal variable)
void setColChanged(int i)
Mark column as changed.
const CoinBigIndex * getRowStarts() const
Get row start vector for row-major packed matrix.
double * acts_
Vector of constraint left-hand-side values (row activity)
bool rowIsBasic(int sequence) const
Check if artificial for this row is basic.
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.
int ALIGN_DOUBLE(int n)
int * usefulColumnInt_
Useful int array 2* number columns.
const double * getColLower() const
Get column lower bounds.
unsigned char * rowstat_
Status of constraints.
void setMaximumSubstitutionLevel(int level)
Set Maximum substitution level (normally 3)
void setRowProhibited(int i)
Mark row as ineligible for preprocessing.
double * cup_
Column (primal variable) upper bounds.
Abstract base class of all presolve routines.
bool colProhibited2(int i) const
Test if column is eligible for preprocessing.
void setPrimalTolerance(double primTol)
Set the primal feasibility tolerance.
bool anyProhibited() const
Check if there are any prohibited rows or columns.
int numberColsToDo()
Return the number of columns on the colsToDo_ list.
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.
const double * getRowActivity() const
Get row activity (constraint lhs values)
CoinBigIndex presolve_find_minor(int tgt, CoinBigIndex ks, CoinBigIndex ke, const int *minndxs)
Find position of a minor index in a major vector.
void setMatrix(const CoinPackedMatrix *mtx)
Load the cofficient matrix.
int * hinrow_
Vector of row lengths.
int presolveOptions() const
Picks up any special options.
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 unsetColChanged(int i)
Mark column as not changed.
bool columnIsBasic(int sequence) const
Check if column (structural variable) is basic.
int presolveOptions_
Presolve options 1 set if allow duplicate column tests for integer variables 2 set to allow code to t...
double * rcosts_
Vector of reduced costs.
int ncols0_
Allocated number of columns.
const double * getColUpper() const
Get column upper bounds.
Class to hold and manipulate an array of massaged messages.
double ztolzb_
Primal feasibility tolerance.
double * clo_
Column (primal variable) lower bounds.
void setObjOffset(double offset)
Set the objective function offset for the original system.
int stepRowsToDo()
Step row ToDo lists.
double * colels_
Coefficients (positional correspondence with hrow_)
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.
Error Class thrown by an exception.
Definition: CoinError.hpp:40
double ztoldj_
Dual feasibility tolerance.
void unsetColUsed(int i)
Mark column as unused.
bool rowChanged(int i) const
Has row been changed?
CoinBigIndex bulk0_
Allocated size of bulk storage for row indices and coefficients.
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 initColsToDo()
Initialise the column ToDo lists.
virtual ~CoinPresolveAction()
Virtual destructor.
unsigned char * colstat_
Status of primal variables.
int maxlink_
Allocated size of link_.
virtual const char * name() const =0
A name for debug printing.
presolvehlink * rlink_
Linked list for the row-major representation.
void setRowUpper(const double *rowUpper, int lenParam)
Set row upper bounds.
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 check_nbasic()
debug
friend void assignPresolveToPostsolve(CoinPresolveMatrix *&preObj)
Initialize a CoinPostsolveMatrix object, destroying the CoinPresolveMatrix object.
double originalOffset_
Original objective offset.
bool rowProhibited(int i) const
Test if row is eligible for preprocessing.
const int * getColLengths() const
Get column length vector for column-major packed matrix.
void unsetRowChanged(int i)
Mark row as not changed.
~CoinPresolveMatrix()
Destructor.
int initializeStuff()
Initialize random numbers etc (nonzero if infeasible)
void presolve_make_memlists(int *lengths, presolvehlink *link, int n)
Initialise linked list for major vector order in bulk storage.
void setColumnStatusUsingValue(int iColumn)
Set status of column (structural variable) to the correct nonbasic status given bounds and current va...
#define NO_LINK
CoinBigIndex nelems_
current number of coefficients
static void throwCoinError(const char *error, const char *ps_routine)
Stub routine to throw exceptions.
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.
CoinPrePostsolveMatrix(int ncols_alloc, int nrows_alloc, CoinBigIndex nelems_alloc)
`Native' constructor
bool anyInteger() const
Check if there are any integer variables.
bool rowProhibited2(int i) const
Test if row is eligible for preprocessing.
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 * randomNumber_
Array of random numbers (max row,column)
CoinBigIndex * mrstrt_
Vector of row start positions in #hcol, rowels_.
void setPass(int pass=0)
Set pass number.
int * infiniteDown_
Array giving number of infinite downs on a row.
bool colProhibited(int i) const
Test if column is eligible for preprocessing.
CoinBigIndex * link_
Thread array.
int countEmptyRows()
Count number of empty rows.
double feasibilityTolerance()
Return feasibility tolerance.
void deleteStuff()
Delete useful arrays.
int recomputeSums(int iRow)
Recompute ups and downs for a row (nonzero if infeasible).
void statistics()
Say we want statistics - also set time.
bool rowUsed(int i) const
Test if row is marked as used.
bool isInteger(int i) const
Check for integrality of the specified variable.
double * sol_
Vector of primal variable values.
The standard set of Coin messages.
Definition: CoinMessage.hpp:75
int numberRowsToDo_
Length of rowsToDo_.
const double * getElementsByRow() const
Get vector of elements for row-major packed matrix.
int maxSubstLevel_
Maximum substitution level.
int * nextColsToDo_
Output list of columns to process next.
double * rowels_
Coefficients (positional correspondence with hcol_)
const double ZTOLDP2
The default COIN simplex (basis-oriented) warm start class.
int * colsToDo_
Input list of columns to process.
double feasibilityTolerance_
Bounds can be moved by this to retain feasibility.
int * nextRowsToDo_
Output list of rows to process next.
double * rup_
Row (constraint) upper bounds.
void setCost(const double *cost, int lenParam)
Set objective coefficients.
int stepColsToDo()
Step column ToDo lists.
const CoinPresolveAction * next
The next presolve transformation.
void setStatus(int status)
Set problem status.
int ALIGN(int n, int m)
const int * getRowIndicesByCol() const
Get vector of row indices for column-major packed matrix.