CoinUtils  2.11.4
CoinPresolveMatrix.hpp
Go to the documentation of this file.
1 /* $Id: CoinPresolveMatrix.hpp 2083 2019-01-06 19:38:09Z unxusr $ */
2 // Copyright (C) 2002, International Business Machines
3 // Corporation and others. All Rights Reserved.
4 // This code is licensed under the terms of the Eclipse Public License (EPL).
5 
6 #ifndef CoinPresolveMatrix_H
7 #define CoinPresolveMatrix_H
8 
9 #include "CoinPragma.hpp"
10 #include "CoinPackedMatrix.hpp"
11 #include "CoinMessage.hpp"
12 #include "CoinTime.hpp"
13 
14 #include <cmath>
15 #include <cassert>
16 #include <cfloat>
17 #include <cassert>
18 #include <cstdlib>
19 
20 //# define COIN_PRESOLVE_TUNING 2
21 #if PRESOLVE_DEBUG > 0
22 #include "CoinFinite.hpp"
23 #endif
24 
32 #if defined(_MSC_VER)
33 // Avoid MS Compiler problem in recognizing type to delete
34 // by casting to type.
35 // Is this still necessary? -- lh, 111202 --
36 #define deleteAction(array, type) delete[]((type)array)
37 #else
38 #define deleteAction(array, type) delete[] array
39 #endif
40 
41 /*
42  Define PRESOLVE_DEBUG and PRESOLVE_CONSISTENCY on the configure command
43  line or in a Makefile! See comments in CoinPresolvePsdebug.hpp.
44 */
45 #if PRESOLVE_DEBUG > 0 || PRESOLVE_CONSISTENCY > 0
46 
47 #define PRESOLVE_STMT(s) s
48 
49 #define PRESOLVEASSERT(x) \
50  ((x) ? 1 : ((std::cerr << "FAILED ASSERTION at line " << __LINE__ << ": " #x "\n"), abort(), 0))
51 
52 inline void DIE(const char *s)
53 {
54  std::cout << s;
55  abort();
56 }
57 
68 #define PRESENT_IN_REDUCED '\377'
69 
70 #else
71 
72 #define PRESOLVEASSERT(x) \
73  { \
74  }
75 #define PRESOLVE_STMT(s) \
76  { \
77  }
78 
79 inline void DIE(const char *) {}
80 
81 #endif
82 
83 /*
84  Unclear why these are separate from standard debug.
85 */
86 #ifndef PRESOLVE_DETAIL
87 #define PRESOLVE_DETAIL_PRINT(s) \
88  { \
89  }
90 #else
91 #define PRESOLVE_DETAIL_PRINT(s) s
92 #endif
93 
98 const double ZTOLDP = 1e-12;
103 const double ZTOLDP2 = 1e-10;
104 
106 #define PRESOLVE_INF COIN_DBL_MAX
108 #define PRESOLVE_SMALL_INF 1.0e20
110 #define PRESOLVEFINITE(n) (-PRESOLVE_INF < (n) && (n) < PRESOLVE_INF)
111 
112 class CoinPostsolveMatrix;
113 
164 public:
171  static void throwCoinError(const char *error, const char *ps_routine)
172  {
173  throw CoinError(error, ps_routine, "CoinPresolve");
174  }
175 
181 
188  : next(next)
189  {
190  }
192  inline void setNext(const CoinPresolveAction *nextAction)
193  {
194  next = nextAction;
195  }
196 
201  virtual const char *name() const = 0;
202 
206  virtual void postsolve(CoinPostsolveMatrix *prob) const = 0;
207 
209  virtual ~CoinPresolveAction() {}
210 };
211 
212 /*
213  These are needed for OSI-aware constructors associated with
214  CoinPrePostsolveMatrix, CoinPresolveMatrix, and CoinPostsolveMatrix.
215 */
216 class ClpSimplex;
217 class OsiSolverInterface;
218 
219 /*
220  CoinWarmStartBasis is required for methods in CoinPrePostsolveMatrix
221  that accept/return a CoinWarmStartBasis object.
222 */
223 class CoinWarmStartBasis;
224 
280 public:
290  CoinPrePostsolveMatrix(int ncols_alloc, int nrows_alloc,
291  CoinBigIndex nelems_alloc);
292 
297  CoinPrePostsolveMatrix(const OsiSolverInterface *si,
298  int ncols_,
299  int nrows_,
301 
306  CoinPrePostsolveMatrix(const ClpSimplex *si,
307  int ncols_,
308  int nrows_,
310  double bulkRatio);
311 
315 
325  enum Status {
326  isFree = 0x00,
327  basic = 0x01,
328  atUpperBound = 0x02,
329  atLowerBound = 0x03,
330  superBasic = 0x04
331  };
332 
345 
347  inline void setRowStatus(int sequence, Status status)
348  {
349  unsigned char &st_byte = rowstat_[sequence];
350  st_byte = static_cast< unsigned char >(st_byte & (~7));
351  st_byte = static_cast< unsigned char >(st_byte | status);
352  }
354  inline Status getRowStatus(int sequence) const
355  {
356  return static_cast< Status >(rowstat_[sequence] & 7);
357  }
359  inline bool rowIsBasic(int sequence) const
360  {
361  return (static_cast< Status >(rowstat_[sequence] & 7) == basic);
362  }
364  inline void setColumnStatus(int sequence, Status status)
365  {
366  unsigned char &st_byte = colstat_[sequence];
367  st_byte = static_cast< unsigned char >(st_byte & (~7));
368  st_byte = static_cast< unsigned char >(st_byte | status);
369 
370 #ifdef PRESOLVE_DEBUG
371  switch (status) {
372  case isFree: {
373  if (clo_[sequence] > -PRESOLVE_INF || cup_[sequence] < PRESOLVE_INF) {
374  std::cout << "Bad status: Var " << sequence
375  << " isFree, lb = " << clo_[sequence]
376  << ", ub = " << cup_[sequence] << std::endl;
377  }
378  break;
379  }
380  case basic: {
381  break;
382  }
383  case atUpperBound: {
384  if (cup_[sequence] >= PRESOLVE_INF) {
385  std::cout << "Bad status: Var " << sequence
386  << " atUpperBound, lb = " << clo_[sequence]
387  << ", ub = " << cup_[sequence] << std::endl;
388  }
389  break;
390  }
391  case atLowerBound: {
392  if (clo_[sequence] <= -PRESOLVE_INF) {
393  std::cout << "Bad status: Var " << sequence
394  << " atLowerBound, lb = " << clo_[sequence]
395  << ", ub = " << cup_[sequence] << std::endl;
396  }
397  break;
398  }
399  case superBasic: {
400  if (clo_[sequence] <= -PRESOLVE_INF && cup_[sequence] >= PRESOLVE_INF) {
401  std::cout << "Bad status: Var " << sequence
402  << " superBasic, lb = " << clo_[sequence]
403  << ", ub = " << cup_[sequence] << std::endl;
404  }
405  break;
406  }
407  default: {
408  assert(false);
409  break;
410  }
411  }
412 #endif
413  }
415  inline Status getColumnStatus(int sequence) const
416  {
417  return static_cast< Status >(colstat_[sequence] & 7);
418  }
420  inline bool columnIsBasic(int sequence) const
421  {
422  return (static_cast< Status >(colstat_[sequence] & 7) == basic);
423  }
427  void setRowStatusUsingValue(int iRow);
431  void setColumnStatusUsingValue(int iColumn);
433  void setStructuralStatus(const char *strucStatus, int lenParam);
435  void setArtificialStatus(const char *artifStatus, int lenParam);
437  void setStatus(const CoinWarmStartBasis *basis);
443  const char *columnStatusString(int j) const;
447  const char *rowStatusString(int i) const;
449 
458  void setObjOffset(double offset);
465  void setObjSense(double objSense);
467  void setPrimalTolerance(double primTol);
469  void setDualTolerance(double dualTol);
471  void setColLower(const double *colLower, int lenParam);
473  void setColUpper(const double *colUpper, int lenParam);
475  void setColSolution(const double *colSol, int lenParam);
477  void setCost(const double *cost, int lenParam);
479  void setReducedCost(const double *redCost, int lenParam);
481  void setRowLower(const double *rowLower, int lenParam);
483  void setRowUpper(const double *rowUpper, int lenParam);
485  void setRowPrice(const double *rowSol, int lenParam);
487  void setRowActivity(const double *rowAct, int lenParam);
489 
493  inline int getNumCols() const
494  {
495  return (ncols_);
496  }
498  inline int getNumRows() const
499  {
500  return (nrows_);
501  }
503  inline CoinBigIndex getNumElems() const
504  {
505  return (nelems_);
506  }
508  inline const CoinBigIndex *getColStarts() const
509  {
510  return (mcstrt_);
511  }
513  inline const int *getColLengths() const
514  {
515  return (hincol_);
516  }
518  inline const int *getRowIndicesByCol() const
519  {
520  return (hrow_);
521  }
523  inline const double *getElementsByCol() const
524  {
525  return (colels_);
526  }
528  inline const double *getColLower() const
529  {
530  return (clo_);
531  }
533  inline const double *getColUpper() const
534  {
535  return (cup_);
536  }
538  inline const double *getCost() const
539  {
540  return (cost_);
541  }
543  inline const double *getRowLower() const
544  {
545  return (rlo_);
546  }
548  inline const double *getRowUpper() const
549  {
550  return (rup_);
551  }
553  inline const double *getColSolution() const
554  {
555  return (sol_);
556  }
558  inline const double *getRowActivity() const
559  {
560  return (acts_);
561  }
563  inline const double *getRowPrice() const
564  {
565  return (rowduals_);
566  }
568  inline const double *getReducedCost() const
569  {
570  return (rcosts_);
571  }
573  inline int countEmptyCols()
574  {
575  int empty = 0;
576  for (int i = 0; i < ncols_; i++)
577  if (hincol_[i] == 0)
578  empty++;
579  return (empty);
580  }
582 
587  {
588  return handler_;
589  }
595  inline void setMessageHandler(CoinMessageHandler *handler)
596  {
597  if (defaultHandler_ == true) {
598  delete handler_;
599  defaultHandler_ = false;
600  }
601  handler_ = handler;
602  }
604  inline CoinMessages messages() const
605  {
606  return messages_;
607  }
609 
619 
621  int ncols_;
623  int nrows_;
626 
628  int ncols0_;
630  int nrows0_;
643  double bulkRatio_;
645 
657  int *hincol_;
659  int *hrow_;
661  double *colels_;
662 
664  double *cost_;
667 
669  double *clo_;
671  double *cup_;
672 
674  double *rlo_;
676  double *rup_;
677 
692 
694  double ztolzb_;
696  double ztoldj_;
697 
703  double maxmin_;
705 
726  double *sol_;
732  double *rowduals_;
738  double *acts_;
744  double *rcosts_;
745 
752  unsigned char *colstat_;
753 
760  unsigned char *rowstat_;
762 
778 };
779 
784 
810 public:
811  int pre, suc;
812 };
813 
814 #define NO_LINK -66666666
815 
821 inline void PRESOLVE_REMOVE_LINK(presolvehlink *link, int i)
822 {
823  int ipre = link[i].pre;
824  int isuc = link[i].suc;
825  if (ipre >= 0) {
826  link[ipre].suc = isuc;
827  }
828  if (isuc >= 0) {
829  link[isuc].pre = ipre;
830  }
831  link[i].pre = NO_LINK, link[i].suc = NO_LINK;
832 }
833 
839 inline void PRESOLVE_INSERT_LINK(presolvehlink *link, int i, int j)
840 {
841  int isuc = link[j].suc;
842  link[j].suc = i;
843  link[i].pre = j;
844  if (isuc >= 0) {
845  link[isuc].pre = i;
846  }
847  link[i].suc = isuc;
848 }
849 
861 inline void PRESOLVE_MOVE_LINK(presolvehlink *link, int i, int j)
862 {
863  int ipre = link[i].pre;
864  int isuc = link[i].suc;
865  if (ipre >= 0) {
866  link[ipre].suc = j;
867  }
868  if (isuc >= 0) {
869  link[isuc].pre = j;
870  }
871  link[i].pre = NO_LINK, link[i].suc = NO_LINK;
872 }
873 
906 public:
913  CoinPresolveMatrix(int ncols_alloc, int nrows_alloc,
914  CoinBigIndex nelems_alloc);
915 
920  CoinPresolveMatrix(int ncols0,
921  double maxmin,
922  // end prepost members
923 
924  ClpSimplex *si,
925 
926  // rowrep
927  int nrows,
928  CoinBigIndex nelems,
929  bool doStatus,
930  double nonLinearVariable,
931  double bulkRatio);
932 
934  void update_model(ClpSimplex *si,
935  int nrows0,
936  int ncols0,
937  CoinBigIndex nelems0);
942  CoinPresolveMatrix(int ncols0,
943  double maxmin,
944  // end prepost members
945  OsiSolverInterface *si,
946  // rowrep
947  int nrows,
948  CoinBigIndex nelems,
949  bool doStatus,
950  double nonLinearVariable,
951  const char *prohibited,
952  const char *rowProhibited = NULL);
953 
955  void update_model(OsiSolverInterface *si,
956  int nrows0,
957  int ncols0,
958  CoinBigIndex nelems0);
959 
962 
969 
978  void setMatrix(const CoinPackedMatrix *mtx);
979 
981  inline int countEmptyRows()
982  {
983  int empty = 0;
984  for (int i = 0; i < nrows_; i++)
985  if (hinrow_[i] == 0)
986  empty++;
987  return (empty);
988  }
989 
995  inline void setVariableType(int i, int variableType)
996  {
997  if (integerType_ == 0)
998  integerType_ = new unsigned char[ncols0_];
999  integerType_[i] = static_cast< unsigned char >(variableType);
1000  }
1001 
1007  void setVariableType(const unsigned char *variableType, int lenParam);
1008 
1014  void setVariableType(bool allIntegers, int lenParam);
1015 
1017  inline void setAnyInteger(bool anyInteger = true)
1018  {
1020  }
1022 
1026 
1028  inline const CoinBigIndex *getRowStarts() const
1029  {
1030  return (mrstrt_);
1031  }
1033  inline const int *getColIndicesByRow() const
1034  {
1035  return (hcol_);
1036  }
1038  inline const double *getElementsByRow() const
1039  {
1040  return (rowels_);
1041  }
1042 
1048  inline bool isInteger(int i) const
1049  {
1050  if (integerType_ == 0) {
1051  return (anyInteger_);
1052  } else if (integerType_[i] == 1) {
1053  return (true);
1054  } else {
1055  return (false);
1056  }
1057  }
1058 
1063  inline bool anyInteger() const
1064  {
1065  return (anyInteger_);
1066  }
1068  inline int presolveOptions() const
1069  {
1070  return presolveOptions_;
1071  }
1073  inline void setPresolveOptions(int value)
1074  {
1075  presolveOptions_ = value;
1076  }
1078 
1091 
1093  double dobias_;
1094 
1096  inline void change_bias(double change_amount)
1097  {
1098  dobias_ += change_amount;
1099 #if PRESOLVE_DEBUG > 2
1100  assert(fabs(change_amount) < 1.0e50);
1101  if (change_amount)
1102  PRESOLVE_STMT(printf("changing bias by %g to %g\n",
1103  change_amount, dobias_));
1104 #endif
1105  }
1106 
1118  int *hinrow_;
1120  double *rowels_;
1122  int *hcol_;
1124 
1126  unsigned char *integerType_;
1134  bool tuning_;
1136  void statistics();
1138  double startTime_;
1139 
1143  inline double feasibilityTolerance()
1144  {
1145  return (feasibilityTolerance_);
1146  }
1148  inline void setFeasibilityTolerance(double val)
1149  {
1150  feasibilityTolerance_ = val;
1151  }
1152 
1158  int status_;
1160  inline int status()
1161  {
1162  return (status_);
1163  }
1165  inline void setStatus(int status)
1166  {
1167  status_ = (status & 0x3);
1168  }
1169 
1177  int pass_;
1179  inline void setPass(int pass = 0)
1180  {
1181  pass_ = pass;
1182  }
1183 
1190  inline void setMaximumSubstitutionLevel(int level)
1191  {
1192  maxSubstLevel_ = level;
1193  }
1194 
1218  unsigned char *colChanged_;
1227 
1237  unsigned char *rowChanged_;
1271 
1291  double *randomNumber_;
1292 
1296  double *sumUp_;
1300  double *sumDown_;
1302 
1314  int recomputeSums(int whichRow);
1315 
1319  void deleteStuff();
1320 
1323 
1330 
1337 
1339  inline int numberColsToDo()
1340  {
1341  return (numberColsToDo_);
1342  }
1343 
1345  inline bool colChanged(int i) const
1346  {
1347  return (colChanged_[i] & 1) != 0;
1348  }
1350  inline void unsetColChanged(int i)
1351  {
1352  colChanged_[i] = static_cast< unsigned char >(colChanged_[i] & (~1));
1353  }
1355  inline void setColChanged(int i)
1356  {
1357  colChanged_[i] = static_cast< unsigned char >(colChanged_[i] | (1));
1358  }
1360  inline void addCol(int i)
1361  {
1362  if ((colChanged_[i] & 1) == 0) {
1363  colChanged_[i] = static_cast< unsigned char >(colChanged_[i] | (1));
1365  }
1366  }
1368  inline bool colProhibited(int i) const
1369  {
1370  return (colChanged_[i] & 2) != 0;
1371  }
1378  inline bool colProhibited2(int i) const
1379  {
1380  if (!anyProhibited_)
1381  return false;
1382  else
1383  return (colChanged_[i] & 2) != 0;
1384  }
1386  inline void setColProhibited(int i)
1387  {
1388  colChanged_[i] = static_cast< unsigned char >(colChanged_[i] | (2));
1389  }
1395  inline bool colUsed(int i) const
1396  {
1397  return (colChanged_[i] & 4) != 0;
1398  }
1400  inline void setColUsed(int i)
1401  {
1402  colChanged_[i] = static_cast< unsigned char >(colChanged_[i] | (4));
1403  }
1405  inline void unsetColUsed(int i)
1406  {
1407  colChanged_[i] = static_cast< unsigned char >(colChanged_[i] & (~4));
1408  }
1410  inline bool colInfinite(int i) const
1411  {
1412  return (colChanged_[i] & 8) != 0;
1413  }
1415  inline void unsetColInfinite(int i)
1416  {
1417  colChanged_[i] = static_cast< unsigned char >(colChanged_[i] & (~8));
1418  }
1420  inline void setColInfinite(int i)
1421  {
1422  colChanged_[i] = static_cast< unsigned char >(colChanged_[i] | (8));
1423  }
1424 
1431 
1438 
1440  inline int numberRowsToDo()
1441  {
1442  return (numberRowsToDo_);
1443  }
1444 
1446  inline bool rowChanged(int i) const
1447  {
1448  return (rowChanged_[i] & 1) != 0;
1449  }
1451  inline void unsetRowChanged(int i)
1452  {
1453  rowChanged_[i] = static_cast< unsigned char >(rowChanged_[i] & (~1));
1454  }
1456  inline void setRowChanged(int i)
1457  {
1458  rowChanged_[i] = static_cast< unsigned char >(rowChanged_[i] | (1));
1459  }
1461  inline void addRow(int i)
1462  {
1463  if ((rowChanged_[i] & 1) == 0) {
1464  rowChanged_[i] = static_cast< unsigned char >(rowChanged_[i] | (1));
1466  }
1467  }
1469  inline bool rowProhibited(int i) const
1470  {
1471  return (rowChanged_[i] & 2) != 0;
1472  }
1479  inline bool rowProhibited2(int i) const
1480  {
1481  if (!anyProhibited_)
1482  return false;
1483  else
1484  return (rowChanged_[i] & 2) != 0;
1485  }
1487  inline void setRowProhibited(int i)
1488  {
1489  rowChanged_[i] = static_cast< unsigned char >(rowChanged_[i] | (2));
1490  }
1496  inline bool rowUsed(int i) const
1497  {
1498  return (rowChanged_[i] & 4) != 0;
1499  }
1501  inline void setRowUsed(int i)
1502  {
1503  rowChanged_[i] = static_cast< unsigned char >(rowChanged_[i] | (4));
1504  }
1506  inline void unsetRowUsed(int i)
1507  {
1508  rowChanged_[i] = static_cast< unsigned char >(rowChanged_[i] & (~4));
1509  }
1510 
1512  inline bool anyProhibited() const
1513  {
1514  return anyProhibited_;
1515  }
1517  inline void setAnyProhibited(bool val = true)
1518  {
1519  anyProhibited_ = val;
1520  }
1522 };
1523 
1553 public:
1560  CoinPostsolveMatrix(int ncols_alloc, int nrows_alloc,
1561  CoinBigIndex nelems_alloc);
1562 
1567  CoinPostsolveMatrix(ClpSimplex *si,
1568 
1569  int ncols0,
1570  int nrows0,
1571  CoinBigIndex nelems0,
1572 
1573  double maxmin_,
1574  // end prepost members
1575 
1576  double *sol,
1577  double *acts,
1578 
1579  unsigned char *colstat,
1580  unsigned char *rowstat);
1581 
1586  CoinPostsolveMatrix(OsiSolverInterface *si,
1587 
1588  int ncols0,
1589  int nrows0,
1590  CoinBigIndex nelems0,
1591 
1592  double maxmin_,
1593  // end prepost members
1594 
1595  double *sol,
1596  double *acts,
1597 
1598  unsigned char *colstat,
1599  unsigned char *rowstat);
1600 
1612 
1615 
1627 
1637 
1639 
1647  char *cdone_;
1648  char *rdone_;
1650 
1653 };
1654 
1661 
1666 void presolve_make_memlists(/*CoinBigIndex *starts,*/ int *lengths,
1667  presolvehlink *link, int n);
1668 
1676 bool presolve_expand_major(CoinBigIndex *majstrts, double *majels,
1677  int *minndxs, int *majlens,
1678  presolvehlink *majlinks, int nmaj, int k);
1679 
1685 inline bool presolve_expand_col(CoinBigIndex *mcstrt, double *colels,
1686  int *hrow, int *hincol,
1687  presolvehlink *clink, int ncols, int colx)
1688 {
1689  return presolve_expand_major(mcstrt, colels,
1690  hrow, hincol, clink, ncols, colx);
1691 }
1692 
1698 inline bool presolve_expand_row(CoinBigIndex *mrstrt, double *rowels,
1699  int *hcol, int *hinrow,
1700  presolvehlink *rlink, int nrows, int rowx)
1701 {
1702  return presolve_expand_major(mrstrt, rowels,
1703  hcol, hinrow, rlink, nrows, rowx);
1704 }
1705 
1715  CoinBigIndex ks, CoinBigIndex ke,
1716  const int *minndxs)
1717 {
1718  CoinBigIndex k;
1719  for (k = ks; k < ke; k++)
1720 #ifndef NDEBUG
1721  {
1722  if (minndxs[k] == tgt)
1723  return (k);
1724  }
1725  DIE("FIND_MINOR");
1726 
1727  abort();
1728  return -1;
1729 #else
1730  {
1731  if (minndxs[k] == tgt)
1732  break;
1733  }
1734  return (k);
1735 #endif
1736 }
1737 
1745  CoinBigIndex kce, const int *hrow)
1746 {
1747  return presolve_find_minor(row, kcs, kce, hrow);
1748 }
1749 
1757  CoinBigIndex kre, const int *hcol)
1758 {
1759  return presolve_find_minor(col, krs, kre, hcol);
1760 }
1761 
1771  const int *minndxs);
1772 
1780  CoinBigIndex kce, const int *hrow)
1781 {
1782  return presolve_find_minor1(row, kcs, kce, hrow);
1783 }
1784 
1792  CoinBigIndex kre, const int *hcol)
1793 {
1794  return presolve_find_minor1(col, krs, kre, hcol);
1795 }
1796 
1806  const int *minndxs,
1807  const CoinBigIndex *majlinks);
1808 
1816 inline CoinBigIndex presolve_find_row2(int row, CoinBigIndex kcs, int collen,
1817  const int *hrow,
1818  const CoinBigIndex *clinks)
1819 {
1820  return presolve_find_minor2(row, kcs, collen, hrow, clinks);
1821 }
1822 
1832  const int *minndxs,
1833  const CoinBigIndex *majlinks);
1834 
1842 inline CoinBigIndex presolve_find_row3(int row, CoinBigIndex kcs, int collen,
1843  const int *hrow,
1844  const CoinBigIndex *clinks)
1845 {
1846  return presolve_find_minor3(row, kcs, collen, hrow, clinks);
1847 }
1848 
1858 inline void presolve_delete_from_major(int majndx, int minndx,
1859  const CoinBigIndex *majstrts,
1860  int *majlens, int *minndxs, double *els)
1861 {
1862  const CoinBigIndex ks = majstrts[majndx];
1863  const CoinBigIndex ke = ks + majlens[majndx];
1864 
1865  const CoinBigIndex kmi = presolve_find_minor(minndx, ks, ke, minndxs);
1866 
1867  minndxs[kmi] = minndxs[ke - 1];
1868  els[kmi] = els[ke - 1];
1869  majlens[majndx]--;
1870 
1871  return;
1872 }
1873 
1880 inline void presolve_delete_many_from_major(int majndx, char *marked,
1881  const CoinBigIndex *majstrts,
1882  int *majlens, int *minndxs, double *els)
1883 {
1884  const CoinBigIndex ks = majstrts[majndx];
1885  const CoinBigIndex ke = ks + majlens[majndx];
1886  CoinBigIndex put = ks;
1887  for (CoinBigIndex k = ks; k < ke; k++) {
1888  int iMinor = minndxs[k];
1889  if (!marked[iMinor]) {
1890  minndxs[put] = iMinor;
1891  els[put++] = els[k];
1892  } else {
1893  marked[iMinor] = 0;
1894  }
1895  }
1896  majlens[majndx] = static_cast< int >(put - ks);
1897  return;
1898 }
1899 
1910 inline void presolve_delete_from_col(int row, int col,
1911  const CoinBigIndex *mcstrt,
1912  int *hincol, int *hrow, double *colels)
1913 {
1914  presolve_delete_from_major(col, row, mcstrt, hincol, hrow, colels);
1915 }
1916 
1927 inline void presolve_delete_from_row(int row, int col,
1928  const CoinBigIndex *mrstrt,
1929  int *hinrow, int *hcol, double *rowels)
1930 {
1931  presolve_delete_from_major(row, col, mrstrt, hinrow, hcol, rowels);
1932 }
1933 
1944 void presolve_delete_from_major2(int majndx, int minndx,
1945  CoinBigIndex *majstrts, int *majlens,
1946  int *minndxs, CoinBigIndex *majlinks,
1947  CoinBigIndex *free_listp);
1948 
1959 inline void presolve_delete_from_col2(int row, int col, CoinBigIndex *mcstrt,
1960  int *hincol, int *hrow,
1961  CoinBigIndex *clinks, CoinBigIndex *free_listp)
1962 {
1963  presolve_delete_from_major2(col, row, mcstrt, hincol, hrow, clinks, free_listp);
1964 }
1965 
1967 
1973 
1985 double *presolve_dupmajor(const double *elems, const int *indices,
1986  int length, CoinBigIndex offset, int tgt = -1);
1987 
1989 void coin_init_random_vec(double *work, int n);
1990 
1992 
1993 #endif
1994 
1995 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
1996 */
This file contains the enum for the standard set of Coin messages and a class definition whose sole p...
const double ZTOLDP2
Alternate zero tolerance.
#define NO_LINK
const double ZTOLDP
Zero tolerance.
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.
#define PRESOLVE_INF
The usual finite infinity.
#define PRESOLVE_STMT(s)
void coin_init_random_vec(double *work, int n)
Initialize a vector with random numbers.
void DIE(const char *)
int CoinBigIndex
Error Class thrown by an exception.
Definition: CoinError.hpp:42
Base class for message handling.
The standard set of Coin messages.
Definition: CoinMessage.hpp:78
Class to hold and manipulate an array of massaged messages.
Sparse Matrix Base Class.
Augments CoinPrePostsolveMatrix with information about the problem that is only needed during postsol...
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.
CoinPostsolveMatrix(ClpSimplex *si, int ncols0, int nrows0, CoinBigIndex nelems0, double maxmin_, double *sol, double *acts, unsigned char *colstat, unsigned char *rowstat)
Clp OSI constructor.
~CoinPostsolveMatrix()
Destructor.
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.
CoinBigIndex * link_
Thread array.
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 free_list_
First entry in free entries thread.
void presolve_delete_from_major2(int majndx, int minndx, CoinBigIndex *majstrts, int *majlens, int *minndxs, CoinBigIndex *majlinks, CoinBigIndex *free_listp)
Delete the entry for a minor index from a major vector in a threaded matrix.
CoinBigIndex maxlink_
Allocated size of link_.
void presolve_delete_from_col2(int row, int col, CoinBigIndex *mcstrt, int *hincol, int *hrow, CoinBigIndex *clinks, CoinBigIndex *free_listp)
Delete the entry for row row from column col in a column-major threaded matrix.
void assignPresolveToPostsolve(CoinPresolveMatrix *&preObj)
Load an empty CoinPostsolveMatrix from a CoinPresolveMatrix.
CoinPostsolveMatrix(int ncols_alloc, int nrows_alloc, CoinBigIndex nelems_alloc)
‘Native’ constructor
CoinPostsolveMatrix(OsiSolverInterface *si, int ncols0, int nrows0, CoinBigIndex nelems0, double maxmin_, double *sol, double *acts, unsigned char *colstat, unsigned char *rowstat)
Generic OSI constructor.
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.
void check_nbasic()
debug
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.
Collects all the information about the problem that is needed in both presolve and postsolve.
bool defaultHandler_
Indicates if the current handler_ is default (true) or not (false).
double * rlo_
Row (constraint) lower bounds.
int ncols_
current number of columns
double maxmin_
Maximization/minimization.
double * cup_
Column (primal variable) upper bounds.
int countEmptyCols()
Count empty columns.
void setPrimalTolerance(double primTol)
Set the primal feasibility tolerance.
const int * getColLengths() const
Get column length vector for column-major packed matrix.
double * cost_
Objective coefficients.
void setRowUpper(const double *rowUpper, int lenParam)
Set row upper bounds.
const CoinBigIndex * getColStarts() const
Get column start vector for column-major packed matrix.
double ztoldj_
Dual feasibility tolerance.
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 setRowLower(const double *rowLower, int lenParam)
Set row lower bounds.
const char * columnStatusString(int j) const
Return a print string for status of a column (structural variable)
CoinMessages messages() const
Return messages.
CoinBigIndex bulk0_
Allocated size of bulk storage for row indices and coefficients.
CoinBigIndex getNumElems() const
Get current number of non-zero coefficients.
CoinBigIndex nelems_
current number of coefficients
void setCost(const double *cost, int lenParam)
Set objective coefficients.
int nrows_
current number of rows
double * sol_
Vector of primal variable values.
CoinPrePostsolveMatrix(const OsiSolverInterface *si, int ncols_, int nrows_, CoinBigIndex nelems_)
Generic OSI constructor.
Status getRowStatus(int sequence) const
Get row status.
void setRowStatusUsingValue(int iRow)
Set status of row (artificial variable) to the correct nonbasic status given bounds and current value...
~CoinPrePostsolveMatrix()
Destructor.
int nrows0_
Allocated number of rows.
void setColLower(const double *colLower, int lenParam)
Set column lower bounds.
bool columnIsBasic(int sequence) const
Check if column (structural variable) is basic.
const double * getRowPrice() const
Get row solution (dual variables)
void presolve_make_memlists(int *lengths, presolvehlink *link, int n)
Initialise linked list for major vector order in bulk storage.
CoinPrePostsolveMatrix(const ClpSimplex *si, int ncols_, int nrows_, CoinBigIndex nelems_, double bulkRatio)
ClpOsi constructor.
void setObjOffset(double offset)
Set the objective function offset for the original system.
double ztolzb_
Primal feasibility tolerance.
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.
double * clo_
Column (primal variable) lower bounds.
int getNumRows() const
Get current number of rows.
const double * getRowLower() const
Get row lower bounds.
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 double * getRowUpper() const
Get row upper bounds.
CoinBigIndex nelems0_
Allocated number of coefficients.
int ncols0_
Allocated number of columns.
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.
void setStatus(const CoinWarmStartBasis *basis)
Set the status of all variables from a basis.
int * originalRow_
Original row numbers.
const double * getCost() const
Get objective coefficients.
bool rowIsBasic(int sequence) const
Check if artificial for this row is basic.
CoinMessage messages_
Standard COIN messages.
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.
const double * getReducedCost() const
Get reduced costs.
void setStructuralStatus(const char *strucStatus, int lenParam)
Set column (structural variable) status vector.
const double * getColUpper() const
Get column upper bounds.
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 bulkRatio_
Ratio of bulk0_ to nelems0_; default is 2.
const double * getElementsByCol() const
Get vector of elements for column-major packed matrix.
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 setObjSense(double objSense)
Set the objective sense (max/min)
void setColumnStatusUsingValue(int iColumn)
Set status of column (structural variable) to the correct nonbasic status given bounds and current va...
const double * getRowActivity() const
Get row activity (constraint lhs values)
Status
Enum for status of various sorts.
void setColumnStatus(int sequence, Status status)
Set column status (i.e., status of primal variable)
CoinWarmStartBasis * getStatus()
Get status in the form of a CoinWarmStartBasis.
CoinBigIndex presolve_find_minor(int tgt, CoinBigIndex ks, CoinBigIndex ke, const int *minndxs)
Find position of a minor index in a major vector.
CoinMessageHandler * messageHandler() const
Return message handler.
int * originalColumn_
Original column numbers.
const char * statusName(CoinPrePostsolveMatrix::Status status)
Generate a print string for a status code.
const char * rowStatusString(int i) const
Return a print string for status of a row (artificial variable)
void presolve_delete_many_from_major(int majndx, char *marked, const CoinBigIndex *majstrts, int *majlens, int *minndxs, double *els)
Delete marked entries.
int getNumCols() const
Get current number of columns.
CoinMessageHandler * handler_
Message handler.
void setColUpper(const double *colUpper, int lenParam)
Set column upper bounds.
double * rcosts_
Vector of reduced costs.
CoinBigIndex presolve_find_minor1(int tgt, CoinBigIndex ks, CoinBigIndex ke, const int *minndxs)
Find position of a minor index in a major vector.
CoinPrePostsolveMatrix(int ncols_alloc, int nrows_alloc, CoinBigIndex nelems_alloc)
‘Native’ constructor
unsigned char * colstat_
Status of primal variables.
const int * getRowIndicesByCol() const
Get vector of row indices for column-major packed matrix.
Status getColumnStatus(int sequence) const
Get column (structural variable) status.
double * colels_
Coefficients (positional correspondence with hrow_)
void setDualTolerance(double dualTol)
Set the dual 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.
const double * getColSolution() const
Get column solution (primal variable values)
const double * getColLower() const
Get column lower bounds.
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 originalOffset_
Original objective offset.
int * hincol_
Vector of column lengths.
void setRowPrice(const double *rowSol, int lenParam)
Set row solution.
void setMessageHandler(CoinMessageHandler *handler)
Set message handler.
double * rowduals_
Vector of dual variable values.
void setRowActivity(const double *rowAct, int lenParam)
Set row activity.
double * acts_
Vector of constraint left-hand-side values (row activity)
void setArtificialStatus(const char *artifStatus, int lenParam)
Set row (artificial variable) status vector.
CoinBigIndex * mcstrt_
Vector of column start positions in hrow_, colels_.
int * hrow_
Row indices (positional correspondence with colels_)
double * rup_
Row (constraint) upper bounds.
void setColSolution(const double *colSol, int lenParam)
Set column solution.
void setReducedCost(const double *redCost, int lenParam)
Set reduced costs.
void setRowStatus(int sequence, Status status)
Set row status (i.e., status of artificial for this row)
unsigned char * rowstat_
Status of constraints.
Abstract base class of all presolve routines.
virtual ~CoinPresolveAction()
Virtual destructor.
virtual const char * name() const =0
A name for debug printing.
virtual void postsolve(CoinPostsolveMatrix *prob) const =0
Apply the postsolve transformation for this particular presolve action.
void setNext(const CoinPresolveAction *nextAction)
modify next (when building rather than passing)
static void throwCoinError(const char *error, const char *ps_routine)
Stub routine to throw exceptions.
const CoinPresolveAction * next
The next presolve transformation.
CoinPresolveAction(const CoinPresolveAction *next)
Construct a postsolve object and add it to the transformation list.
Augments CoinPrePostsolveMatrix with information about the problem that is only needed during presolv...
void update_model(ClpSimplex *si, int nrows0, int ncols0, CoinBigIndex nelems0)
Update the model held by a Clp OSI.
friend void assignPresolveToPostsolve(CoinPresolveMatrix *&preObj)
Initialize a CoinPostsolveMatrix object, destroying the CoinPresolveMatrix object.
void setRowChanged(int i)
Mark row as changed.
void change_bias(double change_amount)
Adjust objective function constant offset.
double feasibilityTolerance_
Bounds can be moved by this to retain feasibility.
int stepRowsToDo()
Step row ToDo lists.
void setMaximumSubstitutionLevel(int level)
Set Maximum substitution level (normally 3)
void unsetColInfinite(int i)
Mark column as not infinite ub (originally)
void unsetColChanged(int i)
Mark column as not changed.
double * usefulRowDouble_
Preallocated scratch work array, 2*nrows_.
int * hcol_
Column indices (positional correspondence with rowels_)
void addCol(int i)
Mark column as changed and add to list of columns to process next.
void setRowUsed(int i)
Mark row as used.
void setColUsed(int i)
Mark column as used.
~CoinPresolveMatrix()
Destructor.
double dobias_
Objective function offset introduced during presolve.
int recomputeSums(int whichRow)
Recompute row lhs bounds.
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.
void setRowProhibited(int i)
Mark row as ineligible for preprocessing.
bool rowProhibited(int i) const
Test if row is eligible for preprocessing.
bool anyInteger_
Flag to say if any variables are integer.
bool colProhibited2(int i) const
Test if column is eligible for preprocessing.
int numberNextColsToDo_
Length of nextColsToDo_.
void unsetRowUsed(int i)
Mark row as unused.
void unsetColUsed(int i)
Mark column as unused.
void statistics()
Say we want statistics - also set time.
int * hinrow_
Vector of row lengths.
void setAnyProhibited(bool val=true)
Set a flag for presence of prohibited rows or columns.
void setVariableType(int i, int variableType)
Set variable type information for a single variable.
double startTime_
Start time of presolve.
void setStatus(int status)
Set problem status.
void update_model(OsiSolverInterface *si, int nrows0, int ncols0, CoinBigIndex nelems0)
Update the model held by a generic OSI.
int numberRowsToDo_
Length of rowsToDo_.
int numberColsToDo_
Length of colsToDo_.
bool colUsed(int i) const
Test if column is marked as used.
double * rowels_
Coefficients (positional correspondence with hcol_)
unsigned char * integerType_
Tracks integrality of columns (1 for integer, 0 for continuous)
void unsetRowChanged(int i)
Mark row as not changed.
void initializeStuff()
Allocate scratch arrays.
int * usefulColumnInt_
Preallocated scratch work array, 2*ncols_.
int numberColsToDo()
Return the number of columns on the colsToDo_ list.
CoinBigIndex * mrstrt_
Vector of row start positions in #hcol, rowels_.
presolvehlink * clink_
Linked list for the column-major representation.
unsigned char * rowChanged_
Row change status information.
bool isInteger(int i) const
Check for integrality of the specified variable.
bool colProhibited(int i) const
Test if column is eligible for preprocessing.
int stepColsToDo()
Step column ToDo lists.
void setMatrix(const CoinPackedMatrix *mtx)
Load the cofficient matrix.
bool rowUsed(int i) const
Test if row is marked as used.
void setColProhibited(int i)
Mark column as ineligible for preprocessing.
bool anyInteger() const
Check if there are any integer variables.
void setPass(int pass=0)
Set pass number.
int status_
Output status: 0 = feasible, 1 = infeasible, 2 = unbounded.
void initRowsToDo()
Initialise the row ToDo lists.
int pass_
Presolve pass number.
void setVariableType(bool allIntegers, int lenParam)
Set the type of all variables.
int * usefulRowInt_
Preallocated scratch work array, 3*nrows_.
const double * getElementsByRow() const
Get vector of elements for row-major packed matrix.
int * infiniteUp_
Work array for count of infinite contributions to row lhs upper bound.
int status()
Returns problem status (0 = feasible, 1 = infeasible, 2 = unbounded)
void setColChanged(int i)
Mark column as changed.
int numberNextRowsToDo_
Length of nextRowsToDo_.
const CoinBigIndex * getRowStarts() const
Get row start vector for row-major packed matrix.
void addRow(int i)
Mark row as changed and add to list of rows to process next.
void setFeasibilityTolerance(double val)
Set feasibility tolerance.
void deleteStuff()
Free scratch arrays.
void setPresolveOptions(int value)
Sets any special options (see presolveOptions_)
CoinPresolveMatrix(int ncols0, double maxmin, ClpSimplex *si, int nrows, CoinBigIndex nelems, bool doStatus, double nonLinearVariable, double bulkRatio)
Clp OSI constructor.
bool colChanged(int i) const
Has column been changed?
int presolveOptions_
Fine control over presolve actions.
int numberRowsToDo()
Return the number of rows on the rowsToDo_ list.
double * sumDown_
Work array for sum of finite contributions to row lhs lower bound.
bool rowChanged(int i) const
Has row been changed?
bool tuning_
Print statistics for tuning.
const int * getColIndicesByRow() const
Get vector of column indices for row-major packed matrix.
int * nextRowsToDo_
Output list of rows to process next.
CoinPresolveMatrix(int ncols_alloc, int nrows_alloc, CoinBigIndex nelems_alloc)
‘Native’ constructor
double * randomNumber_
Array of random numbers (max row,column)
int presolveOptions() const
Picks up any special options.
int * infiniteDown_
Work array for count of infinite contributions to row lhs lower bound.
bool rowProhibited2(int i) const
Test if row is eligible for preprocessing.
void initColsToDo()
Initialise the column ToDo lists.
int * colsToDo_
Input list of columns to process.
void setColInfinite(int i)
Mark column as infinite ub (originally)
double feasibilityTolerance()
Return feasibility tolerance.
bool anyProhibited() const
Check if there are any prohibited rows or columns.
int maxSubstLevel_
Maximum substitution level.
int * rowsToDo_
Input list of rows to process.
int * nextColsToDo_
Output list of columns to process next.
double * sumUp_
Work array for sum of finite contributions to row lhs upper bound.
presolvehlink * rlink_
Linked list for the row-major representation.
bool anyProhibited_
Flag to say if any rows or columns are marked as prohibited.
double * usefulColumnDouble_
Preallocated scratch work array, ncols_.
unsigned char * colChanged_
Column change status information.
bool colInfinite(int i) const
Has column infinite ub (originally)
void setVariableType(const unsigned char *variableType, int lenParam)
Set variable type information for all variables.
int countEmptyRows()
Count number of empty rows.
void setAnyInteger(bool anyInteger=true)
Set a flag for presence (true) or absence (false) of integer variables.
The default COIN simplex (basis-oriented) warm start class.