source: stable/2.4/Cbc/src/CbcHeuristic.hpp @ 1271

Last change on this file since 1271 was 1271, checked in by forrest, 10 years ago

Creating new stable branch 2.4 from trunk (rev 1270)

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 20.2 KB
Line 
1/* $Id: CbcHeuristic.hpp 1271 2009-11-05 15:57:25Z forrest $ */
2// Copyright (C) 2002, International Business Machines
3// Corporation and others.  All Rights Reserved.
4#ifndef CbcHeuristic_H
5#define CbcHeuristic_H
6
7#include <string>
8#include <vector>
9#include "CoinPackedMatrix.hpp"
10#include "OsiCuts.hpp"
11#include "CoinHelperFunctions.hpp"
12#include "OsiBranchingObject.hpp"
13
14class OsiSolverInterface;
15
16class CbcModel;
17
18//#############################################################################
19
20class CbcHeuristicNodeList;
21class CbcBranchingObject;
22
23/** A class describing the branching decisions that were made to get
24    to the node where a heuristics was invoked from */
25
26class CbcHeuristicNode {
27private:
28  void gutsOfConstructor(CbcModel& model);
29  CbcHeuristicNode();
30  CbcHeuristicNode& operator=(const CbcHeuristicNode&);
31private:
32  /// The number of branching decisions made
33  int numObjects_;
34  /** The indices of the branching objects. Note: an index may be
35      listed multiple times. E.g., a general integer variable that has
36      been branched on multiple times. */
37  CbcBranchingObject** brObj_;
38public:
39  CbcHeuristicNode(CbcModel& model);
40
41  CbcHeuristicNode(const CbcHeuristicNode& rhs);
42  ~CbcHeuristicNode();
43  double distance(const CbcHeuristicNode* node) const;
44  double minDistance(const CbcHeuristicNodeList& nodeList) const;
45  bool minDistanceIsSmall(const CbcHeuristicNodeList& nodeList,
46                          const double threshold) const;
47  double avgDistance(const CbcHeuristicNodeList& nodeList) const;
48};
49
50class CbcHeuristicNodeList {
51private:
52  void gutsOfDelete();
53  void gutsOfCopy(const CbcHeuristicNodeList& rhs);
54private:
55  std::vector<CbcHeuristicNode*> nodes_;
56public:
57  CbcHeuristicNodeList() {}
58  CbcHeuristicNodeList(const CbcHeuristicNodeList& rhs);
59  CbcHeuristicNodeList& operator=(const CbcHeuristicNodeList& rhs);
60  ~CbcHeuristicNodeList();
61 
62  void append(CbcHeuristicNode*& node);
63  void append(const CbcHeuristicNodeList& nodes);
64  inline const CbcHeuristicNode* node(int i) const { return nodes_[i]; }
65  inline int size() const { return nodes_.size(); }
66};
67
68//#############################################################################
69/** Heuristic base class */
70
71class CbcHeuristic {
72private:
73  void gutsOfDelete() {}
74  void gutsOfCopy(const CbcHeuristic & rhs);
75
76public:
77  // Default Constructor
78  CbcHeuristic ();
79
80  // Constructor with model - assumed before cuts
81  CbcHeuristic (CbcModel & model);
82
83  // Copy constructor
84  CbcHeuristic ( const CbcHeuristic &);
85   
86  virtual ~CbcHeuristic();
87
88  /// Clone
89  virtual CbcHeuristic * clone() const=0;
90
91  /// Assignment operator
92  CbcHeuristic & operator=(const CbcHeuristic& rhs);
93
94  /// update model (This is needed if cliques update matrix etc)
95  virtual void setModel(CbcModel * model);
96 
97  /// Resets stuff if model changes
98  virtual void resetModel(CbcModel * model)=0;
99
100  /** returns 0 if no solution, 1 if valid solution
101      with better objective value than one passed in
102      Sets solution values if good, sets objective value
103      This is called after cuts have been added - so can not add cuts
104  */
105  virtual int solution(double & objectiveValue,
106                       double * newSolution)=0;
107
108  /** returns 0 if no solution, 1 if valid solution, -1 if just
109      returning an estimate of best possible solution
110      with better objective value than one passed in
111      Sets solution values if good, sets objective value (only if nonzero code)
112      This is called at same time as cut generators - so can add cuts
113      Default is do nothing
114  */
115  virtual int solution2(double & /*objectiveValue*/,
116                       double * /*newSolution*/,
117                       OsiCuts & /*cs*/) {return 0;}
118
119  /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
120  virtual void validate() {}
121
122  /** Sets "when" flag - 0 off, 1 at root, 2 other than root, 3 always.
123      If 10 added then don't worry if validate says there are funny objects
124      as user knows it will be fine
125  */
126  inline void setWhen(int value)
127  { when_=value;}
128  /// Gets "when" flag - 0 off, 1 at root, 2 other than root, 3 always
129  inline int when() const
130  { return when_;}
131
132  /// Sets number of nodes in subtree (default 200)
133  inline void setNumberNodes(int value)
134  { numberNodes_=value;}
135  /// Gets number of nodes in a subtree (default 200)
136  inline int numberNodes() const
137  { return numberNodes_;}
138  /** Switches (does not apply equally to all heuristics)
139      1 bit - stop once allowable gap on objective reached
140      2 bit - always do given number of passes
141      4 bit - weaken cutoff by 5% every 50 passes?
142      8 bit - if has cutoff and suminf bobbling for 20 passes then
143              first try halving distance to best possible then
144              try keep halving distance to known cutoff
145      1024 bit - stop all heuristics on max time
146  */
147  inline void setSwitches(int value)
148  { switches_ = value;}
149  /** Switches (does not apply equally to all heuristics)
150      1 bit - stop once allowable gap on objective reached
151      2 bit - always do given number of passes
152      4 bit - weaken cutoff by 5% every 50 passes?
153      8 bit - if has cutoff and suminf bobbling for 20 passes then
154              first try halving distance to best possible then
155              try keep halving distance to known cutoff
156      1024 bit - stop all heuristics on max time
157  */
158  inline int switches() const
159  { return switches_;}
160  /// Whether to exit at once on gap
161  bool exitNow(double bestObjective) const;
162  /// Sets feasibility pump options (-1 is off)
163  inline void setFeasibilityPumpOptions(int value)
164  { feasibilityPumpOptions_=value;}
165  /// Gets feasibility pump options (-1 is off)
166  inline int feasibilityPumpOptions() const
167  { return feasibilityPumpOptions_;}
168  /// Just set model - do not do anything else
169  inline void setModelOnly(CbcModel * model)
170  { model_ = model;}
171 
172
173  /// Sets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1.0)
174  inline void setFractionSmall(double value)
175  { fractionSmall_=value;}
176  /// Gets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1.0)
177  inline double fractionSmall() const
178  { return fractionSmall_;}
179  /// Get how many solutions the heuristic thought it got
180  inline int numberSolutionsFound() const
181  { return numberSolutionsFound_;}
182  /// Increment how many solutions the heuristic thought it got
183  inline void incrementNumberSolutionsFound()
184  { numberSolutionsFound_++;}
185
186  /** Do mini branch and bound - return
187      0 not finished - no solution
188      1 not finished - solution
189      2 finished - no solution
190      3 finished - solution
191      (could add global cut if finished)
192      -1 returned on size
193      -2 time or user event
194  */
195  int smallBranchAndBound(OsiSolverInterface * solver,int numberNodes,
196                          double * newSolution, double & newSolutionValue,
197                          double cutoff , std::string name) const;
198  /// Create C++ lines to get to current state
199  virtual void generateCpp( FILE * ) {}
200  /// Create C++ lines to get to current state - does work for base class
201  void generateCpp( FILE * fp,const char * heuristic) ;
202  /// Returns true if can deal with "odd" problems e.g. sos type 2
203  virtual bool canDealWithOdd() const
204  { return false;}
205  /// return name of heuristic
206  inline const char *heuristicName() const
207  { return heuristicName_.c_str();}
208  /// set name of heuristic
209  inline void setHeuristicName(const char *name)
210  { heuristicName_ = name;}
211  /// Set random number generator seed
212  void setSeed(int value);
213  /// Sets decay factor (for howOften) on failure
214  inline void setDecayFactor(double value)
215  { decayFactor_=value;}
216  /// Set input solution
217  void setInputSolution(const double * solution, double objValue);
218  /* Runs if bit set
219      0 - before cuts at root node (or from doHeuristics)
220      1 - during cuts at root
221      2 - after root node cuts
222      3 - after cuts at other nodes
223      4 - during cuts at other nodes
224          8 added if previous heuristic in loop found solution
225   */
226  inline void setWhereFrom(int value)
227  { whereFrom_=value;}
228  /** Upto this depth we call the tree shallow and the heuristic can be called
229      multiple times. That is, the test whether the current node is far from
230      the others where the jeuristic was invoked will not be done, only the
231      frequency will be tested. After that depth the heuristic will can be
232      invoked only once per node, right before branching. That's when it'll be
233      tested whether the heur should run at all. */
234  inline void setShallowDepth(int value)
235  { shallowDepth_=value;}
236  /** How often to invoke the heuristics in the shallow part of the tree */
237  inline void setHowOftenShallow(int value)
238  { howOftenShallow_=value;}
239  /** How "far" should this node be from every other where the heuristic was
240      run in order to allow the heuristic to run in this node, too. Currently
241      this is tested, but we may switch to avgDistanceToRun_ in the future. */
242  inline void setMinDistanceToRun(int value)
243  { minDistanceToRun_=value;}
244
245  /** Check whether the heuristic should run at all
246      0 - before cuts at root node (or from doHeuristics)
247      1 - during cuts at root
248      2 - after root node cuts
249      3 - after cuts at other nodes
250      4 - during cuts at other nodes
251          8 added if previous heuristic in loop found solution
252  */
253  virtual bool shouldHeurRun(int whereFrom);
254  /** Check whether the heuristic should run this time */
255  bool shouldHeurRun_randomChoice();
256  void debugNodes();
257  void printDistanceToNodes();
258  /// how many times the heuristic has actually run
259  inline int numRuns() const
260  { return numRuns_;}
261
262  /// How many times the heuristic could run
263  inline int numCouldRun() const
264  { return numCouldRun_;}
265  /** Clone but ..
266      type 0 clone solver, 1 clone continuous solver
267      Add 2 to say without integer variables which are at low priority
268      Add 4 to say quite likely infeasible so give up easily.*/
269  OsiSolverInterface * cloneBut(int type);
270protected:
271
272  /// Model
273  CbcModel * model_;
274  /// When flag - 0 off, 1 at root, 2 other than root, 3 always
275  int when_;
276  /// Number of nodes in any sub tree
277  int numberNodes_;
278  /// Feasibility pump options (-1 is off)
279  int feasibilityPumpOptions_;
280  /// Fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound
281  mutable double fractionSmall_;
282  /// Thread specific random number generator
283  CoinThreadRandom randomNumberGenerator_;
284  /// Name for printing
285  std::string heuristicName_;
286
287  /// How often to do (code can change)
288  int howOften_;
289  /// How much to increase how often
290  double decayFactor_;
291  /** Switches (does not apply equally to all heuristics)
292      1 bit - stop once allowable gap on objective reached
293      2 bit - always do given number of passes
294      4 bit - weaken cutoff by 5% every 50 passes?
295      8 bit - if has cutoff and suminf bobbling for 20 passes then
296              first try halving distance to best possible then
297              try keep halving distance to known cutoff
298      1024 bit - stop all heuristics on max time
299  */
300  mutable int switches_;
301  /* Runs if bit set
302      0 - before cuts at root node (or from doHeuristics)
303      1 - during cuts at root
304      2 - after root node cuts
305      3 - after cuts at other nodes
306      4 - during cuts at other nodes
307          8 added if previous heuristic in loop found solution
308   */
309  int whereFrom_;
310  /** Upto this depth we call the tree shallow and the heuristic can be called
311      multiple times. That is, the test whether the current node is far from
312      the others where the jeuristic was invoked will not be done, only the
313      frequency will be tested. After that depth the heuristic will can be
314      invoked only once per node, right before branching. That's when it'll be
315      tested whether the heur should run at all. */
316  int shallowDepth_;
317  /** How often to invoke the heuristics in the shallow part of the tree */
318  int howOftenShallow_;
319  /** How many invocations happened within the same node when in a shallow
320      part of the tree. */
321  int numInvocationsInShallow_;
322  /** How many invocations happened when in the deep part of the tree. For
323      every node we count only one invocation. */
324  int numInvocationsInDeep_;
325  /** After how many deep invocations was the heuristic run last time */
326  int lastRunDeep_;
327  /// how many times the heuristic has actually run
328  int numRuns_;
329  /** How "far" should this node be from every other where the heuristic was
330      run in order to allow the heuristic to run in this node, too. Currently
331      this is tested, but we may switch to avgDistanceToRun_ in the future. */
332  int minDistanceToRun_;
333
334  /// The description of the nodes where this heuristic has been applied
335  CbcHeuristicNodeList runNodes_;
336
337  /// How many times the heuristic could run
338  int numCouldRun_;
339
340  /// How many solutions the heuristic thought it got
341  int numberSolutionsFound_;
342
343  // Input solution - so can be used as seed
344  double * inputSolution_;
345
346
347#if 0
348  /// Lower bounds of last node where the heuristic found a solution
349  double * lowerBoundLastNode_;
350  /// Upper bounds of last node where the heuristic found a solution
351  double * upperBoundLastNode_;
352#endif
353};
354/** Rounding class
355 */
356
357class CbcRounding : public CbcHeuristic {
358public:
359
360  // Default Constructor
361  CbcRounding ();
362
363  // Constructor with model - assumed before cuts
364  CbcRounding (CbcModel & model);
365 
366  // Copy constructor
367  CbcRounding ( const CbcRounding &);
368   
369  // Destructor
370  ~CbcRounding ();
371 
372  /// Assignment operator
373  CbcRounding & operator=(const CbcRounding& rhs);
374
375  /// Clone
376  virtual CbcHeuristic * clone() const;
377  /// Create C++ lines to get to current state
378  virtual void generateCpp( FILE * fp) ;
379
380  /// Resets stuff if model changes
381  virtual void resetModel(CbcModel * model);
382
383  /// update model (This is needed if cliques update matrix etc)
384  virtual void setModel(CbcModel * model);
385 
386  using CbcHeuristic::solution ;
387  /** returns 0 if no solution, 1 if valid solution
388      with better objective value than one passed in
389      Sets solution values if good, sets objective value (only if good)
390      This is called after cuts have been added - so can not add cuts
391  */
392  virtual int solution(double & objectiveValue,
393                       double * newSolution);
394  /** returns 0 if no solution, 1 if valid solution
395      with better objective value than one passed in
396      Sets solution values if good, sets objective value (only if good)
397      This is called after cuts have been added - so can not add cuts
398      Use solutionValue rather than solvers one
399  */
400  virtual int solution(double & objectiveValue,
401                       double * newSolution,
402                       double solutionValue);
403  /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
404  virtual void validate();
405
406
407  /// Set seed
408  void setSeed(int value)
409  { seed_ = value;}
410
411protected:
412  // Data
413
414  // Original matrix by column
415  CoinPackedMatrix matrix_;
416
417  // Original matrix by
418  CoinPackedMatrix matrixByRow_;
419
420  // Down locks
421  unsigned short * down_;
422
423  // Up locks
424  unsigned short * up_;
425
426  // Equality locks
427  unsigned short * equal_;
428
429  // Seed for random stuff
430  int seed_;
431};
432
433/** Partial solution class
434    If user knows a partial solution this tries to get an integer solution
435    it uses hotstart information
436 */
437
438class CbcHeuristicPartial : public CbcHeuristic {
439public:
440
441  // Default Constructor
442  CbcHeuristicPartial ();
443
444  /** Constructor with model - assumed before cuts
445      Fixes all variables with priority <= given
446      and does given number of nodes
447  */
448  CbcHeuristicPartial (CbcModel & model, int fixPriority=10000, int numberNodes=200);
449 
450  // Copy constructor
451  CbcHeuristicPartial ( const CbcHeuristicPartial &);
452   
453  // Destructor
454  ~CbcHeuristicPartial ();
455 
456  /// Assignment operator
457  CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs);
458
459  /// Clone
460  virtual CbcHeuristic * clone() const;
461  /// Create C++ lines to get to current state
462  virtual void generateCpp( FILE * fp) ;
463
464  /// Resets stuff if model changes
465  virtual void resetModel(CbcModel * model);
466
467  /// update model (This is needed if cliques update matrix etc)
468  virtual void setModel(CbcModel * model);
469 
470  using CbcHeuristic::solution ;
471  /** returns 0 if no solution, 1 if valid solution
472      with better objective value than one passed in
473      Sets solution values if good, sets objective value (only if good)
474      This is called after cuts have been added - so can not add cuts
475  */
476  virtual int solution(double & objectiveValue,
477                       double * newSolution);
478  /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
479  virtual void validate();
480
481
482  /// Set priority level
483  void setFixPriority(int value)
484  { fixPriority_ = value;}
485
486  /** Check whether the heuristic should run at all */
487  virtual bool shouldHeurRun(int whereFrom);
488
489protected:
490  // Data
491
492  // All variables with abs priority <= this will be fixed
493  int fixPriority_;
494};
495
496/** heuristic - just picks up any good solution
497    found by solver - see OsiBabSolver
498 */
499
500class CbcSerendipity : public CbcHeuristic {
501public:
502
503  // Default Constructor
504  CbcSerendipity ();
505
506  /* Constructor with model
507  */
508  CbcSerendipity (CbcModel & model);
509 
510  // Copy constructor
511  CbcSerendipity ( const CbcSerendipity &);
512   
513  // Destructor
514  ~CbcSerendipity ();
515 
516  /// Assignment operator
517  CbcSerendipity & operator=(const CbcSerendipity& rhs);
518
519  /// Clone
520  virtual CbcHeuristic * clone() const;
521  /// Create C++ lines to get to current state
522  virtual void generateCpp( FILE * fp) ;
523
524  /// update model
525  virtual void setModel(CbcModel * model);
526 
527  using CbcHeuristic::solution ;
528  /** returns 0 if no solution, 1 if valid solution.
529      Sets solution values if good, sets objective value (only if good)
530      We leave all variables which are at one at this node of the
531      tree to that value and will
532      initially set all others to zero.  We then sort all variables in order of their cost
533      divided by the number of entries in rows which are not yet covered.  We randomize that
534      value a bit so that ties will be broken in different ways on different runs of the heuristic.
535      We then choose the best one and set it to one and repeat the exercise. 
536
537  */
538  virtual int solution(double & objectiveValue,
539                       double * newSolution);
540  /// Resets stuff if model changes
541  virtual void resetModel(CbcModel * model);
542
543protected:
544};
545
546/** Just One class - this chooses one at random
547 */
548
549class CbcHeuristicJustOne : public CbcHeuristic {
550public:
551
552  // Default Constructor
553  CbcHeuristicJustOne ();
554
555  // Constructor with model - assumed before cuts
556  CbcHeuristicJustOne (CbcModel & model);
557 
558  // Copy constructor
559  CbcHeuristicJustOne ( const CbcHeuristicJustOne &);
560   
561  // Destructor
562  ~CbcHeuristicJustOne ();
563
564  /// Clone
565  virtual CbcHeuristicJustOne * clone() const;
566 
567  /// Assignment operator
568  CbcHeuristicJustOne & operator=(const CbcHeuristicJustOne& rhs);
569
570  /// Create C++ lines to get to current state
571  virtual void generateCpp( FILE * fp) ;
572
573  /** returns 0 if no solution, 1 if valid solution
574      with better objective value than one passed in
575      Sets solution values if good, sets objective value (only if good)
576      This is called after cuts have been added - so can not add cuts
577      This does Fractional Diving
578  */
579  virtual int solution(double & objectiveValue,
580                       double * newSolution);
581  /// Resets stuff if model changes
582  virtual void resetModel(CbcModel * model);
583
584  /// update model (This is needed if cliques update matrix etc)
585  virtual void setModel(CbcModel * model);
586  /// Selects the next variable to branch on
587  /** Returns true if all the fractional variables can be trivially
588      rounded. Returns false, if there is at least one fractional variable
589      that is not trivially roundable. In this case, the bestColumn
590      returned will not be trivially roundable.
591      This is dummy as never called
592  */
593  virtual bool selectVariableToBranch(OsiSolverInterface* /*solver*/,
594                                      const double* /*newSolution*/,
595                                      int& /*bestColumn*/,
596                                      int& /*bestRound*/) 
597  { return true;}
598  /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
599  virtual void validate();
600  /// Adds an heuristic with probability
601  void addHeuristic(const CbcHeuristic * heuristic, double probability);
602  /// Normalize probabilities
603  void normalizeProbabilities();
604protected:
605  // Data
606
607  // Probability of running a heuristic
608  double * probabilities_;
609
610  // Heuristics
611  CbcHeuristic ** heuristic_;
612
613  // Number of heuristics
614  int numberHeuristics_;
615
616};
617
618#endif
Note: See TracBrowser for help on using the repository browser.