Clp  1.15.10
AbcSimplex.hpp
Go to the documentation of this file.
1 /* $Id: AbcSimplex.hpp 1910 2013-01-27 02:00:13Z stefan $ */
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"
20 class AbcSimplex;
21 #include "ClpSolve.hpp"
22 #include "CoinAbcCommon.hpp"
23 class ClpSimplex;
24 class AbcDualRowPivot;
27 class AbcNonLinearCost;
28 class OsiAbcSolverInterface;
29 class CoinWarmStartBasis;
30 class ClpDisasterHandler;
31 class AbcSimplexProgress;
32 class AbcMatrix;
33 class AbcTolerancesEtc;
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
62 typedef struct {
63  double result;
64  //const CoinIndexedVector * constVector; // can get rid of
65  //CoinIndexedVector * vectors[2]; // can get rid of
66  int status;
67  int stuff[4];
69 #include "ClpSimplex.hpp"
70 class AbcSimplex : public ClpSimplex {
71  friend void AbcSimplexUnitTest(const std::string & mpsDir);
72 
73 public:
82  enum Status {
83  atLowerBound = 0x00, // so we can use bottom two bits to sort and swap signs
84  atUpperBound = 0x01,
85  isFree = 0x04,
86  superBasic = 0x05,
87  basic = 0x06,
88  isFixed = 0x07
89  };
90  // For Dual
91  enum FakeBound {
92  noFake = 0x00,
93  lowerFake = 0x01,
94  upperFake = 0x02,
95  bothFake = 0x03
96  };
97 
100  AbcSimplex (bool emptyMessages = false );
102 
105  AbcSimplex(const AbcSimplex & rhs);
108  AbcSimplex(const ClpSimplex & rhs);
115  AbcSimplex (const ClpSimplex * wholeModel,
116  int numberRows, const int * whichRows,
117  int numberColumns, const int * whichColumns,
118  bool dropNames = true, bool dropIntegers = true,
119  bool fixOthers = false);
126  AbcSimplex (const AbcSimplex * wholeModel,
127  int numberRows, const int * whichRows,
128  int numberColumns, const int * whichColumns,
129  bool dropNames = true, bool dropIntegers = true,
130  bool fixOthers = false);
134  AbcSimplex (AbcSimplex * wholeModel,
135  int numberColumns, const int * whichColumns);
138  void originalModel(AbcSimplex * miniModel);
140  AbcSimplex (const ClpSimplex * clpSimplex);
142  void putBackSolution(ClpSimplex * simplex);
148  //void setPersistenceFlag(int value);
150  void makeBaseModel();
152  void deleteBaseModel();
154  inline AbcSimplex * baseModel() const {
155  return abcBaseModel_;
156  }
160  void setToBaseModel(AbcSimplex * model = NULL);
162  AbcSimplex & operator=(const AbcSimplex & rhs);
164  ~AbcSimplex ( );
166 
171  int dual();
172  int doAbcDual();
175  int primal(int ifValuesPass);
176  int doAbcPrimal(int ifValuesPass);
178  CoinWarmStartBasis * getBasis() const;
180  void setFactorization( AbcSimplexFactorization & factorization);
182  AbcSimplexFactorization * swapFactorization( AbcSimplexFactorization * factorization);
184  AbcSimplexFactorization * getEmptyFactorization();
194  int tightenPrimalBounds();
196  void setDualRowPivotAlgorithm(AbcDualRowPivot & choice);
198  void setPrimalColumnPivotAlgorithm(AbcPrimalColumnPivot & choice);
200  void defaultFactorizationFrequency();
203 
206  inline AbcSimplexFactorization * factorization() const {
208  return reinterpret_cast<AbcSimplexFactorization *>(abcFactorization_);
209  }
210 #ifdef EARLY_FACTORIZE
211  inline AbcSimplexFactorization * earlyFactorization() const {
213  return reinterpret_cast<AbcSimplexFactorization *>(abcEarlyFactorization_);
214  }
215 #endif
216  int factorizationFrequency() const;
218  void setFactorizationFrequency(int value);
220  inline int maximumAbcNumberRows() const
221  { return maximumAbcNumberRows_;}
223  inline int maximumNumberTotal() const
224  { return maximumNumberTotal_;}
225  inline int maximumTotal() const
226  { return maximumNumberTotal_;}
228  bool isObjectiveLimitTestValid() const ;
230  inline int numberTotal() const
231  { return numberTotal_;}
233  inline int numberTotalWithoutFixed() const
234  { return numberTotalWithoutFixed_;}
236  inline CoinPartitionedVector * usefulArray(int index) {
237  return & usefulArray_[index];
238  }
239  inline CoinPartitionedVector * usefulArray(int index) const {
240  return const_cast<CoinPartitionedVector *>(&usefulArray_[index]);
241  }
243 
244  /******************** End of most useful part **************/
250  int getSolution ();
252  void setClpSimplexObjectiveValue();
258  void setupDualValuesPass(const double * fakeDuals,
259  const double * fakePrimals,
260  int type);
262  inline double minimizationObjectiveValue() const
263  { return objectiveValue_-dblParam_[ClpObjOffset];}
265  inline double currentDualTolerance() const
266  { return currentDualTolerance_;}
267  inline void setCurrentDualTolerance(double value) {
268  currentDualTolerance_ = value;
269  }
272  return abcNonLinearCost_;
273  }
275  double * perturbationSaved() const
276  { return perturbationSaved_;}
278  inline double acceptablePivot() const
279  { return acceptablePivot_;}
281  inline int ordinaryVariables() const
282  { return ordinaryVariables_;}
284  inline int numberOrdinary() const
285  { return numberOrdinary_;}
287  inline void setNumberOrdinary(int number)
288  { numberOrdinary_=number;}
290  inline double currentDualBound() const
291  { return currentDualBound_;}
293  inline AbcDualRowPivot * dualRowPivot() const {
294  return abcDualRowPivot_;
295  }
298  return abcPrimalColumnPivot_;
299  }
301  inline AbcMatrix * abcMatrix() const {
302  return abcMatrix_;
303  }
313  int internalFactorize(int solveType);
329  void permuteIn();
331  void permuteBasis();
333  void permuteOut(int whatsWanted);
335  ClpDataSave saveData() ;
337  void restoreData(ClpDataSave saved);
339  void cleanStatus();
342  int computeDuals(double * givenDjs, CoinIndexedVector * array1, CoinIndexedVector * array2);
344  int computePrimals (CoinIndexedVector * array1, CoinIndexedVector * array2);
346  void computeObjective ();
348  void setMultipleSequenceIn(int sequenceIn[4]);
353  inline void unpack(CoinIndexedVector & rowArray) const
354  {unpack(rowArray,sequenceIn_);}
358  void unpack(CoinIndexedVector & rowArray, int sequence) const;
363  int housekeeping(/*double objectiveChange*/);
366  void checkPrimalSolution(bool justBasic);
369  void checkDualSolution();
372  void checkDualSolutionPlusFake();
374  void checkBothSolutions();
376  int gutsOfSolution(int type);
378  int gutsOfPrimalSolution(int type);
380  void saveGoodStatus();
382  void restoreGoodStatus(int type);
383 #define rowUseScale_ scaleFromExternal_
384 #define inverseRowUseScale_ scaleToExternal_
385  void refreshCosts();
387  void refreshLower(unsigned int type=~(ROW_LOWER_SAME|COLUMN_UPPER_SAME));
388  void refreshUpper(unsigned int type=~(ROW_LOWER_SAME|COLUMN_LOWER_SAME));
390  void setupPointers(int maxRows,int maxColumns);
392  void copyFromSaved(int type=31);
394  void fillPerturbation(int start, int number);
396  void checkArrays(int ignoreEmpty=0) const;
398  void checkDjs(int type=1) const;
400  void checkSolutionBasic() const;
402  void checkMoveBack(bool checkDuals);
403 public:
414  void setValuesPassAction(double incomingInfeasibility,
415  double allowedInfeasibility);
418  int cleanFactorization(int ifValuesPass);
420  void moveStatusToClp(ClpSimplex * clpModel);
422  void moveStatusFromClp(ClpSimplex * clpModel);
424 
426 public:
427 
429  inline double clpObjectiveValue() const {
430  return (objectiveValue_+objectiveOffset_-bestPossibleImprovement_)*optimizationDirection_ - dblParam_[ClpObjOffset];
431  }
434  inline int * pivotVariable() const {
435  return abcPivotVariable_;
436  }
438  inline int stateOfProblem() const
439  { return stateOfProblem_;}
441  inline void setStateOfProblem(int value)
442  { stateOfProblem_=value;}
444  //inline int * fromExternal() const
445  //{ return fromExternal_;}
447  //inline int * toExternal() const
448  //{return toExternal_;}
451  inline double * scaleFromExternal() const
452  {return scaleFromExternal_;}
455  inline double * scaleToExternal() const
456  {return scaleToExternal_;}
458  inline double * rowScale2() const
459  {return rowUseScale_;}
460  inline double * inverseRowScale2() const
461  {return inverseRowUseScale_;}
462  inline double * inverseColumnScale2() const
463  {return inverseColumnUseScale_;}
464  inline double * columnScale2() const
465  {return columnUseScale_;}
466  inline int arrayForDualColumn() const
467  {return arrayForDualColumn_;}
469  inline double upperTheta() const
470  {return upperTheta_;}
471  inline int arrayForReplaceColumn() const
472  { return arrayForReplaceColumn_;}
473  inline int arrayForFlipBounds() const
474  { return arrayForFlipBounds_;}
475  inline int arrayForFlipRhs() const
476  { return arrayForFlipRhs_;}
477  inline int arrayForBtran() const
478  { return arrayForBtran_;}
479  inline int arrayForFtran() const
480  { return arrayForFtran_;}
481  inline int arrayForTableauRow() const
482  { return arrayForTableauRow_;}
484  double valueIncomingDual() const;
486  const double * getColSolution() const;
487 
489  const double * getRowPrice() const;
490 
492  const double * getReducedCost() const;
493 
496  const double * getRowActivity() const;
498 
504  int gutsOfSolution ( double * givenDuals,
505  const double * givenPrimals,
506  bool valuesPass = false);
508  void gutsOfDelete(int type);
510  void gutsOfCopy(const AbcSimplex & rhs);
512  void gutsOfInitialize(int numberRows,int numberColumns,bool doMore);
514  void gutsOfResize(int numberRows,int numberColumns);
518  void translate(int type);
520  void moveToBasic(int which=15);
522 public:
525  inline double * solutionRegion() const {
527  return abcSolution_;
528  }
529  inline double * djRegion() const {
530  return abcDj_;
531  }
532  inline double * lowerRegion() const {
533  return abcLower_;
534  }
535  inline double * upperRegion() const {
536  return abcUpper_;
537  }
538  inline double * costRegion() const {
539  return abcCost_;
540  }
542  inline double * solutionRegion(int which) const {
543  return abcSolution_+which*maximumAbcNumberRows_;
544  }
545  inline double * djRegion(int which) const {
546  return abcDj_+which*maximumAbcNumberRows_;
547  }
548  inline double * lowerRegion(int which) const {
549  return abcLower_+which*maximumAbcNumberRows_;
550  }
551  inline double * upperRegion(int which) const {
552  return abcUpper_+which*maximumAbcNumberRows_;
553  }
554  inline double * costRegion(int which) const {
555  return abcCost_+which*maximumAbcNumberRows_;
556  }
558  inline double * solutionBasic() const {
559  return solutionBasic_;
560  }
561  inline double * djBasic() const {
562  return djBasic_;
563  }
564  inline double * lowerBasic() const {
565  return lowerBasic_;
566  }
567  inline double * upperBasic() const {
568  return upperBasic_;
569  }
570  inline double * costBasic() const {
571  return costBasic_;
572  }
574  inline double * abcPerturbation() const
575  { return abcPerturbation_;}
577  inline double * fakeDjs() const
578  { return djSaved_;}
579  inline unsigned char * internalStatus() const
580  { return internalStatus_;}
581  inline AbcSimplex::Status getInternalStatus(int sequence) const {
582  return static_cast<Status> (internalStatus_[sequence] & 7);
583  }
584  inline AbcSimplex::Status getInternalColumnStatus(int sequence) const {
585  return static_cast<Status> (internalStatus_[sequence+maximumAbcNumberRows_] & 7);
586  }
587  inline void setInternalStatus(int sequence, AbcSimplex::Status newstatus) {
588  unsigned char & st_byte = internalStatus_[sequence];
589  st_byte = static_cast<unsigned char>(st_byte & ~7);
590  st_byte = static_cast<unsigned char>(st_byte | newstatus);
591  }
592  inline void setInternalColumnStatus(int sequence, AbcSimplex::Status newstatus) {
593  unsigned char & st_byte = internalStatus_[sequence+maximumAbcNumberRows_];
594  st_byte = static_cast<unsigned char>(st_byte & ~7);
595  st_byte = static_cast<unsigned char>(st_byte | newstatus);
596  }
601  void setInitialDenseFactorization(bool onOff);
602  bool initialDenseFactorization() const;
604  inline int sequenceIn() const {
605  return sequenceIn_;
606  }
607  inline int sequenceOut() const {
608  return sequenceOut_;
609  }
611  inline void setSequenceIn(int sequence) {
612  sequenceIn_ = sequence;
613  }
614  inline void setSequenceOut(int sequence) {
615  sequenceOut_ = sequence;
616  }
617 #if 0
618 
619  inline int sequenceInternalIn() const {
620  return sequenceInternalIn_;
621  }
622  inline int sequenceInternalOut() const {
623  return sequenceInternalOut_;
624  }
626  inline void setSequenceInternalIn(int sequence) {
627  sequenceInternalIn_ = sequence;
628  }
629  inline void setSequenceInternalOut(int sequence) {
630  sequenceInternalOut_ = sequence;
631  }
632 #endif
633  inline int isColumn(int sequence) const {
635  return sequence >= maximumAbcNumberRows_ ? 1 : 0;
636  }
638  inline int sequenceWithin(int sequence) const {
639  return sequence < maximumAbcNumberRows_ ? sequence : sequence - maximumAbcNumberRows_;
640  }
642  inline int lastPivotRow() const
643  { return lastPivotRow_;}
645  inline int firstFree() const
646  { return firstFree_;}
648  inline int lastFirstFree() const
649  { return lastFirstFree_;}
651  inline int freeSequenceIn() const
652  { return freeSequenceIn_;}
654  inline double currentAcceptablePivot() const
655  { return currentAcceptablePivot_;}
656 #ifdef PAN
657 
663  inline int fakeSuperBasic(int iSequence) {
664  if ((internalStatus_[iSequence]&7)==4)
665  return 0; // free
666  if ((internalStatus_[iSequence]&7)!=5)
667  return -2;
668  double value=abcSolution_[iSequence];
669  if (value<abcLower_[iSequence]+primalTolerance_) {
670  if(abcDj_[iSequence]>=-currentDualTolerance_) {
671  setInternalStatus(iSequence,atLowerBound);
672 #if PRINT_PAN>1
673  printf("Pansetting %d to lb\n",iSequence);
674 #endif
675  return -1;
676  } else {
677  return 1;
678  }
679  } else if (value>abcUpper_[iSequence]-primalTolerance_) {
680  if (abcDj_[iSequence]<=currentDualTolerance_) {
681  setInternalStatus(iSequence,atUpperBound);
682 #if PRINT_PAN>1
683  printf("Pansetting %d to ub\n",iSequence);
684 #endif
685  return -1;
686  } else {
687  return 1;
688  }
689  } else {
690  return 0;
691  }
692  }
693 #endif
694  inline double solution(int sequence) {
696  return abcSolution_[sequence];
697  }
699  inline double & solutionAddress(int sequence) {
700  return abcSolution_[sequence];
701  }
702  inline double reducedCost(int sequence) {
703  return abcDj_[sequence];
704  }
705  inline double & reducedCostAddress(int sequence) {
706  return abcDj_[sequence];
707  }
708  inline double lower(int sequence) {
709  return abcLower_[sequence];
710  }
712  inline double & lowerAddress(int sequence) {
713  return abcLower_[sequence];
714  }
715  inline double upper(int sequence) {
716  return abcUpper_[sequence];
717  }
719  inline double & upperAddress(int sequence) {
720  return abcUpper_[sequence];
721  }
722  inline double cost(int sequence) {
723  return abcCost_[sequence];
724  }
726  inline double & costAddress(int sequence) {
727  return abcCost_[sequence];
728  }
730  inline double originalLower(int iSequence) const {
731  if (iSequence < numberColumns_) return columnLower_[iSequence];
732  else
733  return rowLower_[iSequence-numberColumns_];
734  }
736  inline double originalUpper(int iSequence) const {
737  if (iSequence < numberColumns_) return columnUpper_[iSequence];
738  else
739  return rowUpper_[iSequence-numberColumns_];
740  }
742  inline AbcSimplexProgress * abcProgress()
743  { return &abcProgress_;}
744 public:
747  inline void clearArraysPublic(int which)
748  { clearArrays(which);}
751  inline int getAvailableArrayPublic() const
752  { return getAvailableArray();}
753 #if ABC_PARALLEL
754  inline int parallelMode() const
756  { return parallelMode_;}
758  inline void setParallelMode(int value)
759  { parallelMode_=value;}
761  inline int numberCpus() const
762  { return parallelMode_+1;}
763 #if ABC_PARALLEL==1
764  inline void setStopStart(int value)
766  { stopStart_=value;}
767 #endif
768 #endif
769  //protected:
771  void clearArrays(int which);
773  void clearArrays(CoinPartitionedVector * which);
775  int getAvailableArray() const;
777  inline void setUsedArray(int which) const
778  {int check=1<<which;assert ((stateOfProblem_&check)==0);stateOfProblem_|=check;}
780  inline void setAvailableArray(int which) const
781  {int check=1<<which;assert ((stateOfProblem_&check)!=0);
782  assert (!usefulArray_[which].getNumElements());stateOfProblem_&=~check;}
784  void swapPrimalStuff();
786  void swapDualStuff(int lastSequenceOut,int lastDirectionOut);
787 protected:
789 
791  void swap(int pivotRow,int nonBasicPosition,Status newStatus);
793  inline void setFakeBound(int sequence, FakeBound fakeBound) {
794  unsigned char & st_byte = internalStatus_[sequence];
795  st_byte = static_cast<unsigned char>(st_byte & ~24);
796  st_byte = static_cast<unsigned char>(st_byte | (fakeBound << 3));
797  }
798  inline FakeBound getFakeBound(int sequence) const {
799  return static_cast<FakeBound> ((internalStatus_[sequence] >> 3) & 3);
800  }
801  bool atFakeBound(int sequence) const;
802  inline void setPivoted( int sequence) {
803  internalStatus_[sequence] = static_cast<unsigned char>(internalStatus_[sequence] | 32);
804  }
805  inline void clearPivoted( int sequence) {
806  internalStatus_[sequence] = static_cast<unsigned char>(internalStatus_[sequence] & ~32);
807  }
808  inline bool pivoted(int sequence) const {
809  return (((internalStatus_[sequence] >> 5) & 1) != 0);
810  }
811 public:
813  void swap(int pivotRow,int nonBasicPosition);
815  void setFlagged( int sequence);
816  inline void clearFlagged( int sequence) {
817  internalStatus_[sequence] = static_cast<unsigned char>(internalStatus_[sequence] & ~64);
818  }
819  inline bool flagged(int sequence) const {
820  return ((internalStatus_[sequence] & 64) != 0);
821  }
822 protected:
824  inline void setActive( int iRow) {
825  internalStatus_[iRow] = static_cast<unsigned char>(internalStatus_[iRow] | 128);
826  }
827  inline void clearActive( int iRow) {
828  internalStatus_[iRow] = static_cast<unsigned char>(internalStatus_[iRow] & ~128);
829  }
830  inline bool active(int iRow) const {
831  return ((internalStatus_[iRow] & 128) != 0);
832  }
833 public:
836  void createStatus() ;
838  void crash(int type);
843  void putStuffInBasis(int type);
846  void allSlackBasis();
848  void checkConsistentPivots() const;
850  void printStuff() const;
852  int startup(int ifValuesPass);
853 
855  inline double rawObjectiveValue() const {
856  return objectiveValue_;
857  }
859  void computeObjectiveValue(bool useWorkingSolution = false);
861  double computeInternalObjectiveValue();
863  void moveInfo(const AbcSimplex & rhs, bool justStatus = false);
864 #define NUMBER_THREADS 3
865 #if ABC_PARALLEL==1
866  // For waking up thread
867  inline pthread_mutex_t * mutexPointer(int which,int thread=0)
868  { return mutex_+which+3*thread;}
869  inline pthread_barrier_t * barrierPointer()
870  { return &barrier_;}
871  inline int whichLocked(int thread=0) const
872  { return locked_[thread];}
873  inline CoinAbcThreadInfo * threadInfoPointer(int thread=0)
874  { return threadInfo_+thread;}
875  void startParallelStuff(int type);
876  int stopParallelStuff(int type);
878  int whichThread() const;
879 #elif ABC_PARALLEL==2
880  //inline CoinAbcThreadInfo * threadInfoPointer(int thread=0)
881  //{ return threadInfo_+thread;}
882 #endif
883 
884 
885  //-------------------------------------------------------------------------
889  void setObjectiveCoefficient( int elementIndex, double elementValue );
891  inline void setObjCoeff( int elementIndex, double elementValue ) {
892  setObjectiveCoefficient( elementIndex, elementValue);
893  }
894 
897  void setColumnLower( int elementIndex, double elementValue );
898 
901  void setColumnUpper( int elementIndex, double elementValue );
902 
904  void setColumnBounds( int elementIndex,
905  double lower, double upper );
906 
915  void setColumnSetBounds(const int* indexFirst,
916  const int* indexLast,
917  const double* boundList);
918 
921  inline void setColLower( int elementIndex, double elementValue ) {
922  setColumnLower(elementIndex, elementValue);
923  }
926  inline void setColUpper( int elementIndex, double elementValue ) {
927  setColumnUpper(elementIndex, elementValue);
928  }
929 
931  inline void setColBounds( int elementIndex,
932  double newlower, double newupper ) {
933  setColumnBounds(elementIndex, newlower, newupper);
934  }
935 
942  inline void setColSetBounds(const int* indexFirst,
943  const int* indexLast,
944  const double* boundList) {
945  setColumnSetBounds(indexFirst, indexLast, boundList);
946  }
947 
950  void setRowLower( int elementIndex, double elementValue );
951 
954  void setRowUpper( int elementIndex, double elementValue ) ;
955 
957  void setRowBounds( int elementIndex,
958  double lower, double upper ) ;
959 
966  void setRowSetBounds(const int* indexFirst,
967  const int* indexLast,
968  const double* boundList);
970  void resize (int newNumberRows, int newNumberColumns);
971 
973 
975 protected:
976 
983  double sumNonBasicCosts_;
999  double largestGap_;
1011  double movement_;
1015  double btranAlpha_;
1017 #ifdef ABC_LONG_FACTORIZATION
1018  long
1019 #endif
1020  double ftAlpha_;
1025 public:
1028 protected:
1049  /*
1050  May want to put some arrays into struct
1051  Two arrays point to/from external
1052  Order is basic,unused basic, at lower, at upper, superbasic, free, fixed with starts
1053  */
1059 #define startAtLowerNoOther_ maximumAbcNumberRows_
1060  int startAtLowerOther_;
1070 #ifdef EARLY_FACTORIZE
1071  int numberEarly_;
1073 #endif
1074 
1091 #define ALL_STATUS_OK 2048
1092 #define ROW_PRIMAL_OK 4096
1093 #define ROW_DUAL_OK 8192
1094 #define COLUMN_PRIMAL_OK 16384
1095 #define COLUMN_DUAL_OK 32768
1096 #define PESSIMISTIC 65536
1097 #define ADD_A_BIT 131072
1098 #define DO_SCALE_AND_MATRIX 262144
1099 #define DO_BASIS_AND_ORDER 524288
1100 #define DO_STATUS 1048576
1101 #define DO_SOLUTION 2097152
1102 #define DO_JUST_BOUNDS 0x400000
1103 #define NEED_BASIS_SORT 0x800000
1104 #define FAKE_SUPERBASIC 0x1000000
1105 #define VALUES_PASS 0x2000000
1106 #define VALUES_PASS2 0x4000000
1107  mutable int stateOfProblem_;
1108 #if ABC_PARALLEL
1109 public:
1111  int parallelMode_;
1112 protected:
1113 #endif
1114  int numberOrdinary_;
1129  //int * fromExternal_;
1131  //int * toExternal_;
1145  double * offset_;
1147  double * offsetRhs_;
1149  double * tempArray_;
1154  unsigned char * internalStatus_;
1156  unsigned char * internalStatusSaved_;
1168  double * abcLower_;
1171  double * abcUpper_;
1177  double * abcCost_;
1180  double * abcSolution_;
1183  double * abcDj_;
1185  double * lowerSaved_;
1187  double * upperSaved_;
1189  double * costSaved_;
1191  double * solutionSaved_;
1193  double * djSaved_;
1195  double * lowerBasic_;
1197  double * upperBasic_;
1199  double * costBasic_;
1201  double * solutionBasic_;
1203  double * djBasic_;
1216 #ifdef EARLY_FACTORIZE
1217  AbcSimplexFactorization * abcEarlyFactorization_;
1219 #endif
1220 #ifdef TEMPORARY_FACTORIZATION
1221  AbcSimplexFactorization * abcOtherFactorization_;
1223 #endif
1224  //double * savedSolution_;
1236  /* has secondary offset and counts so row goes first then column
1237  Probably back to CoinPartitionedVector as AbcMatrix has slacks
1238  also says if in use - so we can just get next available one */
1239 #define ABC_NUMBER_USEFUL 8
1240  mutable CoinPartitionedVector usefulArray_[ABC_NUMBER_USEFUL];
1242  AbcSimplexProgress abcProgress_;
1246  double upperTheta_;
1248  int multipleSequenceIn_[4];
1249 public:
1253  int arrayForFlipRhs_; // if sequential can re-use
1254  int arrayForBtran_; // 0
1255  int arrayForFtran_; // 1
1257 protected:
1260  //int nextCleanNonBasicIteration_;
1261 #if ABC_PARALLEL==1
1262  // For waking up thread
1263  pthread_mutex_t mutex_[3*NUMBER_THREADS];
1264  pthread_barrier_t barrier_;
1265  CoinAbcThreadInfo threadInfo_[NUMBER_THREADS];
1266  pthread_t abcThread_[NUMBER_THREADS];
1267  int locked_[NUMBER_THREADS];
1268  int stopStart_;
1269 #elif ABC_PARALLEL==2
1270  //CoinAbcThreadInfo threadInfo_[NUMBER_THREADS];
1271 #endif
1272 
1273 };
1274 //#############################################################################
1283 void
1284 AbcSimplexUnitTest(const std::string & mpsDir);
1285 #endif
int sequenceIn() const
Return sequence In or Out.
Definition: AbcSimplex.hpp:604
int lastPivotRow() const
Current/last pivot row (set after END of choosing pivot row in dual)
Definition: AbcSimplex.hpp:642
int maximumNumberTotal_
Maximum numberTotal.
unsigned char * internalStatusSaved_
Saved status.
int arrayForFlipBounds_
double * offsetRhs_
Offset for accumulated offsets*matrix.
AbcSimplex::Status getInternalStatus(int sequence) const
Definition: AbcSimplex.hpp:581
double * upperBasic() const
Definition: AbcSimplex.hpp:567
double * fakeDjs() const
Fake djs.
Definition: AbcSimplex.hpp:577
double * offset_
Primal offset (in external order) So internal value is (external-offset)*scaleFromExternal.
This just implements AbcFactorization when an AbcMatrix object is passed.
int stateDualColumn_
State of dual waffle -2 - in initial large tolerance phase -1 - in medium tolerance phase n - in corr...
FakeBound getFakeBound(int sequence) const
Definition: AbcSimplex.hpp:798
double & solutionAddress(int sequence)
Return address of row or column values.
Definition: AbcSimplex.hpp:699
double * abcDj_
Working scaled dual solution may have saved from last factorization at end.
int arrayForTableauRow_
AbcNonLinearCost * abcNonLinearCost() const
Return pointer to details of costs.
Definition: AbcSimplex.hpp:271
void setCurrentDualTolerance(double value)
Definition: AbcSimplex.hpp:267
Primal Column Pivot Abstract Base Class.
int lastPivotRow_
Current/last pivot row (set after END of choosing pivot row in dual)
double currentAcceptablePivot_
Acceptable pivot for this iteration.
int maximumNumberTotal() const
Maximum Total.
Definition: AbcSimplex.hpp:223
AbcDualRowPivot * abcDualRowPivot_
dual row pivot choice
int lastFirstFree() const
Last firstFree_.
Definition: AbcSimplex.hpp:648
int maximumAbcNumberColumns_
Maximum number columns.
int * reversePivotVariable_
Reverse abcPivotVariable_ for moving around.
int arrayForFlipRhs_
void setAvailableArray(int which) const
Say array going available.
Definition: AbcSimplex.hpp:780
AbcPrimalColumnPivot * primalColumnPivot() const
primal column pivot choice
Definition: AbcSimplex.hpp:297
double currentAcceptablePivot() const
Acceptable pivot for this iteration.
Definition: AbcSimplex.hpp:654
double currentDualTolerance() const
Current dualTolerance (will end up as dualTolerance_)
Definition: AbcSimplex.hpp:265
void setColBounds(int elementIndex, double newlower, double newupper)
Set a single column lower and upper bound.
Definition: AbcSimplex.hpp:931
unsigned char * internalStatus_
Working status ? may be signed ? link pi_ to an indexed array? may have saved from last factorization...
double * inverseRowScale2() const
Definition: AbcSimplex.hpp:460
double btranAlpha_
Btran alpha.
int * abcPivotVariable_
Basic variables pivoting on which rows followed by atLo/atUp then free/superbasic then fixed...
double objectiveChange_
Objective change.
int numberFlagged_
Current number of variables flagged.
double perturbationFactor_
Perturbation factor If <0.0 then virtual if 0.0 none if >0.0 use this as factor.
Definition: AbcSimplex.hpp:993
double * upperSaved_
Saved scaled copy of upper bounds.
double * upperRegion(int which) const
Definition: AbcSimplex.hpp:551
double lastDualError_
Last dual error.
double * djRegion(int which) const
Definition: AbcSimplex.hpp:545
double clpObjectiveValue() const
Objective value.
Definition: AbcSimplex.hpp:429
double * solutionBasic() const
Return region.
Definition: AbcSimplex.hpp:558
double * abcCost_
Working scaled copy of objective ? where perturbed copy or can we always work with perturbed copy (in...
int arrayForReplaceColumn() const
Definition: AbcSimplex.hpp:471
double primalTolerance_
Current primal tolerance for algorithm.
Base class for Clp disaster handling.
double * upperRegion() const
Definition: AbcSimplex.hpp:535
void setActive(int iRow)
To say row active in primal pivot row choice.
Definition: AbcSimplex.hpp:824
double * solutionSaved_
Saved scaled primal solution.
int initialNumberInfeasibilities_
Initial number of infeasibilities.
int arrayForTableauRow() const
Definition: AbcSimplex.hpp:481
double * abcSolution_
Working scaled primal solution may have saved from last factorization at end.
double * inverseColumnScale2() const
Definition: AbcSimplex.hpp:462
double * perturbationSaved_
saved perturbation
bool active(int iRow) const
Definition: AbcSimplex.hpp:830
void AbcSimplexUnitTest(const std::string &mpsDir)
A function that tests the methods in the AbcSimplex class.
double rawObjectiveValue_
Sum of costs (raw objective value)
Definition: AbcSimplex.hpp:986
#define ROW_LOWER_SAME
Definition: ClpModel.hpp:1204
void setNumberOrdinary(int number)
Set number of ordinary (lo/up) in tableau row.
Definition: AbcSimplex.hpp:287
void setInternalStatus(int sequence, AbcSimplex::Status newstatus)
Definition: AbcSimplex.hpp:587
AbcSimplexProgress abcProgress_
For dealing with all issues of cycling etc.
double initialSumInfeasibilities_
Initial sum of infeasibilities.
CoinPartitionedVector * usefulArray(int index) const
Definition: AbcSimplex.hpp:239
double rawObjectiveValue() const
Raw objective value (so always minimize in primal)
Definition: AbcSimplex.hpp:855
int numberOrdinary() const
Number of ordinary (lo/up) in tableau row.
Definition: AbcSimplex.hpp:284
double * costRegion() const
Definition: AbcSimplex.hpp:538
double * lowerRegion(int which) const
Definition: AbcSimplex.hpp:548
double movement_
Movement of variable.
double upperTheta_
upper theta from dual column
int startFixed_
Start of fixed variables.
#define NUMBER_THREADS
Definition: AbcSimplex.hpp:864
void clearActive(int iRow)
Definition: AbcSimplex.hpp:827
ClpDataSave saveData_
For saving stuff at beginning.
double largestGap_
Largest gap.
Definition: AbcSimplex.hpp:999
#define inverseRowUseScale_
Definition: AbcSimplex.hpp:384
double * scaleToExternal_
Scale from primal internal to external (in external order) Or other way for dual. ...
double reducedCost(int sequence)
Definition: AbcSimplex.hpp:702
double * costBasic() const
Definition: AbcSimplex.hpp:570
#define ABC_NUMBER_USEFUL
Useful arrays (all of row+column+2 length)
AbcPrimalColumnPivot * abcPrimalColumnPivot_
primal column pivot choice
int numberFlipped_
Dual Row Pivot Abstract Base Class.
double & lowerAddress(int sequence)
Return address of row or column lower bound.
Definition: AbcSimplex.hpp:712
void setColLower(int elementIndex, double elementValue)
Set a single column lower bound Use -DBL_MAX for -infinity.
Definition: AbcSimplex.hpp:921
int lastCleaned_
Last time cleaned up.
int lastFirstFree_
Last firstFree_.
double * solutionRegion(int which) const
Return region.
Definition: AbcSimplex.hpp:542
int swappedAlgorithm_
Nonzero (probably 10) if swapped algorithms.
int startOther_
Start of superBasic, free or awkward bounds variables.
This solves LPs using the simplex method.
Definition: ClpSimplex.hpp:55
int arrayForReplaceColumn_
void clearPivoted(int sequence)
Definition: AbcSimplex.hpp:805
double * abcPerturbation() const
Perturbation.
Definition: AbcSimplex.hpp:574
int firstFree() const
First Free_.
Definition: AbcSimplex.hpp:645
void setSequenceOut(int sequence)
Definition: AbcSimplex.hpp:614
double acceptablePivot() const
Acceptable pivot for this iteration.
Definition: AbcSimplex.hpp:278
bool flagged(int sequence) const
Definition: AbcSimplex.hpp:819
unsigned char * internalStatus() const
Definition: AbcSimplex.hpp:579
double & reducedCostAddress(int sequence)
Definition: AbcSimplex.hpp:705
void setUsedArray(int which) const
Say array going to be used.
Definition: AbcSimplex.hpp:777
int maximumAbcNumberRows_
Maximum number rows.
double * abcLower_
Working scaled copy of lower bounds has original scaled copy at end.
int arrayForDualColumn() const
Definition: AbcSimplex.hpp:466
double * costSaved_
Saved scaled copy of objective.
int arrayForBtran_
AbcMatrix * abcMatrix() const
Abc Matrix.
Definition: AbcSimplex.hpp:301
void clearFlagged(int sequence)
Definition: AbcSimplex.hpp:816
AbcSimplexProgress * abcProgress()
For dealing with all issues of cycling etc.
Definition: AbcSimplex.hpp:742
int ordinaryVariables_
Set to 1 if no free or super basic.
double lastDualBound_
Last dual bound.
double currentDualTolerance_
Current dualTolerance (will end up as dualTolerance_)
Definition: AbcSimplex.hpp:995
double currentDualBound_
Current dualBound (will end up as dualBound_)
Definition: AbcSimplex.hpp:997
double originalLower(int iSequence) const
Return original lower bound.
Definition: AbcSimplex.hpp:730
int arrayForFtran_
Objective function constant.
double originalUpper(int iSequence) const
Return original lower bound.
Definition: AbcSimplex.hpp:736
This is a tiny class where data can be saved round calls.
Definition: ClpModel.hpp:1267
int numberFreeNonBasic_
Number of free nonbasic variables.
int numberTotalWithoutFixed() const
Number of variables without fixed to zero (includes spare rows)
Definition: AbcSimplex.hpp:233
double * costRegion(int which) const
Definition: AbcSimplex.hpp:554
int startAtUpperOther_
Start of variables at upper bound with lower.
AbcSimplex * abcBaseModel_
Saved version of solution.
int arrayForBtran() const
Definition: AbcSimplex.hpp:477
AbcSimplexFactorization * abcFactorization_
factorization
int stateOfProblem_
int maximumAbcNumberRows() const
Maximum rows.
Definition: AbcSimplex.hpp:220
int normalDualColumnIteration_
Iteration at which to do relaxed dualColumn.
double upperTheta() const
upper theta from dual column
Definition: AbcSimplex.hpp:469
double * scaleFromExternal_
Points from external to internal.
int arrayForFtran() const
Definition: AbcSimplex.hpp:479
double objectiveOffset_
Objective offset (from offset_)
Definition: AbcSimplex.hpp:988
int maximumTotal() const
Definition: AbcSimplex.hpp:225
void setFakeBound(int sequence, FakeBound fakeBound)
Definition: AbcSimplex.hpp:793
int stateOfIteration_
Where we are in iteration.
double upper(int sequence)
Definition: AbcSimplex.hpp:715
double minimizationObjectiveValue() const
Gets objective value with all offsets but as for minimization.
Definition: AbcSimplex.hpp:262
double ftAlpha_
FT alpha.
double * djRegion() const
Definition: AbcSimplex.hpp:529
AbcTolerancesEtc & operator=(const AbcTolerancesEtc &rhs)
Assignment operator.
double * lowerBasic_
Working scaled copy of basic lower bounds.
AbcSimplex::Status getInternalColumnStatus(int sequence) const
Definition: AbcSimplex.hpp:584
int stateOfProblem() const
State of problem.
Definition: AbcSimplex.hpp:438
double * lowerSaved_
Saved scaled copy of lower bounds.
int arrayForDualColumn_
int numberTotal() const
Number of variables (includes spare rows)
Definition: AbcSimplex.hpp:230
double * rowScale2() const
corresponds to rowScale etc
Definition: AbcSimplex.hpp:458
double * upperBasic_
Working scaled copy of basic upper bounds.
double lastPrimalError_
Last primal error.
void clearArraysPublic(int which)
Clears an array and says available (-1 does all) when no possibility of going parallel.
Definition: AbcSimplex.hpp:747
void setObjCoeff(int elementIndex, double elementValue)
Set an objective function coefficient.
Definition: AbcSimplex.hpp:891
void setColUpper(int elementIndex, double elementValue)
Set a single column upper bound Use DBL_MAX for infinity.
Definition: AbcSimplex.hpp:926
double * inverseColumnUseScale_
use this instead of inverseColumnScale
int freeSequenceIn_
Free chosen vector.
double * djSaved_
Saved scaled dual solution.
double * tempArray_
Useful array of numberTotal length.
AbcMatrix * abcMatrix_
Working matrix.
double & upperAddress(int sequence)
Return address of row or column upper bound.
Definition: AbcSimplex.hpp:719
double * columnUseScale_
use this instead of columnScale
int * pivotVariable() const
Basic variables pivoting on which rows may be same as toExternal but may be as at invert...
Definition: AbcSimplex.hpp:434
#define AbcSimplex
void setSequenceIn(int sequence)
Set sequenceIn or Out.
Definition: AbcSimplex.hpp:611
bool pivoted(int sequence) const
Definition: AbcSimplex.hpp:808
int getAvailableArrayPublic() const
Returns first available empty array (and sets flag) when no possibility of going parallel.
Definition: AbcSimplex.hpp:751
#define COLUMN_LOWER_SAME
Definition: ClpModel.hpp:1207
double * djBasic_
Working scaled basic dual solution (want it to be zero)
double * abcPerturbation_
Perturbation (fixed) - is just scaled random numbers If perturbationFactor_<0 then virtual perturbati...
double * lowerRegion() const
Definition: AbcSimplex.hpp:532
int freeSequenceIn() const
Free chosen vector.
Definition: AbcSimplex.hpp:651
double * solutionBasic_
Working scaled basic primal solution.
double sumFakeInfeasibilities_
Sum of infeasibilities when using fake perturbation tolerance.
int ordinaryVariables() const
Set to 1 if no free or super basic.
Definition: AbcSimplex.hpp:281
double cost(int sequence)
Definition: AbcSimplex.hpp:722
int numberDisasters_
CoinPartitionedVector * usefulArray(int index)
Useful arrays (0,1,2,3,4,5,6,7)
Definition: AbcSimplex.hpp:236
double minimumThetaMovement_
Minimum theta movement.
double & costAddress(int sequence)
Return address of row or column cost.
Definition: AbcSimplex.hpp:726
void setPivoted(int sequence)
Definition: AbcSimplex.hpp:802
double * columnScale2() const
Definition: AbcSimplex.hpp:464
double * scaleFromExternal() const
Points from external to internal.
Definition: AbcSimplex.hpp:451
#define COLUMN_UPPER_SAME
Definition: ClpModel.hpp:1208
int sequenceOut() const
Definition: AbcSimplex.hpp:607
double * scaleToExternal() const
Scale from primal internal to external (in external order) Or other way for dual. ...
Definition: AbcSimplex.hpp:455
int numberTotal_
Number of variables (includes spare rows)
void setStateOfProblem(int value)
State of problem.
Definition: AbcSimplex.hpp:441
int startAtUpperNoOther_
Start of variables at upper bound with no lower.
AbcNonLinearCost * abcNonLinearCost_
Very wasteful way of dealing with infeasibilities in primal.
int numberTotalWithoutFixed_
Number of variables without fixed to zero (includes spare rows)
AbcDualRowPivot * dualRowPivot() const
dual row pivot choice
Definition: AbcSimplex.hpp:293
ClpSimplex * clpModel_
A copy of model as ClpSimplex with certain state.
int arrayForFlipBounds() const
Definition: AbcSimplex.hpp:473
double * djBasic() const
Definition: AbcSimplex.hpp:561
double currentDualBound() const
Current dualBound (will end up as dualBound_)
Definition: AbcSimplex.hpp:290
#define rowUseScale_
Definition: AbcSimplex.hpp:383
double * perturbationBasic_
basic perturbation
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...
Definition: AbcSimplex.hpp:663
double * perturbationSaved() const
Perturbation (fixed) - is just scaled random numbers.
Definition: AbcSimplex.hpp:275
int arrayForFlipRhs() const
Definition: AbcSimplex.hpp:475
AbcSimplex * baseModel() const
See if we have base model.
Definition: AbcSimplex.hpp:154
double * abcUpper_
Working scaled copy of upper bounds has original scaled copy at end.
double * lowerBasic() const
Definition: AbcSimplex.hpp:564
Status
enums for status of various sorts.
Definition: AbcSimplex.hpp:82
void unpack(CoinIndexedVector &rowArray) const
Unpacks one column of the matrix into indexed array Uses sequenceIn_.
Definition: AbcSimplex.hpp:353
int sequenceWithin(int sequence) const
Returns sequence number within section.
Definition: AbcSimplex.hpp:638
double lower(int sequence)
Definition: AbcSimplex.hpp:708
double * costBasic_
Working scaled copy of basic objective.
void setColSetBounds(const int *indexFirst, const int *indexLast, const double *boundList)
Set the bounds on a number of columns simultaneously
Definition: AbcSimplex.hpp:942
void setInternalColumnStatus(int sequence, AbcSimplex::Status newstatus)
Definition: AbcSimplex.hpp:592