source: branches/devel/Cbc/src/CbcHeuristic.hpp @ 545

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

mostly for rins

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