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

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

add CoinHelperFunctions?.hpp

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 8.1 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/** heuristic - just picks up any good solution
224    found by solver - see OsiBabSolver
225 */
226
227class CbcSerendipity : public CbcHeuristic {
228public:
229
230  // Default Constructor
231  CbcSerendipity ();
232
233  /* Constructor with model
234  */
235  CbcSerendipity (CbcModel & model);
236 
237  // Copy constructor
238  CbcSerendipity ( const CbcSerendipity &);
239   
240  // Destructor
241  ~CbcSerendipity ();
242 
243  /// Assignment operator
244  CbcSerendipity & operator=(const CbcSerendipity& rhs);
245
246  /// Clone
247  virtual CbcHeuristic * clone() const;
248  /// Create C++ lines to get to current state
249  virtual void generateCpp( FILE * fp) ;
250
251  /// update model
252  virtual void setModel(CbcModel * model);
253 
254  using CbcHeuristic::solution ;
255  /** returns 0 if no solution, 1 if valid solution.
256      Sets solution values if good, sets objective value (only if good)
257      We leave all variables which are at one at this node of the
258      tree to that value and will
259      initially set all others to zero.  We then sort all variables in order of their cost
260      divided by the number of entries in rows which are not yet covered.  We randomize that
261      value a bit so that ties will be broken in different ways on different runs of the heuristic.
262      We then choose the best one and set it to one and repeat the exercise. 
263
264  */
265  virtual int solution(double & objectiveValue,
266                       double * newSolution);
267  /// Resets stuff if model changes
268  virtual void resetModel(CbcModel * model);
269
270protected:
271};
272
273#endif
Note: See TracBrowser for help on using the repository browser.