source: branches/devel/Cbc/src/CbcHeuristic.hpp @ 607

Last change on this file since 607 was 607, checked in by lou, 13 years ago

Add names for heuristic, analogous to names for cut generators.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 6.9 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
82  /// Sets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1.0)
83  inline void setFractionSmall(double value)
84  { fractionSmall_=value;};
85  /// Gets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1.0)
86  inline double fractionSmall() const
87  { return fractionSmall_;};
88
89  /** Do mini branch and bound - return
90      0 not finished - no solution
91      1 not finished - solution
92      2 finished - no solution
93      3 finished - solution
94      (could add global cut if finished)
95  */
96  int smallBranchAndBound(OsiSolverInterface * solver,int numberNodes,
97                          double * newSolution, double & newSolutionValue,
98                          double cutoff , std::string name) const;
99  /// Create C++ lines to get to current state
100  virtual void generateCpp( FILE * fp) {};
101  /// Create C++ lines to get to current state - does work for base class
102  void generateCpp( FILE * fp,const char * heuristic) ;
103  /// Returns true if can deal with "odd" problems e.g. sos type 2
104  virtual bool canDealWithOdd() const
105  { return false;};
106  /// return name of heuristic
107  inline const char *heuristicName() const
108  { return heuristicName_.c_str();};
109  /// set name of heuristic
110  inline void setHeuristicName(const char *name)
111  { heuristicName_ = name;};
112
113protected:
114
115  /// Model
116  CbcModel * model_;
117  /// When flag - 0 off, 1 at root, 2 other than root, 3 always
118  int when_;
119  /// Number of nodes in any sub tree
120  int numberNodes_;
121  /// Fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound
122  double fractionSmall_;
123  /// Name for printing
124  std::string heuristicName_;
125 
126};
127/** Rounding class
128 */
129
130class CbcRounding : public CbcHeuristic {
131public:
132
133  // Default Constructor
134  CbcRounding ();
135
136  // Constructor with model - assumed before cuts
137  CbcRounding (CbcModel & model);
138 
139  // Copy constructor
140  CbcRounding ( const CbcRounding &);
141   
142  // Destructor
143  ~CbcRounding ();
144 
145  /// Assignment operator
146  CbcRounding & operator=(const CbcRounding& rhs);
147
148  /// Clone
149  virtual CbcHeuristic * clone() const;
150  /// Create C++ lines to get to current state
151  virtual void generateCpp( FILE * fp) ;
152
153  /// Resets stuff if model changes
154  virtual void resetModel(CbcModel * model);
155
156  /// update model (This is needed if cliques update matrix etc)
157  virtual void setModel(CbcModel * model);
158 
159  /** returns 0 if no solution, 1 if valid solution
160      with better objective value than one passed in
161      Sets solution values if good, sets objective value (only if good)
162      This is called after cuts have been added - so can not add cuts
163  */
164  virtual int solution(double & objectiveValue,
165                       double * newSolution);
166  /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
167  virtual void validate();
168
169
170  /// Set seed
171  void setSeed(int value)
172  { seed_ = value;};
173
174protected:
175  // Data
176
177  // Original matrix by column
178  CoinPackedMatrix matrix_;
179
180  // Original matrix by
181  CoinPackedMatrix matrixByRow_;
182
183  // Seed for random stuff
184  int seed_;
185};
186
187/** heuristic - just picks up any good solution
188    found by solver - see OsiBabSolver
189 */
190
191class CbcSerendipity : public CbcHeuristic {
192public:
193
194  // Default Constructor
195  CbcSerendipity ();
196
197  /* Constructor with model
198  */
199  CbcSerendipity (CbcModel & model);
200 
201  // Copy constructor
202  CbcSerendipity ( const CbcSerendipity &);
203   
204  // Destructor
205  ~CbcSerendipity ();
206 
207  /// Assignment operator
208  CbcSerendipity & operator=(const CbcSerendipity& rhs);
209
210  /// Clone
211  virtual CbcHeuristic * clone() const;
212  /// Create C++ lines to get to current state
213  virtual void generateCpp( FILE * fp) ;
214
215  /// update model
216  virtual void setModel(CbcModel * model);
217 
218  /** returns 0 if no solution, 1 if valid solution.
219      Sets solution values if good, sets objective value (only if good)
220      We leave all variables which are at one at this node of the
221      tree to that value and will
222      initially set all others to zero.  We then sort all variables in order of their cost
223      divided by the number of entries in rows which are not yet covered.  We randomize that
224      value a bit so that ties will be broken in different ways on different runs of the heuristic.
225      We then choose the best one and set it to one and repeat the exercise. 
226
227  */
228  virtual int solution(double & objectiveValue,
229                       double * newSolution);
230  /// Resets stuff if model changes
231  virtual void resetModel(CbcModel * model);
232
233protected:
234};
235
236#endif
Note: See TracBrowser for help on using the repository browser.