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

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

header.

  • 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  void debugNodes();
181
182protected:
183
184  /// Model
185  CbcModel * model_;
186  /// When flag - 0 off, 1 at root, 2 other than root, 3 always
187  int when_;
188  /// Number of nodes in any sub tree
189  int numberNodes_;
190  /// Feasibility pump options (-1 is off)
191  int feasibilityPumpOptions_;
192  /// Fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound
193  double fractionSmall_;
194  /// Thread specific random number generator
195  CoinThreadRandom randomNumberGenerator_;
196  /// Name for printing
197  std::string heuristicName_;
198
199  /// How often to do (code can change)
200  int howOften_;
201  /// How much to increase how often
202  double decayFactor_;
203  /** Upto this depth we call the tree shallow and the heuristic can be called
204      multiple times. That is, the test whether the current node is far from
205      the others where the jeuristic was invoked will not be done, only the
206      frequency will be tested. After that depth the heuristic will can be
207      invoked only once per node, right before branching. That's when it'll be
208      tested whether the heur should run at all. */
209  int shallowDepth_;
210  /** How often to invoke the heuristics in the shallow part of the tree */
211  int howOftenShallow_;
212  /** How many invocations happened within the same node when in a shallow
213      part of the tree. */
214  int numInvocationsInShallow_;
215  /** How many invocations happened when in the deep part of the tree. For
216      every node we count only one invocation. */
217  int numInvocationsInDeep_;
218  /** After how many deep invocations was the heuristic run last time */
219  int lastRunDeep_;
220  /// how many times the heuristic has actually run
221  int numRuns_;
222  /** How "far" should this node be from every other where the heuristic was
223      run in order to allow the heuristic to run in this node, too. Currently
224      this is tested, but we may switch to avgDistanceToRun_ in the future. */
225  int minDistanceToRun_;
226
227  /// The description of the nodes where this heuristic has been applied
228  CbcHeuristicNodeList runNodes_;
229
230#if 0
231  /// Lower bounds of last node where the heuristic found a solution
232  double * lowerBoundLastNode_;
233  /// Upper bounds of last node where the heuristic found a solution
234  double * upperBoundLastNode_;
235#endif
236};
237/** Rounding class
238 */
239
240class CbcRounding : public CbcHeuristic {
241public:
242
243  // Default Constructor
244  CbcRounding ();
245
246  // Constructor with model - assumed before cuts
247  CbcRounding (CbcModel & model);
248 
249  // Copy constructor
250  CbcRounding ( const CbcRounding &);
251   
252  // Destructor
253  ~CbcRounding ();
254 
255  /// Assignment operator
256  CbcRounding & operator=(const CbcRounding& rhs);
257
258  /// Clone
259  virtual CbcHeuristic * clone() const;
260  /// Create C++ lines to get to current state
261  virtual void generateCpp( FILE * fp) ;
262
263  /// Resets stuff if model changes
264  virtual void resetModel(CbcModel * model);
265
266  /// update model (This is needed if cliques update matrix etc)
267  virtual void setModel(CbcModel * model);
268 
269  using CbcHeuristic::solution ;
270  /** returns 0 if no solution, 1 if valid solution
271      with better objective value than one passed in
272      Sets solution values if good, sets objective value (only if good)
273      This is called after cuts have been added - so can not add cuts
274  */
275  virtual int solution(double & objectiveValue,
276                       double * newSolution);
277  /** returns 0 if no solution, 1 if valid solution
278      with better objective value than one passed in
279      Sets solution values if good, sets objective value (only if good)
280      This is called after cuts have been added - so can not add cuts
281      Use solutionValue rather than solvers one
282  */
283  virtual int solution(double & objectiveValue,
284                       double * newSolution,
285                       double solutionValue);
286  /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
287  virtual void validate();
288
289
290  /// Set seed
291  void setSeed(int value)
292  { seed_ = value;}
293
294protected:
295  // Data
296
297  // Original matrix by column
298  CoinPackedMatrix matrix_;
299
300  // Original matrix by
301  CoinPackedMatrix matrixByRow_;
302
303  // Down locks
304  unsigned short * down_;
305
306  // Up locks
307  unsigned short * up_;
308
309  // Equality locks
310  unsigned short * equal_;
311
312  // Seed for random stuff
313  int seed_;
314};
315
316/** Partial solution class
317    If user knows a partial solution this tries to get an integer solution
318    it uses hotstart information
319 */
320
321class CbcHeuristicPartial : public CbcHeuristic {
322public:
323
324  // Default Constructor
325  CbcHeuristicPartial ();
326
327  /** Constructor with model - assumed before cuts
328      Fixes all variables with priority <= given
329      and does given number of nodes
330  */
331  CbcHeuristicPartial (CbcModel & model, int fixPriority=10000, int numberNodes=200);
332 
333  // Copy constructor
334  CbcHeuristicPartial ( const CbcHeuristicPartial &);
335   
336  // Destructor
337  ~CbcHeuristicPartial ();
338 
339  /// Assignment operator
340  CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs);
341
342  /// Clone
343  virtual CbcHeuristic * clone() const;
344  /// Create C++ lines to get to current state
345  virtual void generateCpp( FILE * fp) ;
346
347  /// Resets stuff if model changes
348  virtual void resetModel(CbcModel * model);
349
350  /// update model (This is needed if cliques update matrix etc)
351  virtual void setModel(CbcModel * model);
352 
353  using CbcHeuristic::solution ;
354  /** returns 0 if no solution, 1 if valid solution
355      with better objective value than one passed in
356      Sets solution values if good, sets objective value (only if good)
357      This is called after cuts have been added - so can not add cuts
358  */
359  virtual int solution(double & objectiveValue,
360                       double * newSolution);
361  /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
362  virtual void validate();
363
364
365  /// Set priority level
366  void setFixPriority(int value)
367  { fixPriority_ = value;}
368
369protected:
370  // Data
371
372  // All variables with abs priority <= this will be fixed
373  int fixPriority_;
374};
375
376/** heuristic - just picks up any good solution
377    found by solver - see OsiBabSolver
378 */
379
380class CbcSerendipity : public CbcHeuristic {
381public:
382
383  // Default Constructor
384  CbcSerendipity ();
385
386  /* Constructor with model
387  */
388  CbcSerendipity (CbcModel & model);
389 
390  // Copy constructor
391  CbcSerendipity ( const CbcSerendipity &);
392   
393  // Destructor
394  ~CbcSerendipity ();
395 
396  /// Assignment operator
397  CbcSerendipity & operator=(const CbcSerendipity& rhs);
398
399  /// Clone
400  virtual CbcHeuristic * clone() const;
401  /// Create C++ lines to get to current state
402  virtual void generateCpp( FILE * fp) ;
403
404  /// update model
405  virtual void setModel(CbcModel * model);
406 
407  using CbcHeuristic::solution ;
408  /** returns 0 if no solution, 1 if valid solution.
409      Sets solution values if good, sets objective value (only if good)
410      We leave all variables which are at one at this node of the
411      tree to that value and will
412      initially set all others to zero.  We then sort all variables in order of their cost
413      divided by the number of entries in rows which are not yet covered.  We randomize that
414      value a bit so that ties will be broken in different ways on different runs of the heuristic.
415      We then choose the best one and set it to one and repeat the exercise. 
416
417  */
418  virtual int solution(double & objectiveValue,
419                       double * newSolution);
420  /// Resets stuff if model changes
421  virtual void resetModel(CbcModel * model);
422
423protected:
424};
425
426#endif
Note: See TracBrowser for help on using the repository browser.