source: trunk/Cbc/src/CbcBranchDynamic.hpp @ 310

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

for hot start

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 14.0 KB
Line 
1// Copyright (C) 2005, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#ifndef CbcBranchDynamic_H
4#define CbcBranchDynamic_H
5
6#include "CbcBranchActual.hpp"
7#include "CoinPackedMatrix.hpp"
8
9
10/** Define a single integer class but with dynamic pseudo costs.
11    Based on work by Achterberg, Koch and Martin.
12
13    It is wild overkill but to keep design all twiddly things are in each.
14    This could be used for fine tuning.
15
16 */
17
18
19class CbcSimpleIntegerDynamicPseudoCost : public CbcSimpleInteger {
20
21public:
22
23  // Default Constructor
24  CbcSimpleIntegerDynamicPseudoCost ();
25
26  // Useful constructor - passed integer index and model index
27  CbcSimpleIntegerDynamicPseudoCost (CbcModel * model, int sequence, int iColumn, double breakEven=0.5);
28 
29  // Useful constructor - passed integer index and model index and pseudo costs
30  CbcSimpleIntegerDynamicPseudoCost (CbcModel * model, int sequence, int iColumn, 
31                              double downDynamicPseudoCost, double upDynamicPseudoCost);
32 
33  // Copy constructor
34  CbcSimpleIntegerDynamicPseudoCost ( const CbcSimpleIntegerDynamicPseudoCost &);
35   
36  /// Clone
37  virtual CbcObject * clone() const;
38
39  // Assignment operator
40  CbcSimpleIntegerDynamicPseudoCost & operator=( const CbcSimpleIntegerDynamicPseudoCost& rhs);
41
42  // Destructor
43  ~CbcSimpleIntegerDynamicPseudoCost ();
44 
45  /// Infeasibility - large is 0.5
46  virtual double infeasibility(int & preferredWay) const;
47
48  /// Creates a branching object
49  virtual CbcBranchingObject * createBranch(int way) ;
50
51  /** Create an OsiSolverBranch object
52
53      This returns NULL if branch not represented by bound changes
54  */
55  virtual OsiSolverBranch * solverBranch() const;
56 
57  /// Down pseudo cost
58  inline double downDynamicPseudoCost() const
59  { return downDynamicPseudoCost_;};
60  /// Set down pseudo cost
61  inline void setDownDynamicPseudoCost(double value)
62  { downDynamicPseudoCost_=value;};
63
64  /// Up pseudo cost
65  inline double upDynamicPseudoCost() const
66  { return upDynamicPseudoCost_;};
67  /// Set up pseudo cost
68  inline void setUpDynamicPseudoCost(double value)
69  { upDynamicPseudoCost_=value;};
70
71  /// Up down separator
72  inline double upDownSeparator() const
73  { return upDownSeparator_;};
74  /// Set up down separator
75  inline void setUpDownSeparator(double value)
76  { upDownSeparator_=value;};
77
78  /// Down sum cost
79  inline double sumDownCost() const
80  { return sumDownCost_;};
81  /// Set down sum cost
82  inline void setSumDownCost(double value)
83  { sumDownCost_=value;};
84  /// Add to down sum cost and set last and square
85  inline void addToSumDownCost(double value)
86  { sumDownCost_+=value;lastDownCost_=value;sumDownCostSquared_ += value*value;};
87
88  /// Up sum cost
89  inline double sumUpCost() const
90  { return sumUpCost_;};
91  /// Set up sum cost
92  inline void setSumUpCost(double value)
93  { sumUpCost_=value;};
94  /// Add to up sum cost and set last and square
95  inline void addToSumUpCost(double value)
96  { sumUpCost_+=value;lastUpCost_=value;sumUpCostSquared_ += value*value;};
97
98  /// Down sum change
99  inline double sumDownChange() const
100  { return sumDownChange_;};
101  /// Set down sum change
102  inline void setSumDownChange(double value)
103  { sumDownChange_=value;};
104  /// Add to down sum change
105  inline void addToSumDownChange(double value)
106  { sumDownChange_+=value;};
107
108  /// Up sum change
109  inline double sumUpChange() const
110  { return sumUpChange_;};
111  /// Set up sum change
112  inline void setSumUpChange(double value)
113  { sumUpChange_=value;};
114  /// Add to up sum change and set last and square
115  inline void addToSumUpChange(double value)
116  { sumUpChange_+=value;};
117
118  /// Sum down decrease number infeasibilities from strong or actual
119  inline double sumDownDecrease() const
120  { return sumDownDecrease_;};
121  /// Set sum down decrease number infeasibilities from strong or actual
122  inline void setSumDownDecrease(double value)
123  { sumDownDecrease_=value;};
124  /// Add to sum down decrease number infeasibilities from strong or actual
125  inline void addToSumDownDecrease(double value)
126  { sumDownDecrease_+=value;lastDownDecrease_ = (int) value;};
127
128  /// Sum up decrease number infeasibilities from strong or actual
129  inline double sumUpDecrease() const
130  { return sumUpDecrease_;};
131  /// Set sum up decrease number infeasibilities from strong or actual
132  inline void setSumUpDecrease(double value)
133  { sumUpDecrease_=value;};
134  /// Add to sum up decrease number infeasibilities from strong or actual
135  inline void addToSumUpDecrease(double value)
136  { sumUpDecrease_+=value;lastUpDecrease_ = (int) value;};
137
138  /// Down number times
139  inline int numberTimesDown() const
140  { return numberTimesDown_;};
141  /// Set down number times
142  inline void setNumberTimesDown(int value)
143  { numberTimesDown_=value;};
144  /// Increment down number times
145  inline void incrementNumberTimesDown()
146  { numberTimesDown_++;};
147
148  /// Up number times
149  inline int numberTimesUp() const
150  { return numberTimesUp_;};
151  /// Set up number times
152  inline void setNumberTimesUp(int value)
153  { numberTimesUp_=value;};
154  /// Increment up number times
155  inline void incrementNumberTimesUp()
156  { numberTimesUp_++;};
157
158  /// Down number times infeasible
159  inline int numberTimesDownInfeasible() const
160  { return numberTimesDownInfeasible_;};
161  /// Set down number times infeasible
162  inline void setNumberTimesDownInfeasible(int value)
163  { numberTimesDownInfeasible_=value;};
164  /// Increment down number times infeasible
165  inline void incrementNumberTimesDownInfeasible()
166  { numberTimesDownInfeasible_++;};
167
168  /// Up number times infeasible
169  inline int numberTimesUpInfeasible() const
170  { return numberTimesUpInfeasible_;};
171  /// Set up number times infeasible
172  inline void setNumberTimesUpInfeasible(int value)
173  { numberTimesUpInfeasible_=value;};
174  /// Increment up number times infeasible
175  inline void incrementNumberTimesUpInfeasible()
176  { numberTimesUpInfeasible_++;};
177
178  /// Number of times before trusted
179  inline int numberBeforeTrust() const
180  { return numberBeforeTrust_;};
181  /// Set number of times before trusted
182  inline void setNumberBeforeTrust(int value)
183  { numberBeforeTrust_=value;};
184
185  /// Return "up" estimate
186  virtual double upEstimate() const;
187  /// Return "down" estimate (default 1.0e-5)
188  virtual double downEstimate() const;
189 
190  /// method - see below for details
191  inline int method() const
192  { return method_;};
193  /// Set method
194  inline void setMethod(int value)
195  { method_=value;};
196
197  /// Pass in information on a down branch
198  void setDownInformation(double changeObjectiveDown, int changeInfeasibilityDown);
199  /// Pass in information on a up branch
200  void setUpInformation(double changeObjectiveUp, int changeInfeasibilityUp);
201
202  /// Print - 0 -summary, 1 just before strong
203  void print(int type=0, double value=0.0) const;
204protected:
205  /// data
206
207  /// Down pseudo cost
208  double downDynamicPseudoCost_;
209  /// Up pseudo cost
210  double upDynamicPseudoCost_;
211  /** Up/down separator
212      If >0.0 then do first branch up if value-floor(value)
213      >= this value
214  */
215  double upDownSeparator_;
216  /// Sum down cost from strong or actual
217  double sumDownCost_;
218  /// Sum up cost from strong or actual
219  double sumUpCost_;
220  /// Sum of all changes to x when going down
221  double sumDownChange_;
222  /// Sum of all changes to x when going up
223  double sumUpChange_;
224  /// Sum down cost from strong or actual squared
225  double sumDownCostSquared_;
226  /// Sum up cost from strong or actual squared
227  double sumUpCostSquared_;
228  /// Sum down decrease number infeasibilities from strong or actual
229  double sumDownDecrease_;
230  /// Sum up decrease number infeasibilities from strong or actual
231  double sumUpDecrease_;
232  /// Last down cost from strong (i.e. as computed by last strong)
233  double lastDownCost_;
234  /// Last up cost from strong (i.e. as computed by last strong)
235  double lastUpCost_;
236  /// Last down decrease number infeasibilities from strong (i.e. as computed by last strong)
237  int lastDownDecrease_;
238  /// Last up decrease number infeasibilities from strong (i.e. as computed by last strong)
239  int lastUpDecrease_;
240  /// Number of times we have gone down
241  int numberTimesDown_;
242  /// Number of times we have gone up
243  int numberTimesUp_;
244  /// Number of times we have been infeasible going down
245  int numberTimesDownInfeasible_;
246  /// Number of times we have been infeasible going up
247  int numberTimesUpInfeasible_;
248  /// Number of branches before we trust
249  int numberBeforeTrust_;
250  /** Method -
251      ??
252  */
253  int method_;
254};
255
256
257/** Simple branching object for an integer variable with pseudo costs
258
259  This object can specify a two-way branch on an integer variable. For each
260  arm of the branch, the upper and lower bounds on the variable can be
261  independently specified.
262 
263  Variable_ holds the index of the integer variable in the integerVariable_
264  array of the model.
265*/
266
267class CbcDynamicPseudoCostBranchingObject : public CbcIntegerBranchingObject {
268
269public:
270
271  /// Default constructor
272  CbcDynamicPseudoCostBranchingObject ();
273
274  /** Create a standard floor/ceiling branch object
275
276    Specifies a simple two-way branch. Let \p value = x*. One arm of the
277    branch will be is lb <= x <= floor(x*), the other ceil(x*) <= x <= ub.
278    Specify way = -1 to set the object state to perform the down arm first,
279    way = 1 for the up arm.
280  */
281  CbcDynamicPseudoCostBranchingObject (CbcModel *model, int variable,
282                                       int way , double value, 
283                                       CbcSimpleIntegerDynamicPseudoCost * object) ;
284 
285  /** Create a degenerate branch object
286
287    Specifies a `one-way branch'. Calling branch() for this object will
288    always result in lowerValue <= x <= upperValue. Used to fix a variable
289    when lowerValue = upperValue.
290  */
291
292  CbcDynamicPseudoCostBranchingObject (CbcModel *model, int variable, int way,
293                             double lowerValue, double upperValue) ;
294 
295  /// Copy constructor
296  CbcDynamicPseudoCostBranchingObject ( const CbcDynamicPseudoCostBranchingObject &);
297   
298  /// Assignment operator
299  CbcDynamicPseudoCostBranchingObject & operator= (const CbcDynamicPseudoCostBranchingObject& rhs);
300
301  /// Clone
302  virtual CbcBranchingObject * clone() const;
303
304  /// Destructor
305  virtual ~CbcDynamicPseudoCostBranchingObject ();
306 
307  /** \brief Sets the bounds for the variable according to the current arm
308             of the branch and advances the object state to the next arm.
309             This version also changes guessed objective value
310  */
311  virtual double branch(bool normalBranch=false);
312  /** Some branchingObjects may claim to be able to skip
313      strong branching.  If so they have to fill in CbcStrongInfo.
314      The object mention in incoming CbcStrongInfo must match.
315      Returns nonzero if skip is wanted */
316  virtual int fillStrongInfo( CbcStrongInfo & info);
317
318  /// Change in guessed
319  inline double changeInGuessed() const
320  { return changeInGuessed_;};
321  /// Set change in guessed
322  inline void setChangeInGuessed(double value)
323  { changeInGuessed_=value;};
324  /// Return object
325  inline CbcSimpleIntegerDynamicPseudoCost * object() const
326  { return object_;};
327protected:
328  /// Change in guessed objective value for next branch
329  double changeInGuessed_;
330  /// Pointer back to object
331  CbcSimpleIntegerDynamicPseudoCost * object_;
332
333};
334/** Branching decision dynamic class
335
336  This class implements a simple algorithm
337  (betterBranch()) for choosing a branching variable when dynamic pseudo costs.
338*/
339
340class CbcBranchDynamicDecision : public CbcBranchDecision {
341public:
342  // Default Constructor
343  CbcBranchDynamicDecision ();
344
345  // Copy constructor
346  CbcBranchDynamicDecision ( const CbcBranchDynamicDecision &);
347
348  virtual ~CbcBranchDynamicDecision();
349
350  /// Clone
351  virtual CbcBranchDecision * clone() const;
352
353  /// Initialize, <i>e.g.</i> before the start of branch selection at a node
354  virtual void initialize(CbcModel * model);
355
356  /** \brief Compare two branching objects. Return nonzero if \p thisOne is
357             better than \p bestSoFar.
358
359    The routine compares branches using the values supplied in \p numInfUp and
360    \p numInfDn until a solution is found by search, after which it uses the
361    values supplied in \p changeUp and \p changeDn. The best branching object
362    seen so far and the associated parameter values are remembered in the
363    \c CbcBranchDynamicDecision object. The nonzero return value is +1 if the
364    up branch is preferred, -1 if the down branch is preferred.
365
366    As the names imply, the assumption is that the values supplied for
367    \p numInfUp and \p numInfDn will be the number of infeasibilities reported
368    by the branching object, and \p changeUp and \p changeDn will be the
369    estimated change in objective. Other measures can be used if desired.
370
371    Because an \c CbcBranchDynamicDecision object remembers the current best
372    branching candidate (#bestObject_) as well as the values used in the
373    comparison, the parameter \p bestSoFar is redundant, hence unused.
374 */
375  virtual int betterBranch(CbcBranchingObject * thisOne,
376                            CbcBranchingObject * bestSoFar,
377                            double changeUp, int numInfUp,
378                            double changeDn, int numInfDn);
379  /** Sets or gets best criterion so far */
380  virtual void setBestCriterion(double value);
381  virtual double getBestCriterion() const;
382  /** Says whether this method can handle both methods -
383      1 better, 2 best, 3 both */
384  virtual int whichMethod() {return 3;};
385
386  /** Saves a clone of current branching object.  Can be used to update
387      information on object causing branch - after branch */
388  virtual void saveBranchingObject(CbcBranchingObject * object) ;
389  /** Pass in information on branch just done.
390      assumes object can get information from solver */
391  virtual void updateInformation(OsiSolverInterface * solver,
392                                 const CbcNode * node);
393
394
395private:
396 
397  /// Illegal Assignment operator
398  CbcBranchDynamicDecision & operator=(const CbcBranchDynamicDecision& rhs);
399
400  /// data
401
402  /// "best" so far
403  double bestCriterion_;
404
405  /// Change up for best
406  double bestChangeUp_;
407
408  /// Number of infeasibilities for up
409  int bestNumberUp_;
410
411  /// Change down for best
412  double bestChangeDown_;
413
414  /// Number of infeasibilities for down
415  int bestNumberDown_;
416
417  /// Pointer to best branching object
418  CbcBranchingObject * bestObject_;
419};
420#endif
Note: See TracBrowser for help on using the repository browser.