source: trunk/Cbc/src/CbcSimpleIntegerDynamicPseudoCost.hpp @ 1424

Last change on this file since 1424 was 1389, checked in by caphillSNL, 10 years ago

Start at adding documentation, removing magic numbers, removing dead code, etc.
Added an enum for type in classes derived from CbCBranchingObject. It's safer,
handier for debugging (inspection in a debugger), and clearly shows the relationship
between the dozen or so special numbers. Numbers are the same as they were before to
ensure no changes in correctness.

File size: 15.4 KB
Line 
1// Edwin 11/17/2009 - carved out of CbcBranchDynamic
2#ifndef CbcSimpleIntegerDynamicPseudoCost_H
3#define CbcSimpleIntegerDynamicPseudoCost_H
4
5#include "CbcSimpleInteger.hpp"
6
7#define TYPERATIO 0.9
8#define MINIMUM_MOVEMENT 0.1
9#define TYPE2 0
10// was 1 - but that looks flakey
11#define INFEAS 1
12#define MOD_SHADOW 1
13// weight at 1.0 is max min
14#define WEIGHT_AFTER 0.8
15#define WEIGHT_BEFORE 0.1
16//Stolen from Constraint Integer Programming book (with epsilon change)
17#define WEIGHT_PRODUCT
18
19
20/** Define a single integer class but with dynamic pseudo costs.
21    Based on work by Achterberg, Koch and Martin.
22
23    It is wild overkill but to keep design all twiddly things are in each.
24    This could be used for fine tuning.
25
26 */
27
28
29class CbcSimpleIntegerDynamicPseudoCost : public CbcSimpleInteger {
30
31public:
32
33    // Default Constructor
34    CbcSimpleIntegerDynamicPseudoCost ();
35
36    // Useful constructor - passed  model index
37    CbcSimpleIntegerDynamicPseudoCost (CbcModel * model,  int iColumn, double breakEven = 0.5);
38
39    // Useful constructor - passed  model index and pseudo costs
40    CbcSimpleIntegerDynamicPseudoCost (CbcModel * model, int iColumn,
41                                       double downDynamicPseudoCost, double upDynamicPseudoCost);
42
43    // Useful constructor - passed  model index and pseudo costs
44    CbcSimpleIntegerDynamicPseudoCost (CbcModel * model, int dummy, int iColumn,
45                                       double downDynamicPseudoCost, double upDynamicPseudoCost);
46
47    // Copy constructor
48    CbcSimpleIntegerDynamicPseudoCost ( const CbcSimpleIntegerDynamicPseudoCost &);
49
50    /// Clone
51    virtual CbcObject * clone() const;
52
53    // Assignment operator
54    CbcSimpleIntegerDynamicPseudoCost & operator=( const CbcSimpleIntegerDynamicPseudoCost& rhs);
55
56    // Destructor
57    virtual ~CbcSimpleIntegerDynamicPseudoCost ();
58
59    /// Infeasibility - large is 0.5
60    virtual double infeasibility(const OsiBranchingInformation * info,
61                                 int &preferredWay) const;
62
63    /// Creates a branching object
64    virtual CbcBranchingObject * createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) ;
65
66
67    /// Fills in a created branching object
68    void fillCreateBranch(CbcIntegerBranchingObject * branching, const OsiBranchingInformation * info, int way) ;
69
70
71    /** Pass in information on branch just done and create CbcObjectUpdateData instance.
72        If object does not need data then backward pointer will be NULL.
73        Assumes can get information from solver */
74    virtual CbcObjectUpdateData createUpdateInformation(const OsiSolverInterface * solver,
75            const CbcNode * node,
76            const CbcBranchingObject * branchingObject);
77    /// Update object by CbcObjectUpdateData
78    virtual void updateInformation(const CbcObjectUpdateData & data) ;
79    /// Copy some information i.e. just variable stuff
80    void copySome(const CbcSimpleIntegerDynamicPseudoCost * otherObject);
81    /// Updates stuff like pseudocosts before threads
82    virtual void updateBefore(const OsiObject * rhs) ;
83    /// Updates stuff like pseudocosts after threads finished
84    virtual void updateAfter(const OsiObject * rhs, const OsiObject * baseObject) ;
85    /// Updates stuff like pseudocosts after mini branch and bound
86    void updateAfterMini(int numberDown, int numberDownInfeasible, double sumDown,
87                         int numberUp, int numberUpInfeasible, double sumUp);
88
89    using CbcSimpleInteger::solverBranch ;
90    /** Create an OsiSolverBranch object
91
92        This returns NULL if branch not represented by bound changes
93    */
94    virtual OsiSolverBranch * solverBranch() const;
95
96    /// Down pseudo cost
97    inline double downDynamicPseudoCost() const {
98        return downDynamicPseudoCost_;
99    }
100    /// Set down pseudo cost
101    void setDownDynamicPseudoCost(double value) ;
102    /// Modify down pseudo cost in a slightly different way
103    void updateDownDynamicPseudoCost(double value);
104
105    /// Up pseudo cost
106    inline double upDynamicPseudoCost() const {
107        return upDynamicPseudoCost_;
108    }
109    /// Set up pseudo cost
110    void setUpDynamicPseudoCost(double value);
111    /// Modify up pseudo cost in a slightly different way
112    void updateUpDynamicPseudoCost(double value);
113
114    /// Down pseudo shadow price cost
115    inline double downShadowPrice() const {
116        return downShadowPrice_;
117    }
118    /// Set down pseudo shadow price cost
119    inline void setDownShadowPrice(double value) {
120        downShadowPrice_ = value;
121    }
122    /// Up pseudo shadow price cost
123    inline double upShadowPrice() const {
124        return upShadowPrice_;
125    }
126    /// Set up pseudo shadow price cost
127    inline void setUpShadowPrice(double value) {
128        upShadowPrice_ = value;
129    }
130
131    /// Up down separator
132    inline double upDownSeparator() const {
133        return upDownSeparator_;
134    }
135    /// Set up down separator
136    inline void setUpDownSeparator(double value) {
137        upDownSeparator_ = value;
138    }
139
140    /// Down sum cost
141    inline double sumDownCost() const {
142        return sumDownCost_;
143    }
144    /// Set down sum cost
145    inline void setSumDownCost(double value) {
146        sumDownCost_ = value;
147    }
148    /// Add to down sum cost and set last and square
149    inline void addToSumDownCost(double value) {
150        sumDownCost_ += value;
151        lastDownCost_ = value;
152    }
153
154    /// Up sum cost
155    inline double sumUpCost() const {
156        return sumUpCost_;
157    }
158    /// Set up sum cost
159    inline void setSumUpCost(double value) {
160        sumUpCost_ = value;
161    }
162    /// Add to up sum cost and set last and square
163    inline void addToSumUpCost(double value) {
164        sumUpCost_ += value;
165        lastUpCost_ = value;
166    }
167
168    /// Down sum change
169    inline double sumDownChange() const {
170        return sumDownChange_;
171    }
172    /// Set down sum change
173    inline void setSumDownChange(double value) {
174        sumDownChange_ = value;
175    }
176    /// Add to down sum change
177    inline void addToSumDownChange(double value) {
178        sumDownChange_ += value;
179    }
180
181    /// Up sum change
182    inline double sumUpChange() const {
183        return sumUpChange_;
184    }
185    /// Set up sum change
186    inline void setSumUpChange(double value) {
187        sumUpChange_ = value;
188    }
189    /// Add to up sum change and set last and square
190    inline void addToSumUpChange(double value) {
191        sumUpChange_ += value;
192    }
193
194    /// Sum down decrease number infeasibilities from strong or actual
195    inline double sumDownDecrease() const {
196        return sumDownDecrease_;
197    }
198    /// Set sum down decrease number infeasibilities from strong or actual
199    inline void setSumDownDecrease(double value) {
200        sumDownDecrease_ = value;
201    }
202    /// Add to sum down decrease number infeasibilities from strong or actual
203    inline void addToSumDownDecrease(double value) {
204        sumDownDecrease_ += value;/*lastDownDecrease_ = (int) value;*/
205    }
206
207    /// Sum up decrease number infeasibilities from strong or actual
208    inline double sumUpDecrease() const {
209        return sumUpDecrease_;
210    }
211    /// Set sum up decrease number infeasibilities from strong or actual
212    inline void setSumUpDecrease(double value) {
213        sumUpDecrease_ = value;
214    }
215    /// Add to sum up decrease number infeasibilities from strong or actual
216    inline void addToSumUpDecrease(double value) {
217        sumUpDecrease_ += value;/*lastUpDecrease_ = (int) value;*/
218    }
219
220    /// Down number times
221    inline int numberTimesDown() const {
222        return numberTimesDown_;
223    }
224    /// Set down number times
225    inline void setNumberTimesDown(int value) {
226        numberTimesDown_ = value;
227    }
228    /// Increment down number times
229    inline void incrementNumberTimesDown() {
230        numberTimesDown_++;
231    }
232
233    /// Up number times
234    inline int numberTimesUp() const {
235        return numberTimesUp_;
236    }
237    /// Set up number times
238    inline void setNumberTimesUp(int value) {
239        numberTimesUp_ = value;
240    }
241    /// Increment up number times
242    inline void incrementNumberTimesUp() {
243        numberTimesUp_++;
244    }
245
246    /// Down number times infeasible
247    inline int numberTimesDownInfeasible() const {
248        return numberTimesDownInfeasible_;
249    }
250    /// Set down number times infeasible
251    inline void setNumberTimesDownInfeasible(int value) {
252        numberTimesDownInfeasible_ = value;
253    }
254    /// Increment down number times infeasible
255    inline void incrementNumberTimesDownInfeasible() {
256        numberTimesDownInfeasible_++;
257    }
258
259    /// Up number times infeasible
260    inline int numberTimesUpInfeasible() const {
261        return numberTimesUpInfeasible_;
262    }
263    /// Set up number times infeasible
264    inline void setNumberTimesUpInfeasible(int value) {
265        numberTimesUpInfeasible_ = value;
266    }
267    /// Increment up number times infeasible
268    inline void incrementNumberTimesUpInfeasible() {
269        numberTimesUpInfeasible_++;
270    }
271
272    /// Number of times before trusted
273    inline int numberBeforeTrust() const {
274        return numberBeforeTrust_;
275    }
276    /// Set number of times before trusted
277    inline void setNumberBeforeTrust(int value) {
278        numberBeforeTrust_ = value;
279    }
280    /// Increment number of times before trusted
281    inline void incrementNumberBeforeTrust() {
282        numberBeforeTrust_++;
283    }
284
285    /// Return "up" estimate
286    virtual double upEstimate() const;
287    /// Return "down" estimate (default 1.0e-5)
288    virtual double downEstimate() const;
289
290    /// method - see below for details
291    inline int method() const {
292        return method_;
293    }
294    /// Set method
295    inline void setMethod(int value) {
296        method_ = value;
297    }
298
299    /// Pass in information on a down branch
300    void setDownInformation(double changeObjectiveDown, int changeInfeasibilityDown);
301    /// Pass in information on a up branch
302    void setUpInformation(double changeObjectiveUp, int changeInfeasibilityUp);
303    /// Pass in probing information
304    void setProbingInformation(int fixedDown, int fixedUp);
305
306    /// Print - 0 -summary, 1 just before strong
307    void print(int type = 0, double value = 0.0) const;
308    /// Same - returns true if contents match(ish)
309    bool same(const CbcSimpleIntegerDynamicPseudoCost * obj) const;
310protected:
311    /// data
312
313    /// Down pseudo cost
314    double downDynamicPseudoCost_;
315    /// Up pseudo cost
316    double upDynamicPseudoCost_;
317    /** Up/down separator
318        If >0.0 then do first branch up if value-floor(value)
319        >= this value
320    */
321    double upDownSeparator_;
322    /// Sum down cost from strong or actual
323    double sumDownCost_;
324    /// Sum up cost from strong or actual
325    double sumUpCost_;
326    /// Sum of all changes to x when going down
327    double sumDownChange_;
328    /// Sum of all changes to x when going up
329    double sumUpChange_;
330    /// Current pseudo-shadow price estimate down
331    mutable double downShadowPrice_;
332    /// Current pseudo-shadow price estimate up
333    mutable double upShadowPrice_;
334    /// Sum down decrease number infeasibilities from strong or actual
335    double sumDownDecrease_;
336    /// Sum up decrease number infeasibilities from strong or actual
337    double sumUpDecrease_;
338    /// Last down cost from strong (i.e. as computed by last strong)
339    double lastDownCost_;
340    /// Last up cost from strong (i.e. as computed by last strong)
341    double lastUpCost_;
342    /// Last down decrease number infeasibilities from strong (i.e. as computed by last strong)
343    mutable int lastDownDecrease_;
344    /// Last up decrease number infeasibilities from strong (i.e. as computed by last strong)
345    mutable int lastUpDecrease_;
346    /// Number of times we have gone down
347    int numberTimesDown_;
348    /// Number of times we have gone up
349    int numberTimesUp_;
350    /// Number of times we have been infeasible going down
351    int numberTimesDownInfeasible_;
352    /// Number of times we have been infeasible going up
353    int numberTimesUpInfeasible_;
354    /// Number of branches before we trust
355    int numberBeforeTrust_;
356    /// Number of local probing fixings going down
357    int numberTimesDownLocalFixed_;
358    /// Number of local probing fixings going up
359    int numberTimesUpLocalFixed_;
360    /// Number of total probing fixings going down
361    double numberTimesDownTotalFixed_;
362    /// Number of total probing fixings going up
363    double numberTimesUpTotalFixed_;
364    /// Number of times probing done
365    int numberTimesProbingTotal_;
366    /// Number of times infeasible when tested
367    /** Method -
368        0 - pseudo costs
369        1 - probing
370    */
371    int method_;
372};
373/** Simple branching object for an integer variable with pseudo costs
374
375  This object can specify a two-way branch on an integer variable. For each
376  arm of the branch, the upper and lower bounds on the variable can be
377  independently specified.
378
379  Variable_ holds the index of the integer variable in the integerVariable_
380  array of the model.
381*/
382
383class CbcIntegerPseudoCostBranchingObject : public CbcIntegerBranchingObject {
384
385public:
386
387    /// Default constructor
388    CbcIntegerPseudoCostBranchingObject ();
389
390    /** Create a standard floor/ceiling branch object
391
392      Specifies a simple two-way branch. Let \p value = x*. One arm of the
393      branch will be is lb <= x <= floor(x*), the other ceil(x*) <= x <= ub.
394      Specify way = -1 to set the object state to perform the down arm first,
395      way = 1 for the up arm.
396    */
397    CbcIntegerPseudoCostBranchingObject (CbcModel *model, int variable,
398                                         int way , double value) ;
399
400    /** Create a degenerate branch object
401
402      Specifies a `one-way branch'. Calling branch() for this object will
403      always result in lowerValue <= x <= upperValue. Used to fix a variable
404      when lowerValue = upperValue.
405    */
406
407    CbcIntegerPseudoCostBranchingObject (CbcModel *model, int variable, int way,
408                                         double lowerValue, double upperValue) ;
409
410    /// Copy constructor
411    CbcIntegerPseudoCostBranchingObject ( const CbcIntegerPseudoCostBranchingObject &);
412
413    /// Assignment operator
414    CbcIntegerPseudoCostBranchingObject & operator= (const CbcIntegerPseudoCostBranchingObject& rhs);
415
416    /// Clone
417    virtual CbcBranchingObject * clone() const;
418
419    /// Destructor
420    virtual ~CbcIntegerPseudoCostBranchingObject ();
421
422    using CbcBranchingObject::branch ;
423    /** \brief Sets the bounds for the variable according to the current arm
424           of the branch and advances the object state to the next arm.
425           This version also changes guessed objective value
426    */
427    virtual double branch();
428
429    /// Change in guessed
430    inline double changeInGuessed() const {
431        return changeInGuessed_;
432    }
433    /// Set change in guessed
434    inline void setChangeInGuessed(double value) {
435        changeInGuessed_ = value;
436    }
437
438    /** Return the type (an integer identifier) of \c this */
439    virtual CbcBranchObjType type() const {
440        return SimpleIntegerDynamicPseudoCostBranchObj;
441    }
442
443    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
444        same type and must have the same original object, but they may have
445        different feasible regions.
446        Return the appropriate CbcRangeCompare value (first argument being the
447        sub/superset if that's the case). In case of overlap (and if \c
448        replaceIfOverlap is true) replace the current branching object with one
449        whose feasible region is the overlap.
450     */
451    virtual CbcRangeCompare compareBranchingObject
452    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
453
454protected:
455    /// Change in guessed objective value for next branch
456    double changeInGuessed_;
457};
458#endif
Note: See TracBrowser for help on using the repository browser.