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

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

Cleaned up a little bit.

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