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

Last change on this file since 862 was 765, checked in by andreasw, 12 years ago

merging changes from Bug Squashing Party Aug 2007 to regular trunk

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 7.3 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  using CbcBranchingObject::print ;
142  /** \brief Print something about branch - only if log level high
143  */
144  virtual void print();
145
146  /** \brief Return true if branch should fix variables
147  */
148  virtual bool boundBranch() const;
149
150protected:
151  /// Cut for the down arm (way_ = -1)
152  OsiRowCut down_;
153  /// Cut for the up arm (way_ = 1)
154  OsiRowCut up_;
155  /// True if one way can fix variables
156  bool canFix_;
157};
158
159
160/** Define a branch class that branches so that one way variables are fixed
161    while the other way cuts off that solution.
162    a) On reduced cost
163    b) When enough ==1 or <=1 rows have been satisfied (not fixed - satisfied)
164*/
165
166
167class CbcBranchToFixLots : public CbcBranchCut {
168
169public:
170
171  // Default Constructor
172  CbcBranchToFixLots ();
173
174  /** Useful constructor - passed reduced cost tolerance and fraction we would like fixed.
175      Also depth level to do at.
176      Also passed number of 1 rows which when clean triggers fix
177      Always does if all 1 rows cleaned up and number>0 or if fraction columns reached
178      Also whether to create branch if can't reach fraction.
179  */ 
180  CbcBranchToFixLots (CbcModel * model, double djTolerance,
181                      double fractionFixed, int depth,
182                      int numberClean=0,
183                      const char * mark=NULL,
184                      bool alwaysCreate=false);
185 
186  // Copy constructor
187  CbcBranchToFixLots ( const CbcBranchToFixLots &);
188   
189  /// Clone
190  virtual CbcObject * clone() const;
191
192  // Assignment operator
193  CbcBranchToFixLots & operator=( const CbcBranchToFixLots& rhs);
194
195  // Destructor
196  ~CbcBranchToFixLots ();
197
198  /** Does a lot of the work,
199      Returns 0 if no good, 1 if dj, 2 if clean, 3 if both
200  */
201  int shallWe() const;
202
203  using CbcObject::infeasibility ;
204  /// Infeasibility - large is 0.5
205  virtual double infeasibility(int & preferredWay) const;
206
207  using CbcObject::createBranch ;
208  /// Creates a branching object
209  virtual CbcBranchingObject * createBranch(int way);
210
211
212protected:
213  /// data
214
215  /// Reduced cost tolerance i.e. dj has to be >= this before fixed
216  double djTolerance_;
217  /// We only need to make sure this fraction fixed
218  double fractionFixed_;
219  /// Never fix ones marked here
220  char * mark_;
221  /// Matrix by row
222  CoinPackedMatrix matrixByRow_; 
223  /// Do if depth multiple of this
224  int depth_;
225  /// number of ==1 rows which need to be clean
226  int numberClean_;
227  /// If true then always create branch
228  bool alwaysCreate_;
229};
230
231/** Define a branch class that branches so that it is only satsified if all
232    members have different values
233    So cut is x <= y-1 or x >= y+1
234*/
235
236
237class CbcBranchAllDifferent : public CbcBranchCut {
238
239public:
240
241  // Default Constructor
242  CbcBranchAllDifferent ();
243
244  /** Useful constructor - passed set of integer variables which must all be different
245  */ 
246  CbcBranchAllDifferent (CbcModel * model, int number,const int * which);
247 
248  // Copy constructor
249  CbcBranchAllDifferent ( const CbcBranchAllDifferent &);
250   
251  /// Clone
252  virtual CbcObject * clone() const;
253
254  // Assignment operator
255  CbcBranchAllDifferent & operator=( const CbcBranchAllDifferent& rhs);
256
257  // Destructor
258  ~CbcBranchAllDifferent ();
259
260  using CbcObject::infeasibility ;
261  /// Infeasibility - large is 0.5
262  virtual double infeasibility(int & preferredWay) const;
263
264  using CbcObject::createBranch ;
265  /// Creates a branching object
266  virtual CbcBranchingObject * createBranch(int way);
267
268
269protected:
270  /// data
271
272  /// Number of entries
273  int numberInSet_;
274  /// Which variables
275  int * which_;
276};
277#endif
Note: See TracBrowser for help on using the repository browser.