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

Last change on this file since 838 was 838, checked in by forrest, 13 years ago

for deterministic parallel

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