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

Last change on this file since 356 was 356, checked in by ladanyi, 13 years ago

finishing conversion to svn

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