Clp 1.17.5
Loading...
Searching...
No Matches
AbcSimplex.hpp
Go to the documentation of this file.
1/* $Id: AbcSimplex.hpp 2385 2019-01-06 19:43:06Z unxusr $ */
2// Copyright (C) 2002, International Business Machines
3// Corporation and others, Copyright (C) 2012, FasterCoin. All Rights Reserved.
4// This code is licensed under the terms of the Eclipse Public License (EPL).
5/*
6 Authors
7
8 John Forrest
9
10*/
11#ifndef AbcSimplex_H
12#define AbcSimplex_H
13
14#include <iostream>
15#include <cfloat>
16#include "ClpModel.hpp"
17#include "ClpMatrixBase.hpp"
18#include "CoinIndexedVector.hpp"
19#include "AbcCommon.hpp"
20class AbcSimplex;
21#include "ClpSolve.hpp"
22#include "CoinAbcCommon.hpp"
23#include "ClpSimplex.hpp"
24class AbcDualRowPivot;
28class OsiAbcSolverInterface;
29class CoinWarmStartBasis;
31class AbcSimplexProgress;
32class AbcMatrix;
34
52#define PAN
53#if ABC_NORMAL_DEBUG > 0
54#define PRINT_PAN 1
55#endif
56#define TRY_ABC_GUS
57#define HEAVY_PERTURBATION 57
58#if ABC_PARALLEL == 1
59// Use pthreads
60#include <pthread.h>
61#endif
62class AbcSimplex : public ClpSimplex {
63 friend void AbcSimplexUnitTest(const std::string &mpsDir);
64
65public:
74 enum Status {
75 atLowerBound = 0x00, // so we can use bottom two bits to sort and swap signs
77 isFree = 0x04,
78 superBasic = 0x05,
79 basic = 0x06,
80 isFixed = 0x07
81 };
82 // For Dual
83 enum FakeBound {
84 noFake = 0x00,
85 lowerFake = 0x01,
86 upperFake = 0x02,
87 bothFake = 0x03
88 };
89
93 AbcSimplex(bool emptyMessages = false);
94
107 AbcSimplex(const ClpSimplex *wholeModel,
108 int numberRows, const int *whichRows,
109 int numberColumns, const int *whichColumns,
110 bool dropNames = true, bool dropIntegers = true,
111 bool fixOthers = false);
118 AbcSimplex(const AbcSimplex *wholeModel,
119 int numberRows, const int *whichRows,
120 int numberColumns, const int *whichColumns,
121 bool dropNames = true, bool dropIntegers = true,
122 bool fixOthers = false);
127 int numberColumns, const int *whichColumns);
130 void originalModel(AbcSimplex *miniModel);
132 AbcSimplex(const ClpSimplex *clpSimplex);
140 //void setPersistenceFlag(int value);
146 inline AbcSimplex *baseModel() const
147 {
148 return abcBaseModel_;
149 }
153 void setToBaseModel(AbcSimplex *model = NULL);
159
164 int dual();
168 int primal(int ifValuesPass);
169 int doAbcPrimal(int ifValuesPass);
171 CoinWarmStartBasis *getBasis() const;
193
196
201 {
202 return reinterpret_cast< AbcSimplexFactorization * >(abcFactorization_);
203 }
204#ifdef EARLY_FACTORIZE
206 inline AbcSimplexFactorization *earlyFactorization() const
207 {
208 return reinterpret_cast< AbcSimplexFactorization * >(abcEarlyFactorization_);
209 }
210#endif
215 inline int maximumAbcNumberRows() const
216 {
218 }
220 inline int maximumNumberTotal() const
221 {
222 return maximumNumberTotal_;
223 }
224 inline int maximumTotal() const
225 {
226 return maximumNumberTotal_;
227 }
231 inline int numberTotal() const
232 {
233 return numberTotal_;
234 }
236 inline int numberTotalWithoutFixed() const
237 {
239 }
241 inline CoinPartitionedVector *usefulArray(int index)
242 {
243 return &usefulArray_[index];
244 }
245 inline CoinPartitionedVector *usefulArray(int index) const
246 {
247 return const_cast< CoinPartitionedVector * >(&usefulArray_[index]);
248 }
250
251 /******************** End of most useful part **************/
265 void setupDualValuesPass(const double *fakeDuals,
266 const double *fakePrimals,
267 int type);
269 inline double minimizationObjectiveValue() const
270 {
272 }
274 inline double currentDualTolerance() const
275 {
277 }
278 inline void setCurrentDualTolerance(double value)
279 {
280 currentDualTolerance_ = value;
281 }
284 {
285 return abcNonLinearCost_;
286 }
288 double *perturbationSaved() const
289 {
290 return perturbationSaved_;
291 }
293 inline double acceptablePivot() const
294 {
295 return acceptablePivot_;
296 }
298 inline int ordinaryVariables() const
299 {
300 return ordinaryVariables_;
301 }
303 inline int numberOrdinary() const
304 {
305 return numberOrdinary_;
306 }
308 inline void setNumberOrdinary(int number)
309 {
310 numberOrdinary_ = number;
311 }
313 inline double currentDualBound() const
314 {
315 return currentDualBound_;
316 }
319 {
320 return abcDualRowPivot_;
321 }
324 {
326 }
328 inline AbcMatrix *abcMatrix() const
329 {
330 return abcMatrix_;
331 }
341 int internalFactorize(int solveType);
357 void permuteIn();
361 void permuteOut(int whatsWanted);
367 void cleanStatus(bool valuesPass = false);
370 int computeDuals(double *givenDjs, CoinIndexedVector *array1, CoinIndexedVector *array2);
372 int computePrimals(CoinIndexedVector *array1, CoinIndexedVector *array2);
376 void setMultipleSequenceIn(int sequenceIn[4]);
381 inline void unpack(CoinIndexedVector &rowArray) const
382 {
383 unpack(rowArray, sequenceIn_);
384 }
388 void unpack(CoinIndexedVector &rowArray, int sequence) const;
393 int housekeeping(/*double objectiveChange*/);
396 void checkPrimalSolution(bool justBasic);
406 int gutsOfSolution(int type);
408 int gutsOfPrimalSolution(int type);
412 void restoreGoodStatus(int type);
413#define rowUseScale_ scaleFromExternal_
414#define inverseRowUseScale_ scaleToExternal_
417 void refreshLower(unsigned int type = ~(ROW_LOWER_SAME | COLUMN_UPPER_SAME));
418 void refreshUpper(unsigned int type = ~(ROW_LOWER_SAME | COLUMN_LOWER_SAME));
420 void setupPointers(int maxRows, int maxColumns);
422 void copyFromSaved(int type = 31);
424 void fillPerturbation(int start, int number);
426 void checkArrays(int ignoreEmpty = 0) const;
428 void checkDjs(int type = 1) const;
430 void checkSolutionBasic() const;
432 void checkMoveBack(bool checkDuals);
433
434public:
445 void setValuesPassAction(double incomingInfeasibility,
446 double allowedInfeasibility);
449 int cleanFactorization(int ifValuesPass);
455
457public:
465 inline int *pivotVariable() const
466 {
467 return abcPivotVariable_;
468 }
470 inline int stateOfProblem() const
471 {
472 return stateOfProblem_;
473 }
475 inline void setStateOfProblem(int value)
476 {
477 stateOfProblem_ = value;
478 }
480 //inline int * fromExternal() const
481 //{ return fromExternal_;}
483 //inline int * toExternal() const
484 //{return toExternal_;}
487 inline double *scaleFromExternal() const
488 {
489 return scaleFromExternal_;
490 }
493 inline double *scaleToExternal() const
494 {
495 return scaleToExternal_;
496 }
498 inline double *rowScale2() const
499 {
500 return rowUseScale_;
501 }
502 inline double *inverseRowScale2() const
503 {
504 return inverseRowUseScale_;
505 }
506 inline double *inverseColumnScale2() const
507 {
509 }
510 inline double *columnScale2() const
511 {
512 return columnUseScale_;
513 }
514 inline int arrayForDualColumn() const
515 {
516 return arrayForDualColumn_;
517 }
519 inline double upperTheta() const
520 {
521 return upperTheta_;
522 }
523 inline int arrayForReplaceColumn() const
524 {
526 }
527 inline int arrayForFlipBounds() const
528 {
529 return arrayForFlipBounds_;
530 }
531 inline int arrayForFlipRhs() const
532 {
533 return arrayForFlipRhs_;
534 }
535 inline int arrayForBtran() const
536 {
537 return arrayForBtran_;
538 }
539 inline int arrayForFtran() const
540 {
541 return arrayForFtran_;
542 }
543 inline int arrayForTableauRow() const
544 {
545 return arrayForTableauRow_;
546 }
548 double valueIncomingDual() const;
550 const double *getColSolution() const;
551
553 const double *getRowPrice() const;
554
556 const double *getReducedCost() const;
557
560 const double *getRowActivity() const;
562
568 int gutsOfSolution(double *givenDuals,
569 const double *givenPrimals,
570 bool valuesPass = false);
572 void gutsOfDelete(int type);
574 void gutsOfCopy(const AbcSimplex &rhs);
576 void gutsOfInitialize(int numberRows, int numberColumns, bool doMore);
578 void gutsOfResize(int numberRows, int numberColumns);
582 void translate(int type);
584 void moveToBasic(int which = 15);
586public:
590 inline double *solutionRegion() const
591 {
592 return abcSolution_;
593 }
594 inline double *djRegion() const
595 {
596 return abcDj_;
597 }
598 inline double *lowerRegion() const
599 {
600 return abcLower_;
601 }
602 inline double *upperRegion() const
603 {
604 return abcUpper_;
605 }
606 inline double *costRegion() const
607 {
608 return abcCost_;
609 }
611 inline double *solutionRegion(int which) const
612 {
613 return abcSolution_ + which * maximumAbcNumberRows_;
614 }
615 inline double *djRegion(int which) const
616 {
617 return abcDj_ + which * maximumAbcNumberRows_;
618 }
619 inline double *lowerRegion(int which) const
620 {
621 return abcLower_ + which * maximumAbcNumberRows_;
622 }
623 inline double *upperRegion(int which) const
624 {
625 return abcUpper_ + which * maximumAbcNumberRows_;
626 }
627 inline double *costRegion(int which) const
628 {
629 return abcCost_ + which * maximumAbcNumberRows_;
630 }
632 inline double *solutionBasic() const
633 {
634 return solutionBasic_;
635 }
636 inline double *djBasic() const
637 {
638 return djBasic_;
639 }
640 inline double *lowerBasic() const
641 {
642 return lowerBasic_;
643 }
644 inline double *upperBasic() const
645 {
646 return upperBasic_;
647 }
648 inline double *costBasic() const
649 {
650 return costBasic_;
651 }
653 inline double *abcPerturbation() const
654 {
655 return abcPerturbation_;
656 }
658 inline double *fakeDjs() const
659 {
660 return djSaved_;
661 }
662 inline unsigned char *internalStatus() const
663 {
664 return internalStatus_;
665 }
666 inline AbcSimplex::Status getInternalStatus(int sequence) const
667 {
668 return static_cast< Status >(internalStatus_[sequence] & 7);
669 }
671 {
672 return static_cast< Status >(internalStatus_[sequence + maximumAbcNumberRows_] & 7);
673 }
674 inline void setInternalStatus(int sequence, AbcSimplex::Status newstatus)
675 {
676 unsigned char &st_byte = internalStatus_[sequence];
677 st_byte = static_cast< unsigned char >(st_byte & ~7);
678 st_byte = static_cast< unsigned char >(st_byte | newstatus);
679 }
680 inline void setInternalColumnStatus(int sequence, AbcSimplex::Status newstatus)
681 {
682 unsigned char &st_byte = internalStatus_[sequence + maximumAbcNumberRows_];
683 st_byte = static_cast< unsigned char >(st_byte & ~7);
684 st_byte = static_cast< unsigned char >(st_byte | newstatus);
685 }
693 inline int sequenceIn() const
694 {
695 return sequenceIn_;
696 }
697 inline int sequenceOut() const
698 {
699 return sequenceOut_;
700 }
702 inline void setSequenceIn(int sequence)
703 {
704 sequenceIn_ = sequence;
705 }
706 inline void setSequenceOut(int sequence)
707 {
708 sequenceOut_ = sequence;
709 }
710#if 0
712 inline int sequenceInternalIn() const {
713 return sequenceInternalIn_;
714 }
715 inline int sequenceInternalOut() const {
716 return sequenceInternalOut_;
717 }
719 inline void setSequenceInternalIn(int sequence) {
720 sequenceInternalIn_ = sequence;
721 }
722 inline void setSequenceInternalOut(int sequence) {
723 sequenceInternalOut_ = sequence;
724 }
725#endif
727 inline int isColumn(int sequence) const
728 {
729 return sequence >= maximumAbcNumberRows_ ? 1 : 0;
730 }
732 inline int sequenceWithin(int sequence) const
733 {
734 return sequence < maximumAbcNumberRows_ ? sequence : sequence - maximumAbcNumberRows_;
735 }
737 inline int lastPivotRow() const
738 {
739 return lastPivotRow_;
740 }
742 inline int firstFree() const
743 {
744 return firstFree_;
745 }
747 inline int lastFirstFree() const
748 {
749 return lastFirstFree_;
750 }
752 inline int freeSequenceIn() const
753 {
754 return freeSequenceIn_;
755 }
757 inline double currentAcceptablePivot() const
758 {
760 }
761#ifdef PAN
768 inline int fakeSuperBasic(int iSequence)
769 {
770 if ((internalStatus_[iSequence] & 7) == 4)
771 return 0; // free
772 if ((internalStatus_[iSequence] & 7) != 5)
773 return -2;
774 double value = abcSolution_[iSequence];
775 if (value < abcLower_[iSequence] + primalTolerance_) {
776 if (abcDj_[iSequence] >= -currentDualTolerance_) {
778#if PRINT_PAN > 1
779 printf("Pansetting %d to lb\n", iSequence);
780#endif
781 return -1;
782 } else {
783 return 1;
784 }
785 } else if (value > abcUpper_[iSequence] - primalTolerance_) {
786 if (abcDj_[iSequence] <= currentDualTolerance_) {
788#if PRINT_PAN > 1
789 printf("Pansetting %d to ub\n", iSequence);
790#endif
791 return -1;
792 } else {
793 return 1;
794 }
795 } else {
796 return 0;
797 }
798 }
799#endif
801 inline double solution(int sequence)
802 {
803 return abcSolution_[sequence];
804 }
806 inline double &solutionAddress(int sequence)
807 {
808 return abcSolution_[sequence];
809 }
810 inline double reducedCost(int sequence)
811 {
812 return abcDj_[sequence];
813 }
814 inline double &reducedCostAddress(int sequence)
815 {
816 return abcDj_[sequence];
817 }
818 inline double lower(int sequence)
819 {
820 return abcLower_[sequence];
821 }
823 inline double &lowerAddress(int sequence)
824 {
825 return abcLower_[sequence];
826 }
827 inline double upper(int sequence)
828 {
829 return abcUpper_[sequence];
830 }
832 inline double &upperAddress(int sequence)
833 {
834 return abcUpper_[sequence];
835 }
836 inline double cost(int sequence)
837 {
838 return abcCost_[sequence];
839 }
841 inline double &costAddress(int sequence)
842 {
843 return abcCost_[sequence];
844 }
846 inline double originalLower(int iSequence) const
847 {
848 if (iSequence < numberColumns_)
849 return columnLower_[iSequence];
850 else
851 return rowLower_[iSequence - numberColumns_];
852 }
854 inline double originalUpper(int iSequence) const
855 {
856 if (iSequence < numberColumns_)
857 return columnUpper_[iSequence];
858 else
859 return rowUpper_[iSequence - numberColumns_];
860 }
862 inline AbcSimplexProgress *abcProgress()
863 {
864 return &abcProgress_;
865 }
866#ifdef ABC_SPRINT
868 AbcSimplex *createSubProblem(int numberColumns, const int *whichColumn);
870 void restoreFromSubProblem(AbcSimplex *fullProblem, const int *whichColumn);
871#endif
872public:
875 inline void clearArraysPublic(int which)
876 {
877 clearArrays(which);
878 }
881 inline int getAvailableArrayPublic() const
882 {
883 return getAvailableArray();
884 }
885#if ABC_PARALLEL
887 inline int parallelMode() const
888 {
889 return parallelMode_;
890 }
892 inline void setParallelMode(int value)
893 {
894 parallelMode_ = value;
895 }
897 inline int numberCpus() const
898 {
899 return parallelMode_ + 1;
900 }
901#if ABC_PARALLEL == 1
903 inline void setStopStart(int value)
904 {
905 stopStart_ = value;
906 }
907#endif
908#endif
909 //protected:
911 void clearArrays(int which);
913 void clearArrays(CoinPartitionedVector *which);
915 int getAvailableArray() const;
917 inline void setUsedArray(int which) const
918 {
919 int check = 1 << which;
920 assert((stateOfProblem_ & check) == 0);
921 stateOfProblem_ |= check;
922 }
924 inline void setAvailableArray(int which) const
925 {
926 int check = 1 << which;
927 assert((stateOfProblem_ & check) != 0);
928 assert(!usefulArray_[which].getNumElements());
929 stateOfProblem_ &= ~check;
930 }
934 void swapDualStuff(int lastSequenceOut, int lastDirectionOut);
935
936protected:
938
941 void swap(int pivotRow, int nonBasicPosition, Status newStatus);
942 inline void setFakeBound(int sequence, FakeBound fakeBound)
943 {
944 unsigned char &st_byte = internalStatus_[sequence];
945 st_byte = static_cast< unsigned char >(st_byte & ~24);
946 st_byte = static_cast< unsigned char >(st_byte | (fakeBound << 3));
947 }
948 inline FakeBound getFakeBound(int sequence) const
949 {
950 return static_cast< FakeBound >((internalStatus_[sequence] >> 3) & 3);
951 }
952 bool atFakeBound(int sequence) const;
953 inline void setPivoted(int sequence)
954 {
955 internalStatus_[sequence] = static_cast< unsigned char >(internalStatus_[sequence] | 32);
956 }
957 inline void clearPivoted(int sequence)
958 {
959 internalStatus_[sequence] = static_cast< unsigned char >(internalStatus_[sequence] & ~32);
960 }
961 inline bool pivoted(int sequence) const
962 {
963 return (((internalStatus_[sequence] >> 5) & 1) != 0);
964 }
965
966public:
968 void swap(int pivotRow, int nonBasicPosition);
970 void setFlagged(int sequence);
971 inline void clearFlagged(int sequence)
972 {
973 internalStatus_[sequence] = static_cast< unsigned char >(internalStatus_[sequence] & ~64);
974 }
975 inline bool flagged(int sequence) const
976 {
977 return ((internalStatus_[sequence] & 64) != 0);
978 }
979
980protected:
982 inline void setActive(int iRow)
983 {
984 internalStatus_[iRow] = static_cast< unsigned char >(internalStatus_[iRow] | 128);
985 }
986 inline void clearActive(int iRow)
987 {
988 internalStatus_[iRow] = static_cast< unsigned char >(internalStatus_[iRow] & ~128);
989 }
990 inline bool active(int iRow) const
991 {
992 return ((internalStatus_[iRow] & 128) != 0);
993 }
994
995public:
1000 void crash(int type);
1005 void putStuffInBasis(int type);
1012 void printStuff() const;
1014 int startup(int ifValuesPass);
1015
1017 inline double rawObjectiveValue() const
1018 {
1019 return objectiveValue_;
1020 }
1022 void computeObjectiveValue(bool useWorkingSolution = false);
1026 void moveInfo(const AbcSimplex &rhs, bool justStatus = false);
1027#ifndef NUMBER_THREADS
1028#define NUMBER_THREADS 3
1029#endif
1030#if ABC_PARALLEL == 1
1031 // For waking up thread
1032 inline pthread_mutex_t *mutexPointer(int which, int thread = 0)
1033 {
1034 return mutex_ + which + 3 * thread;
1035 }
1036 inline pthread_barrier_t *barrierPointer()
1037 {
1038 return &barrier_;
1039 }
1040 inline int whichLocked(int thread = 0) const
1041 {
1042 return locked_[thread];
1043 }
1044 inline CoinThreadInfo *threadInfoPointer(int thread = 0)
1045 {
1046 return threadInfo_ + thread;
1047 }
1048 void startParallelStuff(int type);
1049 int stopParallelStuff(int type);
1051 int whichThread() const;
1052#elif ABC_PARALLEL == 2
1053 //inline CoinThreadInfo * threadInfoPointer(int thread=0)
1054 //{ return threadInfo_+thread;}
1055#endif
1057
1058 //-------------------------------------------------------------------------
1062 void setObjectiveCoefficient(int elementIndex, double elementValue);
1064 inline void setObjCoeff(int elementIndex, double elementValue)
1065 {
1066 setObjectiveCoefficient(elementIndex, elementValue);
1067 }
1068
1071 void setColumnLower(int elementIndex, double elementValue);
1072
1075 void setColumnUpper(int elementIndex, double elementValue);
1076
1078 void setColumnBounds(int elementIndex,
1079 double lower, double upper);
1080
1089 void setColumnSetBounds(const int *indexFirst,
1090 const int *indexLast,
1091 const double *boundList);
1092
1095 inline void setColLower(int elementIndex, double elementValue)
1096 {
1097 setColumnLower(elementIndex, elementValue);
1098 }
1101 inline void setColUpper(int elementIndex, double elementValue)
1102 {
1103 setColumnUpper(elementIndex, elementValue);
1104 }
1105
1107 inline void setColBounds(int elementIndex,
1108 double newlower, double newupper)
1109 {
1110 setColumnBounds(elementIndex, newlower, newupper);
1111 }
1112
1119 inline void setColSetBounds(const int *indexFirst,
1120 const int *indexLast,
1121 const double *boundList)
1122 {
1123 setColumnSetBounds(indexFirst, indexLast, boundList);
1124 }
1125
1128 void setRowLower(int elementIndex, double elementValue);
1129
1132 void setRowUpper(int elementIndex, double elementValue);
1133
1135 void setRowBounds(int elementIndex,
1136 double lower, double upper);
1137
1144 void setRowSetBounds(const int *indexFirst,
1145 const int *indexLast,
1146 const double *boundList);
1148 void resize(int newNumberRows, int newNumberColumns);
1149
1151
1153protected:
1194#ifdef ABC_LONG_FACTORIZATION
1195 long
1196#endif
1197 double ftAlpha_;
1202
1203public:
1206
1207protected:
1228 /*
1229 May want to put some arrays into struct
1230 Two arrays point to/from external
1231 Order is basic,unused basic, at lower, at upper, superbasic, free, fixed with starts
1232 */
1238#define startAtLowerNoOther_ maximumAbcNumberRows_
1249#ifdef EARLY_FACTORIZE
1251 int numberEarly_;
1252#endif
1270#define ALL_STATUS_OK 2048
1271#define ROW_PRIMAL_OK 4096
1272#define ROW_DUAL_OK 8192
1273#define COLUMN_PRIMAL_OK 16384
1274#define COLUMN_DUAL_OK 32768
1275#define PESSIMISTIC 65536
1276#define ADD_A_BIT 131072
1277#define DO_SCALE_AND_MATRIX 262144
1278#define DO_BASIS_AND_ORDER 524288
1279#define DO_STATUS 1048576
1280#define DO_SOLUTION 2097152
1281#define DO_JUST_BOUNDS 0x400000
1282#define NEED_BASIS_SORT 0x800000
1283#define FAKE_SUPERBASIC 0x1000000
1284#define VALUES_PASS 0x2000000
1285#define VALUES_PASS2 0x4000000
1286 mutable int stateOfProblem_;
1287#if ABC_PARALLEL
1288public:
1290 int parallelMode_;
1291
1292protected:
1293#endif
1309 //int * fromExternal_;
1311 //int * toExternal_;
1325 double *offset_;
1327 double *offsetRhs_;
1329 double *tempArray_;
1334 unsigned char *internalStatus_;
1336 unsigned char *internalStatusSaved_;
1348 double *abcLower_;
1351 double *abcUpper_;
1357 double *abcCost_;
1363 double *abcDj_;
1369 double *costSaved_;
1373 double *djSaved_;
1379 double *costBasic_;
1383 double *djBasic_;
1396#ifdef EARLY_FACTORIZE
1398 AbcSimplexFactorization *abcEarlyFactorization_;
1399#endif
1400#ifdef TEMPORARY_FACTORIZATION
1402 AbcSimplexFactorization *abcOtherFactorization_;
1403#endif
1405 //double * savedSolution_;
1416 /* has secondary offset and counts so row goes first then column
1417 Probably back to CoinPartitionedVector as AbcMatrix has slacks
1418 also says if in use - so we can just get next available one */
1419#define ABC_NUMBER_USEFUL 8
1420 mutable CoinPartitionedVector usefulArray_[ABC_NUMBER_USEFUL];
1422 AbcSimplexProgress abcProgress_;
1429
1430public:
1434 int arrayForFlipRhs_; // if sequential can re-use
1438protected:
1441 //int nextCleanNonBasicIteration_;
1442#if ABC_PARALLEL == 1
1443 // For waking up thread
1444 pthread_mutex_t mutex_[3 * NUMBER_THREADS];
1445 pthread_barrier_t barrier_;
1446 CoinThreadInfo threadInfo_[NUMBER_THREADS];
1447 pthread_t abcThread_[NUMBER_THREADS];
1448 int locked_[NUMBER_THREADS];
1449 int stopStart_;
1450#elif ABC_PARALLEL == 2
1451 //CoinThreadInfo threadInfo_[NUMBER_THREADS];
1452#endif
1454};
1455//#############################################################################
1464void AbcSimplexUnitTest(const std::string &mpsDir);
1465#endif
1466
1467/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
1468*/
#define NUMBER_THREADS
void AbcSimplexUnitTest(const std::string &mpsDir)
A function that tests the methods in the AbcSimplex class.
#define ABC_NUMBER_USEFUL
Useful arrays (all of row+column+2 length)
#define rowUseScale_
#define inverseRowUseScale_
#define ROW_LOWER_SAME
#define COLUMN_UPPER_SAME
#define COLUMN_LOWER_SAME
@ ClpObjOffset
Objective function constant.
Dual Row Pivot Abstract Base Class.
Primal Column Pivot Abstract Base Class.
This just implements AbcFactorization when an AbcMatrix object is passed.
void restoreGoodStatus(int type)
Restores previous good status and says trouble.
int housekeeping()
This does basis housekeeping and does values for in/out variables.
int initialNumberInfeasibilities_
Initial number of infeasibilities.
void moveStatusToClp(ClpSimplex *clpModel)
Move status and solution to ClpSimplex.
void checkArrays(int ignoreEmpty=0) const
For debug - prints summary of arrays which are out of kilter.
AbcSimplex(const AbcSimplex &rhs)
Copy constructor.
double * costSaved_
Saved scaled copy of objective.
double * abcPerturbation() const
Perturbation.
int normalDualColumnIteration_
Iteration at which to do relaxed dualColumn.
int startOther_
Start of superBasic, free or awkward bounds variables.
double largestGap_
Largest gap.
void setValuesPassAction(double incomingInfeasibility, double allowedInfeasibility)
For advanced use.
void setFakeBound(int sequence, FakeBound fakeBound)
int arrayForFlipRhs() const
void fillPerturbation(int start, int number)
fills in perturbationSaved_ from start with 0.5+random
void setClpSimplexObjectiveValue()
Sets objectiveValue_ from rawObjectiveValue_.
AbcMatrix * abcMatrix() const
Abc Matrix.
bool flagged(int sequence) const
double * abcUpper_
Working scaled copy of upper bounds has original scaled copy at end.
int numberFlagged_
Current number of variables flagged.
int maximumNumberTotal_
Maximum numberTotal.
double upper(int sequence)
void setObjectiveCoefficient(int elementIndex, double elementValue)
Set an objective function coefficient.
void checkMoveBack(bool checkDuals)
For debug - moves solution back to external and computes stuff (always checks djs)
int startFixed_
Start of fixed variables.
int numberTotalWithoutFixed_
Number of variables without fixed to zero (includes spare rows)
int * reversePivotVariable_
Reverse abcPivotVariable_ for moving around.
AbcSimplex * abcBaseModel_
Saved version of solution.
void checkDjs(int type=1) const
For debug - summarizes dj situation (1 recomputes duals first, 2 checks duals as well)
AbcSimplexFactorization * swapFactorization(AbcSimplexFactorization *factorization)
Swaps factorization.
double currentAcceptablePivot() const
Acceptable pivot for this iteration.
void setCurrentDualTolerance(double value)
int lastFirstFree() const
Last firstFree_.
void setPivoted(int sequence)
bool atFakeBound(int sequence) const
AbcSimplex(AbcSimplex *wholeModel, int numberColumns, const int *whichColumns)
This constructor modifies original AbcSimplex and stores original stuff in created AbcSimplex.
int arrayForTableauRow_
int gutsOfSolution(int type)
Computes solutions - 1 do duals, 2 do primals, 3 both (returns number of refinements)
void gutsOfDelete(int type)
Does most of deletion for arrays etc(0 just null arrays, 1 delete first)
void gutsOfCopy(const AbcSimplex &rhs)
Does most of copying.
double minimizationObjectiveValue() const
Gets objective value with all offsets but as for minimization.
void gutsOfResize(int numberRows, int numberColumns)
resizes arrays
int gutsOfSolution(double *givenDuals, const double *givenPrimals, bool valuesPass=false)
May change basis and then returns number changed.
void checkPrimalSolution(bool justBasic)
This sets largest infeasibility and most infeasible and sum and number of infeasibilities (Primal)
int firstFree() const
First Free_.
double * upperRegion(int which) const
int arrayForDualColumn() const
double * djSaved_
Saved scaled dual solution.
double * costBasic_
Working scaled copy of basic objective.
int tightenPrimalBounds()
Tightens primal bounds to make dual faster.
AbcDualRowPivot * abcDualRowPivot_
dual row pivot choice
AbcSimplexProgress abcProgress_
For dealing with all issues of cycling etc.
double acceptablePivot() const
Acceptable pivot for this iteration.
int startAtUpperNoOther_
Start of variables at upper bound with no lower.
double reducedCost(int sequence)
int stateOfIteration_
Where we are in iteration.
int freeSequenceIn() const
Free chosen vector.
int numberTotal() const
Number of variables (includes spare rows)
void swapPrimalStuff()
Swaps primal stuff.
double computeInternalObjectiveValue()
Compute minimization objective value from internal solution without perturbation.
void allSlackBasis()
Sets up all slack basis and resets solution to as it was after initial load or readMps.
int lastPivotRow() const
Current/last pivot row (set after END of choosing pivot row in dual)
void setStateOfProblem(int value)
State of problem.
void permuteBasis()
deals with new basis and puts in abcPivotVariable_
double * fakeDjs() const
Fake djs.
double initialSumInfeasibilities_
Initial sum of infeasibilities.
void copyFromSaved(int type=31)
Copies all saved versions to working versions and may do something for perturbation.
int getSolution()
Given an existing factorization computes and checks primal and dual solutions.
double * abcDj_
Working scaled dual solution may have saved from last factorization at end.
double * lowerRegion(int which) const
friend void AbcSimplexUnitTest(const std::string &mpsDir)
A function that tests the methods in the AbcSimplex class.
void setSequenceOut(int sequence)
void setFactorizationFrequency(int value)
int ordinaryVariables_
Set to 1 if no free or super basic.
void moveToBasic(int which=15)
Moves basic stuff to basic area.
int maximumNumberTotal() const
Maximum Total.
int gutsOfPrimalSolution(int type)
Computes solutions - 1 do duals, 2 do primals, 3 both (returns number of refinements)
AbcSimplex::Status getInternalColumnStatus(int sequence) const
int fakeSuperBasic(int iSequence)
Returns 1 if fake superbasic 0 if free or true superbasic -1 if was fake but has cleaned itself up (s...
void setColumnBounds(int elementIndex, double lower, double upper)
Set a single column lower and upper bound.
double * solutionRegion(int which) const
Return region.
double * perturbationBasic_
basic perturbation
double * upperRegion() const
double & lowerAddress(int sequence)
Return address of row or column lower bound.
double * scaleToExternal_
Scale from primal internal to external (in external order) Or other way for dual.
double sumFakeInfeasibilities_
Sum of infeasibilities when using fake perturbation tolerance.
double objectiveChange_
Objective change.
double * costRegion(int which) const
int sequenceWithin(int sequence) const
Returns sequence number within section.
unsigned char * internalStatus() const
int cleanFactorization(int ifValuesPass)
Get a clean factorization - i.e.
void computeObjective()
Computes nonbasic cost and total cost.
void setupDualValuesPass(const double *fakeDuals, const double *fakePrimals, int type)
Sets dual values pass djs using unscaled duals type 1 - values pass type 2 - just use as infeasibilit...
double * abcPerturbation_
Perturbation (fixed) - is just scaled random numbers If perturbationFactor_<0 then virtual perturbati...
AbcSimplex(const AbcSimplex *wholeModel, int numberRows, const int *whichRows, int numberColumns, const int *whichColumns, bool dropNames=true, bool dropIntegers=true, bool fixOthers=false)
Subproblem constructor.
double clpObjectiveValue() const
Objective value.
double lastPrimalError_
Last primal error.
void setColumnSetBounds(const int *indexFirst, const int *indexLast, const double *boundList)
Set the bounds on a number of columns simultaneously The default implementation just invokes setColL...
void defaultFactorizationFrequency()
If user left factorization frequency then compute.
void resize(int newNumberRows, int newNumberColumns)
Resizes rim part of model.
int stateDualColumn_
State of dual waffle -2 - in initial large tolerance phase -1 - in medium tolerance phase n - in corr...
double movement_
Movement of variable.
void setFactorization(AbcSimplexFactorization &factorization)
Passes in factorization.
void setPrimalColumnPivotAlgorithm(AbcPrimalColumnPivot &choice)
Sets column pivot choice algorithm in primal.
double * scaleFromExternal_
Points from external to internal.
void originalModel(AbcSimplex *miniModel)
This copies back stuff from miniModel and then deletes miniModel.
int numberOrdinary() const
Number of ordinary (lo/up) in tableau row.
void setActive(int iRow)
To say row active in primal pivot row choice.
void printStuff() const
Print stuff.
void setDualRowPivotAlgorithm(AbcDualRowPivot &choice)
Sets row pivot choice algorithm in dual.
double * solutionBasic_
Working scaled basic primal solution.
void setMultipleSequenceIn(int sequenceIn[4])
set multiple sequence in
void moveInfo(const AbcSimplex &rhs, bool justStatus=false)
Move status and solution across.
void clearPivoted(int sequence)
void checkConsistentPivots() const
For debug - check pivotVariable consistent.
void checkSolutionBasic() const
For debug - checks solutionBasic.
void checkDualSolutionPlusFake()
This sets largest infeasibility and most infeasible and sum and number of infeasibilities AND sumFake...
AbcDualRowPivot * dualRowPivot() const
dual row pivot choice
double lower(int sequence)
double * lowerBasic_
Working scaled copy of basic lower bounds.
const double * getRowPrice() const
Get pointer to array[getNumRows()] of dual prices.
double & reducedCostAddress(int sequence)
int arrayForFtran() const
const double * getRowActivity() const
Get pointer to array[getNumRows()] of row activity levels (constraint matrix times the solution vecto...
int lastPivotRow_
Current/last pivot row (set after END of choosing pivot row in dual)
int multipleSequenceIn_[4]
Multiple sequence in.
void clearArrays(int which)
Clears an array and says available (-1 does all)
int primal(int ifValuesPass)
Primal algorithm - see AbcSimplexPrimal.hpp for method.
double * offsetRhs_
Offset for accumulated offsets*matrix.
double * inverseColumnScale2() const
int startup(int ifValuesPass)
Common bits of coding for dual and primal.
ClpDataSave saveData_
For saving stuff at beginning.
void setColBounds(int elementIndex, double newlower, double newupper)
Set a single column lower and upper bound.
int freeSequenceIn_
Free chosen vector.
int getAvailableArrayPublic() const
Returns first available empty array (and sets flag) when no possibility of going parallel.
double * abcLower_
Working scaled copy of lower bounds has original scaled copy at end.
void restoreData(ClpDataSave saved)
Restore data.
double currentAcceptablePivot_
Acceptable pivot for this iteration.
void unpack(CoinIndexedVector &rowArray, int sequence) const
Unpacks one column of the matrix into indexed array.
bool pivoted(int sequence) const
const double * getReducedCost() const
Get a pointer to array[getNumCols()] of reduced costs.
double solution(int sequence)
Return row or column values.
int arrayForFlipBounds() const
void checkDualSolution()
This sets largest infeasibility and most infeasible and sum and number of infeasibilities (Dual)
void setInternalColumnStatus(int sequence, AbcSimplex::Status newstatus)
void clearFlagged(int sequence)
int getAvailableArray() const
Returns first available empty array (and sets flag)
int sequenceIn() const
Return sequence In or Out.
int internalFactorize(int solveType)
Factorizes using current basis.
void moveStatusFromClp(ClpSimplex *clpModel)
Move status and solution from ClpSimplex.
void putStuffInBasis(int type)
Puts more stuff in basis 1 bit set - do even if basis exists 2 bit set - don't bother staying triangu...
double & solutionAddress(int sequence)
Return address of row or column values.
void makeBaseModel()
Array persistence flag If 0 then as now (delete/new) 1 then only do arrays if bigger needed 2 as 1 bu...
AbcSimplexFactorization * abcFactorization_
factorization
AbcSimplex(bool emptyMessages=false)
Default constructor.
double * costRegion() const
AbcSimplex(const ClpSimplex &rhs)
Copy constructor from model.
AbcPrimalColumnPivot * primalColumnPivot() const
primal column pivot choice
double btranAlpha_
Btran alpha.
void unpack(CoinIndexedVector &rowArray) const
Unpacks one column of the matrix into indexed array Uses sequenceIn_.
double * scaleToExternal() const
Scale from primal internal to external (in external order) Or other way for dual.
void setInternalStatus(int sequence, AbcSimplex::Status newstatus)
double * inverseColumnUseScale_
use this instead of inverseColumnScale
double & costAddress(int sequence)
Return address of row or column cost.
int startAtUpperOther_
Start of variables at upper bound with lower.
int startAtLowerOther_
Start of variables at lower bound with upper.
void setRowLower(int elementIndex, double elementValue)
Set a single row lower bound Use -DBL_MAX for -infinity.
double valueIncomingDual() const
value of incoming variable (in Dual)
void setColLower(int elementIndex, double elementValue)
Set a single column lower bound Use -DBL_MAX for -infinity.
double & upperAddress(int sequence)
Return address of row or column upper bound.
void setToBaseModel(AbcSimplex *model=NULL)
Reset to base model (just size and arrays needed) If model NULL use internal copy.
void setUsedArray(int which) const
Say array going to be used.
double currentDualTolerance_
Current dualTolerance (will end up as dualTolerance_)
const double * getColSolution() const
Get pointer to array[getNumCols()] of primal solution vector.
void saveGoodStatus()
Saves good status etc.
bool initialDenseFactorization() const
double * djBasic() const
void putBackSolution(ClpSimplex *simplex)
Put back solution into ClpSimplex.
int numberFreeNonBasic_
Number of free nonbasic variables.
int maximumAbcNumberRows_
Maximum number rows.
unsigned char * internalStatusSaved_
Saved status.
void setupPointers(int maxRows, int maxColumns)
Sets up all extra pointers.
void clearArraysPublic(int which)
Clears an array and says available (-1 does all) when no possibility of going parallel.
void setAvailableArray(int which) const
Say array going available.
double * costBasic() const
int * pivotVariable() const
Basic variables pivoting on which rows may be same as toExternal but may be as at invert.
double perturbationFactor_
Perturbation factor If <0.0 then virtual if 0.0 none if >0.0 use this as factor.
void setColumnLower(int elementIndex, double elementValue)
Set a single column lower bound Use -DBL_MAX for -infinity.
void checkBothSolutions()
This sets sum and number of infeasibilities (Dual and Primal)
int sequenceOut() const
int * abcPivotVariable_
Basic variables pivoting on which rows followed by atLo/atUp then free/superbasic then fixed.
int ordinaryVariables() const
Set to 1 if no free or super basic.
AbcSimplex(const ClpSimplex *clpSimplex)
This constructor copies from ClpSimplex.
double currentDualBound_
Current dualBound (will end up as dualBound_)
void setColSetBounds(const int *indexFirst, const int *indexLast, const double *boundList)
Set the bounds on a number of columns simultaneously
AbcSimplex(const ClpSimplex *wholeModel, int numberRows, const int *whichRows, int numberColumns, const int *whichColumns, bool dropNames=true, bool dropIntegers=true, bool fixOthers=false)
Subproblem constructor.
int lastFirstFree_
Last firstFree_.
int maximumAbcNumberColumns_
Maximum number columns.
double cost(int sequence)
int arrayForDualColumn_
int dual()
Dual algorithm - see AbcSimplexDual.hpp for method.
void translate(int type)
Translates ClpModel to AbcSimplex See DO_ bits in stateOfProblem_ for type e.g.
void setColumnUpper(int elementIndex, double elementValue)
Set a single column upper bound Use DBL_MAX for infinity.
int arrayForReplaceColumn_
double ftAlpha_
FT alpha.
double minimumThetaMovement_
Minimum theta movement.
void setRowSetBounds(const int *indexFirst, const int *indexLast, const double *boundList)
Set the bounds on a number of rows simultaneously
double * upperSaved_
Saved scaled copy of upper bounds.
double * perturbationSaved() const
Perturbation (fixed) - is just scaled random numbers.
void swapDualStuff(int lastSequenceOut, int lastDirectionOut)
Swaps dual stuff.
int numberOrdinary_
Number of ordinary (lo/up) in tableau row.
AbcSimplexProgress * abcProgress()
For dealing with all issues of cycling etc.
void setObjCoeff(int elementIndex, double elementValue)
Set an objective function coefficient.
CoinPartitionedVector * usefulArray(int index)
Useful arrays (0,1,2,3,4,5,6,7)
void swap(int pivotRow, int nonBasicPosition)
Swaps two variables.
double * djRegion(int which) const
CoinPartitionedVector usefulArray_[ABC_NUMBER_USEFUL]
int arrayForTableauRow() const
void cleanStatus(bool valuesPass=false)
Clean up status - make sure no superbasic etc.
bool isObjectiveLimitTestValid() const
Return true if the objective limit test can be relied upon.
int numberTotal_
Number of variables (includes spare rows)
double * abcCost_
Working scaled copy of objective ? where perturbed copy or can we always work with perturbed copy (in...
void computeObjectiveValue(bool useWorkingSolution=false)
Compute objective value from solution and put in objectiveValue_.
void setNumberOrdinary(int number)
Set number of ordinary (lo/up) in tableau row.
int isColumn(int sequence) const
Returns 1 if sequence indicates column.
int computePrimals(CoinIndexedVector *array1, CoinIndexedVector *array2)
Computes primals from scratch. Returns number of refinements.
void clearArrays(CoinPartitionedVector *which)
Clears an array and says available.
void setColUpper(int elementIndex, double elementValue)
Set a single column upper bound Use DBL_MAX for infinity.
double * solutionBasic() const
Return region.
AbcSimplexFactorization * getEmptyFactorization()
Gets clean and emptyish factorization.
int doAbcDual()
void refreshUpper(unsigned int type=~(ROW_LOWER_SAME|COLUMN_LOWER_SAME))
double * tempArray_
Useful array of numberTotal length.
double * columnScale2() const
int numberTotalWithoutFixed() const
Number of variables without fixed to zero (includes spare rows)
double * djRegion() const
unsigned char * internalStatus_
Working status ? may be signed ? link pi_ to an indexed array? may have saved from last factorization...
double * columnUseScale_
use this instead of columnScale
double * lowerBasic() const
double * lowerRegion() const
CoinWarmStartBasis * getBasis() const
Returns a basis (to be deleted by user)
AbcSimplexFactorization * factorization() const
factorization
AbcNonLinearCost * abcNonLinearCost_
Very wasteful way of dealing with infeasibilities in primal.
void permuteOut(int whatsWanted)
Permutes out - bit settings same as stateOfProblem.
void swap(int pivotRow, int nonBasicPosition, Status newStatus)
Swaps two variables and does status.
ClpSimplex * clpModel_
A copy of model as ClpSimplex with certain state.
void setRowBounds(int elementIndex, double lower, double upper)
Set a single row lower and upper bound.
double originalUpper(int iSequence) const
Return original lower bound.
double upperTheta_
upper theta from dual column
double * upperBasic() const
int doAbcPrimal(int ifValuesPass)
AbcNonLinearCost * abcNonLinearCost() const
Return pointer to details of costs.
FakeBound getFakeBound(int sequence) const
double * offset_
Primal offset (in external order) So internal value is (external-offset)*scaleFromExternal.
AbcSimplex * baseModel() const
See if we have base model.
int arrayForFlipBounds_
int stateOfProblem() const
State of problem.
double objectiveOffset_
Objective offset (from offset_)
int arrayForReplaceColumn() const
double * rowScale2() const
corresponds to rowScale etc
void refreshCosts()
After modifying first copy refreshes second copy and marks as updated.
double * scaleFromExternal() const
Points from external to internal.
double lastDualBound_
Last dual bound.
double currentDualBound() const
Current dualBound (will end up as dualBound_)
AbcSimplex & operator=(const AbcSimplex &rhs)
Assignment operator. This copies the data.
double currentDualTolerance() const
Current dualTolerance (will end up as dualTolerance_)
Status
enums for status of various sorts.
void setInitialDenseFactorization(bool onOff)
Normally the first factorization does sparse coding because the factorization could be singular.
void clearActive(int iRow)
double sumNonBasicCosts_
Sum of nonbasic costs.
void setSequenceIn(int sequence)
Set sequenceIn or Out.
int arrayForBtran() const
double originalLower(int iSequence) const
Return original lower bound.
bool active(int iRow) const
double * upperBasic_
Working scaled copy of basic upper bounds.
int maximumAbcNumberRows() const
Maximum rows.
AbcMatrix * abcMatrix_
Working matrix.
double lastDualError_
Last dual error.
double * solutionSaved_
Saved scaled primal solution.
double * inverseRowScale2() const
int computeDuals(double *givenDjs, CoinIndexedVector *array1, CoinIndexedVector *array2)
Computes duals from scratch.
void gutsOfInitialize(int numberRows, int numberColumns, bool doMore)
Initializes arrays.
void crash(int type)
Does sort of crash.
double * solutionRegion() const
Return region.
void createStatus()
Set up status array (can be used by OsiAbc).
CoinPartitionedVector * usefulArray(int index) const
double * djBasic_
Working scaled basic dual solution (want it to be zero)
ClpDataSave saveData()
Save data.
void refreshLower(unsigned int type=~(ROW_LOWER_SAME|COLUMN_UPPER_SAME))
void setRowUpper(int elementIndex, double elementValue)
Set a single row upper bound Use DBL_MAX for infinity.
double * abcSolution_
Working scaled primal solution may have saved from last factorization at end.
int maximumTotal() const
void deleteBaseModel()
Switch off base model.
double rawObjectiveValue() const
Raw objective value (so always minimize in primal)
double upperTheta() const
upper theta from dual column
double * lowerSaved_
Saved scaled copy of lower bounds.
~AbcSimplex()
Destructor.
AbcPrimalColumnPivot * abcPrimalColumnPivot_
primal column pivot choice
int lastCleaned_
Last time cleaned up.
void permuteIn()
Permutes in from ClpModel data - assumes scale factors done and AbcMatrix exists but is in original o...
int factorizationFrequency() const
Factorization frequency.
double * perturbationSaved_
saved perturbation
int swappedAlgorithm_
Nonzero (probably 10) if swapped algorithms.
AbcSimplex::Status getInternalStatus(int sequence) const
double rawObjectiveValue_
Sum of costs (raw objective value)
void setFlagged(int sequence)
To flag a variable.
This is a tiny class where data can be saved round calls.
Base class for Clp disaster handling.
int numberColumns_
Number of columns.
CoinBigIndex getNumElements() const
Number of elements in matrix.
Definition ClpModel.hpp:780
double optimizationDirection_
Direction of optimization (1 - minimize, -1 - maximize, 0 - ignore.
double * rowUpper_
Row upper.
double * rowLower_
Row lower.
double * columnUpper_
Column Upper.
double dblParam_[ClpLastDblParam]
Array of double parameters.
double objectiveValue_
Objective value.
double * columnLower_
Column Lower.
This solves LPs using the simplex method.
double primalTolerance_
Current primal tolerance for algorithm.
double bestPossibleImprovement_
Best possible improvement using djs (primal) or obj change by flipping bounds to make dual feasible (...
double acceptablePivot_
Acceptable pivot value just after factorization.
int sequenceOut_
Sequence of Out variable.
int sequenceIn_
Sequence of In variable.
int firstFree_
First free/super-basic variable (-1 if none)