CbcHeuristic.hpp
Go to the documentation of this file.
1 /* $Id: CbcHeuristic.hpp 1432 2010-02-07 19:33:53Z bjarni $ */
2 // Copyright (C) 2002, International Business Machines
3 // Corporation and others. All Rights Reserved.
4 #ifndef CbcHeuristic_H
5 #define CbcHeuristic_H
6 
7 #include <string>
8 #include <vector>
9 #include "CoinPackedMatrix.hpp"
10 #include "OsiCuts.hpp"
11 #include "CoinHelperFunctions.hpp"
12 #include "OsiBranchingObject.hpp"
13 
14 class OsiSolverInterface;
15 
16 class CbcModel;
17 
18 //#############################################################################
19 
21 class CbcBranchingObject;
22 
27 private:
28  void gutsOfConstructor(CbcModel& model);
31 private:
38 public:
39  CbcHeuristicNode(CbcModel& model);
40 
43  double distance(const CbcHeuristicNode* node) const;
44  double minDistance(const CbcHeuristicNodeList& nodeList) const;
45  bool minDistanceIsSmall(const CbcHeuristicNodeList& nodeList,
46  const double threshold) const;
47  double avgDistance(const CbcHeuristicNodeList& nodeList) const;
48 };
49 
51 private:
52  void gutsOfDelete();
53  void gutsOfCopy(const CbcHeuristicNodeList& rhs);
54 private:
55  std::vector<CbcHeuristicNode*> nodes_;
56 public:
61 
63  void append(const CbcHeuristicNodeList& nodes);
64  inline const CbcHeuristicNode* node(int i) const {
65  return nodes_[i];
66  }
67  inline int size() const {
68  return nodes_.size();
69  }
70 };
71 
72 //#############################################################################
75 class CbcHeuristic {
76 private:
77  void gutsOfDelete() {}
78  void gutsOfCopy(const CbcHeuristic & rhs);
79 
80 public:
81  // Default Constructor
82  CbcHeuristic ();
83 
84  // Constructor with model - assumed before cuts
85  CbcHeuristic (CbcModel & model);
86 
87  // Copy constructor
88  CbcHeuristic ( const CbcHeuristic &);
89 
90  virtual ~CbcHeuristic();
91 
93  virtual CbcHeuristic * clone() const = 0;
94 
96  CbcHeuristic & operator=(const CbcHeuristic& rhs);
97 
99  virtual void setModel(CbcModel * model);
100 
102  virtual void resetModel(CbcModel * model) = 0;
103 
109  virtual int solution(double & objectiveValue,
110  double * newSolution) = 0;
111 
119  virtual int solution2(double & /*objectiveValue*/,
120  double * /*newSolution*/,
121  OsiCuts & /*cs*/) {
122  return 0;
123  }
124 
126  virtual void validate() {}
127 
132  inline void setWhen(int value) {
133  when_ = value;
134  }
136  inline int when() const {
137  return when_;
138  }
139 
141  inline void setNumberNodes(int value) {
142  numberNodes_ = value;
143  }
145  inline int numberNodes() const {
146  return numberNodes_;
147  }
157  inline void setSwitches(int value) {
158  switches_ = value;
159  }
169  inline int switches() const {
170  return switches_;
171  }
173  bool exitNow(double bestObjective) const;
175  inline void setFeasibilityPumpOptions(int value) {
176  feasibilityPumpOptions_ = value;
177  }
179  inline int feasibilityPumpOptions() const {
181  }
183  inline void setModelOnly(CbcModel * model) {
184  model_ = model;
185  }
186 
187 
189  inline void setFractionSmall(double value) {
190  fractionSmall_ = value;
191  }
193  inline double fractionSmall() const {
194  return fractionSmall_;
195  }
197  inline int numberSolutionsFound() const {
198  return numberSolutionsFound_;
199  }
203  }
204 
214  int smallBranchAndBound(OsiSolverInterface * solver, int numberNodes,
215  double * newSolution, double & newSolutionValue,
216  double cutoff , std::string name) const;
218  virtual void generateCpp( FILE * ) {}
220  void generateCpp( FILE * fp, const char * heuristic) ;
222  virtual bool canDealWithOdd() const {
223  return false;
224  }
226  inline const char *heuristicName() const {
227  return heuristicName_.c_str();
228  }
230  inline void setHeuristicName(const char *name) {
231  heuristicName_ = name;
232  }
234  void setSeed(int value);
236  inline void setDecayFactor(double value) {
237  decayFactor_ = value;
238  }
240  void setInputSolution(const double * solution, double objValue);
241  /* Runs if bit set
242  0 - before cuts at root node (or from doHeuristics)
243  1 - during cuts at root
244  2 - after root node cuts
245  3 - after cuts at other nodes
246  4 - during cuts at other nodes
247  8 added if previous heuristic in loop found solution
248  */
249  inline void setWhereFrom(int value) {
250  whereFrom_ = value;
251  }
258  inline void setShallowDepth(int value) {
259  shallowDepth_ = value;
260  }
262  inline void setHowOftenShallow(int value) {
263  howOftenShallow_ = value;
264  }
268  inline void setMinDistanceToRun(int value) {
269  minDistanceToRun_ = value;
270  }
271 
280  virtual bool shouldHeurRun(int whereFrom);
283  void debugNodes();
284  void printDistanceToNodes();
286  inline int numRuns() const {
287  return numRuns_;
288  }
289 
291  inline int numCouldRun() const {
292  return numCouldRun_;
293  }
298  OsiSolverInterface * cloneBut(int type);
299 protected:
300 
304  int when_;
310  mutable double fractionSmall_;
312  CoinThreadRandom randomNumberGenerator_;
314  std::string heuristicName_;
315 
319  double decayFactor_;
329  mutable int switches_;
330  /* Runs if bit set
331  0 - before cuts at root node (or from doHeuristics)
332  1 - during cuts at root
333  2 - after root node cuts
334  3 - after cuts at other nodes
335  4 - during cuts at other nodes
336  8 added if previous heuristic in loop found solution
337  */
357  int numRuns_;
362 
365 
368 
371 
372  // Input solution - so can be used as seed
373  double * inputSolution_;
374 
375 
376 #ifdef JJF_ZERO
377 
378  double * lowerBoundLastNode_;
380  double * upperBoundLastNode_;
381 #endif
382 };
386 class CbcRounding : public CbcHeuristic {
387 public:
388 
389  // Default Constructor
390  CbcRounding ();
391 
392  // Constructor with model - assumed before cuts
393  CbcRounding (CbcModel & model);
394 
395  // Copy constructor
396  CbcRounding ( const CbcRounding &);
397 
398  // Destructor
399  ~CbcRounding ();
400 
402  CbcRounding & operator=(const CbcRounding& rhs);
403 
405  virtual CbcHeuristic * clone() const;
407  virtual void generateCpp( FILE * fp) ;
408 
410  virtual void resetModel(CbcModel * model);
411 
413  virtual void setModel(CbcModel * model);
414 
415  using CbcHeuristic::solution ;
421  virtual int solution(double & objectiveValue,
422  double * newSolution);
429  virtual int solution(double & objectiveValue,
430  double * newSolution,
431  double solutionValue);
433  virtual void validate();
434 
435 
437  void setSeed(int value) {
438  seed_ = value;
439  }
440 
441 protected:
442  // Data
443 
444  // Original matrix by column
445  CoinPackedMatrix matrix_;
446 
447  // Original matrix by
448  CoinPackedMatrix matrixByRow_;
449 
450  // Down locks
451  unsigned short * down_;
452 
453  // Up locks
454  unsigned short * up_;
455 
456  // Equality locks
457  unsigned short * equal_;
458 
459  // Seed for random stuff
460  int seed_;
461 };
462 
469 public:
470 
471  // Default Constructor
473 
478  CbcHeuristicPartial (CbcModel & model, int fixPriority = 10000, int numberNodes = 200);
479 
480  // Copy constructor
482 
483  // Destructor
485 
488 
490  virtual CbcHeuristic * clone() const;
492  virtual void generateCpp( FILE * fp) ;
493 
495  virtual void resetModel(CbcModel * model);
496 
498  virtual void setModel(CbcModel * model);
499 
500  using CbcHeuristic::solution ;
506  virtual int solution(double & objectiveValue,
507  double * newSolution);
509  virtual void validate();
510 
511 
513  void setFixPriority(int value) {
514  fixPriority_ = value;
515  }
516 
518  virtual bool shouldHeurRun(int whereFrom);
519 
520 protected:
521  // Data
522 
523  // All variables with abs priority <= this will be fixed
525 };
526 
531 class CbcSerendipity : public CbcHeuristic {
532 public:
533 
534  // Default Constructor
535  CbcSerendipity ();
536 
537  /* Constructor with model
538  */
539  CbcSerendipity (CbcModel & model);
540 
541  // Copy constructor
542  CbcSerendipity ( const CbcSerendipity &);
543 
544  // Destructor
545  ~CbcSerendipity ();
546 
549 
551  virtual CbcHeuristic * clone() const;
553  virtual void generateCpp( FILE * fp) ;
554 
556  virtual void setModel(CbcModel * model);
557 
558  using CbcHeuristic::solution ;
569  virtual int solution(double & objectiveValue,
570  double * newSolution);
572  virtual void resetModel(CbcModel * model);
573 
574 protected:
575 };
576 
581 public:
582 
583  // Default Constructor
585 
586  // Constructor with model - assumed before cuts
587  CbcHeuristicJustOne (CbcModel & model);
588 
589  // Copy constructor
591 
592  // Destructor
594 
596  virtual CbcHeuristicJustOne * clone() const;
597 
600 
602  virtual void generateCpp( FILE * fp) ;
603 
610  virtual int solution(double & objectiveValue,
611  double * newSolution);
613  virtual void resetModel(CbcModel * model);
614 
616  virtual void setModel(CbcModel * model);
618 
624  virtual bool selectVariableToBranch(OsiSolverInterface* /*solver*/,
625  const double* /*newSolution*/,
626  int& /*bestColumn*/,
627  int& /*bestRound*/) {
628  return true;
629  }
631  virtual void validate();
633  void addHeuristic(const CbcHeuristic * heuristic, double probability);
635  void normalizeProbabilities();
636 protected:
637  // Data
638 
639  // Probability of running a heuristic
640  double * probabilities_;
641 
642  // Heuristics
644 
645  // Number of heuristics
647 
648 };
649 
650 #endif
651