source: trunk/Cbc/src/CbcHeuristic.hpp @ 1127

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

changes to fpump

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