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

Last change on this file since 2094 was 2094, checked in by forrest, 4 years ago

for memory leaks and heuristics and some experimental stuff

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 18.4 KB
Line 
1// $Id: CbcSimpleIntegerDynamicPseudoCost.hpp 2094 2014-11-18 11:15:36Z forrest $
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    /// Number times branched
253    inline int numberTimesBranched() const {
254        return numberTimesDown_ + numberTimesUp_;
255    }
256    /// Down number times infeasible
257    inline int numberTimesDownInfeasible() const {
258        return numberTimesDownInfeasible_;
259    }
260    /// Set down number times infeasible
261    inline void setNumberTimesDownInfeasible(int value) {
262        numberTimesDownInfeasible_ = value;
263    }
264    /// Increment down number times infeasible
265    inline void incrementNumberTimesDownInfeasible() {
266        numberTimesDownInfeasible_++;
267    }
268
269    /// Up number times infeasible
270    inline int numberTimesUpInfeasible() const {
271        return numberTimesUpInfeasible_;
272    }
273    /// Set up number times infeasible
274    inline void setNumberTimesUpInfeasible(int value) {
275        numberTimesUpInfeasible_ = value;
276    }
277    /// Increment up number times infeasible
278    inline void incrementNumberTimesUpInfeasible() {
279        numberTimesUpInfeasible_++;
280    }
281
282    /// Number of times before trusted
283    inline int numberBeforeTrust() const {
284        return numberBeforeTrust_;
285    }
286    /// Set number of times before trusted
287    inline void setNumberBeforeTrust(int value) {
288        numberBeforeTrust_ = value;
289    }
290    /// Increment number of times before trusted
291    inline void incrementNumberBeforeTrust() {
292        numberBeforeTrust_++;
293    }
294
295    /// Return "up" estimate
296    virtual double upEstimate() const;
297    /// Return "down" estimate (default 1.0e-5)
298    virtual double downEstimate() const;
299
300    /// method - see below for details
301    inline int method() const {
302        return method_;
303    }
304    /// Set method
305    inline void setMethod(int value) {
306        method_ = value;
307    }
308
309    /// Pass in information on a down branch
310    void setDownInformation(double changeObjectiveDown, int changeInfeasibilityDown);
311    /// Pass in information on a up branch
312    void setUpInformation(double changeObjectiveUp, int changeInfeasibilityUp);
313    /// Pass in probing information
314    void setProbingInformation(int fixedDown, int fixedUp);
315
316    /// Print - 0 -summary, 1 just before strong
317    void print(int type = 0, double value = 0.0) const;
318    /// Same - returns true if contents match(ish)
319    bool same(const CbcSimpleIntegerDynamicPseudoCost * obj) const;
320protected:
321    /// data
322
323    /// Down pseudo cost
324    double downDynamicPseudoCost_;
325    /// Up pseudo cost
326    double upDynamicPseudoCost_;
327    /** Up/down separator
328        If >0.0 then do first branch up if value-floor(value)
329        >= this value
330    */
331    double upDownSeparator_;
332    /// Sum down cost from strong or actual
333    double sumDownCost_;
334    /// Sum up cost from strong or actual
335    double sumUpCost_;
336    /// Sum of all changes to x when going down
337    double sumDownChange_;
338    /// Sum of all changes to x when going up
339    double sumUpChange_;
340    /// Current pseudo-shadow price estimate down
341    mutable double downShadowPrice_;
342    /// Current pseudo-shadow price estimate up
343    mutable double upShadowPrice_;
344    /// Sum down decrease number infeasibilities from strong or actual
345    double sumDownDecrease_;
346    /// Sum up decrease number infeasibilities from strong or actual
347    double sumUpDecrease_;
348    /// Last down cost from strong (i.e. as computed by last strong)
349    double lastDownCost_;
350    /// Last up cost from strong (i.e. as computed by last strong)
351    double lastUpCost_;
352    /// Last down decrease number infeasibilities from strong (i.e. as computed by last strong)
353    mutable int lastDownDecrease_;
354    /// Last up decrease number infeasibilities from strong (i.e. as computed by last strong)
355    mutable int lastUpDecrease_;
356    /// Number of times we have gone down
357    int numberTimesDown_;
358    /// Number of times we have gone up
359    int numberTimesUp_;
360    /// Number of times we have been infeasible going down
361    int numberTimesDownInfeasible_;
362    /// Number of times we have been infeasible going up
363    int numberTimesUpInfeasible_;
364    /// Number of branches before we trust
365    int numberBeforeTrust_;
366    /// Number of local probing fixings going down
367    int numberTimesDownLocalFixed_;
368    /// Number of local probing fixings going up
369    int numberTimesUpLocalFixed_;
370    /// Number of total probing fixings going down
371    double numberTimesDownTotalFixed_;
372    /// Number of total probing fixings going up
373    double numberTimesUpTotalFixed_;
374    /// Number of times probing done
375    int numberTimesProbingTotal_;
376    /// Number of times infeasible when tested
377    /** Method -
378        0 - pseudo costs
379        1 - probing
380    */
381    int method_;
382};
383/** Simple branching object for an integer variable with pseudo costs
384
385  This object can specify a two-way branch on an integer variable. For each
386  arm of the branch, the upper and lower bounds on the variable can be
387  independently specified.
388
389  Variable_ holds the index of the integer variable in the integerVariable_
390  array of the model.
391*/
392
393class CbcIntegerPseudoCostBranchingObject : public CbcIntegerBranchingObject {
394
395public:
396
397    /// Default constructor
398    CbcIntegerPseudoCostBranchingObject ();
399
400    /** Create a standard floor/ceiling branch object
401
402      Specifies a simple two-way branch. Let \p value = x*. One arm of the
403      branch will be is lb <= x <= floor(x*), the other ceil(x*) <= x <= ub.
404      Specify way = -1 to set the object state to perform the down arm first,
405      way = 1 for the up arm.
406    */
407    CbcIntegerPseudoCostBranchingObject (CbcModel *model, int variable,
408                                         int way , double value) ;
409
410    /** Create a degenerate branch object
411
412      Specifies a `one-way branch'. Calling branch() for this object will
413      always result in lowerValue <= x <= upperValue. Used to fix a variable
414      when lowerValue = upperValue.
415    */
416
417    CbcIntegerPseudoCostBranchingObject (CbcModel *model, int variable, int way,
418                                         double lowerValue, double upperValue) ;
419
420    /// Copy constructor
421    CbcIntegerPseudoCostBranchingObject ( const CbcIntegerPseudoCostBranchingObject &);
422
423    /// Assignment operator
424    CbcIntegerPseudoCostBranchingObject & operator= (const CbcIntegerPseudoCostBranchingObject& rhs);
425
426    /// Clone
427    virtual CbcBranchingObject * clone() const;
428
429    /// Destructor
430    virtual ~CbcIntegerPseudoCostBranchingObject ();
431
432    using CbcBranchingObject::branch ;
433    /** \brief Sets the bounds for the variable according to the current arm
434           of the branch and advances the object state to the next arm.
435           This version also changes guessed objective value
436    */
437    virtual double branch();
438
439    /// Change in guessed
440    inline double changeInGuessed() const {
441        return changeInGuessed_;
442    }
443    /// Set change in guessed
444    inline void setChangeInGuessed(double value) {
445        changeInGuessed_ = value;
446    }
447
448    /** Return the type (an integer identifier) of \c this */
449    virtual CbcBranchObjType type() const {
450        return SimpleIntegerDynamicPseudoCostBranchObj;
451    }
452
453    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
454        same type and must have the same original object, but they may have
455        different feasible regions.
456        Return the appropriate CbcRangeCompare value (first argument being the
457        sub/superset if that's the case). In case of overlap (and if \c
458        replaceIfOverlap is true) replace the current branching object with one
459        whose feasible region is the overlap.
460     */
461    virtual CbcRangeCompare compareBranchingObject
462    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
463
464protected:
465    /// Change in guessed objective value for next branch
466    double changeInGuessed_;
467};
468#ifdef SWITCH_VARIABLES
469/** Define a single integer class but with associated switched variable
470    So Binary variable switches on/off a continuous variable
471    designed for badly scaled problems
472 */
473
474
475class CbcSwitchingBinary : public CbcSimpleIntegerDynamicPseudoCost {
476
477public:
478
479    // Default Constructor
480    CbcSwitchingBinary ();
481
482    // Useful constructor
483    CbcSwitchingBinary (CbcSimpleIntegerDynamicPseudoCost * oldObject,
484                        int nOdd,const int * other, const int * otherRow);
485
486
487    // Copy constructor
488    CbcSwitchingBinary ( const CbcSwitchingBinary &);
489
490    /// Clone
491    virtual CbcObject * clone() const;
492
493    // Assignment operator
494    CbcSwitchingBinary & operator=( const CbcSwitchingBinary& rhs);
495
496    // Destructor
497    virtual ~CbcSwitchingBinary ();
498
499    /// Add in zero switches
500    void addZeroSwitches(int nAdd,const int * columns);
501    /// Infeasibility - large is 0.5
502    virtual double infeasibility(const OsiBranchingInformation * info,
503                                 int &preferredWay) const;
504
505    /// Same - returns true if contents match(ish)
506    bool same(const CbcSwitchingBinary * obj) const;
507    /// Set associated bounds
508    virtual int setAssociatedBounds(OsiSolverInterface * solver=NULL,
509                          int cleanBasis=0) const;
510    /// Check associated bounds
511    int checkAssociatedBounds(const OsiSolverInterface * solver,const double * solution,
512                              int printLevel, int state[3], int & nBadFixed) const;
513    /// Lower bound when binary zero
514    inline const double * zeroLowerBound() const
515    { return zeroLowerBound_; }
516    /// Lower bound when binary one
517    inline const double * oneLowerBound() const
518    { return oneLowerBound_; }
519    /// Upper bound when binary zero
520    inline const double * zeroUpperBound() const
521    { return zeroUpperBound_; }
522    /// Upper bound when binary one
523    inline const double * oneUpperBound() const
524    { return oneUpperBound_; }
525    /** Continuous variable -
526    */
527    inline const int * otherVariable() const
528    { return otherVariable_;}
529    /// Number of other variables
530    inline int numberOther() const
531    { return numberOther_;}
532    /** Type
533        1 - single switch
534        2 - double switch
535        3 - both
536    */
537    inline int type() const
538    { return type_;}
539protected:
540    /// data
541
542    /// Lower bound when binary zero
543    double * zeroLowerBound_;
544    /// Lower bound when binary one
545    double * oneLowerBound_;
546    /// Upper bound when binary zero
547    double * zeroUpperBound_;
548    /// Upper bound when binary one
549    double * oneUpperBound_;
550    /** Continuous variable -
551    */
552    int * otherVariable_;
553    /// Number of other variables
554    int numberOther_;
555    /** Type
556        1 - single switch
557        2 - double switch
558        3 - both
559    */
560    int type_;
561};
562#endif
563#endif
564
Note: See TracBrowser for help on using the repository browser.