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

Last change on this file since 838 was 838, checked in by forrest, 13 years ago

for deterministic parallel

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