Cbc  2.10.5
CbcHeuristic.hpp
Go to the documentation of this file.
1 /* $Id$ */
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 #ifdef COIN_HAS_CLP
20 #include "OsiClpSolverInterface.hpp"
21 #endif
22 //#############################################################################
23 
25 class CbcBranchingObject;
26 
31 private:
32  void gutsOfConstructor(CbcModel &model);
35 
36 private:
43 
44 public:
45  CbcHeuristicNode(CbcModel &model);
46 
49  double distance(const CbcHeuristicNode *node) const;
50  double minDistance(const CbcHeuristicNodeList &nodeList) const;
51  bool minDistanceIsSmall(const CbcHeuristicNodeList &nodeList,
52  const double threshold) const;
53  double avgDistance(const CbcHeuristicNodeList &nodeList) const;
54 };
55 
57 private:
58  void gutsOfDelete();
59  void gutsOfCopy(const CbcHeuristicNodeList &rhs);
60 
61 private:
62  std::vector< CbcHeuristicNode * > nodes_;
63 
64 public:
69 
71  void append(const CbcHeuristicNodeList &nodes);
72  inline const CbcHeuristicNode *node(int i) const
73  {
74  return nodes_[i];
75  }
76  inline int size() const
77  {
78  return static_cast< int >(nodes_.size());
79  }
80 };
81 
82 //#############################################################################
85 class CbcHeuristic {
86 private:
87  void gutsOfDelete() {}
88  void gutsOfCopy(const CbcHeuristic &rhs);
89 
90 public:
91  // Default Constructor
92  CbcHeuristic();
93 
94  // Constructor with model - assumed before cuts
95  CbcHeuristic(CbcModel &model);
96 
97  // Copy constructor
98  CbcHeuristic(const CbcHeuristic &);
99 
100  virtual ~CbcHeuristic();
101 
103  virtual CbcHeuristic *clone() const = 0;
104 
106  CbcHeuristic &operator=(const CbcHeuristic &rhs);
107 
109  virtual void setModel(CbcModel *model);
110 
112  virtual void resetModel(CbcModel *model) = 0;
113 
119  virtual int solution(double &objectiveValue,
120  double *newSolution)
121  = 0;
122 
130  virtual int solution2(double & /*objectiveValue*/,
131  double * /*newSolution*/,
132  OsiCuts & /*cs*/)
133  {
134  return 0;
135  }
136 
138  virtual void validate() {}
139 
144  inline void setWhen(int value)
145  {
146  when_ = value;
147  }
149  inline int when() const
150  {
151  return when_;
152  }
153 
155  inline void setNumberNodes(int value)
156  {
157  numberNodes_ = value;
158  }
160  inline int numberNodes() const
161  {
162  return numberNodes_;
163  }
174  inline void setSwitches(int value)
175  {
176  switches_ = value;
177  }
189  inline int switches() const
190  {
191  return switches_;
192  }
194  bool exitNow(double bestObjective) const;
196  inline void setFeasibilityPumpOptions(int value)
197  {
198  feasibilityPumpOptions_ = value;
199  }
201  inline int feasibilityPumpOptions() const
202  {
204  }
206  inline void setModelOnly(CbcModel *model)
207  {
208  model_ = model;
209  }
210 
212  inline void setFractionSmall(double value)
213  {
214  fractionSmall_ = value;
215  }
217  inline double fractionSmall() const
218  {
219  return fractionSmall_;
220  }
222  inline int numberSolutionsFound() const
223  {
224  return numberSolutionsFound_;
225  }
228  {
230  }
231 
241  int smallBranchAndBound(OsiSolverInterface *solver, int numberNodes,
242  double *newSolution, double &newSolutionValue,
243  double cutoff, std::string name) const;
245  virtual void generateCpp(FILE *) {}
247  void generateCpp(FILE *fp, const char *heuristic);
249  virtual bool canDealWithOdd() const
250  {
251  return false;
252  }
254  inline const char *heuristicName() const
255  {
256  return heuristicName_.c_str();
257  }
259  inline void setHeuristicName(const char *name)
260  {
261  heuristicName_ = name;
262  }
264  void setSeed(int value);
266  int getSeed() const;
268  inline void setDecayFactor(double value)
269  {
270  decayFactor_ = value;
271  }
273  void setInputSolution(const double *solution, double objValue);
274  /* Runs if bit set
275  0 - before cuts at root node (or from doHeuristics)
276  1 - during cuts at root
277  2 - after root node cuts
278  3 - after cuts at other nodes
279  4 - during cuts at other nodes
280  8 added if previous heuristic in loop found solution
281  */
282  inline void setWhereFrom(int value)
283  {
284  whereFrom_ = value;
285  }
286  inline int whereFrom() const
287  {
288  return whereFrom_;
289  }
296  inline void setShallowDepth(int value)
297  {
298  shallowDepth_ = value;
299  }
301  inline void setHowOftenShallow(int value)
302  {
303  howOftenShallow_ = value;
304  }
308  inline void setMinDistanceToRun(int value)
309  {
310  minDistanceToRun_ = value;
311  }
312 
321  virtual bool shouldHeurRun(int whereFrom);
324  void debugNodes();
325  void printDistanceToNodes();
327  inline int numRuns() const
328  {
329  return numRuns_;
330  }
331 
333  inline int numCouldRun() const
334  {
335  return numCouldRun_;
336  }
338 #ifdef COIN_HAS_CLP
339  inline bool isHeuristicInteger(const OsiSolverInterface *solver, int iColumn) const
340  {
341  const OsiClpSolverInterface *clpSolver
342  = dynamic_cast< const OsiClpSolverInterface * >(solver);
343  if (clpSolver)
344  return clpSolver->isHeuristicInteger(iColumn);
345  else
346  return solver->isInteger(iColumn);
347  }
348 #else
349  inline bool isHeuristicInteger(const OsiSolverInterface *solver, int iColumn)
350  {
351  return solver->isInteger(iColumn);
352  }
353 #endif
354 
362  OsiSolverInterface *cloneBut(int type);
363 
364 protected:
368  int when_;
378  mutable double fractionSmall_;
380  CoinThreadRandom randomNumberGenerator_;
382  std::string heuristicName_;
383 
385  mutable int howOften_;
387  double decayFactor_;
398  mutable int switches_;
399  /* Runs if bit set
400  0 - before cuts at root node (or from doHeuristics)
401  1 - during cuts at root
402  2 - after root node cuts
403  3 - after cuts at other nodes
404  4 - during cuts at other nodes
405  8 added if previous heuristic in loop found solution
406  */
426  int numRuns_;
431 
434 
437 
440 
442  mutable int numberNodesDone_;
443 
444  // Input solution - so can be used as seed
445  double *inputSolution_;
446 
447 #ifdef JJF_ZERO
448  double *lowerBoundLastNode_;
451  double *upperBoundLastNode_;
452 #endif
453 };
457 class CbcRounding : public CbcHeuristic {
458 public:
459  // Default Constructor
460  CbcRounding();
461 
462  // Constructor with model - assumed before cuts
463  CbcRounding(CbcModel &model);
464 
465  // Copy constructor
466  CbcRounding(const CbcRounding &);
467 
468  // Destructor
469  ~CbcRounding();
470 
472  CbcRounding &operator=(const CbcRounding &rhs);
473 
475  virtual CbcHeuristic *clone() const;
477  virtual void generateCpp(FILE *fp);
478 
480  virtual void resetModel(CbcModel *model);
481 
483  virtual void setModel(CbcModel *model);
484 
491  virtual int solution(double &objectiveValue,
492  double *newSolution);
499  virtual int solution(double &objectiveValue,
500  double *newSolution,
501  double solutionValue);
503  virtual void validate();
504 
506  void setSeed(int value)
507  {
508  seed_ = value;
509  }
518  virtual bool shouldHeurRun(int whereFrom);
519 
520 protected:
521  // Data
522 
523  // Original matrix by column
524  CoinPackedMatrix matrix_;
525 
526  // Original matrix by
527  CoinPackedMatrix matrixByRow_;
528 
529  // Down locks
530  unsigned short *down_;
531 
532  // Up locks
533  unsigned short *up_;
534 
535  // Equality locks
536  unsigned short *equal_;
537 
538  // Seed for random stuff
539  int seed_;
540 };
541 
548 public:
549  // Default Constructor
551 
556  CbcHeuristicPartial(CbcModel &model, int fixPriority = 10000, int numberNodes = 200);
557 
558  // Copy constructor
560 
561  // Destructor
563 
566 
568  virtual CbcHeuristic *clone() const;
570  virtual void generateCpp(FILE *fp);
571 
573  virtual void resetModel(CbcModel *model);
574 
576  virtual void setModel(CbcModel *model);
577 
584  virtual int solution(double &objectiveValue,
585  double *newSolution);
587  virtual void validate();
588 
590  void setFixPriority(int value)
591  {
592  fixPriority_ = value;
593  }
594 
596  virtual bool shouldHeurRun(int whereFrom);
597 
598 protected:
599  // Data
600 
601  // All variables with abs priority <= this will be fixed
603 };
604 
609 class CbcSerendipity : public CbcHeuristic {
610 public:
611  // Default Constructor
612  CbcSerendipity();
613 
614  /* Constructor with model
615  */
616  CbcSerendipity(CbcModel &model);
617 
618  // Copy constructor
620 
621  // Destructor
622  ~CbcSerendipity();
623 
626 
628  virtual CbcHeuristic *clone() const;
630  virtual void generateCpp(FILE *fp);
631 
633  virtual void setModel(CbcModel *model);
634 
646  virtual int solution(double &objectiveValue,
647  double *newSolution);
649  virtual void resetModel(CbcModel *model);
650 
651 protected:
652 };
653 
658 public:
659  // Default Constructor
661 
662  // Constructor with model - assumed before cuts
664 
665  // Copy constructor
667 
668  // Destructor
670 
672  virtual CbcHeuristicJustOne *clone() const;
673 
676 
678  virtual void generateCpp(FILE *fp);
679 
686  virtual int solution(double &objectiveValue,
687  double *newSolution);
689  virtual void resetModel(CbcModel *model);
690 
692  virtual void setModel(CbcModel *model);
694 
700  virtual bool selectVariableToBranch(OsiSolverInterface * /*solver*/,
701  const double * /*newSolution*/,
702  int & /*bestColumn*/,
703  int & /*bestRound*/)
704  {
705  return true;
706  }
708  virtual void validate();
710  void addHeuristic(const CbcHeuristic *heuristic, double probability);
712  void normalizeProbabilities();
713 
714 protected:
715  // Data
716 
717  // Probability of running a heuristic
718  double *probabilities_;
719 
720  // Heuristics
722 
723  // Number of heuristics
725 };
726 #endif
727 
728 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
729 */
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.
CbcHeuristicJustOne & operator=(const CbcHeuristicJustOne &rhs)
Assignment operator.
double fractionSmall_
Fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound.
void gutsOfCopy(const CbcHeuristic &rhs)
CoinThreadRandom randomNumberGenerator_
Thread specific random number generator.
void debugNodes()
void setFixPriority(int value)
Set priority level.
CbcHeuristic & operator=(const CbcHeuristic &rhs)
Assignment operator.
unsigned short * down_
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...
double avgDistance(const CbcHeuristicNodeList &nodeList) const
virtual void setModel(CbcModel *model)
update model (This is needed if cliques update matrix etc)
virtual bool canDealWithOdd() const
Returns true if can deal with "odd" problems e.g. sos type 2.
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.
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...
bool isHeuristicInteger(const OsiSolverInterface *solver, int iColumn)
Is it integer for heuristics?
std::vector< CbcHeuristicNode *> nodes_
double minDistance(const CbcHeuristicNodeList &nodeList) const
CbcHeuristicNode & operator=(const CbcHeuristicNode &)
void append(CbcHeuristicNode *&node)
virtual CbcHeuristic * clone() const
Clone.
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...
virtual CbcHeuristic * clone() const
Clone.
virtual CbcHeuristic * clone() const
Clone.
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.
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
const CbcHeuristicNode * node(int i) const
void printDistanceToNodes()
virtual void resetModel(CbcModel *model)
Resets stuff if model changes.
void setHeuristicName(const char *name)
set name of heuristic
const char * heuristicName() const
return name of heuristic
bool exitNow(double bestObjective) const
Whether to exit at once on gap.
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. ...
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 -...
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)
bool minDistanceIsSmall(const CbcHeuristicNodeList &nodeList, const double threshold) const
virtual void setModel(CbcModel *model)
update model (This is needed if cliques update matrix etc)
CbcHeuristicPartial & operator=(const CbcHeuristicPartial &rhs)
Assignment operator.
int whereFrom() const
CbcRounding & operator=(const CbcRounding &rhs)
Assignment operator.
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.
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.
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.
Heuristic base class.
int numObjects_
The number of branching decisions made.
double distance(const CbcHeuristicNode *node) const
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.
virtual void generateCpp(FILE *fp)
Create C++ lines to get to current state.
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.
void setInputSolution(const double *solution, double objValue)
Set input solution.
CbcBranchingObject ** brObj_
The indices of the branching objects.
int getSeed() const
Get random number generator seed.
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)
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)
void normalizeProbabilities()
Normalize probabilities.
int numCouldRun() const
How many times the heuristic could run.
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 CbcHeuristicJustOne * clone() const
Clone.
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:100
void setHowOftenShallow(int value)
How often to invoke the heuristics in the shallow part of the tree.
double * inputSolution_
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 numberSolutionsFound() const
Get how many solutions the heuristic thought it got.
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)