source: branches/devel/Cbc/src/CbcBranchDynamic.hpp

Last change on this file was 662, checked in by forrest, 12 years ago

faster parallel?

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