source: branches/sandbox/Cbc/src/CbcBranchDynamic.hpp @ 1286

Last change on this file since 1286 was 1286, checked in by EdwinStraver, 10 years ago

Changed formatting using AStyle -A4 -p

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 18.9 KB
Line 
1/* $Id: CbcBranchDynamic.hpp 1286 2009-11-09 23:33:07Z EdwinStraver $ */
2// Copyright (C) 2005, International Business Machines
3// Corporation and others.  All Rights Reserved.
4#ifndef CbcBranchDynamic_H
5#define CbcBranchDynamic_H
6
7#include "CbcBranchActual.hpp"
8#include "CoinPackedMatrix.hpp"
9
10
11/** Define a single integer class but with dynamic pseudo costs.
12    Based on work by Achterberg, Koch and Martin.
13
14    It is wild overkill but to keep design all twiddly things are in each.
15    This could be used for fine tuning.
16
17 */
18
19
20class CbcSimpleIntegerDynamicPseudoCost : public CbcSimpleInteger {
21
22public:
23
24    // Default Constructor
25    CbcSimpleIntegerDynamicPseudoCost ();
26
27    // Useful constructor - passed  model index
28    CbcSimpleIntegerDynamicPseudoCost (CbcModel * model,  int iColumn, double breakEven = 0.5);
29
30    // Useful constructor - passed  model index and pseudo costs
31    CbcSimpleIntegerDynamicPseudoCost (CbcModel * model, int iColumn,
32                                       double downDynamicPseudoCost, double upDynamicPseudoCost);
33
34    // Useful constructor - passed  model index and pseudo costs
35    CbcSimpleIntegerDynamicPseudoCost (CbcModel * model, int dummy, int iColumn,
36                                       double downDynamicPseudoCost, double upDynamicPseudoCost);
37
38    // Copy constructor
39    CbcSimpleIntegerDynamicPseudoCost ( const CbcSimpleIntegerDynamicPseudoCost &);
40
41    /// Clone
42    virtual CbcObject * clone() const;
43
44    // Assignment operator
45    CbcSimpleIntegerDynamicPseudoCost & operator=( const CbcSimpleIntegerDynamicPseudoCost& rhs);
46
47    // Destructor
48    virtual ~CbcSimpleIntegerDynamicPseudoCost ();
49
50    /// Infeasibility - large is 0.5
51    virtual double infeasibility(const OsiBranchingInformation * info,
52                                 int &preferredWay) const;
53
54    /// Creates a branching object
55    virtual CbcBranchingObject * createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) ;
56
57
58    /// Fills in a created branching object
59    void fillCreateBranch(CbcIntegerBranchingObject * branching, const OsiBranchingInformation * info, int way) ;
60
61
62    /** Pass in information on branch just done and create CbcObjectUpdateData instance.
63        If object does not need data then backward pointer will be NULL.
64        Assumes can get information from solver */
65    virtual CbcObjectUpdateData createUpdateInformation(const OsiSolverInterface * solver,
66            const CbcNode * node,
67            const CbcBranchingObject * branchingObject);
68    /// Update object by CbcObjectUpdateData
69    virtual void updateInformation(const CbcObjectUpdateData & data) ;
70    /// Copy some information i.e. just variable stuff
71    void copySome(const CbcSimpleIntegerDynamicPseudoCost * otherObject);
72    /// Updates stuff like pseudocosts before threads
73    virtual void updateBefore(const OsiObject * rhs) ;
74    /// Updates stuff like pseudocosts after threads finished
75    virtual void updateAfter(const OsiObject * rhs, const OsiObject * baseObject) ;
76    /// Updates stuff like pseudocosts after mini branch and bound
77    void updateAfterMini(int numberDown, int numberDownInfeasible, double sumDown,
78                         int numberUp, int numberUpInfeasible, double sumUp);
79
80    using CbcSimpleInteger::solverBranch ;
81    /** Create an OsiSolverBranch object
82
83        This returns NULL if branch not represented by bound changes
84    */
85    virtual OsiSolverBranch * solverBranch() const;
86
87    /// Down pseudo cost
88    inline double downDynamicPseudoCost() const {
89        return downDynamicPseudoCost_;
90    }
91    /// Set down pseudo cost
92    void setDownDynamicPseudoCost(double value) ;
93    /// Modify down pseudo cost in a slightly different way
94    void updateDownDynamicPseudoCost(double value);
95
96    /// Up pseudo cost
97    inline double upDynamicPseudoCost() const {
98        return upDynamicPseudoCost_;
99    }
100    /// Set up pseudo cost
101    void setUpDynamicPseudoCost(double value);
102    /// Modify up pseudo cost in a slightly different way
103    void updateUpDynamicPseudoCost(double value);
104
105    /// Down pseudo shadow price cost
106    inline double downShadowPrice() const {
107        return downShadowPrice_;
108    }
109    /// Set down pseudo shadow price cost
110    inline void setDownShadowPrice(double value) {
111        downShadowPrice_ = value;
112    }
113    /// Up pseudo shadow price cost
114    inline double upShadowPrice() const {
115        return upShadowPrice_;
116    }
117    /// Set up pseudo shadow price cost
118    inline void setUpShadowPrice(double value) {
119        upShadowPrice_ = value;
120    }
121
122    /// Up down separator
123    inline double upDownSeparator() const {
124        return upDownSeparator_;
125    }
126    /// Set up down separator
127    inline void setUpDownSeparator(double value) {
128        upDownSeparator_ = value;
129    }
130
131    /// Down sum cost
132    inline double sumDownCost() const {
133        return sumDownCost_;
134    }
135    /// Set down sum cost
136    inline void setSumDownCost(double value) {
137        sumDownCost_ = value;
138    }
139    /// Add to down sum cost and set last and square
140    inline void addToSumDownCost(double value) {
141        sumDownCost_ += value;
142        lastDownCost_ = value;
143    }
144
145    /// Up sum cost
146    inline double sumUpCost() const {
147        return sumUpCost_;
148    }
149    /// Set up sum cost
150    inline void setSumUpCost(double value) {
151        sumUpCost_ = value;
152    }
153    /// Add to up sum cost and set last and square
154    inline void addToSumUpCost(double value) {
155        sumUpCost_ += value;
156        lastUpCost_ = value;
157    }
158
159    /// Down sum change
160    inline double sumDownChange() const {
161        return sumDownChange_;
162    }
163    /// Set down sum change
164    inline void setSumDownChange(double value) {
165        sumDownChange_ = value;
166    }
167    /// Add to down sum change
168    inline void addToSumDownChange(double value) {
169        sumDownChange_ += value;
170    }
171
172    /// Up sum change
173    inline double sumUpChange() const {
174        return sumUpChange_;
175    }
176    /// Set up sum change
177    inline void setSumUpChange(double value) {
178        sumUpChange_ = value;
179    }
180    /// Add to up sum change and set last and square
181    inline void addToSumUpChange(double value) {
182        sumUpChange_ += value;
183    }
184
185    /// Sum down decrease number infeasibilities from strong or actual
186    inline double sumDownDecrease() const {
187        return sumDownDecrease_;
188    }
189    /// Set sum down decrease number infeasibilities from strong or actual
190    inline void setSumDownDecrease(double value) {
191        sumDownDecrease_ = value;
192    }
193    /// Add to sum down decrease number infeasibilities from strong or actual
194    inline void addToSumDownDecrease(double value) {
195        sumDownDecrease_ += value;/*lastDownDecrease_ = (int) value;*/
196    }
197
198    /// Sum up decrease number infeasibilities from strong or actual
199    inline double sumUpDecrease() const {
200        return sumUpDecrease_;
201    }
202    /// Set sum up decrease number infeasibilities from strong or actual
203    inline void setSumUpDecrease(double value) {
204        sumUpDecrease_ = value;
205    }
206    /// Add to sum up decrease number infeasibilities from strong or actual
207    inline void addToSumUpDecrease(double value) {
208        sumUpDecrease_ += value;/*lastUpDecrease_ = (int) value;*/
209    }
210
211    /// Down number times
212    inline int numberTimesDown() const {
213        return numberTimesDown_;
214    }
215    /// Set down number times
216    inline void setNumberTimesDown(int value) {
217        numberTimesDown_ = value;
218    }
219    /// Increment down number times
220    inline void incrementNumberTimesDown() {
221        numberTimesDown_++;
222    }
223
224    /// Up number times
225    inline int numberTimesUp() const {
226        return numberTimesUp_;
227    }
228    /// Set up number times
229    inline void setNumberTimesUp(int value) {
230        numberTimesUp_ = value;
231    }
232    /// Increment up number times
233    inline void incrementNumberTimesUp() {
234        numberTimesUp_++;
235    }
236
237    /// Down number times infeasible
238    inline int numberTimesDownInfeasible() const {
239        return numberTimesDownInfeasible_;
240    }
241    /// Set down number times infeasible
242    inline void setNumberTimesDownInfeasible(int value) {
243        numberTimesDownInfeasible_ = value;
244    }
245    /// Increment down number times infeasible
246    inline void incrementNumberTimesDownInfeasible() {
247        numberTimesDownInfeasible_++;
248    }
249
250    /// Up number times infeasible
251    inline int numberTimesUpInfeasible() const {
252        return numberTimesUpInfeasible_;
253    }
254    /// Set up number times infeasible
255    inline void setNumberTimesUpInfeasible(int value) {
256        numberTimesUpInfeasible_ = value;
257    }
258    /// Increment up number times infeasible
259    inline void incrementNumberTimesUpInfeasible() {
260        numberTimesUpInfeasible_++;
261    }
262
263    /// Number of times before trusted
264    inline int numberBeforeTrust() const {
265        return numberBeforeTrust_;
266    }
267    /// Set number of times before trusted
268    inline void setNumberBeforeTrust(int value) {
269        numberBeforeTrust_ = value;
270    }
271    /// Increment number of times before trusted
272    inline void incrementNumberBeforeTrust() {
273        numberBeforeTrust_++;
274    }
275
276    /// Return "up" estimate
277    virtual double upEstimate() const;
278    /// Return "down" estimate (default 1.0e-5)
279    virtual double downEstimate() const;
280
281    /// method - see below for details
282    inline int method() const {
283        return method_;
284    }
285    /// Set method
286    inline void setMethod(int value) {
287        method_ = value;
288    }
289
290    /// Pass in information on a down branch
291    void setDownInformation(double changeObjectiveDown, int changeInfeasibilityDown);
292    /// Pass in information on a up branch
293    void setUpInformation(double changeObjectiveUp, int changeInfeasibilityUp);
294    /// Pass in probing information
295    void setProbingInformation(int fixedDown, int fixedUp);
296
297    /// Print - 0 -summary, 1 just before strong
298    void print(int type = 0, double value = 0.0) const;
299    /// Same - returns true if contents match(ish)
300    bool same(const CbcSimpleIntegerDynamicPseudoCost * obj) const;
301protected:
302    /// data
303
304    /// Down pseudo cost
305    double downDynamicPseudoCost_;
306    /// Up pseudo cost
307    double upDynamicPseudoCost_;
308    /** Up/down separator
309        If >0.0 then do first branch up if value-floor(value)
310        >= this value
311    */
312    double upDownSeparator_;
313    /// Sum down cost from strong or actual
314    double sumDownCost_;
315    /// Sum up cost from strong or actual
316    double sumUpCost_;
317    /// Sum of all changes to x when going down
318    double sumDownChange_;
319    /// Sum of all changes to x when going up
320    double sumUpChange_;
321    /// Current pseudo-shadow price estimate down
322    mutable double downShadowPrice_;
323    /// Current pseudo-shadow price estimate up
324    mutable double upShadowPrice_;
325    /// Sum down decrease number infeasibilities from strong or actual
326    double sumDownDecrease_;
327    /// Sum up decrease number infeasibilities from strong or actual
328    double sumUpDecrease_;
329    /// Last down cost from strong (i.e. as computed by last strong)
330    double lastDownCost_;
331    /// Last up cost from strong (i.e. as computed by last strong)
332    double lastUpCost_;
333    /// Last down decrease number infeasibilities from strong (i.e. as computed by last strong)
334    mutable int lastDownDecrease_;
335    /// Last up decrease number infeasibilities from strong (i.e. as computed by last strong)
336    mutable int lastUpDecrease_;
337    /// Number of times we have gone down
338    int numberTimesDown_;
339    /// Number of times we have gone up
340    int numberTimesUp_;
341    /// Number of times we have been infeasible going down
342    int numberTimesDownInfeasible_;
343    /// Number of times we have been infeasible going up
344    int numberTimesUpInfeasible_;
345    /// Number of branches before we trust
346    int numberBeforeTrust_;
347    /// Number of local probing fixings going down
348    int numberTimesDownLocalFixed_;
349    /// Number of local probing fixings going up
350    int numberTimesUpLocalFixed_;
351    /// Number of total probing fixings going down
352    double numberTimesDownTotalFixed_;
353    /// Number of total probing fixings going up
354    double numberTimesUpTotalFixed_;
355    /// Number of times probing done
356    int numberTimesProbingTotal_;
357    /// Number of times infeasible when tested
358    /** Method -
359        0 - pseudo costs
360        1 - probing
361    */
362    int method_;
363};
364
365
366/** Simple branching object for an integer variable with pseudo costs
367
368  This object can specify a two-way branch on an integer variable. For each
369  arm of the branch, the upper and lower bounds on the variable can be
370  independently specified.
371
372  Variable_ holds the index of the integer variable in the integerVariable_
373  array of the model.
374*/
375
376class CbcDynamicPseudoCostBranchingObject : public CbcIntegerBranchingObject {
377
378public:
379
380    /// Default constructor
381    CbcDynamicPseudoCostBranchingObject ();
382
383    /** Create a standard floor/ceiling branch object
384
385      Specifies a simple two-way branch. Let \p value = x*. One arm of the
386      branch will be is lb <= x <= floor(x*), the other ceil(x*) <= x <= ub.
387      Specify way = -1 to set the object state to perform the down arm first,
388      way = 1 for the up arm.
389    */
390    CbcDynamicPseudoCostBranchingObject (CbcModel *model, int variable,
391                                         int way , double value,
392                                         CbcSimpleIntegerDynamicPseudoCost * object) ;
393
394    /** Create a degenerate branch object
395
396      Specifies a `one-way branch'. Calling branch() for this object will
397      always result in lowerValue <= x <= upperValue. Used to fix a variable
398      when lowerValue = upperValue.
399    */
400
401    CbcDynamicPseudoCostBranchingObject (CbcModel *model, int variable, int way,
402                                         double lowerValue, double upperValue) ;
403
404    /// Copy constructor
405    CbcDynamicPseudoCostBranchingObject ( const CbcDynamicPseudoCostBranchingObject &);
406
407    /// Assignment operator
408    CbcDynamicPseudoCostBranchingObject & operator= (const CbcDynamicPseudoCostBranchingObject& rhs);
409
410    /// Clone
411    virtual CbcBranchingObject * clone() const;
412
413    /// Destructor
414    virtual ~CbcDynamicPseudoCostBranchingObject ();
415
416    /// Does part of constructor
417    void fillPart (int variable,
418                   int way , double value,
419                   CbcSimpleIntegerDynamicPseudoCost * object) ;
420
421    using CbcBranchingObject::branch ;
422    /** \brief Sets the bounds for the variable according to the current arm
423           of the branch and advances the object state to the next arm.
424           This version also changes guessed objective value
425    */
426    virtual double branch();
427
428    /** Some branchingObjects may claim to be able to skip
429        strong branching.  If so they have to fill in CbcStrongInfo.
430        The object mention in incoming CbcStrongInfo must match.
431        Returns nonzero if skip is wanted */
432    virtual int fillStrongInfo( CbcStrongInfo & info);
433
434    /// Change in guessed
435    inline double changeInGuessed() const {
436        return changeInGuessed_;
437    }
438    /// Set change in guessed
439    inline void setChangeInGuessed(double value) {
440        changeInGuessed_ = value;
441    }
442    /// Return object
443    inline CbcSimpleIntegerDynamicPseudoCost * object() const {
444        return object_;
445    }
446    /// Set object
447    inline void setObject(CbcSimpleIntegerDynamicPseudoCost * object) {
448        object_ = object;
449    }
450
451    /** Return the type (an integer identifier) of \c this */
452    virtual int type() const {
453        return 400;
454    }
455
456    // LL: compareOriginalObject and compareBranchingObject are inherited from
457    // CbcIntegerBranchingObject thus need not be declared/defined here. After
458    // all, this kind of branching object is simply using pseudocosts to make
459    // decisions, but once the decisions are made they are the same kind as in
460    // the underlying class.
461
462protected:
463    /// Change in guessed objective value for next branch
464    double changeInGuessed_;
465    /// Pointer back to object
466    CbcSimpleIntegerDynamicPseudoCost * object_;
467
468};
469/** Branching decision dynamic class
470
471  This class implements a simple algorithm
472  (betterBranch()) for choosing a branching variable when dynamic pseudo costs.
473*/
474
475class CbcBranchDynamicDecision : public CbcBranchDecision {
476public:
477    // Default Constructor
478    CbcBranchDynamicDecision ();
479
480    // Copy constructor
481    CbcBranchDynamicDecision ( const CbcBranchDynamicDecision &);
482
483    virtual ~CbcBranchDynamicDecision();
484
485    /// Clone
486    virtual CbcBranchDecision * clone() const;
487
488    /// Initialize, <i>e.g.</i> before the start of branch selection at a node
489    virtual void initialize(CbcModel * model);
490
491    /** \brief Compare two branching objects. Return nonzero if \p thisOne is
492           better than \p bestSoFar.
493
494      The routine compares branches using the values supplied in \p numInfUp and
495      \p numInfDn until a solution is found by search, after which it uses the
496      values supplied in \p changeUp and \p changeDn. The best branching object
497      seen so far and the associated parameter values are remembered in the
498      \c CbcBranchDynamicDecision object. The nonzero return value is +1 if the
499      up branch is preferred, -1 if the down branch is preferred.
500
501      As the names imply, the assumption is that the values supplied for
502      \p numInfUp and \p numInfDn will be the number of infeasibilities reported
503      by the branching object, and \p changeUp and \p changeDn will be the
504      estimated change in objective. Other measures can be used if desired.
505
506      Because an \c CbcBranchDynamicDecision object remembers the current best
507      branching candidate (#bestObject_) as well as the values used in the
508      comparison, the parameter \p bestSoFar is redundant, hence unused.
509    */
510    virtual int betterBranch(CbcBranchingObject * thisOne,
511                             CbcBranchingObject * bestSoFar,
512                             double changeUp, int numInfUp,
513                             double changeDn, int numInfDn);
514    /** Sets or gets best criterion so far */
515    virtual void setBestCriterion(double value);
516    virtual double getBestCriterion() const;
517    /** Says whether this method can handle both methods -
518        1 better, 2 best, 3 both */
519    virtual int whichMethod() {
520        return 3;
521    }
522
523    /** Saves a clone of current branching object.  Can be used to update
524        information on object causing branch - after branch */
525    virtual void saveBranchingObject(OsiBranchingObject * object) ;
526    /** Pass in information on branch just done.
527        assumes object can get information from solver */
528    virtual void updateInformation(OsiSolverInterface * solver,
529                                   const CbcNode * node);
530
531
532private:
533
534    /// Illegal Assignment operator
535    CbcBranchDynamicDecision & operator=(const CbcBranchDynamicDecision& rhs);
536
537    /// data
538
539    /// "best" so far
540    double bestCriterion_;
541
542    /// Change up for best
543    double bestChangeUp_;
544
545    /// Number of infeasibilities for up
546    int bestNumberUp_;
547
548    /// Change down for best
549    double bestChangeDown_;
550
551    /// Number of infeasibilities for down
552    int bestNumberDown_;
553
554    /// Pointer to best branching object
555    CbcBranchingObject * bestObject_;
556};
557#endif
Note: See TracBrowser for help on using the repository browser.