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

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

for owning solution in OsiBranchingObject?

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