CoinUtils  2.11.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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
107 #define PRESOLVE_SMALL_INF 1.0e20
109 #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_,
309  CoinBigIndex nelems_,
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 
459  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 
494  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 
587  inline CoinMessageHandler *messageHandler() const
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 
785 const char *statusName(CoinPrePostsolveMatrix::Status status);
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 
970  friend void assignPresolveToPostsolve(CoinPresolveMatrix *&preObj);
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 
1284  int *usefulRowInt_;
1293  double *randomNumber_;
1294 
1298  double *sumUp_;
1302  double *sumDown_;
1304 
1316  int recomputeSums(int whichRow);
1317 
1319  void initializeStuff();
1321  void deleteStuff();
1322 
1325 
1331  void initColsToDo();
1332 
1338  int stepColsToDo();
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 
1432  void initRowsToDo();
1433 
1439  int stepRowsToDo();
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 
1654  void check_nbasic();
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 
1807 CoinBigIndex presolve_find_minor2(int tgt, CoinBigIndex ks, int majlen,
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 
1833 CoinBigIndex presolve_find_minor3(int tgt, CoinBigIndex ks, int majlen,
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 */
const char * rowStatusString(int i) const
Return a print string for status of a row (artificial variable)
unsigned char * rowChanged_
Row change status information.
void setColChanged(int i)
Mark column as changed.
void statistics()
Say we want statistics - also set time.
int * originalRow_
Original row numbers.
bool rowIsBasic(int sequence) const
Check if artificial for this row is basic.
Error Class thrown by an exception.
Definition: CoinError.hpp:42
void setPass(int pass=0)
Set pass number.
int * colsToDo_
Input list of columns to process.
int getNumRows() const
Get current number of rows.
void setMessageHandler(CoinMessageHandler *handler)
Set message handler.
CoinBigIndex getNumElems() const
Get current number of non-zero coefficients.
virtual void postsolve(CoinPostsolveMatrix *prob) const =0
Apply the postsolve transformation for this particular presolve action.
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.
int * usefulRowInt_
Preallocated scratch work array, 3*nrows_.
void setReducedCost(const double *redCost, int lenParam)
Set reduced costs.
double ztolzb_
Primal feasibility tolerance.
void setFeasibilityTolerance(double val)
Set feasibility tolerance.
~CoinPresolveMatrix()
Destructor.
Collects all the information about the problem that is needed in both presolve and postsolve...
int * originalColumn_
Original column numbers.
bool anyInteger_
Flag to say if any variables are integer.
Status getRowStatus(int sequence) const
Get row status.
double * sumDown_
Work array for sum of finite contributions to row lhs lower bound.
int nrows0_
Allocated number of rows.
void setColSolution(const double *colSol, int lenParam)
Set column solution.
double * colels_
Coefficients (positional correspondence with hrow_)
CoinMessage messages_
Standard COIN messages.
CoinPresolveMatrix(int ncols_alloc, int nrows_alloc, CoinBigIndex nelems_alloc)
`Native&#39; constructor
Status getColumnStatus(int sequence) const
Get column (structural variable) status.
void setCost(const double *cost, int lenParam)
Set objective coefficients.
const CoinBigIndex * getColStarts() const
Get column start vector for column-major packed matrix.
CoinBigIndex presolve_find_row3(int row, CoinBigIndex kcs, int collen, const int *hrow, const CoinBigIndex *clinks)
Find position of a row in a column in a column-major threaded matrix.
CoinWarmStartBasis * getStatus()
Get status in the form of a CoinWarmStartBasis.
CoinBigIndex nelems0_
Allocated number of coefficients.
int * infiniteUp_
Work array for count of infinite contributions to row lhs upper bound.
double * usefulColumnDouble_
Preallocated scratch work array, ncols_.
unsigned char * rowstat_
Status of constraints.
bool columnIsBasic(int sequence) const
Check if column (structural variable) is basic.
void initRowsToDo()
Initialise the row ToDo lists.
double * rup_
Row (constraint) upper bounds.
void unsetRowChanged(int i)
Mark row as not changed.
double * randomNumber_
Array of random numbers (max row,column)
int stepRowsToDo()
Step row ToDo lists.
int * hcol_
Column indices (positional correspondence with rowels_)
const int * getColLengths() const
Get column length vector for column-major packed matrix.
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.
const double ZTOLDP2
Alternate zero tolerance.
int presolveOptions_
Fine control over presolve actions.
double * rcosts_
Vector of reduced costs.
CoinBigIndex nelems_
current number of coefficients
void initializeStuff()
Allocate scratch arrays.
int * nextColsToDo_
Output list of columns to process next.
int ncols0_
Allocated number of columns.
int * rowsToDo_
Input list of rows to process.
int recomputeSums(int whichRow)
Recompute row lhs bounds.
Abstract base class of all presolve routines.
double maxmin_
Maximization/minimization.
double bulkRatio_
Ratio of bulk0_ to nelems0_; default is 2.
static void throwCoinError(const char *error, const char *ps_routine)
Stub routine to throw exceptions.
void presolve_delete_from_col(int row, int col, const CoinBigIndex *mcstrt, int *hincol, int *hrow, double *colels)
Delete the entry for row row from column col in a column-major matrix.
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.
int countEmptyCols()
Count empty columns.
int numberNextColsToDo_
Length of nextColsToDo_.
bool anyInteger() const
Check if there are any integer variables.
int status()
Returns problem status (0 = feasible, 1 = infeasible, 2 = unbounded)
void unsetColUsed(int i)
Mark column as unused.
void setStatus(int status)
Set problem status.
const char * columnStatusString(int j) const
Return a print string for status of a column (structural variable)
void setDualTolerance(double dualTol)
Set the dual feasibility tolerance.
void setObjSense(double objSense)
Set the objective sense (max/min)
The default COIN simplex (basis-oriented) warm start class.
int numberColsToDo_
Length of colsToDo_.
const char * statusName(CoinPrePostsolveMatrix::Status status)
Generate a print string for a status code.
CoinBigIndex presolve_find_minor(int tgt, CoinBigIndex ks, CoinBigIndex ke, const int *minndxs)
Find position of a minor index in a major vector.
int numberColsToDo()
Return the number of columns on the colsToDo_ list.
void setPresolveOptions(int value)
Sets any special options (see presolveOptions_)
Status
Enum for status of various sorts.
Base class for message handling.
double * cost_
Objective coefficients.
void presolve_delete_from_major(int majndx, int minndx, const CoinBigIndex *majstrts, int *majlens, int *minndxs, double *els)
Delete the entry for a minor index from a major vector.
bool rowProhibited2(int i) const
Test if row is eligible for preprocessing.
~CoinPrePostsolveMatrix()
Destructor.
bool anyProhibited_
Flag to say if any rows or columns are marked as prohibited.
double startTime_
Start time of presolve.
double * presolve_dupmajor(const double *elems, const int *indices, int length, CoinBigIndex offset, int tgt=-1)
Duplicate a major-dimension vector; optionally omit the entry with minor index tgt.
void setVariableType(int i, int variableType)
Set variable type information for a single variable.
The standard set of Coin messages.
Definition: CoinMessage.hpp:78
CoinBigIndex presolve_find_minor1(int tgt, CoinBigIndex ks, CoinBigIndex ke, const int *minndxs)
Find position of a minor index in a major vector.
void setNext(const CoinPresolveAction *nextAction)
modify next (when building rather than passing)
void assignPresolveToPostsolve(CoinPresolveMatrix *&preObj)
Load an empty CoinPostsolveMatrix from a CoinPresolveMatrix.
void addCol(int i)
Mark column as changed and add to list of columns to process next.
void setRowStatus(int sequence, Status status)
Set row status (i.e., status of artificial for this row)
unsigned char * integerType_
Tracks integrality of columns (1 for integer, 0 for continuous)
void coin_init_random_vec(double *work, int n)
Initialize a vector with random numbers.
void setStructuralStatus(const char *strucStatus, int lenParam)
Set column (structural variable) status vector.
void setColumnStatusUsingValue(int iColumn)
Set status of column (structural variable) to the correct nonbasic status given bounds and current va...
int nrows_
current number of rows
const double * getCost() const
Get objective coefficients.
const double * getElementsByCol() const
Get vector of elements for column-major packed matrix.
virtual ~CoinPresolveAction()
Virtual destructor.
void setAnyInteger(bool anyInteger=true)
Set a flag for presence (true) or absence (false) of integer variables.
bool rowChanged(int i) const
Has row been changed?
bool isInteger(int i) const
Check for integrality of the specified variable.
CoinPostsolveMatrix(int ncols_alloc, int nrows_alloc, CoinBigIndex nelems_alloc)
`Native&#39; constructor
double * usefulRowDouble_
Preallocated scratch work array, 2*nrows_.
int stepColsToDo()
Step column ToDo lists.
double * cup_
Column (primal variable) upper bounds.
CoinBigIndex * mrstrt_
Vector of row start positions in #hcol, rowels_.
void setColumnStatus(int sequence, Status status)
Set column status (i.e., status of primal variable)
int status_
Output status: 0 = feasible, 1 = infeasible, 2 = unbounded.
void setAnyProhibited(bool val=true)
Set a flag for presence of prohibited rows or columns.
int * hincol_
Vector of column lengths.
bool rowUsed(int i) const
Test if row is marked as used.
CoinBigIndex maxlink_
Allocated size of link_.
double * acts_
Vector of constraint left-hand-side values (row activity)
int * hrow_
Row indices (positional correspondence with colels_)
CoinPresolveAction(const CoinPresolveAction *next)
Construct a postsolve object and add it to the transformation list.
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, CoinBigIndex *majlinks, CoinBigIndex *free_listp)
Delete the entry for a minor index from a major vector in a threaded matrix.
void presolve_delete_many_from_major(int majndx, char *marked, const CoinBigIndex *majstrts, int *majlens, int *minndxs, double *els)
Delete marked entries.
bool anyProhibited() const
Check if there are any prohibited rows or columns.
int numberNextRowsToDo_
Length of nextRowsToDo_.
void setColProhibited(int i)
Mark column as ineligible for preprocessing.
void setArtificialStatus(const char *artifStatus, int lenParam)
Set row (artificial variable) status vector.
double ztoldj_
Dual feasibility tolerance.
void initColsToDo()
Initialise the column ToDo lists.
const double ZTOLDP
Zero tolerance.
CoinBigIndex presolve_find_row(int row, CoinBigIndex kcs, CoinBigIndex kce, const int *hrow)
Find position of a row in a column in a column-major matrix.
const CoinPresolveAction * next
The next presolve transformation.
bool rowProhibited(int i) const
Test if row is eligible for preprocessing.
const double * getColSolution() const
Get column solution (primal variable values)
void presolve_delete_from_row(int row, int col, const CoinBigIndex *mrstrt, int *hinrow, int *hcol, double *rowels)
Delete the entry for column col from row row in a row-major matrix.
const double * getRowPrice() const
Get row solution (dual variables)
Augments CoinPrePostsolveMatrix with information about the problem that is only needed during postsol...
friend void assignPresolveToPostsolve(CoinPresolveMatrix *&preObj)
Initialize a CoinPostsolveMatrix object, destroying the CoinPresolveMatrix object.
void setRowProhibited(int i)
Mark row as ineligible for preprocessing.
CoinBigIndex bulk0_
Allocated size of bulk storage for row indices and coefficients.
void setMaximumSubstitutionLevel(int level)
Set Maximum substitution level (normally 3)
~CoinPostsolveMatrix()
Destructor.
void unsetColInfinite(int i)
Mark column as not infinite ub (originally)
const double * getRowUpper() const
Get row upper bounds.
unsigned char * colChanged_
Column change status information.
bool colUsed(int i) const
Test if column is marked as used.
void setRowUpper(const double *rowUpper, int lenParam)
Set row upper bounds.
const double * getRowActivity() const
Get row activity (constraint lhs values)
void setRowLower(const double *rowLower, int lenParam)
Set row lower bounds.
bool defaultHandler_
Indicates if the current handler_ is default (true) or not (false).
Sparse Matrix Base Class.
void setRowChanged(int i)
Mark row as changed.
void change_bias(double change_amount)
Adjust objective function constant offset.
double originalOffset_
Original objective offset.
int countEmptyRows()
Count number of empty rows.
void setMatrix(const CoinPackedMatrix *mtx)
Load the cofficient matrix.
Augments CoinPrePostsolveMatrix with information about the problem that is only needed during presolv...
const CoinBigIndex * getRowStarts() const
Get row start vector for row-major packed matrix.
int * hinrow_
Vector of row lengths.
presolvehlink * clink_
Linked list for the column-major representation.
void setColInfinite(int i)
Mark column as infinite ub (originally)
int * nextRowsToDo_
Output list of rows to process next.
int numberRowsToDo_
Length of rowsToDo_.
const double * getColLower() const
Get column lower bounds.
double * sumUp_
Work array for sum of finite contributions to row lhs upper bound.
int ncols_
current number of columns
void addRow(int i)
Mark row as changed and add to list of rows to process next.
void setStatus(const CoinWarmStartBasis *basis)
Set the status of all variables from a basis.
double dobias_
Objective function offset introduced during presolve.
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.
int CoinBigIndex
CoinMessages messages() const
Return messages.
double * rowels_
Coefficients (positional correspondence with hcol_)
bool tuning_
Print statistics for tuning.
#define PRESOLVE_INF
The usual finite infinity.
int * infiniteDown_
Work array for count of infinite contributions to row lhs lower bound.
int numberRowsToDo()
Return the number of rows on the rowsToDo_ list.
bool colInfinite(int i) const
Has column infinite ub (originally)
void setPrimalTolerance(double primTol)
Set the primal feasibility tolerance.
int * usefulColumnInt_
Preallocated scratch work array, 2*ncols_.
double feasibilityTolerance()
Return feasibility tolerance.
CoinBigIndex free_list_
First entry in free entries thread.
const double * getElementsByRow() const
Get vector of elements for row-major packed matrix.
void check_nbasic()
debug
bool colChanged(int i) const
Has column been changed?
const double * getRowLower() const
Get row lower bounds.
double * clo_
Column (primal variable) lower bounds.
const double * getReducedCost() const
Get reduced costs.
void deleteStuff()
Free scratch arrays.
double feasibilityTolerance_
Bounds can be moved by this to retain feasibility.
void unsetColChanged(int i)
Mark column as not changed.
This file contains the enum for the standard set of Coin messages and a class definition whose sole p...
presolvehlink * rlink_
Linked list for the row-major representation.
void setColUpper(const double *colUpper, int lenParam)
Set column upper bounds.
void presolve_make_memlists(int *lengths, presolvehlink *link, int n)
Initialise linked list for major vector order in bulk storage.
void setRowPrice(const double *rowSol, int lenParam)
Set row solution.
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 getNumCols() const
Get current number of columns.
void setColLower(const double *colLower, int lenParam)
Set column lower bounds.
bool colProhibited2(int i) const
Test if column is eligible for preprocessing.
CoinBigIndex presolve_find_col1(int col, CoinBigIndex krs, CoinBigIndex kre, const int *hcol)
Find position of a column in a row in a row-major matrix.
unsigned char * colstat_
Status of primal variables.
const int * getRowIndicesByCol() const
Get vector of row indices for column-major packed matrix.
double * sol_
Vector of primal variable values.
double * rowduals_
Vector of dual variable values.
CoinBigIndex * link_
Thread array.
#define NO_LINK
void setColUsed(int i)
Mark column as used.
virtual const char * name() const =0
A name for debug printing.
CoinBigIndex presolve_find_row2(int row, CoinBigIndex kcs, int collen, const int *hrow, const CoinBigIndex *clinks)
Find position of a row in a column in a column-major threaded matrix.
CoinMessageHandler * handler_
Message handler.
void setObjOffset(double offset)
Set the objective function offset for the original system.
CoinBigIndex presolve_find_col(int col, CoinBigIndex krs, CoinBigIndex kre, const int *hcol)
Find position of a column in a row in a row-major matrix.
void setRowActivity(const double *rowAct, int lenParam)
Set row activity.
void DIE(const char *)
void setRowStatusUsingValue(int iRow)
Set status of row (artificial variable) to the correct nonbasic status given bounds and current value...
void setRowUsed(int i)
Mark row as used.
CoinPrePostsolveMatrix(int ncols_alloc, int nrows_alloc, CoinBigIndex nelems_alloc)
`Native&#39; 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.
int pass_
Presolve pass number.
const int * getColIndicesByRow() const
Get vector of column indices for row-major packed matrix.
Class to hold and manipulate an array of massaged messages.
int maxSubstLevel_
Maximum substitution level.
CoinMessageHandler * messageHandler() const
Return message handler.
CoinBigIndex * mcstrt_
Vector of column start positions in hrow_, colels_.
#define PRESOLVE_STMT(s)
void unsetRowUsed(int i)
Mark row as unused.
const double * getColUpper() const
Get column upper bounds.
double * rlo_
Row (constraint) lower bounds.
bool colProhibited(int i) const
Test if column is eligible for preprocessing.
bool presolve_expand_col(CoinBigIndex *mcstrt, double *colels, int *hrow, int *hincol, presolvehlink *clink, int ncols, int colx)
Make sure a column (colx) in a column-major matrix has room for one more coefficient.
int presolveOptions() const
Picks up any special options.