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

Last change on this file since 833 was 833, checked in by forrest, 12 years ago

changes to heuristics and allow collection of more statistics

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 7.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
11class OsiSolverInterface;
12
13class CbcModel;
14
15//#############################################################################
16/** Heuristic base class */
17
18class CbcHeuristic {
19public:
20  // Default Constructor
21  CbcHeuristic ();
22
23  // Constructor with model - assumed before cuts
24  CbcHeuristic (CbcModel & model);
25
26  // Copy constructor
27  CbcHeuristic ( const CbcHeuristic &);
28   
29  virtual ~CbcHeuristic();
30
31  /// Clone
32  virtual CbcHeuristic * clone() const=0;
33
34  /// Assignment operator
35  CbcHeuristic & operator=(const CbcHeuristic& rhs);
36
37  /// update model (This is needed if cliques update matrix etc)
38  virtual void setModel(CbcModel * model);
39 
40  /// Resets stuff if model changes
41  virtual void resetModel(CbcModel * model)=0;
42
43  /** returns 0 if no solution, 1 if valid solution
44      with better objective value than one passed in
45      Sets solution values if good, sets objective value
46      This is called after cuts have been added - so can not add cuts
47  */
48  virtual int solution(double & objectiveValue,
49                       double * newSolution)=0;
50
51  /** returns 0 if no solution, 1 if valid solution, -1 if just
52      returning an estimate of best possible solution
53      with better objective value than one passed in
54      Sets solution values if good, sets objective value (only if nonzero code)
55      This is called at same time as cut generators - so can add cuts
56      Default is do nothing
57  */
58  virtual int solution(double & objectiveValue,
59                       double * newSolution,
60                       OsiCuts & cs) {return 0;}
61
62  /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
63  virtual void validate() {}
64
65  /** Sets "when" flag - 0 off, 1 at root, 2 other than root, 3 always.
66      If 10 added then don't worry if validate says there are funny objects
67      as user knows it will be fine
68  */
69  inline void setWhen(int value)
70  { when_=value;}
71  /// Gets "when" flag - 0 off, 1 at root, 2 other than root, 3 always
72  inline int when() const
73  { return when_;}
74
75  /// Sets number of nodes in subtree (default 200)
76  inline void setNumberNodes(int value)
77  { numberNodes_=value;}
78  /// Gets number of nodes in a subtree (default 200)
79  inline int numberNodes() const
80  { return numberNodes_;}
81  /// Sets feasibility pump options (-1 is off)
82  inline void setFeasibilityPumpOptions(int value)
83  { feasibilityPumpOptions_=value;}
84  /// Gets feasibility pump options (-1 is off)
85  inline int feasibilityPumpOptions() const
86  { return feasibilityPumpOptions_;}
87  /// Just set model - do not do anything else
88  inline void setModelOnly(CbcModel * model)
89  { model_ = model;}
90 
91
92  /// Sets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1.0)
93  inline void setFractionSmall(double value)
94  { fractionSmall_=value;}
95  /// Gets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1.0)
96  inline double fractionSmall() const
97  { return fractionSmall_;}
98
99  /** Do mini branch and bound - return
100      0 not finished - no solution
101      1 not finished - solution
102      2 finished - no solution
103      3 finished - solution
104      (could add global cut if finished)
105  */
106  int smallBranchAndBound(OsiSolverInterface * solver,int numberNodes,
107                          double * newSolution, double & newSolutionValue,
108                          double cutoff , std::string name) const;
109  /// Create C++ lines to get to current state
110  virtual void generateCpp( FILE * fp) {}
111  /// Create C++ lines to get to current state - does work for base class
112  void generateCpp( FILE * fp,const char * heuristic) ;
113  /// Returns true if can deal with "odd" problems e.g. sos type 2
114  virtual bool canDealWithOdd() const
115  { return false;}
116  /// return name of heuristic
117  inline const char *heuristicName() const
118  { return heuristicName_.c_str();}
119  /// set name of heuristic
120  inline void setHeuristicName(const char *name)
121  { heuristicName_ = name;}
122
123protected:
124
125  /// Model
126  CbcModel * model_;
127  /// When flag - 0 off, 1 at root, 2 other than root, 3 always
128  int when_;
129  /// Number of nodes in any sub tree
130  int numberNodes_;
131  /// Feasibility pump options (-1 is off)
132  int feasibilityPumpOptions_;
133  /// Fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound
134  double fractionSmall_;
135  /// Name for printing
136  std::string heuristicName_;
137 
138};
139/** Rounding class
140 */
141
142class CbcRounding : public CbcHeuristic {
143public:
144
145  // Default Constructor
146  CbcRounding ();
147
148  // Constructor with model - assumed before cuts
149  CbcRounding (CbcModel & model);
150 
151  // Copy constructor
152  CbcRounding ( const CbcRounding &);
153   
154  // Destructor
155  ~CbcRounding ();
156 
157  /// Assignment operator
158  CbcRounding & operator=(const CbcRounding& rhs);
159
160  /// Clone
161  virtual CbcHeuristic * clone() const;
162  /// Create C++ lines to get to current state
163  virtual void generateCpp( FILE * fp) ;
164
165  /// Resets stuff if model changes
166  virtual void resetModel(CbcModel * model);
167
168  /// update model (This is needed if cliques update matrix etc)
169  virtual void setModel(CbcModel * model);
170 
171  using CbcHeuristic::solution ;
172  /** returns 0 if no solution, 1 if valid solution
173      with better objective value than one passed in
174      Sets solution values if good, sets objective value (only if good)
175      This is called after cuts have been added - so can not add cuts
176  */
177  virtual int solution(double & objectiveValue,
178                       double * newSolution);
179  /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
180  virtual void validate();
181
182
183  /// Set seed
184  void setSeed(int value)
185  { seed_ = value;}
186
187protected:
188  // Data
189
190  // Original matrix by column
191  CoinPackedMatrix matrix_;
192
193  // Original matrix by
194  CoinPackedMatrix matrixByRow_;
195
196  // Seed for random stuff
197  int seed_;
198};
199
200/** heuristic - just picks up any good solution
201    found by solver - see OsiBabSolver
202 */
203
204class CbcSerendipity : public CbcHeuristic {
205public:
206
207  // Default Constructor
208  CbcSerendipity ();
209
210  /* Constructor with model
211  */
212  CbcSerendipity (CbcModel & model);
213 
214  // Copy constructor
215  CbcSerendipity ( const CbcSerendipity &);
216   
217  // Destructor
218  ~CbcSerendipity ();
219 
220  /// Assignment operator
221  CbcSerendipity & operator=(const CbcSerendipity& rhs);
222
223  /// Clone
224  virtual CbcHeuristic * clone() const;
225  /// Create C++ lines to get to current state
226  virtual void generateCpp( FILE * fp) ;
227
228  /// update model
229  virtual void setModel(CbcModel * model);
230 
231  using CbcHeuristic::solution ;
232  /** returns 0 if no solution, 1 if valid solution.
233      Sets solution values if good, sets objective value (only if good)
234      We leave all variables which are at one at this node of the
235      tree to that value and will
236      initially set all others to zero.  We then sort all variables in order of their cost
237      divided by the number of entries in rows which are not yet covered.  We randomize that
238      value a bit so that ties will be broken in different ways on different runs of the heuristic.
239      We then choose the best one and set it to one and repeat the exercise. 
240
241  */
242  virtual int solution(double & objectiveValue,
243                       double * newSolution);
244  /// Resets stuff if model changes
245  virtual void resetModel(CbcModel * model);
246
247protected:
248};
249
250#endif
Note: See TracBrowser for help on using the repository browser.