1 | /* $Id: CbcBranchDynamic.hpp 2465 2019-01-03 19:26:52Z unxusr $ */ |
---|
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 | #ifndef CbcBranchDynamic_H |
---|
7 | #define CbcBranchDynamic_H |
---|
8 | |
---|
9 | #include "CoinPackedMatrix.hpp" |
---|
10 | #include "CbcSimpleIntegerDynamicPseudoCost.hpp" |
---|
11 | #include "CbcBranchActual.hpp" |
---|
12 | |
---|
13 | /** Branching decision dynamic class |
---|
14 | |
---|
15 | This class implements a simple algorithm |
---|
16 | (betterBranch()) for choosing a branching variable when dynamic pseudo costs. |
---|
17 | */ |
---|
18 | |
---|
19 | class CbcBranchDynamicDecision : public CbcBranchDecision { |
---|
20 | public: |
---|
21 | // Default Constructor |
---|
22 | CbcBranchDynamicDecision(); |
---|
23 | |
---|
24 | // Copy constructor |
---|
25 | CbcBranchDynamicDecision(const CbcBranchDynamicDecision &); |
---|
26 | |
---|
27 | virtual ~CbcBranchDynamicDecision(); |
---|
28 | |
---|
29 | /// Clone |
---|
30 | virtual CbcBranchDecision *clone() const; |
---|
31 | |
---|
32 | /// Initialize, <i>e.g.</i> before the start of branch selection at a node |
---|
33 | virtual void initialize(CbcModel *model); |
---|
34 | |
---|
35 | /** \brief Compare two branching objects. Return nonzero if \p thisOne is |
---|
36 | better than \p bestSoFar. |
---|
37 | |
---|
38 | The routine compares branches using the values supplied in \p numInfUp and |
---|
39 | \p numInfDn until a solution is found by search, after which it uses the |
---|
40 | values supplied in \p changeUp and \p changeDn. The best branching object |
---|
41 | seen so far and the associated parameter values are remembered in the |
---|
42 | \c CbcBranchDynamicDecision object. The nonzero return value is +1 if the |
---|
43 | up branch is preferred, -1 if the down branch is preferred. |
---|
44 | |
---|
45 | As the names imply, the assumption is that the values supplied for |
---|
46 | \p numInfUp and \p numInfDn will be the number of infeasibilities reported |
---|
47 | by the branching object, and \p changeUp and \p changeDn will be the |
---|
48 | estimated change in objective. Other measures can be used if desired. |
---|
49 | |
---|
50 | Because an \c CbcBranchDynamicDecision object remembers the current best |
---|
51 | branching candidate (#bestObject_) as well as the values used in the |
---|
52 | comparison, the parameter \p bestSoFar is redundant, hence unused. |
---|
53 | */ |
---|
54 | virtual int betterBranch(CbcBranchingObject *thisOne, |
---|
55 | CbcBranchingObject *bestSoFar, |
---|
56 | double changeUp, int numInfUp, |
---|
57 | double changeDn, int numInfDn); |
---|
58 | /** Sets or gets best criterion so far */ |
---|
59 | virtual void setBestCriterion(double value); |
---|
60 | virtual double getBestCriterion() const; |
---|
61 | /** Says whether this method can handle both methods - |
---|
62 | 1 better, 2 best, 3 both */ |
---|
63 | virtual int whichMethod() |
---|
64 | { |
---|
65 | return 3; |
---|
66 | } |
---|
67 | |
---|
68 | /** Saves a clone of current branching object. Can be used to update |
---|
69 | information on object causing branch - after branch */ |
---|
70 | virtual void saveBranchingObject(OsiBranchingObject *object); |
---|
71 | /** Pass in information on branch just done. |
---|
72 | assumes object can get information from solver */ |
---|
73 | virtual void updateInformation(OsiSolverInterface *solver, |
---|
74 | const CbcNode *node); |
---|
75 | |
---|
76 | private: |
---|
77 | /// Illegal Assignment operator |
---|
78 | CbcBranchDynamicDecision &operator=(const CbcBranchDynamicDecision &rhs); |
---|
79 | |
---|
80 | /// data |
---|
81 | |
---|
82 | /// "best" so far |
---|
83 | double bestCriterion_; |
---|
84 | |
---|
85 | /// Change up for best |
---|
86 | double bestChangeUp_; |
---|
87 | |
---|
88 | /// Number of infeasibilities for up |
---|
89 | int bestNumberUp_; |
---|
90 | |
---|
91 | /// Change down for best |
---|
92 | double bestChangeDown_; |
---|
93 | |
---|
94 | /// Number of infeasibilities for down |
---|
95 | int bestNumberDown_; |
---|
96 | |
---|
97 | /// Pointer to best branching object |
---|
98 | CbcBranchingObject *bestObject_; |
---|
99 | }; |
---|
100 | /** Simple branching object for an integer variable with pseudo costs |
---|
101 | |
---|
102 | This object can specify a two-way branch on an integer variable. For each |
---|
103 | arm of the branch, the upper and lower bounds on the variable can be |
---|
104 | independently specified. |
---|
105 | |
---|
106 | Variable_ holds the index of the integer variable in the integerVariable_ |
---|
107 | array of the model. |
---|
108 | */ |
---|
109 | |
---|
110 | class CbcDynamicPseudoCostBranchingObject : public CbcIntegerBranchingObject { |
---|
111 | |
---|
112 | public: |
---|
113 | /// Default constructor |
---|
114 | CbcDynamicPseudoCostBranchingObject(); |
---|
115 | |
---|
116 | /** Create a standard floor/ceiling branch object |
---|
117 | |
---|
118 | Specifies a simple two-way branch. Let \p value = x*. One arm of the |
---|
119 | branch will be is lb <= x <= floor(x*), the other ceil(x*) <= x <= ub. |
---|
120 | Specify way = -1 to set the object state to perform the down arm first, |
---|
121 | way = 1 for the up arm. |
---|
122 | */ |
---|
123 | CbcDynamicPseudoCostBranchingObject(CbcModel *model, int variable, |
---|
124 | int way, double value, |
---|
125 | CbcSimpleIntegerDynamicPseudoCost *object); |
---|
126 | |
---|
127 | /** Create a degenerate branch object |
---|
128 | |
---|
129 | Specifies a `one-way branch'. Calling branch() for this object will |
---|
130 | always result in lowerValue <= x <= upperValue. Used to fix a variable |
---|
131 | when lowerValue = upperValue. |
---|
132 | */ |
---|
133 | |
---|
134 | CbcDynamicPseudoCostBranchingObject(CbcModel *model, int variable, int way, |
---|
135 | double lowerValue, double upperValue); |
---|
136 | |
---|
137 | /// Copy constructor |
---|
138 | CbcDynamicPseudoCostBranchingObject(const CbcDynamicPseudoCostBranchingObject &); |
---|
139 | |
---|
140 | /// Assignment operator |
---|
141 | CbcDynamicPseudoCostBranchingObject &operator=(const CbcDynamicPseudoCostBranchingObject &rhs); |
---|
142 | |
---|
143 | /// Clone |
---|
144 | virtual CbcBranchingObject *clone() const; |
---|
145 | |
---|
146 | /// Destructor |
---|
147 | virtual ~CbcDynamicPseudoCostBranchingObject(); |
---|
148 | |
---|
149 | /// Does part of constructor |
---|
150 | void fillPart(int variable, |
---|
151 | int way, double value, |
---|
152 | CbcSimpleIntegerDynamicPseudoCost *object); |
---|
153 | |
---|
154 | using CbcBranchingObject::branch; |
---|
155 | /** \brief Sets the bounds for the variable according to the current arm |
---|
156 | of the branch and advances the object state to the next arm. |
---|
157 | This version also changes guessed objective value |
---|
158 | */ |
---|
159 | virtual double branch(); |
---|
160 | |
---|
161 | /** Some branchingObjects may claim to be able to skip |
---|
162 | strong branching. If so they have to fill in CbcStrongInfo. |
---|
163 | The object mention in incoming CbcStrongInfo must match. |
---|
164 | Returns nonzero if skip is wanted */ |
---|
165 | virtual int fillStrongInfo(CbcStrongInfo &info); |
---|
166 | |
---|
167 | /// Change in guessed |
---|
168 | inline double changeInGuessed() const |
---|
169 | { |
---|
170 | return changeInGuessed_; |
---|
171 | } |
---|
172 | /// Set change in guessed |
---|
173 | inline void setChangeInGuessed(double value) |
---|
174 | { |
---|
175 | changeInGuessed_ = value; |
---|
176 | } |
---|
177 | /// Return object |
---|
178 | inline CbcSimpleIntegerDynamicPseudoCost *object() const |
---|
179 | { |
---|
180 | return object_; |
---|
181 | } |
---|
182 | /// Set object |
---|
183 | inline void setObject(CbcSimpleIntegerDynamicPseudoCost *object) |
---|
184 | { |
---|
185 | object_ = object; |
---|
186 | } |
---|
187 | |
---|
188 | /** Return the type (an integer identifier) of \c this */ |
---|
189 | virtual CbcBranchObjType type() const |
---|
190 | { |
---|
191 | return DynamicPseudoCostBranchObj; |
---|
192 | } |
---|
193 | |
---|
194 | // LL: compareOriginalObject and compareBranchingObject are inherited from |
---|
195 | // CbcIntegerBranchingObject thus need not be declared/defined here. After |
---|
196 | // all, this kind of branching object is simply using pseudocosts to make |
---|
197 | // decisions, but once the decisions are made they are the same kind as in |
---|
198 | // the underlying class. |
---|
199 | |
---|
200 | protected: |
---|
201 | /// Change in guessed objective value for next branch |
---|
202 | double changeInGuessed_; |
---|
203 | /// Pointer back to object |
---|
204 | CbcSimpleIntegerDynamicPseudoCost *object_; |
---|
205 | }; |
---|
206 | |
---|
207 | #endif |
---|
208 | |
---|
209 | /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2 |
---|
210 | */ |
---|