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

Last change on this file since 765 was 765, checked in by andreasw, 14 years ago

merging changes from Bug Squashing Party Aug 2007 to regular trunk

  • 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  using CbcHeuristic::solution ;
164  /** returns 0 if no solution, 1 if valid solution
165      with better objective value than one passed in
166      Sets solution values if good, sets objective value (only if good)
167      This is called after cuts have been added - so can not add cuts
168  */
169  virtual int solution(double & objectiveValue,
170                       double * newSolution);
171  /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
172  virtual void validate();
173
174
175  /// Set seed
176  void setSeed(int value)
177  { seed_ = value;}
178
179protected:
180  // Data
181
182  // Original matrix by column
183  CoinPackedMatrix matrix_;
184
185  // Original matrix by
186  CoinPackedMatrix matrixByRow_;
187
188  // Seed for random stuff
189  int seed_;
190};
191
192/** heuristic - just picks up any good solution
193    found by solver - see OsiBabSolver
194 */
195
196class CbcSerendipity : public CbcHeuristic {
197public:
198
199  // Default Constructor
200  CbcSerendipity ();
201
202  /* Constructor with model
203  */
204  CbcSerendipity (CbcModel & model);
205 
206  // Copy constructor
207  CbcSerendipity ( const CbcSerendipity &);
208   
209  // Destructor
210  ~CbcSerendipity ();
211 
212  /// Assignment operator
213  CbcSerendipity & operator=(const CbcSerendipity& rhs);
214
215  /// Clone
216  virtual CbcHeuristic * clone() const;
217  /// Create C++ lines to get to current state
218  virtual void generateCpp( FILE * fp) ;
219
220  /// update model
221  virtual void setModel(CbcModel * model);
222 
223  using CbcHeuristic::solution ;
224  /** returns 0 if no solution, 1 if valid solution.
225      Sets solution values if good, sets objective value (only if good)
226      We leave all variables which are at one at this node of the
227      tree to that value and will
228      initially set all others to zero.  We then sort all variables in order of their cost
229      divided by the number of entries in rows which are not yet covered.  We randomize that
230      value a bit so that ties will be broken in different ways on different runs of the heuristic.
231      We then choose the best one and set it to one and repeat the exercise. 
232
233  */
234  virtual int solution(double & objectiveValue,
235                       double * newSolution);
236  /// Resets stuff if model changes
237  virtual void resetModel(CbcModel * model);
238
239protected:
240};
241
242#endif
Note: See TracBrowser for help on using the repository browser.