source: stable/2.4/Cbc/src/CbcBranchCut.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: 9.1 KB
Line 
1/* $Id: CbcBranchCut.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 CbcBranchCut_H
5#define CbcBranchCut_H
6
7#include "CbcBranchBase.hpp"
8#include "OsiRowCut.hpp"
9#include "CoinPackedMatrix.hpp"
10
11/** Define a cut branching class.
12    At present empty - all stuff in descendants
13*/
14
15class CbcBranchCut : public CbcObject {
16
17public:
18
19  // Default Constructor
20  CbcBranchCut ();
21
22  /** In to maintain normal methods
23  */ 
24  CbcBranchCut (CbcModel * model);
25  // Copy constructor
26  CbcBranchCut ( const CbcBranchCut &);
27   
28  /// Clone
29  virtual CbcObject * clone() const;
30
31  // Assignment operator
32  CbcBranchCut & operator=( const CbcBranchCut& rhs);
33
34  // Destructor
35  ~CbcBranchCut ();
36 
37  /// Infeasibility
38  virtual double infeasibility(const OsiBranchingInformation * info,
39                               int &preferredWay) const;
40
41  using CbcObject::feasibleRegion ;
42  /** Set bounds to contain the current solution.
43
44    More precisely, for the variable associated with this object, take the
45    value given in the current solution, force it within the current bounds
46    if required, then set the bounds to fix the variable at the integer
47    nearest the solution value.
48
49    At present this will do nothing
50  */
51  virtual void feasibleRegion();
52
53  /** \brief Return true if branch created by object should fix variables
54  */
55  virtual bool boundBranch() const ;
56
57  /// Creates a branching object
58  virtual CbcBranchingObject * createCbcBranch(OsiSolverInterface * solver,const OsiBranchingInformation * info, 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  /// Infeasibility - large is 0.5
235  virtual double infeasibility(const OsiBranchingInformation * info,
236                               int &preferredWay) const;
237  /** \brief Return true if object can take part in normal heuristics
238  */
239  virtual bool canDoHeuristics() const 
240  {return true;}
241
242  /// Creates a branching object
243  virtual CbcBranchingObject * createCbcBranch(OsiSolverInterface * solver,const OsiBranchingInformation * info, int way) ;
244  /// Redoes data when sequence numbers change
245  virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns);
246
247
248protected:
249  /// data
250
251  /// Reduced cost tolerance i.e. dj has to be >= this before fixed
252  double djTolerance_;
253  /// We only need to make sure this fraction fixed
254  double fractionFixed_;
255  /// Never fix ones marked here
256  char * mark_;
257  /// Matrix by row
258  CoinPackedMatrix matrixByRow_; 
259  /// Do if depth multiple of this
260  int depth_;
261  /// number of ==1 rows which need to be clean
262  int numberClean_;
263  /// If true then always create branch
264  bool alwaysCreate_;
265};
266
267/** Define a branch class that branches so that it is only satsified if all
268    members have different values
269    So cut is x <= y-1 or x >= y+1
270*/
271
272
273class CbcBranchAllDifferent : public CbcBranchCut {
274
275public:
276
277  // Default Constructor
278  CbcBranchAllDifferent ();
279
280  /** Useful constructor - passed set of integer variables which must all be different
281  */ 
282  CbcBranchAllDifferent (CbcModel * model, int number,const int * which);
283 
284  // Copy constructor
285  CbcBranchAllDifferent ( const CbcBranchAllDifferent &);
286   
287  /// Clone
288  virtual CbcObject * clone() const;
289
290  // Assignment operator
291  CbcBranchAllDifferent & operator=( const CbcBranchAllDifferent& rhs);
292
293  // Destructor
294  ~CbcBranchAllDifferent ();
295
296  /// Infeasibility - large is 0.5
297  virtual double infeasibility(const OsiBranchingInformation * info,
298                               int &preferredWay) const;
299
300  /// Creates a branching object
301  virtual CbcBranchingObject * createCbcBranch(OsiSolverInterface * solver,const OsiBranchingInformation * info, int way) ;
302
303
304protected:
305  /// data
306
307  /// Number of entries
308  int numberInSet_;
309  /// Which variables
310  int * which_;
311};
312#endif
Note: See TracBrowser for help on using the repository browser.