Cbc  2.8.12
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
CbcHeuristic.hpp
Go to the documentation of this file.
1 /* $Id: CbcHeuristic.hpp 1883 2013-04-06 13:33:15Z stefan $ */
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:
63 
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  }
173  inline int switches() const {
174  return switches_;
175  }
177  bool exitNow(double bestObjective) const;
179  inline void setFeasibilityPumpOptions(int value) {
180  feasibilityPumpOptions_ = value;
181  }
183  inline int feasibilityPumpOptions() const {
185  }
187  inline void setModelOnly(CbcModel * model) {
188  model_ = model;
189  }
190 
191 
193  inline void setFractionSmall(double value) {
194  fractionSmall_ = value;
195  }
197  inline double fractionSmall() const {
198  return fractionSmall_;
199  }
201  inline int numberSolutionsFound() const {
202  return numberSolutionsFound_;
203  }
207  }
208 
218  int smallBranchAndBound(OsiSolverInterface * solver, int numberNodes,
219  double * newSolution, double & newSolutionValue,
220  double cutoff , std::string name) const;
222  virtual void generateCpp( FILE * ) {}
224  void generateCpp( FILE * fp, const char * heuristic) ;
226  virtual bool canDealWithOdd() const {
227  return false;
228  }
230  inline const char *heuristicName() const {
231  return heuristicName_.c_str();
232  }
234  inline void setHeuristicName(const char *name) {
235  heuristicName_ = name;
236  }
238  void setSeed(int value);
240  int getSeed() const;
242  inline void setDecayFactor(double value) {
243  decayFactor_ = value;
244  }
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  }
258  inline int whereFrom() const {
259  return whereFrom_;
260  }
267  inline void setShallowDepth(int value) {
268  shallowDepth_ = value;
269  }
271  inline void setHowOftenShallow(int value) {
272  howOftenShallow_ = value;
273  }
277  inline void setMinDistanceToRun(int value) {
278  minDistanceToRun_ = value;
279  }
280 
289  virtual bool shouldHeurRun(int whereFrom);
292  void debugNodes();
293  void printDistanceToNodes();
295  inline int numRuns() const {
296  return numRuns_;
297  }
298 
300  inline int numCouldRun() const {
301  return numCouldRun_;
302  }
311  OsiSolverInterface * cloneBut(int type);
312 protected:
313 
317  int when_;
327  mutable double fractionSmall_;
329  CoinThreadRandom randomNumberGenerator_;
331  std::string heuristicName_;
332 
336  double decayFactor_;
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  */
375  int numRuns_;
380 
383 
386 
389 
391  mutable int numberNodesDone_;
392 
393  // Input solution - so can be used as seed
394  double * inputSolution_;
395 
396 
397 #ifdef JJF_ZERO
398  double * lowerBoundLastNode_;
401  double * upperBoundLastNode_;
402 #endif
403 };
407 class CbcRounding : public CbcHeuristic {
408 public:
409 
410  // Default Constructor
411  CbcRounding ();
412 
413  // Constructor with model - assumed before cuts
414  CbcRounding (CbcModel & model);
415 
416  // Copy constructor
417  CbcRounding ( const CbcRounding &);
418 
419  // Destructor
420  ~CbcRounding ();
421 
423  CbcRounding & operator=(const CbcRounding& rhs);
424 
426  virtual CbcHeuristic * clone() const;
428  virtual void generateCpp( FILE * fp) ;
429 
431  virtual void resetModel(CbcModel * model);
432 
434  virtual void setModel(CbcModel * model);
435 
436  using CbcHeuristic::solution ;
442  virtual int solution(double & objectiveValue,
443  double * newSolution);
450  virtual int solution(double & objectiveValue,
451  double * newSolution,
452  double solutionValue);
454  virtual void validate();
455 
456 
458  void setSeed(int value) {
459  seed_ = value;
460  }
461 
462 protected:
463  // Data
464 
465  // Original matrix by column
466  CoinPackedMatrix matrix_;
467 
468  // Original matrix by
469  CoinPackedMatrix matrixByRow_;
470 
471  // Down locks
472  unsigned short * down_;
473 
474  // Up locks
475  unsigned short * up_;
476 
477  // Equality locks
478  unsigned short * equal_;
479 
480  // Seed for random stuff
481  int seed_;
482 };
483 
490 public:
491 
492  // Default Constructor
494 
499  CbcHeuristicPartial (CbcModel & model, int fixPriority = 10000, int numberNodes = 200);
500 
501  // Copy constructor
503 
504  // Destructor
506 
509 
511  virtual CbcHeuristic * clone() const;
513  virtual void generateCpp( FILE * fp) ;
514 
516  virtual void resetModel(CbcModel * model);
517 
519  virtual void setModel(CbcModel * model);
520 
521  using CbcHeuristic::solution ;
527  virtual int solution(double & objectiveValue,
528  double * newSolution);
530  virtual void validate();
531 
532 
534  void setFixPriority(int value) {
535  fixPriority_ = value;
536  }
537 
539  virtual bool shouldHeurRun(int whereFrom);
540 
541 protected:
542  // Data
543 
544  // All variables with abs priority <= this will be fixed
546 };
547 
552 class CbcSerendipity : public CbcHeuristic {
553 public:
554 
555  // Default Constructor
556  CbcSerendipity ();
557 
558  /* Constructor with model
559  */
560  CbcSerendipity (CbcModel & model);
561 
562  // Copy constructor
563  CbcSerendipity ( const CbcSerendipity &);
564 
565  // Destructor
566  ~CbcSerendipity ();
567 
570 
572  virtual CbcHeuristic * clone() const;
574  virtual void generateCpp( FILE * fp) ;
575 
577  virtual void setModel(CbcModel * model);
578 
579  using CbcHeuristic::solution ;
590  virtual int solution(double & objectiveValue,
591  double * newSolution);
593  virtual void resetModel(CbcModel * model);
594 
595 protected:
596 };
597 
602 public:
603 
604  // Default Constructor
606 
607  // Constructor with model - assumed before cuts
608  CbcHeuristicJustOne (CbcModel & model);
609 
610  // Copy constructor
612 
613  // Destructor
615 
617  virtual CbcHeuristicJustOne * clone() const;
618 
621 
623  virtual void generateCpp( FILE * fp) ;
624 
631  virtual int solution(double & objectiveValue,
632  double * newSolution);
634  virtual void resetModel(CbcModel * model);
635 
637  virtual void setModel(CbcModel * model);
639 
645  virtual bool selectVariableToBranch(OsiSolverInterface* /*solver*/,
646  const double* /*newSolution*/,
647  int& /*bestColumn*/,
648  int& /*bestRound*/) {
649  return true;
650  }
652  virtual void validate();
654  void addHeuristic(const CbcHeuristic * heuristic, double probability);
656  void normalizeProbabilities();
657 protected:
658  // Data
659 
660  // Probability of running a heuristic
661  double * probabilities_;
662 
663  // Heuristics
665 
666  // Number of heuristics
668 
669 };
670 
671 #endif
672 
void incrementNumberSolutionsFound()
Increment how many solutions the heuristic thought it got.
virtual int solution(double &objectiveValue, double *newSolution)
returns 0 if no solution, 1 if valid solution with better objective value than one passed in Sets sol...
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.
virtual bool shouldHeurRun(int whereFrom)
Check whether the heuristic should run at all.
int numberNodesDone_
How many nodes the heuristic did this go.
virtual CbcHeuristic * clone() const
Clone.
CbcHeuristicJustOne & operator=(const CbcHeuristicJustOne &rhs)
Assignment operator.
double fractionSmall_
Fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound.
const char * heuristicName() const
return name of heuristic
CoinThreadRandom randomNumberGenerator_
Thread specific random number generator.
virtual CbcHeuristicJustOne * clone() const
Clone.
void debugNodes()
void setFixPriority(int value)
Set priority level.
int whereFrom() const
CbcHeuristic & operator=(const CbcHeuristic &rhs)
Assignment operator.
unsigned short * down_
double distance(const CbcHeuristicNode *node) const
virtual void setModel(CbcModel *model)
update model (This is needed if cliques update matrix etc)
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...
virtual void setModel(CbcModel *model)
update model (This is needed if cliques update matrix etc)
virtual void generateCpp(FILE *fp)
Create C++ lines to get to current state.
int feasibilityPumpOptions() const
Gets feasibility pump options (-1 is off)
void setSeed(int value)
Set seed.
OsiSolverInterface * cloneBut(int type)
Clone, but ...
int numInvocationsInShallow_
How many invocations happened within the same node when in a shallow part of the tree.
double minDistance(const CbcHeuristicNodeList &nodeList) const
virtual void resetModel(CbcModel *model)
Resets stuff if model changes.
void setShallowDepth(int value)
Upto this depth we call the tree shallow and the heuristic can be called multiple times...
int switches() const
Switches (does not apply equally to all heuristics) 1 bit - stop once allowable gap on objective reac...
void append(CbcHeuristicNode *&node)
int numInvocationsInDeep_
How many invocations happened when in the deep part of the tree.
virtual void resetModel(CbcModel *model)
Resets stuff if model changes.
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...
int numberSolutionsFound() const
Get how many solutions the heuristic thought it got.
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...
virtual void resetModel(CbcModel *model)
Resets stuff if model changes.
CbcModel * model_
Model.
int numberNodes() const
Gets number of nodes in a subtree (default 200)
virtual void resetModel(CbcModel *model)=0
Resets stuff if model changes.
void setSeed(int value)
Set random number generator seed.
void setModelOnly(CbcModel *model)
Just set model - do not do anything else.
virtual void generateCpp(FILE *fp)
Create C++ lines to get to current state.
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
virtual CbcHeuristic * clone() const
Clone.
void printDistanceToNodes()
virtual void resetModel(CbcModel *model)
Resets stuff if model changes.
void setHeuristicName(const char *name)
set name of heuristic
virtual void generateCpp(FILE *fp)
Create C++ lines to get to current state.
int howOften_
How often to do (code can change)
CbcHeuristic ** heuristic_
Abstract branching object base class Now just difference with OsiBranchingObject. ...
const CbcHeuristicNode * node(int i) const
Partial solution class If user knows a partial solution this tries to get an integer solution it uses...
CbcHeuristicNodeList & operator=(const CbcHeuristicNodeList &rhs)
virtual void setModel(CbcModel *model)
update model (This is needed if cliques update matrix etc)
bool exitNow(double bestObjective) const
Whether to exit at once on gap.
CbcHeuristicPartial & operator=(const CbcHeuristicPartial &rhs)
Assignment operator.
CbcRounding & operator=(const CbcRounding &rhs)
Assignment operator.
double fractionSmall() const
Gets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1...
virtual int solution(double &objectiveValue, double *newSolution)
returns 0 if no solution, 1 if valid solution with better objective value than one passed in Sets sol...
CoinPackedMatrix matrixByRow_
int numCouldRun_
How many times the heuristic could run.
Just One class - this chooses one at random.
double avgDistance(const CbcHeuristicNodeList &nodeList) const
Rounding class.
CbcHeuristicNodeList runNodes_
The description of the nodes where this heuristic has been applied.
virtual void validate()
Validate model i.e. sets when_ to 0 if necessary (may be NULL)
virtual void validate()
Validate model i.e. sets when_ to 0 if necessary (may be NULL)
void setWhereFrom(int value)
virtual bool shouldHeurRun(int whereFrom)
Check whether the heuristic should run at all 0 - before cuts at root node (or from doHeuristics) 1 -...
int shallowDepth_
Upto this depth we call the tree shallow and the heuristic can be called multiple times...
virtual ~CbcHeuristic()
CbcSerendipity & operator=(const CbcSerendipity &rhs)
Assignment operator.
int getSeed() const
Get random number generator seed.
Heuristic base class.
virtual bool canDealWithOdd() const
Returns true if can deal with "odd" problems e.g. sos type 2.
virtual int solution(double &objectiveValue, double *newSolution)
returns 0 if no solution, 1 if valid solution.
int numberSolutionsFound_
How many solutions the heuristic thought it got.
int when() const
Gets "when" flag - 0 off, 1 at root, 2 other than root, 3 always.
virtual void generateCpp(FILE *fp)
Create C++ lines to get to current state.
bool minDistanceIsSmall(const CbcHeuristicNodeList &nodeList, const double threshold) const
virtual CbcHeuristic * clone() const
Clone.
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...
void setInputSolution(const double *solution, double objValue)
Set input solution.
virtual void generateCpp(FILE *)
Create C++ lines to get to current state.
std::string heuristicName_
Name for printing.
CoinPackedMatrix matrix_
virtual void setModel(CbcModel *model)
update model (This is needed if cliques update matrix etc)
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...
void normalizeProbabilities()
Normalize probabilities.
bool shouldHeurRun_randomChoice()
Check whether the heuristic should run this time.
virtual CbcHeuristic * clone() const =0
Clone.
virtual bool selectVariableToBranch(OsiSolverInterface *, const double *, int &, int &)
Selects the next variable to branch on.
void addHeuristic(const CbcHeuristic *heuristic, double probability)
Adds an heuristic with probability.
virtual void validate()
Validate model i.e. sets when_ to 0 if necessary (may be NULL)
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:100
void setHowOftenShallow(int value)
How often to invoke the heuristics in the shallow part of the tree.
int smallBranchAndBound(OsiSolverInterface *solver, int numberNodes, double *newSolution, double &newSolutionValue, double cutoff, std::string name) const
Do mini branch and bound - return 0 not finished - no solution 1 not finished - solution 2 finished -...
double * inputSolution_
int numRuns() const
how many times the heuristic has actually run
virtual int solution(double &objectiveValue, double *newSolution)
returns 0 if no solution, 1 if valid solution with better objective value than one passed in Sets sol...
int numCouldRun() const
How many times the heuristic could run.
virtual void setModel(CbcModel *model)
update model
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)