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

Last change on this file since 765 was 765, checked in by andreasw, 14 years ago

merging changes from Bug Squashing Party Aug 2007 to regular trunk

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