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

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

many changes

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