source: stable/2.4/Cbc/src/CbcBranchDynamic.hpp @ 1271

Last change on this file since 1271 was 1271, checked in by forrest, 10 years ago

Creating new stable branch 2.4 from trunk (rev 1270)

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