[1271] | 1 | /* $Id: CbcHeuristic.hpp 1883 2013-04-06 13:33:15Z tkr $ */ |
---|
[2] | 2 | // Copyright (C) 2002, International Business Machines |
---|
| 3 | // Corporation and others. All Rights Reserved. |
---|
[1573] | 4 | // This code is licensed under the terms of the Eclipse Public License (EPL). |
---|
| 5 | |
---|
[2] | 6 | #ifndef CbcHeuristic_H |
---|
| 7 | #define CbcHeuristic_H |
---|
| 8 | |
---|
| 9 | #include <string> |
---|
| 10 | #include <vector> |
---|
| 11 | #include "CoinPackedMatrix.hpp" |
---|
| 12 | #include "OsiCuts.hpp" |
---|
[841] | 13 | #include "CoinHelperFunctions.hpp" |
---|
[912] | 14 | #include "OsiBranchingObject.hpp" |
---|
[2] | 15 | |
---|
| 16 | class OsiSolverInterface; |
---|
| 17 | |
---|
| 18 | class CbcModel; |
---|
| 19 | |
---|
| 20 | //############################################################################# |
---|
[912] | 21 | |
---|
| 22 | class CbcHeuristicNodeList; |
---|
| 23 | class CbcBranchingObject; |
---|
| 24 | |
---|
| 25 | /** A class describing the branching decisions that were made to get |
---|
[1505] | 26 | to the node where a heuristic was invoked from */ |
---|
[912] | 27 | |
---|
| 28 | class CbcHeuristicNode { |
---|
| 29 | private: |
---|
[1286] | 30 | void gutsOfConstructor(CbcModel& model); |
---|
| 31 | CbcHeuristicNode(); |
---|
| 32 | CbcHeuristicNode& operator=(const CbcHeuristicNode&); |
---|
[912] | 33 | private: |
---|
[1286] | 34 | /// The number of branching decisions made |
---|
| 35 | int numObjects_; |
---|
| 36 | /** The indices of the branching objects. Note: an index may be |
---|
| 37 | listed multiple times. E.g., a general integer variable that has |
---|
| 38 | been branched on multiple times. */ |
---|
| 39 | CbcBranchingObject** brObj_; |
---|
[912] | 40 | public: |
---|
[1286] | 41 | CbcHeuristicNode(CbcModel& model); |
---|
[912] | 42 | |
---|
[1286] | 43 | CbcHeuristicNode(const CbcHeuristicNode& rhs); |
---|
| 44 | ~CbcHeuristicNode(); |
---|
| 45 | double distance(const CbcHeuristicNode* node) const; |
---|
| 46 | double minDistance(const CbcHeuristicNodeList& nodeList) const; |
---|
| 47 | bool minDistanceIsSmall(const CbcHeuristicNodeList& nodeList, |
---|
| 48 | const double threshold) const; |
---|
| 49 | double avgDistance(const CbcHeuristicNodeList& nodeList) const; |
---|
[912] | 50 | }; |
---|
| 51 | |
---|
| 52 | class CbcHeuristicNodeList { |
---|
| 53 | private: |
---|
[1286] | 54 | void gutsOfDelete(); |
---|
| 55 | void gutsOfCopy(const CbcHeuristicNodeList& rhs); |
---|
[912] | 56 | private: |
---|
[1286] | 57 | std::vector<CbcHeuristicNode*> nodes_; |
---|
[912] | 58 | public: |
---|
[1286] | 59 | CbcHeuristicNodeList() {} |
---|
| 60 | CbcHeuristicNodeList(const CbcHeuristicNodeList& rhs); |
---|
| 61 | CbcHeuristicNodeList& operator=(const CbcHeuristicNodeList& rhs); |
---|
| 62 | ~CbcHeuristicNodeList(); |
---|
| 63 | |
---|
| 64 | void append(CbcHeuristicNode*& node); |
---|
| 65 | void append(const CbcHeuristicNodeList& nodes); |
---|
| 66 | inline const CbcHeuristicNode* node(int i) const { |
---|
| 67 | return nodes_[i]; |
---|
| 68 | } |
---|
| 69 | inline int size() const { |
---|
[1505] | 70 | return static_cast<int>(nodes_.size()); |
---|
[1286] | 71 | } |
---|
[912] | 72 | }; |
---|
| 73 | |
---|
| 74 | //############################################################################# |
---|
[2] | 75 | /** Heuristic base class */ |
---|
| 76 | |
---|
| 77 | class CbcHeuristic { |
---|
[912] | 78 | private: |
---|
[1286] | 79 | void gutsOfDelete() {} |
---|
| 80 | void gutsOfCopy(const CbcHeuristic & rhs); |
---|
[912] | 81 | |
---|
[2] | 82 | public: |
---|
[1286] | 83 | // Default Constructor |
---|
| 84 | CbcHeuristic (); |
---|
[2] | 85 | |
---|
[1286] | 86 | // Constructor with model - assumed before cuts |
---|
| 87 | CbcHeuristic (CbcModel & model); |
---|
[2] | 88 | |
---|
[1286] | 89 | // Copy constructor |
---|
| 90 | CbcHeuristic ( const CbcHeuristic &); |
---|
[2] | 91 | |
---|
[1286] | 92 | virtual ~CbcHeuristic(); |
---|
[640] | 93 | |
---|
[1286] | 94 | /// Clone |
---|
| 95 | virtual CbcHeuristic * clone() const = 0; |
---|
[640] | 96 | |
---|
[1286] | 97 | /// Assignment operator |
---|
| 98 | CbcHeuristic & operator=(const CbcHeuristic& rhs); |
---|
[6] | 99 | |
---|
[1286] | 100 | /// update model (This is needed if cliques update matrix etc) |
---|
| 101 | virtual void setModel(CbcModel * model); |
---|
[2] | 102 | |
---|
[1286] | 103 | /// Resets stuff if model changes |
---|
| 104 | virtual void resetModel(CbcModel * model) = 0; |
---|
[2] | 105 | |
---|
[1286] | 106 | /** returns 0 if no solution, 1 if valid solution |
---|
| 107 | with better objective value than one passed in |
---|
| 108 | Sets solution values if good, sets objective value |
---|
| 109 | This is called after cuts have been added - so can not add cuts |
---|
| 110 | */ |
---|
| 111 | virtual int solution(double & objectiveValue, |
---|
| 112 | double * newSolution) = 0; |
---|
[72] | 113 | |
---|
[1286] | 114 | /** returns 0 if no solution, 1 if valid solution, -1 if just |
---|
| 115 | returning an estimate of best possible solution |
---|
| 116 | with better objective value than one passed in |
---|
| 117 | Sets solution values if good, sets objective value (only if nonzero code) |
---|
| 118 | This is called at same time as cut generators - so can add cuts |
---|
| 119 | Default is do nothing |
---|
| 120 | */ |
---|
| 121 | virtual int solution2(double & /*objectiveValue*/, |
---|
| 122 | double * /*newSolution*/, |
---|
| 123 | OsiCuts & /*cs*/) { |
---|
| 124 | return 0; |
---|
| 125 | } |
---|
[2] | 126 | |
---|
[1286] | 127 | /// Validate model i.e. sets when_ to 0 if necessary (may be NULL) |
---|
| 128 | virtual void validate() {} |
---|
[640] | 129 | |
---|
[1286] | 130 | /** Sets "when" flag - 0 off, 1 at root, 2 other than root, 3 always. |
---|
| 131 | If 10 added then don't worry if validate says there are funny objects |
---|
| 132 | as user knows it will be fine |
---|
| 133 | */ |
---|
| 134 | inline void setWhen(int value) { |
---|
| 135 | when_ = value; |
---|
| 136 | } |
---|
| 137 | /// Gets "when" flag - 0 off, 1 at root, 2 other than root, 3 always |
---|
| 138 | inline int when() const { |
---|
| 139 | return when_; |
---|
| 140 | } |
---|
[640] | 141 | |
---|
[1286] | 142 | /// Sets number of nodes in subtree (default 200) |
---|
| 143 | inline void setNumberNodes(int value) { |
---|
| 144 | numberNodes_ = value; |
---|
| 145 | } |
---|
| 146 | /// Gets number of nodes in a subtree (default 200) |
---|
| 147 | inline int numberNodes() const { |
---|
| 148 | return numberNodes_; |
---|
| 149 | } |
---|
| 150 | /** Switches (does not apply equally to all heuristics) |
---|
| 151 | 1 bit - stop once allowable gap on objective reached |
---|
| 152 | 2 bit - always do given number of passes |
---|
| 153 | 4 bit - weaken cutoff by 5% every 50 passes? |
---|
| 154 | 8 bit - if has cutoff and suminf bobbling for 20 passes then |
---|
| 155 | first try halving distance to best possible then |
---|
| 156 | try keep halving distance to known cutoff |
---|
[1802] | 157 | 16 bit - needs new solution to run |
---|
[1286] | 158 | 1024 bit - stop all heuristics on max time |
---|
| 159 | */ |
---|
| 160 | inline void setSwitches(int value) { |
---|
| 161 | switches_ = value; |
---|
| 162 | } |
---|
| 163 | /** Switches (does not apply equally to all heuristics) |
---|
| 164 | 1 bit - stop once allowable gap on objective reached |
---|
| 165 | 2 bit - always do given number of passes |
---|
| 166 | 4 bit - weaken cutoff by 5% every 50 passes? |
---|
| 167 | 8 bit - if has cutoff and suminf bobbling for 20 passes then |
---|
| 168 | first try halving distance to best possible then |
---|
| 169 | try keep halving distance to known cutoff |
---|
[1802] | 170 | 16 bit - needs new solution to run |
---|
[1286] | 171 | 1024 bit - stop all heuristics on max time |
---|
| 172 | */ |
---|
| 173 | inline int switches() const { |
---|
| 174 | return switches_; |
---|
| 175 | } |
---|
| 176 | /// Whether to exit at once on gap |
---|
| 177 | bool exitNow(double bestObjective) const; |
---|
| 178 | /// Sets feasibility pump options (-1 is off) |
---|
| 179 | inline void setFeasibilityPumpOptions(int value) { |
---|
| 180 | feasibilityPumpOptions_ = value; |
---|
| 181 | } |
---|
| 182 | /// Gets feasibility pump options (-1 is off) |
---|
| 183 | inline int feasibilityPumpOptions() const { |
---|
| 184 | return feasibilityPumpOptions_; |
---|
| 185 | } |
---|
| 186 | /// Just set model - do not do anything else |
---|
| 187 | inline void setModelOnly(CbcModel * model) { |
---|
| 188 | model_ = model; |
---|
| 189 | } |
---|
[197] | 190 | |
---|
[912] | 191 | |
---|
[1286] | 192 | /// Sets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1.0) |
---|
| 193 | inline void setFractionSmall(double value) { |
---|
| 194 | fractionSmall_ = value; |
---|
| 195 | } |
---|
| 196 | /// Gets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1.0) |
---|
| 197 | inline double fractionSmall() const { |
---|
| 198 | return fractionSmall_; |
---|
| 199 | } |
---|
| 200 | /// Get how many solutions the heuristic thought it got |
---|
| 201 | inline int numberSolutionsFound() const { |
---|
| 202 | return numberSolutionsFound_; |
---|
| 203 | } |
---|
| 204 | /// Increment how many solutions the heuristic thought it got |
---|
| 205 | inline void incrementNumberSolutionsFound() { |
---|
| 206 | numberSolutionsFound_++; |
---|
| 207 | } |
---|
| 208 | |
---|
| 209 | /** Do mini branch and bound - return |
---|
| 210 | 0 not finished - no solution |
---|
| 211 | 1 not finished - solution |
---|
| 212 | 2 finished - no solution |
---|
| 213 | 3 finished - solution |
---|
| 214 | (could add global cut if finished) |
---|
| 215 | -1 returned on size |
---|
| 216 | -2 time or user event |
---|
| 217 | */ |
---|
| 218 | int smallBranchAndBound(OsiSolverInterface * solver, int numberNodes, |
---|
| 219 | double * newSolution, double & newSolutionValue, |
---|
| 220 | double cutoff , std::string name) const; |
---|
| 221 | /// Create C++ lines to get to current state |
---|
| 222 | virtual void generateCpp( FILE * ) {} |
---|
| 223 | /// Create C++ lines to get to current state - does work for base class |
---|
| 224 | void generateCpp( FILE * fp, const char * heuristic) ; |
---|
| 225 | /// Returns true if can deal with "odd" problems e.g. sos type 2 |
---|
| 226 | virtual bool canDealWithOdd() const { |
---|
| 227 | return false; |
---|
| 228 | } |
---|
| 229 | /// return name of heuristic |
---|
| 230 | inline const char *heuristicName() const { |
---|
| 231 | return heuristicName_.c_str(); |
---|
| 232 | } |
---|
| 233 | /// set name of heuristic |
---|
| 234 | inline void setHeuristicName(const char *name) { |
---|
| 235 | heuristicName_ = name; |
---|
| 236 | } |
---|
| 237 | /// Set random number generator seed |
---|
| 238 | void setSeed(int value); |
---|
[1883] | 239 | /// Get random number generator seed |
---|
| 240 | int getSeed() const; |
---|
[1286] | 241 | /// Sets decay factor (for howOften) on failure |
---|
| 242 | inline void setDecayFactor(double value) { |
---|
| 243 | decayFactor_ = value; |
---|
| 244 | } |
---|
| 245 | /// Set input solution |
---|
| 246 | void setInputSolution(const double * solution, double objValue); |
---|
| 247 | /* Runs if bit set |
---|
| 248 | 0 - before cuts at root node (or from doHeuristics) |
---|
| 249 | 1 - during cuts at root |
---|
| 250 | 2 - after root node cuts |
---|
| 251 | 3 - after cuts at other nodes |
---|
| 252 | 4 - during cuts at other nodes |
---|
| 253 | 8 added if previous heuristic in loop found solution |
---|
| 254 | */ |
---|
| 255 | inline void setWhereFrom(int value) { |
---|
| 256 | whereFrom_ = value; |
---|
| 257 | } |
---|
[1564] | 258 | inline int whereFrom() const { |
---|
| 259 | return whereFrom_; |
---|
| 260 | } |
---|
[1286] | 261 | /** Upto this depth we call the tree shallow and the heuristic can be called |
---|
| 262 | multiple times. That is, the test whether the current node is far from |
---|
| 263 | the others where the jeuristic was invoked will not be done, only the |
---|
| 264 | frequency will be tested. After that depth the heuristic will can be |
---|
| 265 | invoked only once per node, right before branching. That's when it'll be |
---|
| 266 | tested whether the heur should run at all. */ |
---|
| 267 | inline void setShallowDepth(int value) { |
---|
| 268 | shallowDepth_ = value; |
---|
| 269 | } |
---|
| 270 | /** How often to invoke the heuristics in the shallow part of the tree */ |
---|
| 271 | inline void setHowOftenShallow(int value) { |
---|
| 272 | howOftenShallow_ = value; |
---|
| 273 | } |
---|
| 274 | /** How "far" should this node be from every other where the heuristic was |
---|
| 275 | run in order to allow the heuristic to run in this node, too. Currently |
---|
| 276 | this is tested, but we may switch to avgDistanceToRun_ in the future. */ |
---|
| 277 | inline void setMinDistanceToRun(int value) { |
---|
| 278 | minDistanceToRun_ = value; |
---|
| 279 | } |
---|
| 280 | |
---|
| 281 | /** Check whether the heuristic should run at all |
---|
| 282 | 0 - before cuts at root node (or from doHeuristics) |
---|
| 283 | 1 - during cuts at root |
---|
| 284 | 2 - after root node cuts |
---|
| 285 | 3 - after cuts at other nodes |
---|
| 286 | 4 - during cuts at other nodes |
---|
| 287 | 8 added if previous heuristic in loop found solution |
---|
| 288 | */ |
---|
| 289 | virtual bool shouldHeurRun(int whereFrom); |
---|
| 290 | /** Check whether the heuristic should run this time */ |
---|
| 291 | bool shouldHeurRun_randomChoice(); |
---|
| 292 | void debugNodes(); |
---|
| 293 | void printDistanceToNodes(); |
---|
| 294 | /// how many times the heuristic has actually run |
---|
| 295 | inline int numRuns() const { |
---|
| 296 | return numRuns_; |
---|
| 297 | } |
---|
| 298 | |
---|
| 299 | /// How many times the heuristic could run |
---|
| 300 | inline int numCouldRun() const { |
---|
| 301 | return numCouldRun_; |
---|
| 302 | } |
---|
[1600] | 303 | /*! \brief Clone, but ... |
---|
| 304 | |
---|
| 305 | If type is |
---|
| 306 | - 0 clone the solver for the model, |
---|
| 307 | - 1 clone the continuous solver for the model |
---|
| 308 | - Add 2 to say without integer variables which are at low priority |
---|
| 309 | - Add 4 to say quite likely infeasible so give up easily (clp only). |
---|
| 310 | */ |
---|
[1286] | 311 | OsiSolverInterface * cloneBut(int type); |
---|
[2] | 312 | protected: |
---|
| 313 | |
---|
[1286] | 314 | /// Model |
---|
| 315 | CbcModel * model_; |
---|
| 316 | /// When flag - 0 off, 1 at root, 2 other than root, 3 always |
---|
| 317 | int when_; |
---|
| 318 | /// Number of nodes in any sub tree |
---|
| 319 | int numberNodes_; |
---|
[1802] | 320 | /** Feasibility pump options , -1 is off |
---|
| 321 | >=0 for feasibility pump itself |
---|
| 322 | -2 quick proximity search |
---|
| 323 | -3 longer proximity search |
---|
| 324 | */ |
---|
[1286] | 325 | int feasibilityPumpOptions_; |
---|
| 326 | /// Fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound |
---|
| 327 | mutable double fractionSmall_; |
---|
| 328 | /// Thread specific random number generator |
---|
| 329 | CoinThreadRandom randomNumberGenerator_; |
---|
| 330 | /// Name for printing |
---|
| 331 | std::string heuristicName_; |
---|
[912] | 332 | |
---|
[1286] | 333 | /// How often to do (code can change) |
---|
| 334 | int howOften_; |
---|
| 335 | /// How much to increase how often |
---|
| 336 | double decayFactor_; |
---|
| 337 | /** Switches (does not apply equally to all heuristics) |
---|
| 338 | 1 bit - stop once allowable gap on objective reached |
---|
| 339 | 2 bit - always do given number of passes |
---|
| 340 | 4 bit - weaken cutoff by 5% every 50 passes? |
---|
| 341 | 8 bit - if has cutoff and suminf bobbling for 20 passes then |
---|
| 342 | first try halving distance to best possible then |
---|
| 343 | try keep halving distance to known cutoff |
---|
[1802] | 344 | 16 bit - needs new solution to run |
---|
[1286] | 345 | 1024 bit - stop all heuristics on max time |
---|
| 346 | */ |
---|
| 347 | mutable int switches_; |
---|
| 348 | /* Runs if bit set |
---|
| 349 | 0 - before cuts at root node (or from doHeuristics) |
---|
| 350 | 1 - during cuts at root |
---|
| 351 | 2 - after root node cuts |
---|
| 352 | 3 - after cuts at other nodes |
---|
| 353 | 4 - during cuts at other nodes |
---|
| 354 | 8 added if previous heuristic in loop found solution |
---|
| 355 | */ |
---|
| 356 | int whereFrom_; |
---|
| 357 | /** Upto this depth we call the tree shallow and the heuristic can be called |
---|
| 358 | multiple times. That is, the test whether the current node is far from |
---|
| 359 | the others where the jeuristic was invoked will not be done, only the |
---|
| 360 | frequency will be tested. After that depth the heuristic will can be |
---|
| 361 | invoked only once per node, right before branching. That's when it'll be |
---|
| 362 | tested whether the heur should run at all. */ |
---|
| 363 | int shallowDepth_; |
---|
| 364 | /** How often to invoke the heuristics in the shallow part of the tree */ |
---|
| 365 | int howOftenShallow_; |
---|
| 366 | /** How many invocations happened within the same node when in a shallow |
---|
| 367 | part of the tree. */ |
---|
| 368 | int numInvocationsInShallow_; |
---|
| 369 | /** How many invocations happened when in the deep part of the tree. For |
---|
| 370 | every node we count only one invocation. */ |
---|
| 371 | int numInvocationsInDeep_; |
---|
| 372 | /** After how many deep invocations was the heuristic run last time */ |
---|
| 373 | int lastRunDeep_; |
---|
| 374 | /// how many times the heuristic has actually run |
---|
| 375 | int numRuns_; |
---|
| 376 | /** How "far" should this node be from every other where the heuristic was |
---|
| 377 | run in order to allow the heuristic to run in this node, too. Currently |
---|
| 378 | this is tested, but we may switch to avgDistanceToRun_ in the future. */ |
---|
| 379 | int minDistanceToRun_; |
---|
[912] | 380 | |
---|
[1286] | 381 | /// The description of the nodes where this heuristic has been applied |
---|
| 382 | CbcHeuristicNodeList runNodes_; |
---|
[912] | 383 | |
---|
[1286] | 384 | /// How many times the heuristic could run |
---|
| 385 | int numCouldRun_; |
---|
[912] | 386 | |
---|
[1286] | 387 | /// How many solutions the heuristic thought it got |
---|
| 388 | int numberSolutionsFound_; |
---|
[912] | 389 | |
---|
[1822] | 390 | /// How many nodes the heuristic did this go |
---|
| 391 | mutable int numberNodesDone_; |
---|
| 392 | |
---|
[1286] | 393 | // Input solution - so can be used as seed |
---|
| 394 | double * inputSolution_; |
---|
[931] | 395 | |
---|
[940] | 396 | |
---|
[1393] | 397 | #ifdef JJF_ZERO |
---|
[1286] | 398 | /// Lower bounds of last node where the heuristic found a solution |
---|
| 399 | double * lowerBoundLastNode_; |
---|
| 400 | /// Upper bounds of last node where the heuristic found a solution |
---|
| 401 | double * upperBoundLastNode_; |
---|
[912] | 402 | #endif |
---|
[2] | 403 | }; |
---|
| 404 | /** Rounding class |
---|
| 405 | */ |
---|
| 406 | |
---|
| 407 | class CbcRounding : public CbcHeuristic { |
---|
| 408 | public: |
---|
| 409 | |
---|
[1286] | 410 | // Default Constructor |
---|
| 411 | CbcRounding (); |
---|
[2] | 412 | |
---|
[1286] | 413 | // Constructor with model - assumed before cuts |
---|
| 414 | CbcRounding (CbcModel & model); |
---|
[640] | 415 | |
---|
[1286] | 416 | // Copy constructor |
---|
| 417 | CbcRounding ( const CbcRounding &); |
---|
[2] | 418 | |
---|
[1286] | 419 | // Destructor |
---|
| 420 | ~CbcRounding (); |
---|
[6] | 421 | |
---|
[1286] | 422 | /// Assignment operator |
---|
| 423 | CbcRounding & operator=(const CbcRounding& rhs); |
---|
[2] | 424 | |
---|
[1286] | 425 | /// Clone |
---|
| 426 | virtual CbcHeuristic * clone() const; |
---|
| 427 | /// Create C++ lines to get to current state |
---|
| 428 | virtual void generateCpp( FILE * fp) ; |
---|
[2] | 429 | |
---|
[1286] | 430 | /// Resets stuff if model changes |
---|
| 431 | virtual void resetModel(CbcModel * model); |
---|
[2] | 432 | |
---|
[1286] | 433 | /// update model (This is needed if cliques update matrix etc) |
---|
| 434 | virtual void setModel(CbcModel * model); |
---|
| 435 | |
---|
| 436 | using CbcHeuristic::solution ; |
---|
| 437 | /** returns 0 if no solution, 1 if valid solution |
---|
| 438 | with better objective value than one passed in |
---|
| 439 | Sets solution values if good, sets objective value (only if good) |
---|
| 440 | This is called after cuts have been added - so can not add cuts |
---|
| 441 | */ |
---|
| 442 | virtual int solution(double & objectiveValue, |
---|
| 443 | double * newSolution); |
---|
| 444 | /** returns 0 if no solution, 1 if valid solution |
---|
| 445 | with better objective value than one passed in |
---|
| 446 | Sets solution values if good, sets objective value (only if good) |
---|
| 447 | This is called after cuts have been added - so can not add cuts |
---|
| 448 | Use solutionValue rather than solvers one |
---|
| 449 | */ |
---|
| 450 | virtual int solution(double & objectiveValue, |
---|
| 451 | double * newSolution, |
---|
| 452 | double solutionValue); |
---|
| 453 | /// Validate model i.e. sets when_ to 0 if necessary (may be NULL) |
---|
| 454 | virtual void validate(); |
---|
| 455 | |
---|
| 456 | |
---|
| 457 | /// Set seed |
---|
| 458 | void setSeed(int value) { |
---|
| 459 | seed_ = value; |
---|
| 460 | } |
---|
| 461 | |
---|
[2] | 462 | protected: |
---|
[1286] | 463 | // Data |
---|
[2] | 464 | |
---|
[1286] | 465 | // Original matrix by column |
---|
| 466 | CoinPackedMatrix matrix_; |
---|
[2] | 467 | |
---|
[1286] | 468 | // Original matrix by |
---|
| 469 | CoinPackedMatrix matrixByRow_; |
---|
[2] | 470 | |
---|
[1286] | 471 | // Down locks |
---|
| 472 | unsigned short * down_; |
---|
[838] | 473 | |
---|
[1286] | 474 | // Up locks |
---|
| 475 | unsigned short * up_; |
---|
[838] | 476 | |
---|
[1286] | 477 | // Equality locks |
---|
| 478 | unsigned short * equal_; |
---|
[838] | 479 | |
---|
[1286] | 480 | // Seed for random stuff |
---|
| 481 | int seed_; |
---|
[2] | 482 | }; |
---|
| 483 | |
---|
[854] | 484 | /** Partial solution class |
---|
| 485 | If user knows a partial solution this tries to get an integer solution |
---|
| 486 | it uses hotstart information |
---|
| 487 | */ |
---|
| 488 | |
---|
| 489 | class CbcHeuristicPartial : public CbcHeuristic { |
---|
| 490 | public: |
---|
| 491 | |
---|
[1286] | 492 | // Default Constructor |
---|
| 493 | CbcHeuristicPartial (); |
---|
[854] | 494 | |
---|
[1286] | 495 | /** Constructor with model - assumed before cuts |
---|
| 496 | Fixes all variables with priority <= given |
---|
| 497 | and does given number of nodes |
---|
| 498 | */ |
---|
| 499 | CbcHeuristicPartial (CbcModel & model, int fixPriority = 10000, int numberNodes = 200); |
---|
[854] | 500 | |
---|
[1286] | 501 | // Copy constructor |
---|
| 502 | CbcHeuristicPartial ( const CbcHeuristicPartial &); |
---|
[854] | 503 | |
---|
[1286] | 504 | // Destructor |
---|
| 505 | ~CbcHeuristicPartial (); |
---|
[854] | 506 | |
---|
[1286] | 507 | /// Assignment operator |
---|
| 508 | CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs); |
---|
[854] | 509 | |
---|
[1286] | 510 | /// Clone |
---|
| 511 | virtual CbcHeuristic * clone() const; |
---|
| 512 | /// Create C++ lines to get to current state |
---|
| 513 | virtual void generateCpp( FILE * fp) ; |
---|
[854] | 514 | |
---|
[1286] | 515 | /// Resets stuff if model changes |
---|
| 516 | virtual void resetModel(CbcModel * model); |
---|
[854] | 517 | |
---|
[1286] | 518 | /// update model (This is needed if cliques update matrix etc) |
---|
| 519 | virtual void setModel(CbcModel * model); |
---|
[1013] | 520 | |
---|
[1286] | 521 | using CbcHeuristic::solution ; |
---|
| 522 | /** returns 0 if no solution, 1 if valid solution |
---|
| 523 | with better objective value than one passed in |
---|
| 524 | Sets solution values if good, sets objective value (only if good) |
---|
| 525 | This is called after cuts have been added - so can not add cuts |
---|
| 526 | */ |
---|
| 527 | virtual int solution(double & objectiveValue, |
---|
| 528 | double * newSolution); |
---|
| 529 | /// Validate model i.e. sets when_ to 0 if necessary (may be NULL) |
---|
| 530 | virtual void validate(); |
---|
| 531 | |
---|
| 532 | |
---|
| 533 | /// Set priority level |
---|
| 534 | void setFixPriority(int value) { |
---|
| 535 | fixPriority_ = value; |
---|
| 536 | } |
---|
| 537 | |
---|
| 538 | /** Check whether the heuristic should run at all */ |
---|
| 539 | virtual bool shouldHeurRun(int whereFrom); |
---|
| 540 | |
---|
[854] | 541 | protected: |
---|
[1286] | 542 | // Data |
---|
[854] | 543 | |
---|
[1286] | 544 | // All variables with abs priority <= this will be fixed |
---|
| 545 | int fixPriority_; |
---|
[854] | 546 | }; |
---|
| 547 | |
---|
[264] | 548 | /** heuristic - just picks up any good solution |
---|
| 549 | found by solver - see OsiBabSolver |
---|
| 550 | */ |
---|
[2] | 551 | |
---|
[264] | 552 | class CbcSerendipity : public CbcHeuristic { |
---|
| 553 | public: |
---|
| 554 | |
---|
[1286] | 555 | // Default Constructor |
---|
| 556 | CbcSerendipity (); |
---|
[264] | 557 | |
---|
[1286] | 558 | /* Constructor with model |
---|
| 559 | */ |
---|
| 560 | CbcSerendipity (CbcModel & model); |
---|
[640] | 561 | |
---|
[1286] | 562 | // Copy constructor |
---|
| 563 | CbcSerendipity ( const CbcSerendipity &); |
---|
[264] | 564 | |
---|
[1286] | 565 | // Destructor |
---|
| 566 | ~CbcSerendipity (); |
---|
[264] | 567 | |
---|
[1286] | 568 | /// Assignment operator |
---|
| 569 | CbcSerendipity & operator=(const CbcSerendipity& rhs); |
---|
[264] | 570 | |
---|
[1286] | 571 | /// Clone |
---|
| 572 | virtual CbcHeuristic * clone() const; |
---|
| 573 | /// Create C++ lines to get to current state |
---|
| 574 | virtual void generateCpp( FILE * fp) ; |
---|
| 575 | |
---|
| 576 | /// update model |
---|
| 577 | virtual void setModel(CbcModel * model); |
---|
| 578 | |
---|
| 579 | using CbcHeuristic::solution ; |
---|
| 580 | /** returns 0 if no solution, 1 if valid solution. |
---|
| 581 | Sets solution values if good, sets objective value (only if good) |
---|
| 582 | We leave all variables which are at one at this node of the |
---|
| 583 | tree to that value and will |
---|
| 584 | initially set all others to zero. We then sort all variables in order of their cost |
---|
| 585 | divided by the number of entries in rows which are not yet covered. We randomize that |
---|
| 586 | value a bit so that ties will be broken in different ways on different runs of the heuristic. |
---|
| 587 | We then choose the best one and set it to one and repeat the exercise. |
---|
| 588 | |
---|
| 589 | */ |
---|
| 590 | virtual int solution(double & objectiveValue, |
---|
| 591 | double * newSolution); |
---|
| 592 | /// Resets stuff if model changes |
---|
| 593 | virtual void resetModel(CbcModel * model); |
---|
| 594 | |
---|
[264] | 595 | protected: |
---|
| 596 | }; |
---|
| 597 | |
---|
[961] | 598 | /** Just One class - this chooses one at random |
---|
| 599 | */ |
---|
| 600 | |
---|
| 601 | class CbcHeuristicJustOne : public CbcHeuristic { |
---|
| 602 | public: |
---|
| 603 | |
---|
[1286] | 604 | // Default Constructor |
---|
| 605 | CbcHeuristicJustOne (); |
---|
[961] | 606 | |
---|
[1286] | 607 | // Constructor with model - assumed before cuts |
---|
| 608 | CbcHeuristicJustOne (CbcModel & model); |
---|
[961] | 609 | |
---|
[1286] | 610 | // Copy constructor |
---|
| 611 | CbcHeuristicJustOne ( const CbcHeuristicJustOne &); |
---|
[961] | 612 | |
---|
[1286] | 613 | // Destructor |
---|
| 614 | ~CbcHeuristicJustOne (); |
---|
[961] | 615 | |
---|
[1286] | 616 | /// Clone |
---|
| 617 | virtual CbcHeuristicJustOne * clone() const; |
---|
[961] | 618 | |
---|
[1286] | 619 | /// Assignment operator |
---|
| 620 | CbcHeuristicJustOne & operator=(const CbcHeuristicJustOne& rhs); |
---|
| 621 | |
---|
| 622 | /// Create C++ lines to get to current state |
---|
| 623 | virtual void generateCpp( FILE * fp) ; |
---|
| 624 | |
---|
| 625 | /** returns 0 if no solution, 1 if valid solution |
---|
| 626 | with better objective value than one passed in |
---|
| 627 | Sets solution values if good, sets objective value (only if good) |
---|
| 628 | This is called after cuts have been added - so can not add cuts |
---|
| 629 | This does Fractional Diving |
---|
| 630 | */ |
---|
| 631 | virtual int solution(double & objectiveValue, |
---|
| 632 | double * newSolution); |
---|
| 633 | /// Resets stuff if model changes |
---|
| 634 | virtual void resetModel(CbcModel * model); |
---|
| 635 | |
---|
| 636 | /// update model (This is needed if cliques update matrix etc) |
---|
| 637 | virtual void setModel(CbcModel * model); |
---|
| 638 | /// Selects the next variable to branch on |
---|
| 639 | /** Returns true if all the fractional variables can be trivially |
---|
| 640 | rounded. Returns false, if there is at least one fractional variable |
---|
| 641 | that is not trivially roundable. In this case, the bestColumn |
---|
| 642 | returned will not be trivially roundable. |
---|
| 643 | This is dummy as never called |
---|
| 644 | */ |
---|
| 645 | virtual bool selectVariableToBranch(OsiSolverInterface* /*solver*/, |
---|
| 646 | const double* /*newSolution*/, |
---|
| 647 | int& /*bestColumn*/, |
---|
| 648 | int& /*bestRound*/) { |
---|
| 649 | return true; |
---|
| 650 | } |
---|
| 651 | /// Validate model i.e. sets when_ to 0 if necessary (may be NULL) |
---|
| 652 | virtual void validate(); |
---|
| 653 | /// Adds an heuristic with probability |
---|
| 654 | void addHeuristic(const CbcHeuristic * heuristic, double probability); |
---|
| 655 | /// Normalize probabilities |
---|
| 656 | void normalizeProbabilities(); |
---|
[961] | 657 | protected: |
---|
[1286] | 658 | // Data |
---|
[961] | 659 | |
---|
[1286] | 660 | // Probability of running a heuristic |
---|
| 661 | double * probabilities_; |
---|
[961] | 662 | |
---|
[1286] | 663 | // Heuristics |
---|
| 664 | CbcHeuristic ** heuristic_; |
---|
[961] | 665 | |
---|
[1286] | 666 | // Number of heuristics |
---|
| 667 | int numberHeuristics_; |
---|
[961] | 668 | |
---|
| 669 | }; |
---|
| 670 | |
---|
[2] | 671 | #endif |
---|
[1432] | 672 | |
---|