source: branches/heur/Cbc/src/CbcHeuristic.hpp @ 891

Last change on this file since 891 was 891, checked in by jpgoncal, 13 years ago

Added gutsOfConstructor in CbcHeuristicNode?.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 13.1 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  CbcHeuristicNode(const CbcHeuristicNode& rhs);
40  ~CbcHeuristicNode();
41  double distance(const CbcHeuristicNode* node) const;
42  double minDistance(const CbcHeuristicNodeList& nodeList);
43  double avgDistance(const CbcHeuristicNodeList& nodeList);
44};
45
46class CbcHeuristicNodeList {
47private:
48  void gutsOfDelete();
49  void gutsOfCopy(const CbcHeuristicNodeList& rhs);
50private:
51  std::vector<CbcHeuristicNode*> nodes_;
52public:
53  CbcHeuristicNodeList() {}
54  CbcHeuristicNodeList(const CbcHeuristicNodeList& rhs);
55  CbcHeuristicNodeList& operator=(const CbcHeuristicNodeList& rhs);
56  ~CbcHeuristicNodeList();
57 
58  void append(CbcHeuristicNode*& node);
59  void append(const CbcHeuristicNodeList& nodes);
60  inline const CbcHeuristicNode* node(int i) const { return nodes_[i]; }
61  inline int size() const { return nodes_.size(); }
62};
63
64//#############################################################################
65/** Heuristic base class */
66
67class CbcHeuristic {
68private:
69  void gutsOfDelete() {}
70  void gutsOfCopy(const CbcHeuristic & rhs);
71
72public:
73  // Default Constructor
74  CbcHeuristic ();
75
76  // Constructor with model - assumed before cuts
77  CbcHeuristic (CbcModel & model);
78
79  // Copy constructor
80  CbcHeuristic ( const CbcHeuristic &);
81   
82  virtual ~CbcHeuristic();
83
84  /// Clone
85  virtual CbcHeuristic * clone() const=0;
86
87  /// Assignment operator
88  CbcHeuristic & operator=(const CbcHeuristic& rhs);
89
90  /// update model (This is needed if cliques update matrix etc)
91  virtual void setModel(CbcModel * model);
92 
93  /// Resets stuff if model changes
94  virtual void resetModel(CbcModel * model)=0;
95
96  /** returns 0 if no solution, 1 if valid solution
97      with better objective value than one passed in
98      Sets solution values if good, sets objective value
99      This is called after cuts have been added - so can not add cuts
100  */
101  virtual int solution(double & objectiveValue,
102                       double * newSolution)=0;
103
104  /** returns 0 if no solution, 1 if valid solution, -1 if just
105      returning an estimate of best possible solution
106      with better objective value than one passed in
107      Sets solution values if good, sets objective value (only if nonzero code)
108      This is called at same time as cut generators - so can add cuts
109      Default is do nothing
110  */
111  virtual int solution(double & objectiveValue,
112                       double * newSolution,
113                       OsiCuts & cs) {return 0;}
114
115  /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
116  virtual void validate() {}
117
118  /** Sets "when" flag - 0 off, 1 at root, 2 other than root, 3 always.
119      If 10 added then don't worry if validate says there are funny objects
120      as user knows it will be fine
121  */
122  inline void setWhen(int value)
123  { when_=value;}
124  /// Gets "when" flag - 0 off, 1 at root, 2 other than root, 3 always
125  inline int when() const
126  { return when_;}
127
128  /// Sets number of nodes in subtree (default 200)
129  inline void setNumberNodes(int value)
130  { numberNodes_=value;}
131  /// Gets number of nodes in a subtree (default 200)
132  inline int numberNodes() const
133  { return numberNodes_;}
134  /// Sets feasibility pump options (-1 is off)
135  inline void setFeasibilityPumpOptions(int value)
136  { feasibilityPumpOptions_=value;}
137  /// Gets feasibility pump options (-1 is off)
138  inline int feasibilityPumpOptions() const
139  { return feasibilityPumpOptions_;}
140  /// Just set model - do not do anything else
141  inline void setModelOnly(CbcModel * model)
142  { model_ = model;}
143 
144
145  /// Sets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1.0)
146  inline void setFractionSmall(double value)
147  { fractionSmall_=value;}
148  /// Gets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1.0)
149  inline double fractionSmall() const
150  { return fractionSmall_;}
151
152  /** Do mini branch and bound - return
153      0 not finished - no solution
154      1 not finished - solution
155      2 finished - no solution
156      3 finished - solution
157      (could add global cut if finished)
158  */
159  int smallBranchAndBound(OsiSolverInterface * solver,int numberNodes,
160                          double * newSolution, double & newSolutionValue,
161                          double cutoff , std::string name) const;
162  /// Create C++ lines to get to current state
163  virtual void generateCpp( FILE * fp) {}
164  /// Create C++ lines to get to current state - does work for base class
165  void generateCpp( FILE * fp,const char * heuristic) ;
166  /// Returns true if can deal with "odd" problems e.g. sos type 2
167  virtual bool canDealWithOdd() const
168  { return false;}
169  /// return name of heuristic
170  inline const char *heuristicName() const
171  { return heuristicName_.c_str();}
172  /// set name of heuristic
173  inline void setHeuristicName(const char *name)
174  { heuristicName_ = name;}
175  /// Set random number generator seed
176  void setSeed(int value);
177
178  /** Check whether the heuristic should run */
179  bool shouldHeurRun();
180
181protected:
182
183  /// Model
184  CbcModel * model_;
185  /// When flag - 0 off, 1 at root, 2 other than root, 3 always
186  int when_;
187  /// Number of nodes in any sub tree
188  int numberNodes_;
189  /// Feasibility pump options (-1 is off)
190  int feasibilityPumpOptions_;
191  /// Fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound
192  double fractionSmall_;
193  /// Thread specific random number generator
194  CoinThreadRandom randomNumberGenerator_;
195  /// Name for printing
196  std::string heuristicName_;
197
198  /// How often to do (code can change)
199  int howOften_;
200  /// How much to increase how often
201  double decayFactor_;
202  /** Upto this depth we call the tree shallow and the heuristic can be called
203      multiple times. That is, the test whether the current node is far from
204      the others where the jeuristic was invoked will not be done, only the
205      frequency will be tested. After that depth the heuristic will can be
206      invoked only once per node, right before branching. That's when it'll be
207      tested whether the heur should run at all. */
208  int shallowDepth_;
209  /** How often to invoke the heuristics in the shallow part of the tree */
210  int howOftenShallow_;
211  /** How many invocations happened within the same node when in a shallow
212      part of the tree. */
213  int numInvocationsInShallow_;
214  /** How many invocations happened when in the deep part of the tree. For
215      every node we count only one invocation. */
216  int numInvocationsInDeep_;
217  /** After how many deep invocations was the heuristic run last time */
218  int lastRunDeep_;
219  /// how many times the heuristic has actually run
220  int numRuns_;
221  /** How "far" should this node be from every other where the heuristic was
222      run in order to allow the heuristic to run in this node, too. Currently
223      this is tested, but we may switch to avgDistanceToRun_ in the future. */
224  int minDistanceToRun_;
225
226  /// The description of the nodes where this heuristic has been applied
227  CbcHeuristicNodeList runNodes_;
228
229#if 0
230  /// Lower bounds of last node where the heuristic found a solution
231  double * lowerBoundLastNode_;
232  /// Upper bounds of last node where the heuristic found a solution
233  double * upperBoundLastNode_;
234#endif
235};
236/** Rounding class
237 */
238
239class CbcRounding : public CbcHeuristic {
240public:
241
242  // Default Constructor
243  CbcRounding ();
244
245  // Constructor with model - assumed before cuts
246  CbcRounding (CbcModel & model);
247 
248  // Copy constructor
249  CbcRounding ( const CbcRounding &);
250   
251  // Destructor
252  ~CbcRounding ();
253 
254  /// Assignment operator
255  CbcRounding & operator=(const CbcRounding& rhs);
256
257  /// Clone
258  virtual CbcHeuristic * clone() const;
259  /// Create C++ lines to get to current state
260  virtual void generateCpp( FILE * fp) ;
261
262  /// Resets stuff if model changes
263  virtual void resetModel(CbcModel * model);
264
265  /// update model (This is needed if cliques update matrix etc)
266  virtual void setModel(CbcModel * model);
267 
268  using CbcHeuristic::solution ;
269  /** returns 0 if no solution, 1 if valid solution
270      with better objective value than one passed in
271      Sets solution values if good, sets objective value (only if good)
272      This is called after cuts have been added - so can not add cuts
273  */
274  virtual int solution(double & objectiveValue,
275                       double * newSolution);
276  /** returns 0 if no solution, 1 if valid solution
277      with better objective value than one passed in
278      Sets solution values if good, sets objective value (only if good)
279      This is called after cuts have been added - so can not add cuts
280      Use solutionValue rather than solvers one
281  */
282  virtual int solution(double & objectiveValue,
283                       double * newSolution,
284                       double solutionValue);
285  /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
286  virtual void validate();
287
288
289  /// Set seed
290  void setSeed(int value)
291  { seed_ = value;}
292
293protected:
294  // Data
295
296  // Original matrix by column
297  CoinPackedMatrix matrix_;
298
299  // Original matrix by
300  CoinPackedMatrix matrixByRow_;
301
302  // Down locks
303  unsigned short * down_;
304
305  // Up locks
306  unsigned short * up_;
307
308  // Equality locks
309  unsigned short * equal_;
310
311  // Seed for random stuff
312  int seed_;
313};
314
315/** Partial solution class
316    If user knows a partial solution this tries to get an integer solution
317    it uses hotstart information
318 */
319
320class CbcHeuristicPartial : public CbcHeuristic {
321public:
322
323  // Default Constructor
324  CbcHeuristicPartial ();
325
326  /** Constructor with model - assumed before cuts
327      Fixes all variables with priority <= given
328      and does given number of nodes
329  */
330  CbcHeuristicPartial (CbcModel & model, int fixPriority=10000, int numberNodes=200);
331 
332  // Copy constructor
333  CbcHeuristicPartial ( const CbcHeuristicPartial &);
334   
335  // Destructor
336  ~CbcHeuristicPartial ();
337 
338  /// Assignment operator
339  CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs);
340
341  /// Clone
342  virtual CbcHeuristic * clone() const;
343  /// Create C++ lines to get to current state
344  virtual void generateCpp( FILE * fp) ;
345
346  /// Resets stuff if model changes
347  virtual void resetModel(CbcModel * model);
348
349  /// update model (This is needed if cliques update matrix etc)
350  virtual void setModel(CbcModel * model);
351 
352  using CbcHeuristic::solution ;
353  /** returns 0 if no solution, 1 if valid solution
354      with better objective value than one passed in
355      Sets solution values if good, sets objective value (only if good)
356      This is called after cuts have been added - so can not add cuts
357  */
358  virtual int solution(double & objectiveValue,
359                       double * newSolution);
360  /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
361  virtual void validate();
362
363
364  /// Set priority level
365  void setFixPriority(int value)
366  { fixPriority_ = value;}
367
368protected:
369  // Data
370
371  // All variables with abs priority <= this will be fixed
372  int fixPriority_;
373};
374
375/** heuristic - just picks up any good solution
376    found by solver - see OsiBabSolver
377 */
378
379class CbcSerendipity : public CbcHeuristic {
380public:
381
382  // Default Constructor
383  CbcSerendipity ();
384
385  /* Constructor with model
386  */
387  CbcSerendipity (CbcModel & model);
388 
389  // Copy constructor
390  CbcSerendipity ( const CbcSerendipity &);
391   
392  // Destructor
393  ~CbcSerendipity ();
394 
395  /// Assignment operator
396  CbcSerendipity & operator=(const CbcSerendipity& rhs);
397
398  /// Clone
399  virtual CbcHeuristic * clone() const;
400  /// Create C++ lines to get to current state
401  virtual void generateCpp( FILE * fp) ;
402
403  /// update model
404  virtual void setModel(CbcModel * model);
405 
406  using CbcHeuristic::solution ;
407  /** returns 0 if no solution, 1 if valid solution.
408      Sets solution values if good, sets objective value (only if good)
409      We leave all variables which are at one at this node of the
410      tree to that value and will
411      initially set all others to zero.  We then sort all variables in order of their cost
412      divided by the number of entries in rows which are not yet covered.  We randomize that
413      value a bit so that ties will be broken in different ways on different runs of the heuristic.
414      We then choose the best one and set it to one and repeat the exercise. 
415
416  */
417  virtual int solution(double & objectiveValue,
418                       double * newSolution);
419  /// Resets stuff if model changes
420  virtual void resetModel(CbcModel * model);
421
422protected:
423};
424
425#endif
Note: See TracBrowser for help on using the repository browser.