Cbc  2.9.8
CbcHeuristic.hpp
Go to the documentation of this file.
1 /* $Id: CbcHeuristic.hpp 2094 2014-11-18 11:15:36Z forrest $ */
2 // Copyright (C) 2002, 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 CbcHeuristic_H
7 #define CbcHeuristic_H
8 
9 #include <string>
10 #include <vector>
11 #include "CoinPackedMatrix.hpp"
12 #include "OsiCuts.hpp"
13 #include "CoinHelperFunctions.hpp"
14 #include "OsiBranchingObject.hpp"
15 
16 class OsiSolverInterface;
17 
18 class CbcModel;
19 
20 //#############################################################################
21 
23 class CbcBranchingObject;
24 
29 private:
30  void gutsOfConstructor(CbcModel& model);
32  CbcHeuristicNode& operator=(const CbcHeuristicNode&);
33 private:
35  int numObjects_;
39  CbcBranchingObject** brObj_;
40 public:
41  CbcHeuristicNode(CbcModel& model);
42 
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;
50 };
51 
53 private:
54  void gutsOfDelete();
55  void gutsOfCopy(const CbcHeuristicNodeList& rhs);
56 private:
57  std::vector<CbcHeuristicNode*> nodes_;
58 public:
61  CbcHeuristicNodeList& operator=(const CbcHeuristicNodeList& rhs);
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 {
70  return static_cast<int>(nodes_.size());
71  }
72 };
73 
74 //#############################################################################
77 class CbcHeuristic {
78 private:
79  void gutsOfDelete() {}
80  void gutsOfCopy(const CbcHeuristic & rhs);
81 
82 public:
83  // Default Constructor
84  CbcHeuristic ();
85 
86  // Constructor with model - assumed before cuts
87  CbcHeuristic (CbcModel & model);
88 
89  // Copy constructor
90  CbcHeuristic ( const CbcHeuristic &);
91 
92  virtual ~CbcHeuristic();
93 
95  virtual CbcHeuristic * clone() const = 0;
96 
98  CbcHeuristic & operator=(const CbcHeuristic& rhs);
99 
101  virtual void setModel(CbcModel * model);
102 
104  virtual void resetModel(CbcModel * model) = 0;
105 
111  virtual int solution(double & objectiveValue,
112  double * newSolution) = 0;
113 
121  virtual int solution2(double & /*objectiveValue*/,
122  double * /*newSolution*/,
123  OsiCuts & /*cs*/) {
124  return 0;
125  }
126 
128  virtual void validate() {}
129 
134  inline void setWhen(int value) {
135  when_ = value;
136  }
138  inline int when() const {
139  return when_;
140  }
141 
143  inline void setNumberNodes(int value) {
144  numberNodes_ = value;
145  }
147  inline int numberNodes() const {
148  return numberNodes_;
149  }
160  inline void setSwitches(int value) {
161  switches_ = value;
162  }
174  inline int switches() const {
175  return switches_;
176  }
178  bool exitNow(double bestObjective) const;
180  inline void setFeasibilityPumpOptions(int value) {
181  feasibilityPumpOptions_ = value;
182  }
184  inline int feasibilityPumpOptions() const {
185  return feasibilityPumpOptions_;
186  }
188  inline void setModelOnly(CbcModel * model) {
189  model_ = model;
190  }
191 
192 
194  inline void setFractionSmall(double value) {
195  fractionSmall_ = value;
196  }
198  inline double fractionSmall() const {
199  return fractionSmall_;
200  }
202  inline int numberSolutionsFound() const {
203  return numberSolutionsFound_;
204  }
207  numberSolutionsFound_++;
208  }
209 
219  int smallBranchAndBound(OsiSolverInterface * solver, int numberNodes,
220  double * newSolution, double & newSolutionValue,
221  double cutoff , std::string name) const;
223  virtual void generateCpp( FILE * ) {}
225  void generateCpp( FILE * fp, const char * heuristic) ;
227  virtual bool canDealWithOdd() const {
228  return false;
229  }
231  inline const char *heuristicName() const {
232  return heuristicName_.c_str();
233  }
235  inline void setHeuristicName(const char *name) {
236  heuristicName_ = name;
237  }
239  void setSeed(int value);
241  int getSeed() const;
243  inline void setDecayFactor(double value) {
244  decayFactor_ = value;
245  }
247  void setInputSolution(const double * solution, double objValue);
248  /* Runs if bit set
249  0 - before cuts at root node (or from doHeuristics)
250  1 - during cuts at root
251  2 - after root node cuts
252  3 - after cuts at other nodes
253  4 - during cuts at other nodes
254  8 added if previous heuristic in loop found solution
255  */
256  inline void setWhereFrom(int value) {
257  whereFrom_ = value;
258  }
259  inline int whereFrom() const {
260  return whereFrom_;
261  }
268  inline void setShallowDepth(int value) {
269  shallowDepth_ = value;
270  }
272  inline void setHowOftenShallow(int value) {
273  howOftenShallow_ = value;
274  }
278  inline void setMinDistanceToRun(int value) {
279  minDistanceToRun_ = value;
280  }
281 
290  virtual bool shouldHeurRun(int whereFrom);
292  bool shouldHeurRun_randomChoice();
293  void debugNodes();
294  void printDistanceToNodes();
296  inline int numRuns() const {
297  return numRuns_;
298  }
299 
301  inline int numCouldRun() const {
302  return numCouldRun_;
303  }
312  OsiSolverInterface * cloneBut(int type);
313 protected:
314 
318  int when_;
328  mutable double fractionSmall_;
330  CoinThreadRandom randomNumberGenerator_;
332  std::string heuristicName_;
333 
335  mutable int howOften_;
337  double decayFactor_;
348  mutable int switches_;
349  /* Runs if bit set
350  0 - before cuts at root node (or from doHeuristics)
351  1 - during cuts at root
352  2 - after root node cuts
353  3 - after cuts at other nodes
354  4 - during cuts at other nodes
355  8 added if previous heuristic in loop found solution
356  */
376  int numRuns_;
381 
384 
387 
390 
392  mutable int numberNodesDone_;
393 
394  // Input solution - so can be used as seed
395  double * inputSolution_;
396 
397 
398 #ifdef JJF_ZERO
399  double * lowerBoundLastNode_;
402  double * upperBoundLastNode_;
403 #endif
404 };
408 class CbcRounding : public CbcHeuristic {
409 public:
410 
411  // Default Constructor
412  CbcRounding ();
413 
414  // Constructor with model - assumed before cuts
415  CbcRounding (CbcModel & model);
416 
417  // Copy constructor
418  CbcRounding ( const CbcRounding &);
419 
420  // Destructor
421  ~CbcRounding ();
422 
424  CbcRounding & operator=(const CbcRounding& rhs);
425 
427  virtual CbcHeuristic * clone() const;
429  virtual void generateCpp( FILE * fp) ;
430 
432  virtual void resetModel(CbcModel * model);
433 
435  virtual void setModel(CbcModel * model);
436 
437  using CbcHeuristic::solution ;
443  virtual int solution(double & objectiveValue,
444  double * newSolution);
451  virtual int solution(double & objectiveValue,
452  double * newSolution,
453  double solutionValue);
455  virtual void validate();
456 
457 
459  void setSeed(int value) {
460  seed_ = value;
461  }
470  virtual bool shouldHeurRun(int whereFrom);
471 
472 protected:
473  // Data
474 
475  // Original matrix by column
476  CoinPackedMatrix matrix_;
477 
478  // Original matrix by
479  CoinPackedMatrix matrixByRow_;
480 
481  // Down locks
482  unsigned short * down_;
483 
484  // Up locks
485  unsigned short * up_;
486 
487  // Equality locks
488  unsigned short * equal_;
489 
490  // Seed for random stuff
491  int seed_;
492 };
493 
500 public:
501 
502  // Default Constructor
504 
509  CbcHeuristicPartial (CbcModel & model, int fixPriority = 10000, int numberNodes = 200);
510 
511  // Copy constructor
513 
514  // Destructor
516 
518  CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs);
519 
521  virtual CbcHeuristic * clone() const;
523  virtual void generateCpp( FILE * fp) ;
524 
526  virtual void resetModel(CbcModel * model);
527 
529  virtual void setModel(CbcModel * model);
530 
531  using CbcHeuristic::solution ;
537  virtual int solution(double & objectiveValue,
538  double * newSolution);
540  virtual void validate();
541 
542 
544  void setFixPriority(int value) {
545  fixPriority_ = value;
546  }
547 
549  virtual bool shouldHeurRun(int whereFrom);
550 
551 protected:
552  // Data
553 
554  // All variables with abs priority <= this will be fixed
556 };
557 
562 class CbcSerendipity : public CbcHeuristic {
563 public:
564 
565  // Default Constructor
566  CbcSerendipity ();
567 
568  /* Constructor with model
569  */
570  CbcSerendipity (CbcModel & model);
571 
572  // Copy constructor
573  CbcSerendipity ( const CbcSerendipity &);
574 
575  // Destructor
576  ~CbcSerendipity ();
577 
579  CbcSerendipity & operator=(const CbcSerendipity& rhs);
580 
582  virtual CbcHeuristic * clone() const;
584  virtual void generateCpp( FILE * fp) ;
585 
587  virtual void setModel(CbcModel * model);
588 
589  using CbcHeuristic::solution ;
600  virtual int solution(double & objectiveValue,
601  double * newSolution);
603  virtual void resetModel(CbcModel * model);
604 
605 protected:
606 };
607 
612 public:
613 
614  // Default Constructor
616 
617  // Constructor with model - assumed before cuts
618  CbcHeuristicJustOne (CbcModel & model);
619 
620  // Copy constructor
622 
623  // Destructor
625 
627  virtual CbcHeuristicJustOne * clone() const;
628 
630  CbcHeuristicJustOne & operator=(const CbcHeuristicJustOne& rhs);
631 
633  virtual void generateCpp( FILE * fp) ;
634 
641  virtual int solution(double & objectiveValue,
642  double * newSolution);
644  virtual void resetModel(CbcModel * model);
645 
647  virtual void setModel(CbcModel * model);
649 
655  virtual bool selectVariableToBranch(OsiSolverInterface* /*solver*/,
656  const double* /*newSolution*/,
657  int& /*bestColumn*/,
658  int& /*bestRound*/) {
659  return true;
660  }
662  virtual void validate();
664  void addHeuristic(const CbcHeuristic * heuristic, double probability);
666  void normalizeProbabilities();
667 protected:
668  // Data
669 
670  // Probability of running a heuristic
671  double * probabilities_;
672 
673  // Heuristics
675 
676  // Number of heuristics
678 
679 };
680 
681 #endif
682 
void incrementNumberSolutionsFound()
Increment how many solutions the heuristic thought it got.
double decayFactor_
How much to increase how often.
int howOftenShallow_
How often to invoke the heuristics in the shallow part of the tree.
int when_
When flag - 0 off, 1 at root, 2 other than root, 3 always.
int numberNodesDone_
How many nodes the heuristic did this go.
double fractionSmall_
Fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound.
CoinThreadRandom randomNumberGenerator_
Thread specific random number generator.
void setFixPriority(int value)
Set priority level.
unsigned short * down_
int lastRunDeep_
After how many deep invocations was the heuristic run last time.
void setFeasibilityPumpOptions(int value)
Sets feasibility pump options (-1 is off)
int switches_
Switches (does not apply equally to all heuristics) 1 bit - stop once allowable gap on objective reac...
double avgDistance(const CbcHeuristicNodeList &nodeList) const
virtual bool canDealWithOdd() const
Returns true if can deal with "odd" problems e.g. sos type 2.
int feasibilityPumpOptions() const
Gets feasibility pump options (-1 is off)
void setSeed(int value)
Set seed.
int numInvocationsInShallow_
How many invocations happened within the same node when in a shallow part of the tree.
void setShallowDepth(int value)
Upto this depth we call the tree shallow and the heuristic can be called multiple times...
double minDistance(const CbcHeuristicNodeList &nodeList) const
int numInvocationsInDeep_
How many invocations happened when in the deep part of the tree.
int numberNodes_
Number of nodes in any sub tree.
int minDistanceToRun_
How "far" should this node be from every other where the heuristic was run in order to allow the heur...
unsigned short * up_
void setFractionSmall(double value)
Sets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1...
void setDecayFactor(double value)
Sets decay factor (for howOften) on failure.
void setNumberNodes(int value)
Sets number of nodes in subtree (default 200)
unsigned short * equal_
int feasibilityPumpOptions_
Feasibility pump options , -1 is off >=0 for feasibility pump itself -2 quick proximity search -3 lon...
void setMinDistanceToRun(int value)
How "far" should this node be from every other where the heuristic was run in order to allow the heur...
CbcModel * model_
Model.
void setModelOnly(CbcModel *model)
Just set model - do not do anything else.
void setWhen(int value)
Sets "when" flag - 0 off, 1 at root, 2 other than root, 3 always.
int numRuns_
how many times the heuristic has actually run
const CbcHeuristicNode * node(int i) const
void setHeuristicName(const char *name)
set name of heuristic
const char * heuristicName() const
return name of heuristic
int howOften_
How often to do (code can change)
CbcHeuristic ** heuristic_
Abstract branching object base class Now just difference with OsiBranchingObject. ...
Partial solution class If user knows a partial solution this tries to get an integer solution it uses...
bool minDistanceIsSmall(const CbcHeuristicNodeList &nodeList, const double threshold) const
int whereFrom() const
CoinPackedMatrix matrixByRow_
int numCouldRun_
How many times the heuristic could run.
Just One class - this chooses one at random.
int switches() const
Switches (does not apply equally to all heuristics) 1 bit - stop once allowable gap on objective reac...
Rounding class.
CbcHeuristicNodeList runNodes_
The description of the nodes where this heuristic has been applied.
void setWhereFrom(int value)
int shallowDepth_
Upto this depth we call the tree shallow and the heuristic can be called multiple times...
Heuristic base class.
double distance(const CbcHeuristicNode *node) const
int numberSolutionsFound_
How many solutions the heuristic thought it got.
int numRuns() const
how many times the heuristic has actually run
virtual int solution(double &objectiveValue, double *newSolution)=0
returns 0 if no solution, 1 if valid solution with better objective value than one passed in Sets sol...
int when() const
Gets "when" flag - 0 off, 1 at root, 2 other than root, 3 always.
virtual void generateCpp(FILE *)
Create C++ lines to get to current state.
std::string heuristicName_
Name for printing.
CoinPackedMatrix matrix_
double fractionSmall() const
Gets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1...
A class describing the branching decisions that were made to get to the node where a heuristic was in...
void setSwitches(int value)
Switches (does not apply equally to all heuristics) 1 bit - stop once allowable gap on objective reac...
int numberNodes() const
Gets number of nodes in a subtree (default 200)
int numCouldRun() const
How many times the heuristic could run.
virtual bool selectVariableToBranch(OsiSolverInterface *, const double *, int &, int &)
Selects the next variable to branch on.
virtual int solution2(double &, double *, OsiCuts &)
returns 0 if no solution, 1 if valid solution, -1 if just returning an estimate of best possible solu...
Simple Branch and bound class.
Definition: CbcModel.hpp:101
void setHowOftenShallow(int value)
How often to invoke the heuristics in the shallow part of the tree.
double * inputSolution_
int numberSolutionsFound() const
Get how many solutions the heuristic thought it got.
heuristic - just picks up any good solution found by solver - see OsiBabSolver
virtual void validate()
Validate model i.e. sets when_ to 0 if necessary (may be NULL)