source: trunk/include/CbcBranchCut.hpp @ 216

Last change on this file since 216 was 216, checked in by forrest, 14 years ago

add branching stuff

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 7.0 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  /// Infeasibility
37  virtual double infeasibility(int & preferredWay) const;
38
39  /** Set bounds to contain the current solution.
40
41    More precisely, for the variable associated with this object, take the
42    value given in the current solution, force it within the current bounds
43    if required, then set the bounds to fix the variable at the integer
44    nearest the solution value.
45
46    At present this will do nothing
47  */
48  virtual void feasibleRegion();
49
50  /** \brief Return true if branch created by object should fix variables
51  */
52  virtual bool boundBranch() const ;
53  /// Creates a branching object
54  virtual CbcBranchingObject * createBranch(int way) ;
55
56  /** \brief Given a valid solution (with reduced costs, etc.),
57      return a branching object which would give a new feasible
58      point in the good direction.
59
60    The preferred branching object will force the variable to be +/-1 from
61    its current value, depending on the reduced cost and objective sense.  If
62    movement in the direction which improves the objective is impossible due
63    to bounds on the variable, the branching object will move in the other
64    direction.  If no movement is possible, the method returns NULL.
65
66    Only the bounds on this variable are considered when determining if the new
67    point is feasible.
68
69    At present this does nothing
70  */
71  virtual CbcBranchingObject * preferredNewFeasible() const;
72 
73  /** \brief Given a valid solution (with reduced costs, etc.),
74      return a branching object which would give a new feasible
75      point in a bad direction.
76
77    As for preferredNewFeasible(), but the preferred branching object will
78    force movement in a direction that degrades the objective.
79
80    At present this does nothing
81  */
82  virtual CbcBranchingObject * notPreferredNewFeasible() const ;
83 
84  /** Reset original upper and lower bound values from the solver.
85 
86    Handy for updating bounds held in this object after bounds held in the
87    solver have been tightened.
88   */
89  virtual void resetBounds();
90 
91
92protected:
93  /// data
94
95};
96
97
98/** Cut branching object
99
100  This object can specify a two-way branch in terms of two cuts
101*/
102
103class CbcCutBranchingObject : public CbcBranchingObject {
104
105public:
106
107  /// Default constructor
108  CbcCutBranchingObject ();
109
110  /** Create a cut branching object
111
112      Cut down will applied on way=-1, up on way==1
113      Assumed down will be first so way_ set to -1
114  */
115  CbcCutBranchingObject (CbcModel * model, OsiRowCut & down, OsiRowCut &up, bool canFix);
116 
117  /// Copy constructor
118  CbcCutBranchingObject ( const CbcCutBranchingObject &);
119   
120  /// Assignment operator
121  CbcCutBranchingObject & operator= (const CbcCutBranchingObject& rhs);
122
123  /// Clone
124  virtual CbcBranchingObject * clone() const;
125
126  /// Destructor
127  virtual ~CbcCutBranchingObject ();
128 
129  /** \brief Sets the bounds for variables or adds a cut depending on the
130             current arm of the branch and advances the object state to the next arm.
131             Returns change in guessed objective on next branch
132  */
133  virtual double branch(bool normalBranch=false);
134
135  /** \brief Print something about branch - only if log level high
136  */
137  virtual void print(bool normalBranch);
138
139  /** \brief Return true if branch should fix variables
140  */
141  virtual bool boundBranch() const;
142
143protected:
144  /// Cut for the down arm (way_ = -1)
145  OsiRowCut down_;
146  /// Cut for the up arm (way_ = 1)
147  OsiRowCut up_;
148  /// True if one way can fix variables
149  bool canFix_;
150};
151
152
153/** Define a branch class that branches so that one way variables are fixed
154    while the other way cuts off that solution.
155    a) On reduced cost
156    b) When enough ==1 or <=1 rows have been satisfied (not fixed - satisfied)
157*/
158
159
160class CbcBranchToFixLots : public CbcBranchCut {
161
162public:
163
164  // Default Constructor
165  CbcBranchToFixLots ();
166
167  /** Useful constructor - passed reduced cost tolerance and fraction we would like fixed.
168      Also depth level to do at.
169      Also passed number of 1 rows which when clean triggers fix
170      Always does if all 1 rows cleaned up and number>0 or if fraction columns reached
171      Also whether to create branch if can't reach fraction.
172  */ 
173  CbcBranchToFixLots (CbcModel * model, double djTolerance,
174                      double fractionFixed, int depth,
175                      int numberClean=0,
176                      const char * mark=NULL,
177                      bool alwaysCreate=false);
178 
179  // Copy constructor
180  CbcBranchToFixLots ( const CbcBranchToFixLots &);
181   
182  /// Clone
183  virtual CbcObject * clone() const;
184
185  // Assignment operator
186  CbcBranchToFixLots & operator=( const CbcBranchToFixLots& rhs);
187
188  // Destructor
189  ~CbcBranchToFixLots ();
190
191  /** Does a lot of the work,
192      Returns 0 if no good, 1 if dj, 2 if clean, 3 if both
193  */
194  int shallWe() const;
195  /// Infeasibility - large is 0.5
196  virtual double infeasibility(int & preferredWay) const;
197
198  /// Creates a branching object
199  virtual CbcBranchingObject * createBranch(int way);
200
201
202protected:
203  /// data
204
205  /// Reduced cost tolerance i.e. dj has to be >= this before fixed
206  double djTolerance_;
207  /// We only need to make sure this fraction fixed
208  double fractionFixed_;
209  /// Never fix ones marked here
210  char * mark_;
211  /// Matrix by row
212  CoinPackedMatrix matrixByRow_; 
213  /// Do if depth multiple of this
214  int depth_;
215  /// number of ==1 rows which need to be clean
216  int numberClean_;
217  /// If true then always create branch
218  bool alwaysCreate_;
219};
220
221/** Define a branch class that branches so that it is only satsified if all
222    members have different values
223    So cut is x <= y-1 or x >= y+1
224*/
225
226
227class CbcBranchAllDifferent : public CbcBranchCut {
228
229public:
230
231  // Default Constructor
232  CbcBranchAllDifferent ();
233
234  /** Useful constructor - passed set of integer variables which must all be different
235  */ 
236  CbcBranchAllDifferent (CbcModel * model, int number,const int * which);
237 
238  // Copy constructor
239  CbcBranchAllDifferent ( const CbcBranchAllDifferent &);
240   
241  /// Clone
242  virtual CbcObject * clone() const;
243
244  // Assignment operator
245  CbcBranchAllDifferent & operator=( const CbcBranchAllDifferent& rhs);
246
247  // Destructor
248  ~CbcBranchAllDifferent ();
249
250  /// Infeasibility - large is 0.5
251  virtual double infeasibility(int & preferredWay) const;
252
253  /// Creates a branching object
254  virtual CbcBranchingObject * createBranch(int way);
255
256
257protected:
258  /// data
259
260  /// Number of entries
261  int numberInSet_;
262  /// Which variables
263  int * which_;
264};
265#endif
Note: See TracBrowser for help on using the repository browser.