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

Last change on this file since 1733 was 1573, checked in by lou, 9 years ago

Change to EPL license notice.

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