source: stable/2.0/Cbc/src/CbcHeuristic.hpp @ 844

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

make useSolution work better

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 8.7 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/** Partial solution class
193    If user knows a partial solution this tries to get an integer solution
194    it uses hotstart information
195 */
196
197class CbcHeuristicPartial : public CbcHeuristic {
198public:
199
200  // Default Constructor
201  CbcHeuristicPartial ();
202
203  /** Constructor with model - assumed before cuts
204      Fixes all variables with priority <= given
205      and does given number of nodes
206  */
207  CbcHeuristicPartial (CbcModel & model, int fixPriority=10000, int numberNodes=200);
208 
209  // Copy constructor
210  CbcHeuristicPartial ( const CbcHeuristicPartial &);
211   
212  // Destructor
213  ~CbcHeuristicPartial ();
214 
215  /// Assignment operator
216  CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs);
217
218  /// Clone
219  virtual CbcHeuristic * clone() const;
220  /// Create C++ lines to get to current state
221  virtual void generateCpp( FILE * fp) ;
222
223  /// Resets stuff if model changes
224  virtual void resetModel(CbcModel * model);
225
226  /// update model (This is needed if cliques update matrix etc)
227  virtual void setModel(CbcModel * model);
228 
229  using CbcHeuristic::solution ;
230  /** returns 0 if no solution, 1 if valid solution
231      with better objective value than one passed in
232      Sets solution values if good, sets objective value (only if good)
233      This is called after cuts have been added - so can not add cuts
234  */
235  virtual int solution(double & objectiveValue,
236                       double * newSolution);
237  /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
238  virtual void validate();
239
240
241  /// Set priority level
242  void setFixPriority(int value)
243  { fixPriority_ = value;}
244
245protected:
246  // Data
247
248  // All variables with abs priority <= this will be fixed
249  int fixPriority_;
250};
251
252/** heuristic - just picks up any good solution
253    found by solver - see OsiBabSolver
254 */
255
256class CbcSerendipity : public CbcHeuristic {
257public:
258
259  // Default Constructor
260  CbcSerendipity ();
261
262  /* Constructor with model
263  */
264  CbcSerendipity (CbcModel & model);
265 
266  // Copy constructor
267  CbcSerendipity ( const CbcSerendipity &);
268   
269  // Destructor
270  ~CbcSerendipity ();
271 
272  /// Assignment operator
273  CbcSerendipity & operator=(const CbcSerendipity& rhs);
274
275  /// Clone
276  virtual CbcHeuristic * clone() const;
277  /// Create C++ lines to get to current state
278  virtual void generateCpp( FILE * fp) ;
279
280  /// update model
281  virtual void setModel(CbcModel * model);
282 
283  using CbcHeuristic::solution ;
284  /** returns 0 if no solution, 1 if valid solution.
285      Sets solution values if good, sets objective value (only if good)
286      We leave all variables which are at one at this node of the
287      tree to that value and will
288      initially set all others to zero.  We then sort all variables in order of their cost
289      divided by the number of entries in rows which are not yet covered.  We randomize that
290      value a bit so that ties will be broken in different ways on different runs of the heuristic.
291      We then choose the best one and set it to one and repeat the exercise. 
292
293  */
294  virtual int solution(double & objectiveValue,
295                       double * newSolution);
296  /// Resets stuff if model changes
297  virtual void resetModel(CbcModel * model);
298
299protected:
300};
301
302#endif
Note: See TracBrowser for help on using the repository browser.