source: branches/sandbox/Cbc/src/CbcNodeInfo.hpp @ 1393

Last change on this file since 1393 was 1393, checked in by lou, 10 years ago

Mark #if 0 with JJF_ZERO and #if 1 with JJF_ONE as a historical reference
point.

File size: 9.7 KB
Line 
1// Edwin 11/24/09 carved from CbcNode
2#ifndef CbcNodeInfo_H
3#define CbcNodeInfo_H
4
5#include <string>
6#include <vector>
7
8#include "CoinWarmStartBasis.hpp"
9#include "CoinSearchTree.hpp"
10#include "CbcBranchBase.hpp"
11
12class OsiSolverInterface;
13class OsiSolverBranch;
14
15class OsiCuts;
16class OsiRowCut;
17class OsiRowCutDebugger;
18class CoinWarmStartBasis;
19class CbcCountRowCut;
20class CbcModel;
21class CbcNode;
22class CbcSubProblem;
23class CbcGeneralBranchingObject;
24
25//#############################################################################
26/** Information required to recreate the subproblem at this node
27
28  When a subproblem is initially created, it is represented by a CbcNode
29  object and an attached CbcNodeInfo object.
30
31  The CbcNode contains information needed while the subproblem remains live.
32  The CbcNode is deleted when the last branch arm has been evaluated.
33
34  The CbcNodeInfo contains information required to maintain the branch-and-cut
35  search tree structure (links and reference counts) and to recreate the
36  subproblem for this node (basis, variable bounds, cutting planes). A
37  CbcNodeInfo object remains in existence until all nodes have been pruned from
38  the subtree rooted at this node.
39
40  The principle used to maintain the reference count is that the reference
41  count is always the sum of all potential and actual children of the node.
42  Specifically,
43  <ul>
44    <li> Once it's determined how the node will branch, the reference count
45         is set to the number of potential children (<i>i.e.</i>, the number
46         of arms of the branch).
47    <li> As each child is created by CbcNode::branch() (converting a potential
48         child to the active subproblem), the reference count is decremented.
49    <li> If the child survives and will become a node in the search tree
50         (converting the active subproblem into an actual child), increment the
51         reference count.
52  </ul>
53  Notice that the active subproblem lives in a sort of limbo, neither a
54  potential or an actual node in the branch-and-cut tree.
55
56  CbcNodeInfo objects come in two flavours. A CbcFullNodeInfo object contains
57  a full record of the information required to recreate a subproblem.
58  A CbcPartialNodeInfo object expresses this information in terms of
59  differences from the parent.
60*/
61
62class CbcNodeInfo {
63
64public:
65
66    /** \name Constructors & destructors */
67//@{
68    /** Default Constructor
69
70      Creates an empty NodeInfo object.
71    */
72    CbcNodeInfo ();
73
74    /// Copy constructor
75    CbcNodeInfo ( const CbcNodeInfo &);
76
77#ifdef JJF_ZERO
78    /** Construct with parent
79
80      Creates a NodeInfo object which knows its parent and assumes it will
81      in turn have two children.
82    */
83    CbcNodeInfo (CbcNodeInfo * parent);
84#endif
85
86    /** Construct with parent and owner
87
88      As for `construct with parent', and attached to \p owner.
89    */
90    CbcNodeInfo (CbcNodeInfo * parent, CbcNode * owner);
91
92    /** Destructor
93
94      Note that the destructor will recursively delete the parent if this
95      nodeInfo is the last child.
96    */
97    virtual ~CbcNodeInfo();
98//@}
99
100
101    /** \brief Modify model according to information at node
102
103        The routine modifies the model according to bound and basis
104        information at node and adds any cuts to the addCuts array.
105    */
106    virtual void applyToModel (CbcModel *model, CoinWarmStartBasis *&basis,
107                               CbcCountRowCut **addCuts,
108                               int &currentNumberCuts) const = 0 ;
109    /// Just apply bounds to one variable - force means overwrite by lower,upper (1=>infeasible)
110    virtual int applyBounds(int iColumn, double & lower, double & upper, int force) = 0;
111
112    /** Builds up row basis backwards (until original model).
113        Returns NULL or previous one to apply .
114        Depends on Free being 0 and impossible for cuts
115    */
116    virtual CbcNodeInfo * buildRowBasis(CoinWarmStartBasis & basis) const = 0;
117    /// Clone
118    virtual CbcNodeInfo * clone() const = 0;
119    /// Called when number branches left down to zero
120    virtual void allBranchesGone() {}
121#ifndef JJF_ONE
122    /// Increment number of references
123    inline void increment(int amount = 1) {
124        numberPointingToThis_ += amount;/*printf("CbcNodeInfo %x incremented by %d to %d\n",this,amount,numberPointingToThis_);*/
125    }
126
127    /// Decrement number of references and return number left
128    inline int decrement(int amount = 1) {
129        numberPointingToThis_ -= amount;/*printf("CbcNodeInfo %x decremented by %d to %d\n",this,amount,numberPointingToThis_);*/
130        return numberPointingToThis_;
131    }
132#else
133    /// Increment number of references
134    void increment(int amount = 1);
135    /// Decrement number of references and return number left
136    int decrement(int amount = 1);
137#endif
138    /** Initialize reference counts
139
140      Initialize the reference counts used for tree maintenance.
141    */
142
143    inline void initializeInfo(int number) {
144        numberPointingToThis_ = number;
145        numberBranchesLeft_ = number;
146    }
147
148    /// Return number of branches left in object
149    inline int numberBranchesLeft() const {
150        return numberBranchesLeft_;
151    }
152
153    /// Set number of branches left in object
154    inline void setNumberBranchesLeft(int value) {
155        numberBranchesLeft_ = value;
156    }
157
158    /// Return number of objects pointing to this
159    inline int numberPointingToThis() const {
160        return numberPointingToThis_;
161    }
162
163    /// Set number of objects pointing to this
164    inline void setNumberPointingToThis(int number) {
165        numberPointingToThis_ = number;
166    }
167
168    /// Increment number of objects pointing to this
169    inline void incrementNumberPointingToThis() {
170        numberPointingToThis_ ++;
171    }
172
173    /// Say one branch taken
174    inline int branchedOn() {
175        numberPointingToThis_--;
176        numberBranchesLeft_--;
177        return numberBranchesLeft_;
178    }
179
180    /// Say thrown away
181    inline void throwAway() {
182        numberPointingToThis_ -= numberBranchesLeft_;
183        numberBranchesLeft_ = 0;
184    }
185
186    /// Parent of this
187    CbcNodeInfo * parent() const {
188        return parent_;
189    }
190    /// Set parent null
191    inline void nullParent() {
192        parent_ = NULL;
193    }
194
195    void addCuts(OsiCuts & cuts, int numberToBranch, //int * whichGenerator,
196                 int numberPointingToThis);
197    void addCuts(int numberCuts, CbcCountRowCut ** cuts, int numberToBranch);
198    /** Delete cuts (decrements counts)
199        Slow unless cuts in same order as saved
200    */
201    void deleteCuts(int numberToDelete, CbcCountRowCut ** cuts);
202    void deleteCuts(int numberToDelete, int * which);
203
204    /// Really delete a cut
205    void deleteCut(int whichOne);
206
207    /// Decrement active cut counts
208    void decrementCuts(int change = 1);
209
210    /// Increment active cut counts
211    void incrementCuts(int change = 1);
212
213    /// Decrement all active cut counts in chain starting at parent
214    void decrementParentCuts(CbcModel * model, int change = 1);
215
216    /// Increment all active cut counts in parent chain
217    void incrementParentCuts(CbcModel * model, int change = 1);
218
219    /// Array of pointers to cuts
220    inline CbcCountRowCut ** cuts() const {
221        return cuts_;
222    }
223
224    /// Number of row cuts (this node)
225    inline int numberCuts() const {
226        return numberCuts_;
227    }
228    inline void setNumberCuts(int value) {
229        numberCuts_ = value;
230    }
231
232    /// Set owner null
233    inline void nullOwner() {
234        owner_ = NULL;
235    }
236    const inline CbcNode * owner() const {
237        return owner_;
238    }
239    inline CbcNode * mutableOwner() const {
240        return owner_;
241    }
242    /// The node number
243    inline int nodeNumber() const {
244        return nodeNumber_;
245    }
246    inline void setNodeNumber(int node) {
247        nodeNumber_ = node;
248    }
249    /** Deactivate node information.
250        1 - bounds
251        2 - cuts
252        4 - basis!
253    */
254    void deactivate(int mode = 3);
255    /// Say if normal
256    inline bool allActivated() const {
257        return (active_ == 7);
258    }
259    /// Say if marked
260    inline bool marked() const {
261        return ((active_&8) != 0);
262    }
263    /// Mark
264    inline void mark() {
265        active_ |= 8;
266    }
267    /// Unmark
268    inline void unmark() {
269        active_ &= ~8;
270    }
271
272    /// Branching object for the parent
273    inline const OsiBranchingObject * parentBranch() const {
274        return parentBranch_;
275    }
276    /// If we need to take off parent based data
277    void unsetParentBasedData();
278protected:
279
280    /** Number of other nodes pointing to this node.
281
282      Number of existing and potential search tree nodes pointing to this node.
283      `Existing' means referenced by #parent_ of some other CbcNodeInfo.
284      `Potential' means children still to be created (#numberBranchesLeft_ of
285      this CbcNodeInfo).
286    */
287    int numberPointingToThis_;
288
289    /// parent
290    CbcNodeInfo * parent_;
291
292    /// Copy of the branching object of the parent when the node is created
293    OsiBranchingObject * parentBranch_;
294
295    /// Owner
296    CbcNode * owner_;
297
298    /// Number of row cuts (this node)
299    int numberCuts_;
300
301    /// The node number
302    int nodeNumber_;
303
304    /// Array of pointers to cuts
305    CbcCountRowCut ** cuts_;
306
307    /** Number of rows in problem (before these cuts).  This
308        means that for top of chain it must be rows at continuous */
309    int numberRows_;
310
311    /** Number of branch arms left to explore at this node
312
313      \todo There seems to be redundancy between this field and
314        CbcBranchingObject::numberBranchesLeft_. It'd be good to sort out if
315        both are necessary.
316    */
317    int numberBranchesLeft_;
318    /** Active node information.
319        1 - bounds
320        2 - cuts
321        4 - basis!
322    */
323    int active_;
324
325private:
326
327    /// Illegal Assignment operator
328    CbcNodeInfo & operator=(const CbcNodeInfo& rhs);
329
330    /// routine common to constructors
331    void setParentBasedData();
332};
333
334#endif // CbcNodeInfo_H
Note: See TracBrowser for help on using the repository browser.