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

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

compiler warnings, deterministic parallel and stability

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