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

Last change on this file since 912 was 912, checked in by ladanyi, 13 years ago

Incorporated changes from branches/heur

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 17.1 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;}
395
396  /** Return the type (an integer identifier) of \c this */
397  virtual int type() const { return 400; }
398
399  // LL: compareOriginalObject and compareBranchingObject are inherited from
400  // CbcIntegerBranchingObject thus need not be declared/defined here. After
401  // all, this kind of branching object is simply using pseudocosts to make
402  // decisions, but once the decisions are made they are the same kind as in
403  // the underlying class.
404
405protected:
406  /// Change in guessed objective value for next branch
407  double changeInGuessed_;
408  /// Pointer back to object
409  CbcSimpleIntegerDynamicPseudoCost * object_;
410
411};
412/** Branching decision dynamic class
413
414  This class implements a simple algorithm
415  (betterBranch()) for choosing a branching variable when dynamic pseudo costs.
416*/
417
418class CbcBranchDynamicDecision : public CbcBranchDecision {
419public:
420  // Default Constructor
421  CbcBranchDynamicDecision ();
422
423  // Copy constructor
424  CbcBranchDynamicDecision ( const CbcBranchDynamicDecision &);
425
426  virtual ~CbcBranchDynamicDecision();
427
428  /// Clone
429  virtual CbcBranchDecision * clone() const;
430
431  /// Initialize, <i>e.g.</i> before the start of branch selection at a node
432  virtual void initialize(CbcModel * model);
433
434  /** \brief Compare two branching objects. Return nonzero if \p thisOne is
435             better than \p bestSoFar.
436
437    The routine compares branches using the values supplied in \p numInfUp and
438    \p numInfDn until a solution is found by search, after which it uses the
439    values supplied in \p changeUp and \p changeDn. The best branching object
440    seen so far and the associated parameter values are remembered in the
441    \c CbcBranchDynamicDecision object. The nonzero return value is +1 if the
442    up branch is preferred, -1 if the down branch is preferred.
443
444    As the names imply, the assumption is that the values supplied for
445    \p numInfUp and \p numInfDn will be the number of infeasibilities reported
446    by the branching object, and \p changeUp and \p changeDn will be the
447    estimated change in objective. Other measures can be used if desired.
448
449    Because an \c CbcBranchDynamicDecision object remembers the current best
450    branching candidate (#bestObject_) as well as the values used in the
451    comparison, the parameter \p bestSoFar is redundant, hence unused.
452 */
453  virtual int betterBranch(CbcBranchingObject * thisOne,
454                            CbcBranchingObject * bestSoFar,
455                            double changeUp, int numInfUp,
456                            double changeDn, int numInfDn);
457  /** Sets or gets best criterion so far */
458  virtual void setBestCriterion(double value);
459  virtual double getBestCriterion() const;
460  /** Says whether this method can handle both methods -
461      1 better, 2 best, 3 both */
462  virtual int whichMethod() {return 3;}
463
464  /** Saves a clone of current branching object.  Can be used to update
465      information on object causing branch - after branch */
466  virtual void saveBranchingObject(OsiBranchingObject * object) ;
467  /** Pass in information on branch just done.
468      assumes object can get information from solver */
469  virtual void updateInformation(OsiSolverInterface * solver,
470                                 const CbcNode * node);
471
472
473private:
474 
475  /// Illegal Assignment operator
476  CbcBranchDynamicDecision & operator=(const CbcBranchDynamicDecision& rhs);
477
478  /// data
479
480  /// "best" so far
481  double bestCriterion_;
482
483  /// Change up for best
484  double bestChangeUp_;
485
486  /// Number of infeasibilities for up
487  int bestNumberUp_;
488
489  /// Change down for best
490  double bestChangeDown_;
491
492  /// Number of infeasibilities for down
493  int bestNumberDown_;
494
495  /// Pointer to best branching object
496  CbcBranchingObject * bestObject_;
497};
498#endif
Note: See TracBrowser for help on using the repository browser.