CoinUtils  2.11.4
CoinPresolveMatrix.hpp
Go to the documentation of this file.
1 /* $Id$ */
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  if (rowstat_ == nullptr) return;
350  unsigned char &st_byte = rowstat_[sequence];
351  st_byte = static_cast< unsigned char >(st_byte & (~7));
352  st_byte = static_cast< unsigned char >(st_byte | status);
353  }
355  inline Status getRowStatus(int sequence) const
356  {
357  return static_cast< Status >(rowstat_[sequence] & 7);
358  }
360  inline bool rowIsBasic(int sequence) const
361  {
362  return (static_cast< Status >(rowstat_[sequence] & 7) == basic);
363  }
365  inline void setColumnStatus(int sequence, Status status)
366  {
367  if (colstat_ == nullptr) return;
368  unsigned char &st_byte = colstat_[sequence];
369  st_byte = static_cast< unsigned char >(st_byte & (~7));
370  st_byte = static_cast< unsigned char >(st_byte | status);
371 
372 #ifdef PRESOLVE_DEBUG
373  switch (status) {
374  case isFree: {
375  if (clo_[sequence] > -PRESOLVE_INF || cup_[sequence] < PRESOLVE_INF) {
376  std::cout << "Bad status: Var " << sequence
377  << " isFree, lb = " << clo_[sequence]
378  << ", ub = " << cup_[sequence] << std::endl;
379  }
380  break;
381  }
382  case basic: {
383  break;
384  }
385  case atUpperBound: {
386  if (cup_[sequence] >= PRESOLVE_INF) {
387  std::cout << "Bad status: Var " << sequence
388  << " atUpperBound, lb = " << clo_[sequence]
389  << ", ub = " << cup_[sequence] << std::endl;
390  }
391  break;
392  }
393  case atLowerBound: {
394  if (clo_[sequence] <= -PRESOLVE_INF) {
395  std::cout << "Bad status: Var " << sequence
396  << " atLowerBound, lb = " << clo_[sequence]
397  << ", ub = " << cup_[sequence] << std::endl;
398  }
399  break;
400  }
401  case superBasic: {
402  if (clo_[sequence] <= -PRESOLVE_INF && cup_[sequence] >= PRESOLVE_INF) {
403  std::cout << "Bad status: Var " << sequence
404  << " superBasic, lb = " << clo_[sequence]
405  << ", ub = " << cup_[sequence] << std::endl;
406  }
407  break;
408  }
409  default: {
410  assert(false);
411  break;
412  }
413  }
414 #endif
415  }
417  inline Status getColumnStatus(int sequence) const
418  {
419  return static_cast< Status >(colstat_[sequence] & 7);
420  }
422  inline bool columnIsBasic(int sequence) const
423  {
424  return (static_cast< Status >(colstat_[sequence] & 7) == basic);
425  }
429  void setRowStatusUsingValue(int iRow);
433  void setColumnStatusUsingValue(int iColumn);
435  void setStructuralStatus(const char *strucStatus, int lenParam);
437  void setArtificialStatus(const char *artifStatus, int lenParam);
439  void setStatus(const CoinWarmStartBasis *basis);
445  const char *columnStatusString(int j) const;
449  const char *rowStatusString(int i) const;
451 
460  void setObjOffset(double offset);
467  void setObjSense(double objSense);
469  void setPrimalTolerance(double primTol);
471  void setDualTolerance(double dualTol);
473  void setColLower(const double *colLower, int lenParam);
475  void setColUpper(const double *colUpper, int lenParam);
477  void setColSolution(const double *colSol, int lenParam);
479  void setCost(const double *cost, int lenParam);
481  void setReducedCost(const double *redCost, int lenParam);
483  void setRowLower(const double *rowLower, int lenParam);
485  void setRowUpper(const double *rowUpper, int lenParam);
487  void setRowPrice(const double *rowSol, int lenParam);
489  void setRowActivity(const double *rowAct, int lenParam);
491 
495  inline int getNumCols() const
496  {
497  return (ncols_);
498  }
500  inline int getNumRows() const
501  {
502  return (nrows_);
503  }
505  inline CoinBigIndex getNumElems() const
506  {
507  return (nelems_);
508  }
510  inline const CoinBigIndex *getColStarts() const
511  {
512  return (mcstrt_);
513  }
515  inline const int *getColLengths() const
516  {
517  return (hincol_);
518  }
520  inline const int *getRowIndicesByCol() const
521  {
522  return (hrow_);
523  }
525  inline const double *getElementsByCol() const
526  {
527  return (colels_);
528  }
530  inline const double *getColLower() const
531  {
532  return (clo_);
533  }
535  inline const double *getColUpper() const
536  {
537  return (cup_);
538  }
540  inline const double *getCost() const
541  {
542  return (cost_);
543  }
545  inline const double *getRowLower() const
546  {
547  return (rlo_);
548  }
550  inline const double *getRowUpper() const
551  {
552  return (rup_);
553  }
555  inline const double *getColSolution() const
556  {
557  return (sol_);
558  }
560  inline const double *getRowActivity() const
561  {
562  return (acts_);
563  }
565  inline const double *getRowPrice() const
566  {
567  return (rowduals_);
568  }
570  inline const double *getReducedCost() const
571  {
572  return (rcosts_);
573  }
575  inline int countEmptyCols()
576  {
577  int empty = 0;
578  for (int i = 0; i < ncols_; i++)
579  if (hincol_[i] == 0)
580  empty++;
581  return (empty);
582  }
584 
589  {
590  return handler_;
591  }
597  inline void setMessageHandler(CoinMessageHandler *handler)
598  {
599  if (defaultHandler_ == true) {
600  delete handler_;
601  defaultHandler_ = false;
602  }
603  handler_ = handler;
604  }
606  inline CoinMessages messages() const
607  {
608  return messages_;
609  }
611 
621 
623  int ncols_;
625  int nrows_;
628 
630  int ncols0_;
632  int nrows0_;
645  double bulkRatio_;
647 
659  int *hincol_;
661  int *hrow_;
663  double *colels_;
664 
666  double *cost_;
669 
671  double *clo_;
673  double *cup_;
674 
676  double *rlo_;
678  double *rup_;
679 
694 
696  double ztolzb_;
698  double ztoldj_;
699 
705  double maxmin_;
707 
728  double *sol_;
734  double *rowduals_;
740  double *acts_;
746  double *rcosts_;
747 
754  unsigned char *colstat_;
755 
762  unsigned char *rowstat_;
764 
780 };
781 
786 
812 public:
813  int pre, suc;
814 };
815 
816 #define NO_LINK -66666666
817 
823 inline void PRESOLVE_REMOVE_LINK(presolvehlink *link, int i)
824 {
825  int ipre = link[i].pre;
826  int isuc = link[i].suc;
827  if (ipre >= 0) {
828  link[ipre].suc = isuc;
829  }
830  if (isuc >= 0) {
831  link[isuc].pre = ipre;
832  }
833  link[i].pre = NO_LINK, link[i].suc = NO_LINK;
834 }
835 
841 inline void PRESOLVE_INSERT_LINK(presolvehlink *link, int i, int j)
842 {
843  int isuc = link[j].suc;
844  link[j].suc = i;
845  link[i].pre = j;
846  if (isuc >= 0) {
847  link[isuc].pre = i;
848  }
849  link[i].suc = isuc;
850 }
851 
863 inline void PRESOLVE_MOVE_LINK(presolvehlink *link, int i, int j)
864 {
865  int ipre = link[i].pre;
866  int isuc = link[i].suc;
867  if (ipre >= 0) {
868  link[ipre].suc = j;
869  }
870  if (isuc >= 0) {
871  link[isuc].pre = j;
872  }
873  link[i].pre = NO_LINK, link[i].suc = NO_LINK;
874 }
875 
908 public:
915  CoinPresolveMatrix(int ncols_alloc, int nrows_alloc,
916  CoinBigIndex nelems_alloc);
917 
922  CoinPresolveMatrix(int ncols0,
923  double maxmin,
924  // end prepost members
925 
926  ClpSimplex *si,
927 
928  // rowrep
929  int nrows,
930  CoinBigIndex nelems,
931  bool doStatus,
932  double nonLinearVariable,
933  double bulkRatio);
934 
936  void update_model(ClpSimplex *si,
937  int nrows0,
938  int ncols0,
939  CoinBigIndex nelems0);
944  CoinPresolveMatrix(int ncols0,
945  double maxmin,
946  // end prepost members
947  OsiSolverInterface *si,
948  // rowrep
949  int nrows,
950  CoinBigIndex nelems,
951  bool doStatus,
952  double nonLinearVariable,
953  const char *prohibited,
954  const char *rowProhibited = NULL);
955 
957  void update_model(OsiSolverInterface *si,
958  int nrows0,
959  int ncols0,
960  CoinBigIndex nelems0);
961 
964 
971 
980  void setMatrix(const CoinPackedMatrix *mtx);
981 
983  inline int countEmptyRows()
984  {
985  int empty = 0;
986  for (int i = 0; i < nrows_; i++)
987  if (hinrow_[i] == 0)
988  empty++;
989  return (empty);
990  }
991 
997  inline void setVariableType(int i, int variableType)
998  {
999  if (integerType_ == 0)
1000  integerType_ = new unsigned char[ncols0_];
1001  integerType_[i] = static_cast< unsigned char >(variableType);
1002  }
1003 
1009  void setVariableType(const unsigned char *variableType, int lenParam);
1010 
1016  void setVariableType(bool allIntegers, int lenParam);
1017 
1019  inline void setAnyInteger(bool anyInteger = true)
1020  {
1022  }
1024 
1028 
1030  inline const CoinBigIndex *getRowStarts() const
1031  {
1032  return (mrstrt_);
1033  }
1035  inline const int *getColIndicesByRow() const
1036  {
1037  return (hcol_);
1038  }
1040  inline const double *getElementsByRow() const
1041  {
1042  return (rowels_);
1043  }
1044 
1050  inline bool isInteger(int i) const
1051  {
1052  if (integerType_ == 0) {
1053  return (anyInteger_);
1054  } else if (integerType_[i] == 1) {
1055  return (true);
1056  } else {
1057  return (false);
1058  }
1059  }
1060 
1065  inline bool anyInteger() const
1066  {
1067  return (anyInteger_);
1068  }
1070  inline int presolveOptions() const
1071  {
1072  return presolveOptions_;
1073  }
1075  inline void setPresolveOptions(int value)
1076  {
1077  presolveOptions_ = value;
1078  }
1080 
1093 
1095  double dobias_;
1096 
1098  inline void change_bias(double change_amount)
1099  {
1100  dobias_ += change_amount;
1101 #if PRESOLVE_DEBUG > 2
1102  assert(fabs(change_amount) < 1.0e50);
1103  if (change_amount)
1104  PRESOLVE_STMT(printf("changing bias by %g to %g\n",
1105  change_amount, dobias_));
1106 #endif
1107  }
1108 
1120  int *hinrow_;
1122  double *rowels_;
1124  int *hcol_;
1126 
1128  unsigned char *integerType_;
1136  bool tuning_;
1138  void statistics();
1140  double startTime_;
1141 
1145  inline double feasibilityTolerance()
1146  {
1147  return (feasibilityTolerance_);
1148  }
1150  inline void setFeasibilityTolerance(double val)
1151  {
1152  feasibilityTolerance_ = val;
1153  }
1154 
1160  int status_;
1162  inline int status()
1163  {
1164  return (status_);
1165  }
1167  inline void setStatus(int status)
1168  {
1169  status_ = (status & 0x3);
1170  }
1171 
1179  int pass_;
1181  inline void setPass(int pass = 0)
1182  {
1183  pass_ = pass;
1184  }
1185 
1192  inline void setMaximumSubstitutionLevel(int level)
1193  {
1194  maxSubstLevel_ = level;
1195  }
1196 
1220  unsigned char *colChanged_;
1229 
1239  unsigned char *rowChanged_;
1273 
1293  double *randomNumber_;
1294 
1298  double *sumUp_;
1302  double *sumDown_;
1304 
1316  int recomputeSums(int whichRow);
1317 
1321  void deleteStuff();
1322 
1325 
1332 
1339 
1341  inline int numberColsToDo()
1342  {
1343  return (numberColsToDo_);
1344  }
1345 
1347  inline bool colChanged(int i) const
1348  {
1349  return (colChanged_[i] & 1) != 0;
1350  }
1352  inline void unsetColChanged(int i)
1353  {
1354  colChanged_[i] = static_cast< unsigned char >(colChanged_[i] & (~1));
1355  }
1357  inline void setColChanged(int i)
1358  {
1359  colChanged_[i] = static_cast< unsigned char >(colChanged_[i] | (1));
1360  }
1362  inline void addCol(int i)
1363  {
1364  if ((colChanged_[i] & 1) == 0) {
1365  colChanged_[i] = static_cast< unsigned char >(colChanged_[i] | (1));
1367  }
1368  }
1370  inline bool colProhibited(int i) const
1371  {
1372  return (colChanged_[i] & 2) != 0;
1373  }
1380  inline bool colProhibited2(int i) const
1381  {
1382  if (!anyProhibited_)
1383  return false;
1384  else
1385  return (colChanged_[i] & 2) != 0;
1386  }
1388  inline void setColProhibited(int i)
1389  {
1390  colChanged_[i] = static_cast< unsigned char >(colChanged_[i] | (2));
1391  }
1397  inline bool colUsed(int i) const
1398  {
1399  return (colChanged_[i] & 4) != 0;
1400  }
1402  inline void setColUsed(int i)
1403  {
1404  colChanged_[i] = static_cast< unsigned char >(colChanged_[i] | (4));
1405  }
1407  inline void unsetColUsed(int i)
1408  {
1409  colChanged_[i] = static_cast< unsigned char >(colChanged_[i] & (~4));
1410  }
1412  inline bool colInfinite(int i) const
1413  {
1414  return (colChanged_[i] & 8) != 0;
1415  }
1417  inline void unsetColInfinite(int i)
1418  {
1419  colChanged_[i] = static_cast< unsigned char >(colChanged_[i] & (~8));
1420  }
1422  inline void setColInfinite(int i)
1423  {
1424  colChanged_[i] = static_cast< unsigned char >(colChanged_[i] | (8));
1425  }
1426 
1433 
1440 
1442  inline int numberRowsToDo()
1443  {
1444  return (numberRowsToDo_);
1445  }
1446 
1448  inline bool rowChanged(int i) const
1449  {
1450  return (rowChanged_[i] & 1) != 0;
1451  }
1453  inline void unsetRowChanged(int i)
1454  {
1455  rowChanged_[i] = static_cast< unsigned char >(rowChanged_[i] & (~1));
1456  }
1458  inline void setRowChanged(int i)
1459  {
1460  rowChanged_[i] = static_cast< unsigned char >(rowChanged_[i] | (1));
1461  }
1463  inline void addRow(int i)
1464  {
1465  if ((rowChanged_[i] & 1) == 0) {
1466  rowChanged_[i] = static_cast< unsigned char >(rowChanged_[i] | (1));
1468  }
1469  }
1471  inline bool rowProhibited(int i) const
1472  {
1473  return (rowChanged_[i] & 2) != 0;
1474  }
1481  inline bool rowProhibited2(int i) const
1482  {
1483  if (!anyProhibited_)
1484  return false;
1485  else
1486  return (rowChanged_[i] & 2) != 0;
1487  }
1489  inline void setRowProhibited(int i)
1490  {
1491  rowChanged_[i] = static_cast< unsigned char >(rowChanged_[i] | (2));
1492  }
1498  inline bool rowUsed(int i) const
1499  {
1500  return (rowChanged_[i] & 4) != 0;
1501  }
1503  inline void setRowUsed(int i)
1504  {
1505  rowChanged_[i] = static_cast< unsigned char >(rowChanged_[i] | (4));
1506  }
1508  inline void unsetRowUsed(int i)
1509  {
1510  rowChanged_[i] = static_cast< unsigned char >(rowChanged_[i] & (~4));
1511  }
1512 
1514  inline bool anyProhibited() const
1515  {
1516  return anyProhibited_;
1517  }
1519  inline void setAnyProhibited(bool val = true)
1520  {
1521  anyProhibited_ = val;
1522  }
1524 };
1525 
1555 public:
1562  CoinPostsolveMatrix(int ncols_alloc, int nrows_alloc,
1563  CoinBigIndex nelems_alloc);
1564 
1569  CoinPostsolveMatrix(ClpSimplex *si,
1570 
1571  int ncols0,
1572  int nrows0,
1573  CoinBigIndex nelems0,
1574 
1575  double maxmin_,
1576  // end prepost members
1577 
1578  double *sol,
1579  double *acts,
1580 
1581  unsigned char *colstat,
1582  unsigned char *rowstat);
1583 
1588  CoinPostsolveMatrix(OsiSolverInterface *si,
1589 
1590  int ncols0,
1591  int nrows0,
1592  CoinBigIndex nelems0,
1593 
1594  double maxmin_,
1595  // end prepost members
1596 
1597  double *sol,
1598  double *acts,
1599 
1600  unsigned char *colstat,
1601  unsigned char *rowstat);
1602 
1614 
1617 
1629 
1639 
1641 
1649  char *cdone_;
1650  char *rdone_;
1652 
1655 };
1656 
1663 
1668 void presolve_make_memlists(/*CoinBigIndex *starts,*/ int *lengths,
1669  presolvehlink *link, int n);
1670 
1678 bool presolve_expand_major(CoinBigIndex *majstrts, double *majels,
1679  int *minndxs, int *majlens,
1680  presolvehlink *majlinks, int nmaj, int k);
1681 
1687 inline bool presolve_expand_col(CoinBigIndex *mcstrt, double *colels,
1688  int *hrow, int *hincol,
1689  presolvehlink *clink, int ncols, int colx)
1690 {
1691  return presolve_expand_major(mcstrt, colels,
1692  hrow, hincol, clink, ncols, colx);
1693 }
1694 
1700 inline bool presolve_expand_row(CoinBigIndex *mrstrt, double *rowels,
1701  int *hcol, int *hinrow,
1702  presolvehlink *rlink, int nrows, int rowx)
1703 {
1704  return presolve_expand_major(mrstrt, rowels,
1705  hcol, hinrow, rlink, nrows, rowx);
1706 }
1707 
1717  CoinBigIndex ks, CoinBigIndex ke,
1718  const int *minndxs)
1719 {
1720  CoinBigIndex k;
1721  for (k = ks; k < ke; k++)
1722 #ifndef NDEBUG
1723  {
1724  if (minndxs[k] == tgt)
1725  return (k);
1726  }
1727  DIE("FIND_MINOR");
1728 
1729  abort();
1730  return -1;
1731 #else
1732  {
1733  if (minndxs[k] == tgt)
1734  break;
1735  }
1736  return (k);
1737 #endif
1738 }
1739 
1747  CoinBigIndex kce, const int *hrow)
1748 {
1749  return presolve_find_minor(row, kcs, kce, hrow);
1750 }
1751 
1759  CoinBigIndex kre, const int *hcol)
1760 {
1761  return presolve_find_minor(col, krs, kre, hcol);
1762 }
1763 
1773  const int *minndxs);
1774 
1782  CoinBigIndex kce, const int *hrow)
1783 {
1784  return presolve_find_minor1(row, kcs, kce, hrow);
1785 }
1786 
1794  CoinBigIndex kre, const int *hcol)
1795 {
1796  return presolve_find_minor1(col, krs, kre, hcol);
1797 }
1798 
1808  const int *minndxs,
1809  const CoinBigIndex *majlinks);
1810 
1818 inline CoinBigIndex presolve_find_row2(int row, CoinBigIndex kcs, int collen,
1819  const int *hrow,
1820  const CoinBigIndex *clinks)
1821 {
1822  return presolve_find_minor2(row, kcs, collen, hrow, clinks);
1823 }
1824 
1834  const int *minndxs,
1835  const CoinBigIndex *majlinks);
1836 
1844 inline CoinBigIndex presolve_find_row3(int row, CoinBigIndex kcs, int collen,
1845  const int *hrow,
1846  const CoinBigIndex *clinks)
1847 {
1848  return presolve_find_minor3(row, kcs, collen, hrow, clinks);
1849 }
1850 
1860 inline void presolve_delete_from_major(int majndx, int minndx,
1861  const CoinBigIndex *majstrts,
1862  int *majlens, int *minndxs, double *els)
1863 {
1864  const CoinBigIndex ks = majstrts[majndx];
1865  const CoinBigIndex ke = ks + majlens[majndx];
1866 
1867  const CoinBigIndex kmi = presolve_find_minor(minndx, ks, ke, minndxs);
1868 
1869  minndxs[kmi] = minndxs[ke - 1];
1870  els[kmi] = els[ke - 1];
1871  majlens[majndx]--;
1872 
1873  return;
1874 }
1875 
1882 inline void presolve_delete_many_from_major(int majndx, char *marked,
1883  const CoinBigIndex *majstrts,
1884  int *majlens, int *minndxs, double *els)
1885 {
1886  const CoinBigIndex ks = majstrts[majndx];
1887  const CoinBigIndex ke = ks + majlens[majndx];
1888  CoinBigIndex put = ks;
1889  for (CoinBigIndex k = ks; k < ke; k++) {
1890  int iMinor = minndxs[k];
1891  if (!marked[iMinor]) {
1892  minndxs[put] = iMinor;
1893  els[put++] = els[k];
1894  } else {
1895  marked[iMinor] = 0;
1896  }
1897  }
1898  majlens[majndx] = static_cast< int >(put - ks);
1899  return;
1900 }
1901 
1912 inline void presolve_delete_from_col(int row, int col,
1913  const CoinBigIndex *mcstrt,
1914  int *hincol, int *hrow, double *colels)
1915 {
1916  presolve_delete_from_major(col, row, mcstrt, hincol, hrow, colels);
1917 }
1918 
1929 inline void presolve_delete_from_row(int row, int col,
1930  const CoinBigIndex *mrstrt,
1931  int *hinrow, int *hcol, double *rowels)
1932 {
1933  presolve_delete_from_major(row, col, mrstrt, hinrow, hcol, rowels);
1934 }
1935 
1946 void presolve_delete_from_major2(int majndx, int minndx,
1947  CoinBigIndex *majstrts, int *majlens,
1948  int *minndxs, CoinBigIndex *majlinks,
1949  CoinBigIndex *free_listp);
1950 
1961 inline void presolve_delete_from_col2(int row, int col, CoinBigIndex *mcstrt,
1962  int *hincol, int *hrow,
1963  CoinBigIndex *clinks, CoinBigIndex *free_listp)
1964 {
1965  presolve_delete_from_major2(col, row, mcstrt, hincol, hrow, clinks, free_listp);
1966 }
1967 
1969 
1975 
1987 double *presolve_dupmajor(const double *elems, const int *indices,
1988  int length, CoinBigIndex offset, int tgt = -1);
1989 
1991 void coin_init_random_vec(double *work, int n);
1992 
1994 
1995 #endif
1996 
1997 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
1998 */
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.