source: trunk/Cbc/src/CbcBranchCut.hpp @ 912

Last change on this file since 912 was 912, checked in by ladanyi, 11 years ago

Incorporated changes from branches/heur

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 8.7 KB
Line 
1// Copyright (C) 2004, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#ifndef CbcBranchCut_H
4#define CbcBranchCut_H
5
6#include "CbcBranchBase.hpp"
7#include "OsiRowCut.hpp"
8#include "CoinPackedMatrix.hpp"
9
10/** Define a cut branching class.
11    At present empty - all stuff in descendants
12*/
13
14class CbcBranchCut : public CbcObject {
15
16public:
17
18  // Default Constructor
19  CbcBranchCut ();
20
21  /** In to maintain normal methods
22  */ 
23  CbcBranchCut (CbcModel * model);
24  // Copy constructor
25  CbcBranchCut ( const CbcBranchCut &);
26   
27  /// Clone
28  virtual CbcObject * clone() const;
29
30  // Assignment operator
31  CbcBranchCut & operator=( const CbcBranchCut& rhs);
32
33  // Destructor
34  ~CbcBranchCut ();
35 
36  using CbcObject::infeasibility ;
37  /// Infeasibility
38  virtual double infeasibility(int & preferredWay) const;
39
40  using CbcObject::feasibleRegion ;
41  /** Set bounds to contain the current solution.
42
43    More precisely, for the variable associated with this object, take the
44    value given in the current solution, force it within the current bounds
45    if required, then set the bounds to fix the variable at the integer
46    nearest the solution value.
47
48    At present this will do nothing
49  */
50  virtual void feasibleRegion();
51
52  /** \brief Return true if branch created by object should fix variables
53  */
54  virtual bool boundBranch() const ;
55
56  using CbcObject::createBranch ;
57  /// Creates a branching object
58  virtual CbcBranchingObject * createBranch(int way) ;
59
60  /** \brief Given a valid solution (with reduced costs, etc.),
61      return a branching object which would give a new feasible
62      point in the good direction.
63
64    The preferred branching object will force the variable to be +/-1 from
65    its current value, depending on the reduced cost and objective sense.  If
66    movement in the direction which improves the objective is impossible due
67    to bounds on the variable, the branching object will move in the other
68    direction.  If no movement is possible, the method returns NULL.
69
70    Only the bounds on this variable are considered when determining if the new
71    point is feasible.
72
73    At present this does nothing
74  */
75  virtual CbcBranchingObject * preferredNewFeasible() const;
76 
77  /** \brief Given a valid solution (with reduced costs, etc.),
78      return a branching object which would give a new feasible
79      point in a bad direction.
80
81    As for preferredNewFeasible(), but the preferred branching object will
82    force movement in a direction that degrades the objective.
83
84    At present this does nothing
85  */
86  virtual CbcBranchingObject * notPreferredNewFeasible() const ;
87 
88  using CbcObject::resetBounds ;
89  /** Reset original upper and lower bound values from the solver.
90 
91    Handy for updating bounds held in this object after bounds held in the
92    solver have been tightened.
93   */
94  virtual void resetBounds();
95 
96
97protected:
98  /// data
99
100};
101
102
103/** Cut branching object
104
105  This object can specify a two-way branch in terms of two cuts
106*/
107
108class CbcCutBranchingObject : public CbcBranchingObject {
109
110public:
111
112  /// Default constructor
113  CbcCutBranchingObject ();
114
115  /** Create a cut branching object
116
117      Cut down will applied on way=-1, up on way==1
118      Assumed down will be first so way_ set to -1
119  */
120  CbcCutBranchingObject (CbcModel * model, OsiRowCut & down, OsiRowCut &up, bool canFix);
121 
122  /// Copy constructor
123  CbcCutBranchingObject ( const CbcCutBranchingObject &);
124   
125  /// Assignment operator
126  CbcCutBranchingObject & operator= (const CbcCutBranchingObject& rhs);
127
128  /// Clone
129  virtual CbcBranchingObject * clone() const;
130
131  /// Destructor
132  virtual ~CbcCutBranchingObject ();
133 
134  using CbcBranchingObject::branch ;
135  /** \brief Sets the bounds for variables or adds a cut depending on the
136             current arm of the branch and advances the object state to the next arm.
137             Returns change in guessed objective on next branch
138  */
139  virtual double branch();
140
141#if 0
142  // No need to override. Default works fine.
143  /** Reset every information so that the branching object appears to point to
144      the previous child. This method does not need to modify anything in any
145      solver. */
146  virtual void previousBranch();
147#endif
148
149  using CbcBranchingObject::print ;
150  /** \brief Print something about branch - only if log level high
151  */
152  virtual void print();
153
154  /** \brief Return true if branch should fix variables
155  */
156  virtual bool boundBranch() const;
157
158  /** Return the type (an integer identifier) of \c this */
159  virtual int type() const { return 200; }
160
161  /** Compare the original object of \c this with the original object of \c
162      brObj. Assumes that there is an ordering of the original objects.
163      This method should be invoked only if \c this and brObj are of the same
164      type.
165      Return negative/0/positive depending on whether \c this is
166      smaller/same/larger than the argument.
167  */
168  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
169
170  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
171      same type and must have the same original object, but they may have
172      different feasible regions.
173      Return the appropriate CbcRangeCompare value (first argument being the
174      sub/superset if that's the case). In case of overlap (and if \c
175      replaceIfOverlap is true) replace the current branching object with one
176      whose feasible region is the overlap.
177   */
178  virtual CbcRangeCompare compareBranchingObject
179  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
180
181protected:
182  /// Cut for the down arm (way_ = -1)
183  OsiRowCut down_;
184  /// Cut for the up arm (way_ = 1)
185  OsiRowCut up_;
186  /// True if one way can fix variables
187  bool canFix_;
188};
189
190
191/** Define a branch class that branches so that one way variables are fixed
192    while the other way cuts off that solution.
193    a) On reduced cost
194    b) When enough ==1 or <=1 rows have been satisfied (not fixed - satisfied)
195*/
196
197
198class CbcBranchToFixLots : public CbcBranchCut {
199
200public:
201
202  // Default Constructor
203  CbcBranchToFixLots ();
204
205  /** Useful constructor - passed reduced cost tolerance and fraction we would like fixed.
206      Also depth level to do at.
207      Also passed number of 1 rows which when clean triggers fix
208      Always does if all 1 rows cleaned up and number>0 or if fraction columns reached
209      Also whether to create branch if can't reach fraction.
210  */ 
211  CbcBranchToFixLots (CbcModel * model, double djTolerance,
212                      double fractionFixed, int depth,
213                      int numberClean=0,
214                      const char * mark=NULL,
215                      bool alwaysCreate=false);
216 
217  // Copy constructor
218  CbcBranchToFixLots ( const CbcBranchToFixLots &);
219   
220  /// Clone
221  virtual CbcObject * clone() const;
222
223  // Assignment operator
224  CbcBranchToFixLots & operator=( const CbcBranchToFixLots& rhs);
225
226  // Destructor
227  ~CbcBranchToFixLots ();
228
229  /** Does a lot of the work,
230      Returns 0 if no good, 1 if dj, 2 if clean, 3 if both
231  */
232  int shallWe() const;
233
234  using CbcObject::infeasibility ;
235  /// Infeasibility - large is 0.5
236  virtual double infeasibility(int & preferredWay) const;
237
238  using CbcObject::createBranch ;
239  /// Creates a branching object
240  virtual CbcBranchingObject * createBranch(int way);
241
242
243protected:
244  /// data
245
246  /// Reduced cost tolerance i.e. dj has to be >= this before fixed
247  double djTolerance_;
248  /// We only need to make sure this fraction fixed
249  double fractionFixed_;
250  /// Never fix ones marked here
251  char * mark_;
252  /// Matrix by row
253  CoinPackedMatrix matrixByRow_; 
254  /// Do if depth multiple of this
255  int depth_;
256  /// number of ==1 rows which need to be clean
257  int numberClean_;
258  /// If true then always create branch
259  bool alwaysCreate_;
260};
261
262/** Define a branch class that branches so that it is only satsified if all
263    members have different values
264    So cut is x <= y-1 or x >= y+1
265*/
266
267
268class CbcBranchAllDifferent : public CbcBranchCut {
269
270public:
271
272  // Default Constructor
273  CbcBranchAllDifferent ();
274
275  /** Useful constructor - passed set of integer variables which must all be different
276  */ 
277  CbcBranchAllDifferent (CbcModel * model, int number,const int * which);
278 
279  // Copy constructor
280  CbcBranchAllDifferent ( const CbcBranchAllDifferent &);
281   
282  /// Clone
283  virtual CbcObject * clone() const;
284
285  // Assignment operator
286  CbcBranchAllDifferent & operator=( const CbcBranchAllDifferent& rhs);
287
288  // Destructor
289  ~CbcBranchAllDifferent ();
290
291  using CbcObject::infeasibility ;
292  /// Infeasibility - large is 0.5
293  virtual double infeasibility(int & preferredWay) const;
294
295  using CbcObject::createBranch ;
296  /// Creates a branching object
297  virtual CbcBranchingObject * createBranch(int way);
298
299
300protected:
301  /// data
302
303  /// Number of entries
304  int numberInSet_;
305  /// Which variables
306  int * which_;
307};
308#endif
Note: See TracBrowser for help on using the repository browser.