CoinUtils 2.11.10
Loading...
Searching...
No Matches
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
52inline 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
79inline 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
98const double ZTOLDP = 1e-12;
103const 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
113
164public:
171 static void throwCoinError(const char *error, const char *ps_routine)
172 {
173 throw CoinError(error, ps_routine, "CoinPresolve");
174 }
175
181
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
210};
211
212/*
213 These are needed for OSI-aware constructors associated with
214 CoinPrePostsolveMatrix, CoinPresolveMatrix, and CoinPostsolveMatrix.
215*/
216class ClpSimplex;
217class OsiSolverInterface;
218
219/*
220 CoinWarmStartBasis is required for methods in CoinPrePostsolveMatrix
221 that accept/return a CoinWarmStartBasis object.
222*/
224
280public:
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,
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 }
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 }
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 }
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
626
645
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
810public:
811 int pre, suc;
812};
813
814#define NO_LINK -66666666
815
821inline 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
839inline 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
861inline 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
906public:
913 CoinPresolveMatrix(int ncols_alloc, int nrows_alloc,
914 CoinBigIndex nelems_alloc);
915
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);
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
1120 double *rowels_;
1122 int *hcol_;
1124
1126 unsigned char *integerType_;
1139
1143 inline double feasibilityTolerance()
1144 {
1145 return (feasibilityTolerance_);
1146 }
1148 inline void setFeasibilityTolerance(double val)
1149 {
1151 }
1152
1160 inline int status()
1161 {
1162 return (status_);
1163 }
1165 inline void setStatus(int status)
1166 {
1167 status_ = (status & 0x3);
1168 }
1169
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
1292
1296 double *sumUp_;
1300 double *sumDown_;
1302
1314 int recomputeSums(int whichRow);
1315
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
1553public:
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
1666void presolve_make_memlists(/*CoinBigIndex *starts,*/ int *lengths,
1667 presolvehlink *link, int n);
1668
1676bool presolve_expand_major(CoinBigIndex *majstrts, double *majels,
1677 int *minndxs, int *majlens,
1678 presolvehlink *majlinks, int nmaj, int k);
1679
1685inline 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
1698inline 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
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
1816inline 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
1842inline 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
1858inline 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
1880inline 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
1910inline 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
1927inline 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
1944void presolve_delete_from_major2(int majndx, int minndx,
1945 CoinBigIndex *majstrts, int *majlens,
1946 int *minndxs, CoinBigIndex *majlinks,
1947 CoinBigIndex *free_listp);
1948
1959inline 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
1985double *presolve_dupmajor(const double *elems, const int *indices,
1986 int length, CoinBigIndex offset, int tgt = -1);
1987
1989void 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.
#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.
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 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.
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.
const int * getColLengths() const
Get column length vector for column-major packed matrix.
double * cup_
Column (primal variable) upper bounds.
int countEmptyCols()
Count empty columns.
const CoinBigIndex * getColStarts() const
Get column start vector for column-major packed matrix.
void setPrimalTolerance(double primTol)
Set the primal feasibility tolerance.
double * cost_
Objective coefficients.
void setRowUpper(const double *rowUpper, int lenParam)
Set row upper bounds.
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 double * getElementsByCol() const
Get vector of elements for column-major packed matrix.
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.
const double * getCost() const
Get objective coefficients.
const double * getReducedCost() const
Get reduced costs.
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.
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 * getRowPrice() const
Get row solution (dual variables)
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.
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.
const char * columnStatusString(int j) const
Return a print string for status of a column (structural variable)
const double * getColLower() const
Get column lower bounds.
void setStatus(const CoinWarmStartBasis *basis)
Set the status of all variables from a basis.
int * originalRow_
Original row numbers.
bool rowIsBasic(int sequence) const
Check if artificial for this row is basic.
const double * getColUpper() const
Get column upper bounds.
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 int * getRowIndicesByCol() const
Get vector of row indices for column-major packed matrix.
void setStructuralStatus(const char *strucStatus, int lenParam)
Set column (structural variable) status vector.
const double * getColSolution() const
Get column solution (primal variable values)
bool presolve_expand_major(CoinBigIndex *majstrts, double *majels, int *minndxs, int *majlens, presolvehlink *majlinks, int nmaj, int k)
Make sure a major-dimension vector k has room for one more coefficient.
double bulkRatio_
Ratio of bulk0_ to nelems0_; default is 2.
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.
CoinMessageHandler * messageHandler() const
Return message handler.
const double * getRowActivity() const
Get row activity (constraint lhs values)
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...
CoinWarmStartBasis * getStatus()
Get status in the form of a CoinWarmStartBasis.
Status
Enum for status of various sorts.
void setColumnStatus(int sequence, Status status)
Set column status (i.e., status of primal variable)
CoinBigIndex presolve_find_minor(int tgt, CoinBigIndex ks, CoinBigIndex ke, const int *minndxs)
Find position of a minor index in a major vector.
int * originalColumn_
Original column numbers.
const char * statusName(CoinPrePostsolveMatrix::Status status)
Generate a print string for a status code.
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.
const char * rowStatusString(int i) const
Return a print string for status of a row (artificial variable)
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.
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 * getRowUpper() const
Get row upper 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)
const double * getRowLower() const
Get row lower bounds.
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.
const double * getElementsByRow() const
Get vector of elements for row-major packed matrix.
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_.
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_.
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.
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.
const int * getColIndicesByRow() const
Get vector of column indices for row-major packed matrix.
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.
const CoinBigIndex * getRowStarts() const
Get row start vector for row-major packed matrix.
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.