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

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

update branches/devel for threads

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