Cbc  2.9.9
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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);
33 private:
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  }
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 {
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  }
208  }
209 
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);
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_;
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
477 
478  // Original matrix by
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 
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 
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 
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.
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...
void gutsOfDelete()
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
void gutsOfCopy(const CbcHeuristic &rhs)
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 gutsOfCopy(const CbcHeuristicNodeList &rhs)
void setShallowDepth(int value)
Upto this depth we call the tree shallow and the heuristic can be called multiple times...
Collections of row cuts and column cuts.
Definition: OsiCuts.hpp:19
int switches() const
Switches (does not apply equally to all heuristics) 1 bit - stop once allowable gap on objective reac...
CbcHeuristicNode & operator=(const CbcHeuristicNode &)
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 &quot;far&quot; 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.
Abstract Base Class for describing an interface to a solver.
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 &gt;=0 for feasibility pump itself -2 quick proximity search -3 lon...
void setMinDistanceToRun(int value)
How &quot;far&quot; 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 &quot;when&quot; 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...
void gutsOfConstructor(CbcModel &model)
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)
Sparse Matrix Base Class.
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.
int numObjects_
The number of branching decisions made.
virtual bool canDealWithOdd() const
Returns true if can deal with &quot;odd&quot; 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 &quot;when&quot; 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.
CbcBranchingObject ** brObj_
The indices of the branching objects.
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 bool shouldHeurRun(int whereFrom)
Check whether the heuristic should run at all 0 - before cuts at root node (or from doHeuristics) 1 -...
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:101
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...
std::vector< CbcHeuristicNode * > nodes_
int numCouldRun() const
How many times the heuristic could run.
Class for thread specific random numbers.
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)