source: trunk/Cbc/src/CbcTreeLocal.hpp @ 1173

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

add $id

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 5.7 KB
Line 
1/* $Id: CbcTreeLocal.hpp 1173 2009-06-04 09:44:10Z 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#endif
192
Note: See TracBrowser for help on using the repository browser.