source: stable/2.4/Cbc/src/CbcTreeLocal.hpp @ 1271

Last change on this file since 1271 was 1271, checked in by forrest, 10 years ago

Creating new stable branch 2.4 from trunk (rev 1270)

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 10.1 KB
Line 
1/* $Id: CbcTreeLocal.hpp 1271 2009-11-05 15:57:25Z forrest $ */
2// Copyright (C) 2004, International Business Machines
3// Corporation and others.  All Rights Reserved.
4#ifndef CbcTreeLocal_H
5#define CbcTreeLocal_H
6
7//#############################################################################
8/*  This implements (approximately) local branching as in the 2002 paper by
9    Matteo Fischetti and Andrea Lodi.
10
11    The very simple version of the algorithm for problems with
12    0-1 variables and continuous is as follows:
13
14    Obtain a feasible solution (one can be passed in).
15
16    Add a cut which limits search to a k neighborhood of this solution.
17    (At most k 0-1 variables may change value)
18    Do branch and bound on this problem.
19
20    If finished search and proven optimal then we can reverse cut so
21    any solutions must be at least k+1 away from solution and we can
22    add a new cut limiting search to a k neighborhood of new solution
23    repeat.
24
25    If finished search and no new solution then the simplest version
26    would reverse last cut and complete search.  The version implemented
27    here can use time and node limits and can widen search (increase effective k)
28    .... and more
29
30*/
31
32#include "CbcTree.hpp"
33#include "CbcNode.hpp"
34#include "OsiRowCut.hpp"
35class CbcModel;
36
37
38class CbcTreeLocal : public CbcTree {
39
40public:
41
42  // Default Constructor
43  CbcTreeLocal ();
44
45  /* Constructor with solution.
46     If solution NULL no solution, otherwise must be integer
47     range is initial upper bound (k) on difference from given solution.
48     typeCuts -
49              0 means just 0-1 cuts and will need to refine 0-1 solution
50              1 uses weaker cuts on all integer variables
51     maxDiversification is maximum number of range widenings to try
52     timeLimit is seconds in subTree
53     nodeLimit is nodes in subTree
54     refine is whether to see if we can prove current solution is optimal
55     when we fix all 0-1 (in case typeCuts==0 and there are general integer variables)
56     if false then no refinement but reverse cuts weaker
57  */
58  CbcTreeLocal (CbcModel * model,const double * solution ,int range=10,
59                   int typeCuts=0,int maxDiversification=0,
60                   int timeLimit=1000000, int nodeLimit=1000000,bool refine=true);
61  // Copy constructor
62  CbcTreeLocal ( const CbcTreeLocal & rhs);
63
64  // = operator
65  CbcTreeLocal & operator=(const CbcTreeLocal & rhs);
66   
67  virtual ~CbcTreeLocal();
68
69  /// Clone
70  virtual CbcTree * clone() const;
71  /// Create C++ lines to get to current state
72  virtual void generateCpp( FILE * fp) ;
73
74/*! \name Heap access and maintenance methods */
75//@{
76
77  /// Return the top node of the heap
78  virtual CbcNode * top() const;
79
80  /// Add a node to the heap
81  virtual void push(CbcNode * x);
82
83  /// Remove the top node from the heap
84  virtual void pop() ;
85
86//@}
87/*! \name Other stuff */
88//@{
89
90  /// Create cut - return -1 if bad, 0 if okay and 1 if cut is everything
91  int createCut(const double * solution, OsiRowCut & cut);
92
93  /// Test if empty *** note may be overridden
94  virtual bool empty() ;
95
96  /// We may have got an intelligent tree so give it one more chance
97  virtual void endSearch() ;
98  /// Other side of last cut branch (if bias==rhs_ will be weakest possible)
99  void reverseCut(int state, double bias=0.0);
100  /// Delete last cut branch
101  void deleteCut(OsiRowCut & cut);
102  /// Pass in solution (so can be used after heuristic)
103  void passInSolution(const double * solution, double solutionValue);
104  // range i.e. k
105  inline int range() const
106  { return range_;}
107  // setrange i.e. k
108  inline void setRange(int value)
109  { range_ = value;}
110  // Type of cuts - 0=just 0-1, 1=all
111  inline int typeCuts() const
112  { return typeCuts_;}
113  // Type of cuts - 0=just 0-1, 1=all
114  inline void setTypeCuts(int value)
115  { typeCuts_ = value;}
116  // maximum number of diversifications
117  inline int maxDiversification() const
118  { return maxDiversification_;}
119  // maximum number of diversifications
120  inline void setMaxDiversification(int value)
121  { maxDiversification_ = value;}
122  // time limit per subtree
123  inline int timeLimit() const
124  { return timeLimit_;}
125  // time limit per subtree
126  inline void setTimeLimit(int value)
127  { timeLimit_ = value;}
128  // node limit for subtree
129  inline int nodeLimit() const
130  { return nodeLimit_;}
131  // node limit for subtree
132  inline void setNodeLimit(int value)
133  { nodeLimit_ = value;}
134  // Whether to do refinement step
135  inline bool refine() const
136  { return refine_;}
137  // Whether to do refinement step
138  inline void setRefine(bool yesNo)
139    { refine_ = yesNo;}
140
141//@}
142private:
143  // Node for local cuts
144  CbcNode * localNode_;
145  // best solution
146  double * bestSolution_;
147  // saved solution
148  double * savedSolution_;
149  // solution number at start of pass
150  int saveNumberSolutions_;
151  /* Cut.  If zero size then no solution yet.  Otherwise is left hand branch */
152  OsiRowCut cut_;
153  // This cut fixes all 0-1 variables
154  OsiRowCut fixedCut_;
155  // Model
156  CbcModel * model_;
157  // Original lower bounds
158  double * originalLower_;
159  // Original upper bounds
160  double * originalUpper_;
161  // range i.e. k
162  int range_;
163  // Type of cuts - 0=just 0-1, 1=all
164  int typeCuts_;
165  // maximum number of diversifications
166  int maxDiversification_;
167  // current diversification
168  int diversification_;
169  // Whether next will be strong diversification
170  bool nextStrong_;
171  // Current rhs
172  double rhs_;
173  // Save allowable gap
174  double savedGap_;
175  // Best solution
176  double bestCutoff_;
177  // time limit per subtree
178  int timeLimit_;
179  // time when subtree started
180  int startTime_;
181  // node limit for subtree
182  int nodeLimit_;
183  // node count when subtree started
184  int startNode_;
185  // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
186  int searchType_;
187  // Whether to do refinement step
188  bool refine_;
189
190};
191
192class CbcTreeVariable : public CbcTree {
193
194public:
195
196  // Default Constructor
197  CbcTreeVariable ();
198
199  /* Constructor with solution.
200     If solution NULL no solution, otherwise must be integer
201     range is initial upper bound (k) on difference from given solution.
202     typeCuts -
203              0 means just 0-1 cuts and will need to refine 0-1 solution
204              1 uses weaker cuts on all integer variables
205     maxDiversification is maximum number of range widenings to try
206     timeLimit is seconds in subTree
207     nodeLimit is nodes in subTree
208     refine is whether to see if we can prove current solution is optimal
209     when we fix all 0-1 (in case typeCuts==0 and there are general integer variables)
210     if false then no refinement but reverse cuts weaker
211  */
212  CbcTreeVariable (CbcModel * model,const double * solution ,int range=10,
213                   int typeCuts=0,int maxDiversification=0,
214                   int timeLimit=1000000, int nodeLimit=1000000,bool refine=true);
215  // Copy constructor
216  CbcTreeVariable ( const CbcTreeVariable & rhs);
217
218  // = operator
219  CbcTreeVariable & operator=(const CbcTreeVariable & rhs);
220   
221  virtual ~CbcTreeVariable();
222
223  /// Clone
224  virtual CbcTree * clone() const;
225  /// Create C++ lines to get to current state
226  virtual void generateCpp( FILE * fp) ;
227
228/*! \name Heap access and maintenance methods */
229//@{
230
231  /// Return the top node of the heap
232  virtual CbcNode * top() const;
233
234  /// Add a node to the heap
235  virtual void push(CbcNode * x);
236
237  /// Remove the top node from the heap
238  virtual void pop() ;
239
240//@}
241/*! \name Other stuff */
242//@{
243
244  /// Create cut - return -1 if bad, 0 if okay and 1 if cut is everything
245  int createCut(const double * solution, OsiRowCut & cut);
246
247  /// Test if empty *** note may be overridden
248  virtual bool empty() ;
249
250  /// We may have got an intelligent tree so give it one more chance
251  virtual void endSearch() ;
252  /// Other side of last cut branch (if bias==rhs_ will be weakest possible)
253  void reverseCut(int state, double bias=0.0);
254  /// Delete last cut branch
255  void deleteCut(OsiRowCut & cut);
256  /// Pass in solution (so can be used after heuristic)
257  void passInSolution(const double * solution, double solutionValue);
258  // range i.e. k
259  inline int range() const
260  { return range_;}
261  // setrange i.e. k
262  inline void setRange(int value)
263  { range_ = value;}
264  // Type of cuts - 0=just 0-1, 1=all
265  inline int typeCuts() const
266  { return typeCuts_;}
267  // Type of cuts - 0=just 0-1, 1=all
268  inline void setTypeCuts(int value)
269  { typeCuts_ = value;}
270  // maximum number of diversifications
271  inline int maxDiversification() const
272  { return maxDiversification_;}
273  // maximum number of diversifications
274  inline void setMaxDiversification(int value)
275  { maxDiversification_ = value;}
276  // time limit per subtree
277  inline int timeLimit() const
278  { return timeLimit_;}
279  // time limit per subtree
280  inline void setTimeLimit(int value)
281  { timeLimit_ = value;}
282  // node limit for subtree
283  inline int nodeLimit() const
284  { return nodeLimit_;}
285  // node limit for subtree
286  inline void setNodeLimit(int value)
287  { nodeLimit_ = value;}
288  // Whether to do refinement step
289  inline bool refine() const
290  { return refine_;}
291  // Whether to do refinement step
292  inline void setRefine(bool yesNo)
293    { refine_ = yesNo;}
294
295//@}
296private:
297  // Node for local cuts
298  CbcNode * localNode_;
299  // best solution
300  double * bestSolution_;
301  // saved solution
302  double * savedSolution_;
303  // solution number at start of pass
304  int saveNumberSolutions_;
305  /* Cut.  If zero size then no solution yet.  Otherwise is left hand branch */
306  OsiRowCut cut_;
307  // This cut fixes all 0-1 variables
308  OsiRowCut fixedCut_;
309  // Model
310  CbcModel * model_;
311  // Original lower bounds
312  double * originalLower_;
313  // Original upper bounds
314  double * originalUpper_;
315  // range i.e. k
316  int range_;
317  // Type of cuts - 0=just 0-1, 1=all
318  int typeCuts_;
319  // maximum number of diversifications
320  int maxDiversification_;
321  // current diversification
322  int diversification_;
323  // Whether next will be strong diversification
324  bool nextStrong_;
325  // Current rhs
326  double rhs_;
327  // Save allowable gap
328  double savedGap_;
329  // Best solution
330  double bestCutoff_;
331  // time limit per subtree
332  int timeLimit_;
333  // time when subtree started
334  int startTime_;
335  // node limit for subtree
336  int nodeLimit_;
337  // node count when subtree started
338  int startNode_;
339  // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
340  int searchType_;
341  // Whether to do refinement step
342  bool refine_;
343
344};
345#endif
346
Note: See TracBrowser for help on using the repository browser.