source: branches/heur/Cbc/src/CbcBranchDynamic.hpp @ 885

Last change on this file since 885 was 848, checked in by forrest, 12 years ago

try slightly different branching

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