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

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

towards common use with other solvers

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 5.4 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  virtual ~CbcHeuristic();
27
28  /// update model (This is needed if cliques update matrix etc)
29  virtual void setModel(CbcModel * model);
30 
31  /// Clone
32  virtual CbcHeuristic * clone() const=0;
33
34  /// Resets stuff if model changes
35  virtual void resetModel(CbcModel * model)=0;
36
37  /** returns 0 if no solution, 1 if valid solution
38      with better objective value than one passed in
39      Sets solution values if good, sets objective value
40      This is called after cuts have been added - so can not add cuts
41  */
42  virtual int solution(double & objectiveValue,
43                       double * newSolution)=0;
44
45  /** returns 0 if no solution, 1 if valid solution, -1 if just
46      returning an estimate of best possible solution
47      with better objective value than one passed in
48      Sets solution values if good, sets objective value (only if nonzero code)
49      This is called at same time as cut generators - so can add cuts
50      Default is do nothing
51  */
52  virtual int solution(double & objectiveValue,
53                       double * newSolution,
54                       OsiCuts & cs) {return 0;};
55
56  /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
57  virtual void validate() {};
58
59  /** Sets "when" flag - 0 off, 1 at root, 2 other than root, 3 always.
60      If 10 added then don't worry if validate says there are funny objects
61      as user knows it will be fine
62  */
63  inline void setWhen(int value)
64  { when_=value;};
65  /// Gets "when" flag - 0 off, 1 at root, 2 other than root, 3 always
66  inline int when() const
67  { return when_;};
68
69  /// Do mini branch and bound (return 1 if solution)
70  int smallBranchAndBound(OsiSolverInterface * solver,int numberNodes,
71                          double * newSolution, double & newSolutionValue,
72                          double cutoff , std::string name) const;
73  /// Create C++ lines to get to current state
74  virtual void generateCpp( FILE * fp) {};
75
76protected:
77
78  /// Model
79  CbcModel * model_;
80  /// When flag - 0 off, 1 at root, 2 other than root, 3 always
81  int when_;
82private:
83 
84  /// Illegal Assignment operator
85  CbcHeuristic & operator=(const CbcHeuristic& rhs);
86 
87};
88/** Rounding class
89 */
90
91class CbcRounding : public CbcHeuristic {
92public:
93
94  // Default Constructor
95  CbcRounding ();
96
97  // Constructor with model - assumed before cuts
98  CbcRounding (CbcModel & model);
99 
100  // Copy constructor
101  CbcRounding ( const CbcRounding &);
102   
103  // Destructor
104  ~CbcRounding ();
105 
106  /// Clone
107  virtual CbcHeuristic * clone() const;
108  /// Create C++ lines to get to current state
109  virtual void generateCpp( FILE * fp) ;
110
111  /// Resets stuff if model changes
112  virtual void resetModel(CbcModel * model);
113
114  /// update model (This is needed if cliques update matrix etc)
115  virtual void setModel(CbcModel * model);
116 
117  /** returns 0 if no solution, 1 if valid solution
118      with better objective value than one passed in
119      Sets solution values if good, sets objective value (only if good)
120      This is called after cuts have been added - so can not add cuts
121  */
122  virtual int solution(double & objectiveValue,
123                       double * newSolution);
124  /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
125  virtual void validate();
126
127
128  /// Set seed
129  void setSeed(int value)
130  { seed_ = value;};
131
132protected:
133  // Data
134
135  // Original matrix by column
136  CoinPackedMatrix matrix_;
137
138  // Original matrix by
139  CoinPackedMatrix matrixByRow_;
140
141  // Seed for random stuff
142  int seed_;
143
144private:
145  /// Illegal Assignment operator
146  CbcRounding & operator=(const CbcRounding& rhs);
147};
148
149/** heuristic - just picks up any good solution
150    found by solver - see OsiBabSolver
151 */
152
153class CbcSerendipity : public CbcHeuristic {
154public:
155
156  // Default Constructor
157  CbcSerendipity ();
158
159  /* Constructor with model
160  */
161  CbcSerendipity (CbcModel & model);
162 
163  // Copy constructor
164  CbcSerendipity ( const CbcSerendipity &);
165   
166  // Destructor
167  ~CbcSerendipity ();
168 
169  /// Clone
170  virtual CbcHeuristic * clone() const;
171  /// Create C++ lines to get to current state
172  virtual void generateCpp( FILE * fp) ;
173
174  /// update model
175  virtual void setModel(CbcModel * model);
176 
177  /** returns 0 if no solution, 1 if valid solution.
178      Sets solution values if good, sets objective value (only if good)
179      We leave all variables which are at one at this node of the
180      tree to that value and will
181      initially set all others to zero.  We then sort all variables in order of their cost
182      divided by the number of entries in rows which are not yet covered.  We randomize that
183      value a bit so that ties will be broken in different ways on different runs of the heuristic.
184      We then choose the best one and set it to one and repeat the exercise. 
185
186  */
187  virtual int solution(double & objectiveValue,
188                       double * newSolution);
189  /// Resets stuff if model changes
190  virtual void resetModel(CbcModel * model);
191
192protected:
193private:
194  /// Illegal Assignment operator
195  CbcSerendipity & operator=(const CbcSerendipity& rhs);
196};
197
198#endif
Note: See TracBrowser for help on using the repository browser.