source: trunk/include/CbcBranchCut.hpp @ 11

Last change on this file since 11 was 11, checked in by forrest, 16 years ago

Trying some odd branching strategies

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 6.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) const;
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);
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};
149
150
151/** Define a branch class that branches so that one way variables are fixed
152    while the other way cuts off that solution.
153    a) On reduced cost
154    b) When enough ==1 or <=1 rows have been satisfied (not fixed - satisfied)
155*/
156
157
158class CbcBranchToFixLots : public CbcBranchCut {
159
160public:
161
162  // Default Constructor
163  CbcBranchToFixLots ();
164
165  /** Useful constructor - passed reduced cost tolerance and fraction we would like fixed.
166      Also depth level to do at.
167      Also passed number of 1 rows which when clean triggers fix
168      Always does if all 1 rows cleaned up and number>0 or if fraction columns reached
169      Also whether to create branch if can't reach fraction.
170  */ 
171  CbcBranchToFixLots (CbcModel * model, double djTolerance,
172                      double fractionFixed, int depth,
173                      int numberClean=0,
174                      const char * mark=NULL,
175                      bool alwaysCreate=false);
176 
177  // Copy constructor
178  CbcBranchToFixLots ( const CbcBranchToFixLots &);
179   
180  /// Clone
181  virtual CbcObject * clone() const;
182
183  // Assignment operator
184  CbcBranchToFixLots & operator=( const CbcBranchToFixLots& rhs);
185
186  // Destructor
187  ~CbcBranchToFixLots ();
188
189  /** Does a lot of the work,
190      Returns 0 if no good, 1 if dj, 2 if clean, 3 if both
191  */
192  int shallWe() const;
193  /// Infeasibility - large is 0.5
194  virtual double infeasibility(int & preferredWay) const;
195
196  /// Creates a branching object
197  virtual CbcBranchingObject * createBranch(int way) const;
198
199
200protected:
201  /// data
202
203  /// Reduced cost tolerance i.e. dj has to be >= this before fixed
204  double djTolerance_;
205  /// We only need to make sure this fraction fixed
206  double fractionFixed_;
207  /// Never fix ones marked here
208  char * mark_;
209  /// Matrix by row
210  CoinPackedMatrix matrixByRow_; 
211  /// Do if depth multiple of this
212  int depth_;
213  /// number of ==1 rows which need to be clean
214  int numberClean_;
215  /// If true then always create branch
216  bool alwaysCreate_;
217};
218#endif
Note: See TracBrowser for help on using the repository browser.