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

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

try and make a bit faster

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