Cbc  2.10.7
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:
35 
36 private:
43 
44 public:
46 
49  double distance(const CbcHeuristicNode *node) const;
50  double minDistance(const CbcHeuristicNodeList &nodeList) const;
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
93 
94  // Constructor with model - assumed before cuts
96 
97  // Copy constructor
99 
100  virtual ~CbcHeuristic();
101 
103  virtual CbcHeuristic *clone() const = 0;
104 
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();
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
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
449  double *lowerBoundLastNode_;
451  double *upperBoundLastNode_;
452 #endif
453 };
457 class CbcRounding : public CbcHeuristic {
458 public:
459  // Default Constructor
461 
462  // Constructor with model - assumed before cuts
464 
465  // Copy constructor
467 
468  // Destructor
470 
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
613 
614  /* Constructor with model
615  */
617 
618  // Copy constructor
620 
621  // Destructor
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);
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 */
Abstract branching object base class Now just difference with OsiBranchingObject.
Just One class - this chooses one at random.
virtual void generateCpp(FILE *fp)
Create C++ lines to get to current state.
virtual CbcHeuristicJustOne * clone() const
Clone.
virtual void validate()
Validate model i.e. sets when_ to 0 if necessary (may be NULL)
CbcHeuristicJustOne & operator=(const CbcHeuristicJustOne &rhs)
Assignment operator.
CbcHeuristic ** heuristic_
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 normalizeProbabilities()
Normalize probabilities.
virtual bool selectVariableToBranch(OsiSolverInterface *, const double *, int &, int &)
Selects the next variable to branch on.
CbcHeuristicJustOne(const CbcHeuristicJustOne &)
CbcHeuristicJustOne(CbcModel &model)
void addHeuristic(const CbcHeuristic *heuristic, double probability)
Adds an heuristic with probability.
virtual void setModel(CbcModel *model)
update model (This is needed if cliques update matrix etc)
virtual void resetModel(CbcModel *model)
Resets stuff if model changes.
CbcHeuristicNodeList(const CbcHeuristicNodeList &rhs)
CbcHeuristicNodeList & operator=(const CbcHeuristicNodeList &rhs)
void append(CbcHeuristicNode *&node)
void gutsOfCopy(const CbcHeuristicNodeList &rhs)
void append(const CbcHeuristicNodeList &nodes)
const CbcHeuristicNode * node(int i) const
std::vector< CbcHeuristicNode * > nodes_
A class describing the branching decisions that were made to get to the node where a heuristic was in...
double distance(const CbcHeuristicNode *node) const
CbcBranchingObject ** brObj_
The indices of the branching objects.
CbcHeuristicNode(CbcModel &model)
double minDistance(const CbcHeuristicNodeList &nodeList) const
double avgDistance(const CbcHeuristicNodeList &nodeList) const
CbcHeuristicNode(const CbcHeuristicNode &rhs)
void gutsOfConstructor(CbcModel &model)
int numObjects_
The number of branching decisions made.
CbcHeuristicNode & operator=(const CbcHeuristicNode &)
bool minDistanceIsSmall(const CbcHeuristicNodeList &nodeList, const double threshold) const
Partial solution class If user knows a partial solution this tries to get an integer solution it uses...
virtual void generateCpp(FILE *fp)
Create C++ lines to get to current state.
void setFixPriority(int value)
Set priority level.
CbcHeuristicPartial(const CbcHeuristicPartial &)
virtual bool shouldHeurRun(int whereFrom)
Check whether the heuristic should run at all.
CbcHeuristicPartial(CbcModel &model, int fixPriority=10000, int numberNodes=200)
Constructor with model - assumed before cuts Fixes all variables with priority <= given and does give...
CbcHeuristicPartial & operator=(const CbcHeuristicPartial &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...
virtual void validate()
Validate model i.e. sets when_ to 0 if necessary (may be NULL)
virtual CbcHeuristic * clone() const
Clone.
virtual void resetModel(CbcModel *model)
Resets stuff if model changes.
virtual void setModel(CbcModel *model)
update model (This is needed if cliques update matrix etc)
Heuristic base class.
std::string heuristicName_
Name for printing.
int howOftenShallow_
How often to invoke the heuristics in the shallow part of the tree.
virtual bool canDealWithOdd() const
Returns true if can deal with "odd" problems e.g. sos type 2.
void gutsOfCopy(const CbcHeuristic &rhs)
bool shouldHeurRun_randomChoice()
Check whether the heuristic should run this time.
void setDecayFactor(double value)
Sets decay factor (for howOften) on failure.
double fractionSmall() const
Gets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1....
void printDistanceToNodes()
virtual CbcHeuristic * clone() const =0
Clone.
CbcHeuristic(CbcModel &model)
virtual bool shouldHeurRun(int whereFrom)
Check whether the heuristic should run at all 0 - before cuts at root node (or from doHeuristics) 1 -...
int lastRunDeep_
After how many deep invocations was the heuristic run last time.
void setHeuristicName(const char *name)
set name of heuristic
void setFractionSmall(double value)
Sets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1....
void incrementNumberSolutionsFound()
Increment how many solutions the heuristic thought it got.
int when_
When flag - 0 off, 1 at root, 2 other than root, 3 always.
int switches_
Switches (does not apply equally to all heuristics) 1 bit - stop once allowable gap on objective reac...
int numCouldRun_
How many times the heuristic could run.
const char * heuristicName() const
return name of heuristic
OsiSolverInterface * cloneBut(int type)
Clone, but ...
int shallowDepth_
Upto this depth we call the tree shallow and the heuristic can be called multiple times.
int numRuns() const
how many times the heuristic has actually run
CbcHeuristic & operator=(const CbcHeuristic &rhs)
Assignment operator.
virtual void resetModel(CbcModel *model)=0
Resets stuff if model changes.
int numCouldRun() const
How many times the heuristic could run.
int whereFrom() const
void setWhen(int value)
Sets "when" flag - 0 off, 1 at root, 2 other than root, 3 always.
void setMinDistanceToRun(int value)
How "far" should this node be from every other where the heuristic was run in order to allow the heur...
int numberSolutionsFound_
How many solutions the heuristic thought it got.
virtual void setModel(CbcModel *model)
update model (This is needed if cliques update matrix etc)
double fractionSmall_
Fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound.
void setFeasibilityPumpOptions(int value)
Sets feasibility pump options (-1 is off)
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 numberNodes() const
Gets number of nodes in a subtree (default 200)
void setModelOnly(CbcModel *model)
Just set model - do not do anything else.
void generateCpp(FILE *fp, const char *heuristic)
Create C++ lines to get to current state - does work for base class.
void setInputSolution(const double *solution, double objValue)
Set input solution.
int numRuns_
how many times the heuristic has actually run
void setShallowDepth(int value)
Upto this depth we call the tree shallow and the heuristic can be called multiple times.
void setWhereFrom(int value)
CbcModel * model_
Model.
int numberNodesDone_
How many nodes the heuristic did this go.
int numberNodes_
Number of nodes in any sub tree.
virtual void generateCpp(FILE *)
Create C++ lines to get to current state.
double * inputSolution_
int when() const
Gets "when" flag - 0 off, 1 at root, 2 other than root, 3 always.
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...
double decayFactor_
How much to increase how often.
int feasibilityPumpOptions_
Feasibility pump options , -1 is off >=0 for feasibility pump itself -2 quick proximity search -3 lon...
virtual void validate()
Validate model i.e. sets when_ to 0 if necessary (may be NULL)
CbcHeuristic(const CbcHeuristic &)
int minDistanceToRun_
How "far" should this node be from every other where the heuristic was run in order to allow the heur...
int numInvocationsInDeep_
How many invocations happened when in the deep part of the tree.
void debugNodes()
CoinThreadRandom randomNumberGenerator_
Thread specific random number generator.
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 -...
void setSeed(int value)
Set random number generator seed.
int numberSolutionsFound() const
Get how many solutions the heuristic thought it got.
void gutsOfDelete()
int getSeed() const
Get random number generator seed.
int feasibilityPumpOptions() const
Gets feasibility pump options (-1 is off)
virtual ~CbcHeuristic()
int switches() const
Switches (does not apply equally to all heuristics) 1 bit - stop once allowable gap on objective reac...
int howOften_
How often to do (code can change)
CbcHeuristicNodeList runNodes_
The description of the nodes where this heuristic has been applied.
void setHowOftenShallow(int value)
How often to invoke the heuristics in the shallow part of the tree.
int numInvocationsInShallow_
How many invocations happened within the same node when in a shallow part of the tree.
bool exitNow(double bestObjective) const
Whether to exit at once on gap.
void setSwitches(int value)
Switches (does not apply equally to all heuristics) 1 bit - stop once allowable gap on objective reac...
bool isHeuristicInteger(const OsiSolverInterface *solver, int iColumn)
Is it integer for heuristics?
void setNumberNodes(int value)
Sets number of nodes in subtree (default 200)
Simple Branch and bound class.
Definition: CbcModel.hpp:100
Rounding class.
CoinPackedMatrix matrix_
CbcRounding(const CbcRounding &)
unsigned short * up_
unsigned short * down_
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.
CoinPackedMatrix matrixByRow_
unsigned short * equal_
virtual CbcHeuristic * clone() const
Clone.
void setSeed(int value)
Set seed.
virtual bool shouldHeurRun(int whereFrom)
Check whether the heuristic should run at all 0 - before cuts at root node (or from doHeuristics) 1 -...
CbcRounding(CbcModel &model)
virtual void resetModel(CbcModel *model)
Resets stuff if model changes.
virtual int solution(double &objectiveValue, double *newSolution, double solutionValue)
returns 0 if no solution, 1 if valid solution with better objective value than one passed in Sets sol...
virtual void validate()
Validate model i.e. sets when_ to 0 if necessary (may be NULL)
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...
heuristic - just picks up any good solution found by solver - see OsiBabSolver
virtual void resetModel(CbcModel *model)
Resets stuff if model changes.
virtual int solution(double &objectiveValue, double *newSolution)
returns 0 if no solution, 1 if valid solution.
virtual void generateCpp(FILE *fp)
Create C++ lines to get to current state.
virtual CbcHeuristic * clone() const
Clone.
CbcSerendipity & operator=(const CbcSerendipity &rhs)
Assignment operator.
CbcSerendipity(const CbcSerendipity &)
virtual void setModel(CbcModel *model)
update model
CbcSerendipity(CbcModel &model)