source: trunk/Cbc/src/CbcNodeInfo.hpp @ 2048

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

First try at orbital branching

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