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

Last change on this file since 484 was 439, checked in by forrest, 13 years ago

towards common use with other solvers

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