source: branches/heur/Cbc/src/CbcHeuristic.hpp @ 884

Last change on this file since 884 was 884, checked in by jpgoncal, 11 years ago

Draft code for heuristic to control heuristics.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 11.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#include "CoinHelperFunctions.hpp"
11
12class OsiSolverInterface;
13
14class CbcModel;
15
16//#############################################################################
17
18/** A class describing the branching decisions that were made to get
19    to the node where a heuristics was invoked from */
20
21class CbcHeuristicNode {
22private::
23  /// The number of branching decisions made
24  int numObjects_;
25  /** The indices of the branching objects. Note: an index may be
26      listed multiple times. E.g., a general integer variable that has
27      been branched on multiple times. */
28  OsiBranchingObject** brObj_;
29public:
30  inline swap(CbcHeuristicNode& node) {
31    ::swap(numObjects_, node.numObjects_);
32    ::swap(objects_, node.objects_);
33    ::swap(bounds_, node.bounds_);
34  }
35};
36
37class CbcHeuristicNodeList {
38private:
39  std::vector<CbcHeuristicNode*> nodes_;
40public:
41  CbcHeuristicNodeList() {}
42  CbcHeuristicNodeList(const CbcHeuristicNodeList& rhs);
43  CbcHeuristicNodeList& operator=(const CbcHeuristicNodeList& rhs);
44  ~CbcHeuristicNodeList() {
45    for (int i = nodes_.size() - 1; i >= 0; --i) {
46      delete nodes_[i];
47    }
48  }
49
50  bool farFrom(const CbcHeuristicNode& node);
51  void append(CbcHeuristicNode*& node) {
52    nodes_.push_back(node);
53    node = NULL;
54  }
55  void append(CbcHeuristicNodeList& nodes) {
56    nodes_.insert(nodes_.end(), nodes.begin(), nodes.end());
57    nodes.clear();
58  }
59};
60
61//#############################################################################
62/** Heuristic base class */
63
64class CbcHeuristic {
65public:
66  // Default Constructor
67  CbcHeuristic ();
68
69  // Constructor with model - assumed before cuts
70  CbcHeuristic (CbcModel & model);
71
72  // Copy constructor
73  CbcHeuristic ( const CbcHeuristic &);
74   
75  virtual ~CbcHeuristic();
76
77  /// Clone
78  virtual CbcHeuristic * clone() const=0;
79
80  /// Assignment operator
81  CbcHeuristic & operator=(const CbcHeuristic& rhs);
82
83  /// update model (This is needed if cliques update matrix etc)
84  virtual void setModel(CbcModel * model);
85 
86  /// Resets stuff if model changes
87  virtual void resetModel(CbcModel * model)=0;
88
89  /** returns 0 if no solution, 1 if valid solution
90      with better objective value than one passed in
91      Sets solution values if good, sets objective value
92      This is called after cuts have been added - so can not add cuts
93  */
94  virtual int solution(double & objectiveValue,
95                       double * newSolution, 
96                       CbcHeuristicInfo* info = NULL)=0;
97
98  /** returns 0 if no solution, 1 if valid solution, -1 if just
99      returning an estimate of best possible solution
100      with better objective value than one passed in
101      Sets solution values if good, sets objective value (only if nonzero code)
102      This is called at same time as cut generators - so can add cuts
103      Default is do nothing
104  */
105  virtual int solution(double & objectiveValue,
106                       double * newSolution,
107                       OsiCuts & cs,
108                       CbcHeuristicInfo* info = NULL) {return 0;}
109
110  /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
111  virtual void validate() {}
112
113  /** Sets "when" flag - 0 off, 1 at root, 2 other than root, 3 always.
114      If 10 added then don't worry if validate says there are funny objects
115      as user knows it will be fine
116  */
117  inline void setWhen(int value)
118  { when_=value;}
119  /// Gets "when" flag - 0 off, 1 at root, 2 other than root, 3 always
120  inline int when() const
121  { return when_;}
122
123  /// Sets number of nodes in subtree (default 200)
124  inline void setNumberNodes(int value)
125  { numberNodes_=value;}
126  /// Gets number of nodes in a subtree (default 200)
127  inline int numberNodes() const
128  { return numberNodes_;}
129  /// Sets feasibility pump options (-1 is off)
130  inline void setFeasibilityPumpOptions(int value)
131  { feasibilityPumpOptions_=value;}
132  /// Gets feasibility pump options (-1 is off)
133  inline int feasibilityPumpOptions() const
134  { return feasibilityPumpOptions_;}
135  /// Just set model - do not do anything else
136  inline void setModelOnly(CbcModel * model)
137  { model_ = model;}
138 
139
140  /// Sets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1.0)
141  inline void setFractionSmall(double value)
142  { fractionSmall_=value;}
143  /// Gets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1.0)
144  inline double fractionSmall() const
145  { return fractionSmall_;}
146
147  /** Do mini branch and bound - return
148      0 not finished - no solution
149      1 not finished - solution
150      2 finished - no solution
151      3 finished - solution
152      (could add global cut if finished)
153  */
154  int smallBranchAndBound(OsiSolverInterface * solver,int numberNodes,
155                          double * newSolution, double & newSolutionValue,
156                          double cutoff , std::string name) const;
157  /// Create C++ lines to get to current state
158  virtual void generateCpp( FILE * fp) {}
159  /// Create C++ lines to get to current state - does work for base class
160  void generateCpp( FILE * fp,const char * heuristic) ;
161  /// Returns true if can deal with "odd" problems e.g. sos type 2
162  virtual bool canDealWithOdd() const
163  { return false;}
164  /// return name of heuristic
165  inline const char *heuristicName() const
166  { return heuristicName_.c_str();}
167  /// set name of heuristic
168  inline void setHeuristicName(const char *name)
169  { heuristicName_ = name;}
170  /// Set random number generator seed
171  void setSeed(int value);
172
173protected:
174
175  /// Model
176  CbcModel * model_;
177  /// When flag - 0 off, 1 at root, 2 other than root, 3 always
178  int when_;
179  /// Number of nodes in any sub tree
180  int numberNodes_;
181  /// Feasibility pump options (-1 is off)
182  int feasibilityPumpOptions_;
183  /// Fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound
184  double fractionSmall_;
185  /// Thread specific random number generator
186  CoinThreadRandom randomNumberGenerator_;
187  /// Name for printing
188  std::string heuristicName_;
189  /// How often to do (code can change)
190  int howOften_;
191  /// How much to increase how often
192  double decayFactor_;
193  /// The description of the nodes where this heuristic has been applied
194  CbcHeuristicNode* runNodes_;
195#if 0
196  /// Lower bounds of last node where the heuristic found a solution
197  double * lowerBoundLastNode_;
198  /// Upper bounds of last node where the heuristic found a solution
199  double * upperBoundLastNode_;
200#endif
201};
202/** Rounding class
203 */
204
205class CbcRounding : public CbcHeuristic {
206public:
207
208  // Default Constructor
209  CbcRounding ();
210
211  // Constructor with model - assumed before cuts
212  CbcRounding (CbcModel & model);
213 
214  // Copy constructor
215  CbcRounding ( const CbcRounding &);
216   
217  // Destructor
218  ~CbcRounding ();
219 
220  /// Assignment operator
221  CbcRounding & operator=(const CbcRounding& rhs);
222
223  /// Clone
224  virtual CbcHeuristic * clone() const;
225  /// Create C++ lines to get to current state
226  virtual void generateCpp( FILE * fp) ;
227
228  /// Resets stuff if model changes
229  virtual void resetModel(CbcModel * model);
230
231  /// update model (This is needed if cliques update matrix etc)
232  virtual void setModel(CbcModel * model);
233 
234  using CbcHeuristic::solution ;
235  /** returns 0 if no solution, 1 if valid solution
236      with better objective value than one passed in
237      Sets solution values if good, sets objective value (only if good)
238      This is called after cuts have been added - so can not add cuts
239  */
240  virtual int solution(double & objectiveValue,
241                       double * newSolution);
242  /** returns 0 if no solution, 1 if valid solution
243      with better objective value than one passed in
244      Sets solution values if good, sets objective value (only if good)
245      This is called after cuts have been added - so can not add cuts
246      Use solutionValue rather than solvers one
247  */
248  virtual int solution(double & objectiveValue,
249                       double * newSolution,
250                       double solutionValue);
251  /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
252  virtual void validate();
253
254
255  /// Set seed
256  void setSeed(int value)
257  { seed_ = value;}
258
259protected:
260  // Data
261
262  // Original matrix by column
263  CoinPackedMatrix matrix_;
264
265  // Original matrix by
266  CoinPackedMatrix matrixByRow_;
267
268  // Down locks
269  unsigned short * down_;
270
271  // Up locks
272  unsigned short * up_;
273
274  // Equality locks
275  unsigned short * equal_;
276
277  // Seed for random stuff
278  int seed_;
279};
280
281/** Partial solution class
282    If user knows a partial solution this tries to get an integer solution
283    it uses hotstart information
284 */
285
286class CbcHeuristicPartial : public CbcHeuristic {
287public:
288
289  // Default Constructor
290  CbcHeuristicPartial ();
291
292  /** Constructor with model - assumed before cuts
293      Fixes all variables with priority <= given
294      and does given number of nodes
295  */
296  CbcHeuristicPartial (CbcModel & model, int fixPriority=10000, int numberNodes=200);
297 
298  // Copy constructor
299  CbcHeuristicPartial ( const CbcHeuristicPartial &);
300   
301  // Destructor
302  ~CbcHeuristicPartial ();
303 
304  /// Assignment operator
305  CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs);
306
307  /// Clone
308  virtual CbcHeuristic * clone() const;
309  /// Create C++ lines to get to current state
310  virtual void generateCpp( FILE * fp) ;
311
312  /// Resets stuff if model changes
313  virtual void resetModel(CbcModel * model);
314
315  /// update model (This is needed if cliques update matrix etc)
316  virtual void setModel(CbcModel * model);
317 
318  using CbcHeuristic::solution ;
319  /** returns 0 if no solution, 1 if valid solution
320      with better objective value than one passed in
321      Sets solution values if good, sets objective value (only if good)
322      This is called after cuts have been added - so can not add cuts
323  */
324  virtual int solution(double & objectiveValue,
325                       double * newSolution);
326  /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
327  virtual void validate();
328
329
330  /// Set priority level
331  void setFixPriority(int value)
332  { fixPriority_ = value;}
333
334protected:
335  // Data
336
337  // All variables with abs priority <= this will be fixed
338  int fixPriority_;
339};
340
341/** heuristic - just picks up any good solution
342    found by solver - see OsiBabSolver
343 */
344
345class CbcSerendipity : public CbcHeuristic {
346public:
347
348  // Default Constructor
349  CbcSerendipity ();
350
351  /* Constructor with model
352  */
353  CbcSerendipity (CbcModel & model);
354 
355  // Copy constructor
356  CbcSerendipity ( const CbcSerendipity &);
357   
358  // Destructor
359  ~CbcSerendipity ();
360 
361  /// Assignment operator
362  CbcSerendipity & operator=(const CbcSerendipity& rhs);
363
364  /// Clone
365  virtual CbcHeuristic * clone() const;
366  /// Create C++ lines to get to current state
367  virtual void generateCpp( FILE * fp) ;
368
369  /// update model
370  virtual void setModel(CbcModel * model);
371 
372  using CbcHeuristic::solution ;
373  /** returns 0 if no solution, 1 if valid solution.
374      Sets solution values if good, sets objective value (only if good)
375      We leave all variables which are at one at this node of the
376      tree to that value and will
377      initially set all others to zero.  We then sort all variables in order of their cost
378      divided by the number of entries in rows which are not yet covered.  We randomize that
379      value a bit so that ties will be broken in different ways on different runs of the heuristic.
380      We then choose the best one and set it to one and repeat the exercise. 
381
382  */
383  virtual int solution(double & objectiveValue,
384                       double * newSolution);
385  /// Resets stuff if model changes
386  virtual void resetModel(CbcModel * model);
387
388protected:
389};
390
391#endif
Note: See TracBrowser for help on using the repository browser.