1 /* $Id$ */ 2 // Copyright (C) 2008, 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 CbcHeuristicDive_H 7 #define CbcHeuristicDive_H 8 9 #include "CbcHeuristic.hpp" 10 class CbcSubProblem; 11 class OsiRowCut; 12 struct PseudoReducedCost { 13 int var; 14 double pseudoRedCost; 15 }; 16 17 /** Dive class 18 */ 19 20 class CbcHeuristicDive : public CbcHeuristic { 21 public: 22 // Default Constructor 23 CbcHeuristicDive(); 24 25 // Constructor with model - assumed before cuts 26 CbcHeuristicDive(CbcModel &model); 27 28 // Copy constructor 29 CbcHeuristicDive(const CbcHeuristicDive &); 30 31 // Destructor 32 ~CbcHeuristicDive(); 33 34 /// Clone 35 virtual CbcHeuristicDive *clone() const = 0; 36 37 /// Assignment operator 38 CbcHeuristicDive &operator=(const CbcHeuristicDive &rhs); 39 40 /// Create C++ lines to get to current state generateCpp(FILE *)41 virtual void generateCpp(FILE *) {} 42 43 /// Create C++ lines to get to current state - does work for base class 44 void generateCpp(FILE *fp, const char *heuristic); 45 46 /// Resets stuff if model changes 47 virtual void resetModel(CbcModel *model); 48 49 /// update model (This is needed if cliques update matrix etc) 50 virtual void setModel(CbcModel *model); 51 52 // REMLOVE using CbcHeuristic::solution ; 53 /** returns 0 if no solution, 1 if valid solution 54 with better objective value than one passed in 55 Sets solution values if good, sets objective value (only if good) 56 This is called after cuts have been added - so can not add cuts 57 This does Fractional Diving 58 */ 59 virtual int solution(double &objectiveValue, 60 double *newSolution); 61 /// inner part of dive 62 int solution(double &objectiveValue, int &numberNodes, 63 int &numberCuts, OsiRowCut **cuts, 64 CbcSubProblem **&nodes, 65 double *newSolution); 66 /** returns 0 if no solution, 1 if valid solution 67 with better objective value than one passed in 68 also returns list of nodes 69 This does Fractional Diving 70 */ 71 int fathom(CbcModel *model, int &numberNodes, CbcSubProblem **&nodes); 72 73 /// Validate model i.e. sets when_ to 0 if necessary (may be NULL) 74 virtual void validate(); 75 76 /// Sets priorities if any 77 void setPriorities(); 78 79 /// Select candidate binary variables for fixing 80 void selectBinaryVariables(); 81 82 /// Set percentage of integer variables to fix at bounds setPercentageToFix(double value)83 void setPercentageToFix(double value) 84 { 85 percentageToFix_ = value; 86 } 87 88 /// Set maximum number of iterations setMaxIterations(int value)89 void setMaxIterations(int value) 90 { 91 maxIterations_ = value; 92 } 93 94 /// Set maximum number of simplex iterations setMaxSimplexIterations(int value)95 void setMaxSimplexIterations(int value) 96 { 97 maxSimplexIterations_ = value; 98 } 99 /// Get maximum number of simplex iterations maxSimplexIterations() const100 inline int maxSimplexIterations() const 101 { 102 return maxSimplexIterations_; 103 } 104 105 /// Set maximum number of simplex iterations at root node setMaxSimplexIterationsAtRoot(int value)106 void setMaxSimplexIterationsAtRoot(int value) 107 { 108 maxSimplexIterationsAtRoot_ = value; 109 } 110 111 /// Set maximum time allowed setMaxTime(double value)112 void setMaxTime(double value) 113 { 114 maxTime_ = value; 115 } 116 117 /// Tests if the heuristic can run 118 virtual bool canHeuristicRun(); 119 120 /** Selects the next variable to branch on 121 Returns true if all the fractional variables can be trivially 122 rounded. Returns false, if there is at least one fractional variable 123 that is not trivially roundable. In this case, the bestColumn 124 returned will not be trivially roundable. 125 */ 126 virtual bool selectVariableToBranch(OsiSolverInterface *solver, 127 const double *newSolution, 128 int &bestColumn, 129 int &bestRound) 130 = 0; 131 /** Initializes any data which is going to be used repeatedly 132 in selectVariableToBranch */ initializeData()133 virtual void initializeData() {} 134 135 /// Perform reduced cost fixing on integer variables 136 int reducedCostFix(OsiSolverInterface *solver); 137 /// Fix other variables at bounds 138 virtual int fixOtherVariables(OsiSolverInterface *solver, 139 const double *solution, 140 PseudoReducedCost *candidate, 141 const double *random); 142 143 protected: 144 // Data 145 146 // Original matrix by column 147 CoinPackedMatrix matrix_; 148 149 // Original matrix by 150 CoinPackedMatrix matrixByRow_; 151 152 // Down locks 153 unsigned short *downLocks_; 154 155 // Up locks 156 unsigned short *upLocks_; 157 158 /// Extra down array (number Integers long) 159 double *downArray_; 160 161 /// Extra up array (number Integers long) 162 double *upArray_; 163 164 /// Array of priorities 165 typedef struct { 166 unsigned int direction : 3; // 0 bit off, 1 bit (0 down first, 1 up first) 2 bit non zero don't try other way 167 unsigned int priority : 29; 168 } PriorityType; 169 PriorityType *priority_; 170 // Indexes of binary variables with 0 objective coefficient 171 // and in variable bound constraints 172 std::vector< int > binVarIndex_; 173 174 // Indexes of variable bound rows for each binary variable 175 std::vector< int > vbRowIndex_; 176 177 // Percentage of integer variables to fix at bounds 178 double percentageToFix_; 179 180 // Maximum time allowed 181 double maxTime_; 182 183 // Small objective (i.e. treat zero objective as this) 184 double smallObjective_; 185 186 // Maximum number of major iterations 187 int maxIterations_; 188 189 // Maximum number of simplex iterations 190 int maxSimplexIterations_; 191 192 // Maximum number of simplex iterations at root node 193 int maxSimplexIterationsAtRoot_; 194 }; 195 #endif 196 197 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2 198 */ 199