source: trunk/Cbc/src/CbcNode.hpp @ 1424

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

Add a final blank line; hudson test server seems to want it.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 11.3 KB
Line 
1/* $Id: CbcNode.hpp 1400 2009-12-11 14:14:06Z forrest $ */
2// Copyright (C) 2002, International Business Machines
3// Corporation and others.  All Rights Reserved.
4#ifndef CbcNode_H
5#define CbcNode_H
6
7#include <string>
8#include <vector>
9
10#include "CoinWarmStartBasis.hpp"
11#include "CoinSearchTree.hpp"
12#include "CbcBranchBase.hpp"
13#include "CbcNodeInfo.hpp"
14#include "CbcFullNodeInfo.hpp"
15#include "CbcPartialNodeInfo.hpp"
16
17class OsiSolverInterface;
18class OsiSolverBranch;
19
20class OsiCuts;
21class OsiRowCut;
22class OsiRowCutDebugger;
23class CoinWarmStartBasis;
24class CbcCountRowCut;
25class CbcModel;
26class CbcNode;
27class CbcSubProblem;
28class CbcGeneralBranchingObject;
29
30/** Information required while the node is live
31
32  When a subproblem is initially created, it is represented by an CbcNode
33  object and an attached CbcNodeInfo object.
34
35  The CbcNode contains information (depth, branching instructions), that's
36  needed while the subproblem remains `live', <i>i.e.</i>, while the
37  subproblem is not fathomed and there are branch arms still be be
38  evaluated.  The CbcNode is deleted when the last branch arm has been
39  evaluated.
40
41  The CbcNodeInfo object contains the information needed to maintain the
42  search tree and recreate the subproblem for the node. It remains in
43  existence until there are no nodes remaining in the subtree rooted at this
44  node.
45*/
46
47class CbcNode : public CoinTreeNode {
48
49public:
50
51    /// Default Constructor
52    CbcNode ();
53
54    /// Construct and increment parent reference count
55    CbcNode (CbcModel * model, CbcNode * lastNode);
56
57    /// Copy constructor
58    CbcNode (const CbcNode &);
59
60    /// Assignment operator
61    CbcNode & operator= (const CbcNode& rhs);
62
63    /// Destructor
64    ~CbcNode ();
65
66    /** Create a description of the subproblem at this node
67
68      The CbcNodeInfo structure holds the information (basis & variable bounds)
69      required to recreate the subproblem for this node. It also links the node
70      to its parent (via the parent's CbcNodeInfo object).
71
72      If lastNode == NULL, a CbcFullNodeInfo object will be created. All
73      parameters except \p model are unused.
74
75      If lastNode != NULL, a CbcPartialNodeInfo object will be created. Basis and
76      bounds information will be stored in the form of differences between the
77      parent subproblem and this subproblem.
78      (More precisely, \p lastws, \p lastUpper, \p lastLower,
79      \p numberOldActiveCuts, and \p numberNewCuts are used.)
80    */
81    void
82    createInfo(CbcModel * model,
83               CbcNode * lastNode,
84               const CoinWarmStartBasis *lastws,
85               const double * lastLower, const double * lastUpper,
86               int numberOldActiveCuts, int numberNewCuts);
87
88    /** Create a branching object for the node
89
90      The routine scans the object list of the model and selects a set of
91      unsatisfied objects as candidates for branching. The candidates are
92      evaluated, and an appropriate branch object is installed.
93
94      The numberPassesLeft is decremented to stop fixing one variable each time
95      and going on and on (e.g. for stock cutting, air crew scheduling)
96
97      If evaluation determines that an object is monotone or infeasible,
98      the routine returns immediately. In the case of a monotone object,
99      the branch object has already been called to modify the model.
100
101      Return value:
102      <ul>
103        <li>  0: A branching object has been installed
104        <li> -1: A monotone object was discovered
105        <li> -2: An infeasible object was discovered
106      </ul>
107    */
108    int chooseBranch (CbcModel * model,
109                      CbcNode * lastNode,
110                      int numberPassesLeft);
111    /** Create a branching object for the node - when dynamic pseudo costs
112
113      The routine scans the object list of the model and selects a set of
114      unsatisfied objects as candidates for branching. The candidates are
115      evaluated, and an appropriate branch object is installed.
116      This version gives preference in evaluation to variables which
117      have not been evaluated many times.  It also uses numberStrong
118      to say give up if last few tries have not changed incumbent.
119      See Achterberg, Koch and Martin.
120
121      The numberPassesLeft is decremented to stop fixing one variable each time
122      and going on and on (e.g. for stock cutting, air crew scheduling)
123
124      If evaluation determines that an object is monotone or infeasible,
125      the routine returns immediately. In the case of a monotone object,
126      the branch object has already been called to modify the model.
127
128      Return value:
129      <ul>
130        <li>  0: A branching object has been installed
131        <li> -1: A monotone object was discovered
132        <li> -2: An infeasible object was discovered
133        <li> >0: Number of quich branching objects (and branches will be non NULL)
134      </ul>
135    */
136    int chooseDynamicBranch (CbcModel * model,
137                             CbcNode * lastNode,
138                             OsiSolverBranch * & branches,
139                             int numberPassesLeft);
140    /** Create a branching object for the node
141
142      The routine scans the object list of the model and selects a set of
143      unsatisfied objects as candidates for branching. The candidates are
144      evaluated, and an appropriate branch object is installed.
145
146      The numberPassesLeft is decremented to stop fixing one variable each time
147      and going on and on (e.g. for stock cutting, air crew scheduling)
148
149      If evaluation determines that an object is monotone or infeasible,
150      the routine returns immediately. In the case of a monotone object,
151      the branch object has already been called to modify the model.
152
153      Return value:
154      <ul>
155        <li>  0: A branching object has been installed
156        <li> -1: A monotone object was discovered
157        <li> -2: An infeasible object was discovered
158      </ul>
159      Branch state:
160      <ul>
161        <li> -1: start
162        <li> -1: A monotone object was discovered
163        <li> -2: An infeasible object was discovered
164      </ul>
165    */
166    int chooseOsiBranch (CbcModel * model,
167                         CbcNode * lastNode,
168                         OsiBranchingInformation * usefulInfo,
169                         int branchState);
170    /** Create a branching object for the node
171
172      The routine scans the object list of the model and selects a set of
173      unsatisfied objects as candidates for branching. It then solves a
174      series of problems and a CbcGeneral branch object is installed.
175
176      If evaluation determines that an object is infeasible,
177      the routine returns immediately.
178
179      Return value:
180      <ul>
181        <li>  0: A branching object has been installed
182        <li> -2: An infeasible object was discovered
183      </ul>
184    */
185    int chooseClpBranch (CbcModel * model,
186                         CbcNode * lastNode);
187    int analyze(CbcModel * model, double * results);
188    /// Decrement active cut counts
189    void decrementCuts(int change = 1);
190
191    /// Decrement all active cut counts in chain starting at parent
192    void decrementParentCuts(CbcModel * model, int change = 1);
193
194    /// Nulls out node info
195    void nullNodeInfo();
196    /** Initialize reference counts in attached CbcNodeInfo
197
198      This is a convenience routine, which will initialize the reference counts
199      in the attached CbcNodeInfo object based on the attached
200      OsiBranchingObject.
201
202      \sa CbcNodeInfo::initializeInfo(int).
203    */
204    void initializeInfo();
205
206    /// Does next branch and updates state
207    int branch(OsiSolverInterface * solver);
208
209    /** Double checks in case node can change its mind!
210        Returns objective value
211        Can change objective etc */
212    double checkIsCutoff(double cutoff);
213    // Information to make basis and bounds
214    inline CbcNodeInfo * nodeInfo() const {
215        return nodeInfo_;
216    }
217
218    // Objective value
219    inline double objectiveValue() const {
220        return objectiveValue_;
221    }
222    inline void setObjectiveValue(double value) {
223        objectiveValue_ = value;
224    }
225    /// Number of arms defined for the attached OsiBranchingObject.
226    inline int numberBranches() const {
227        if (branch_)
228            return (branch_->numberBranches()) ;
229        else
230            return (-1) ;
231    }
232
233    /* Active arm of the attached OsiBranchingObject.
234
235     In the simplest instance, coded -1 for the down arm of the branch, +1 for
236     the up arm. But see OsiBranchingObject::way()
237       Use nodeInfo--.numberBranchesLeft_ to see how active
238    */
239    int way() const;
240    /// Depth in branch-and-cut search tree
241    inline int depth() const {
242        return depth_;
243    }
244    /// Set depth in branch-and-cut search tree
245    inline void setDepth(int value) {
246        depth_ = value;
247    }
248    /// Get the number of objects unsatisfied at this node.
249    inline int numberUnsatisfied() const {
250        return numberUnsatisfied_;
251    }
252    /// Set the number of objects unsatisfied at this node.
253    inline void setNumberUnsatisfied(int value) {
254        numberUnsatisfied_ = value;
255    }
256    /// Get sum of "infeasibilities" reported by each object
257    inline double sumInfeasibilities() const {
258        return sumInfeasibilities_;
259    }
260    /// Set sum of "infeasibilities" reported by each object
261    inline void setSumInfeasibilities(double value) {
262        sumInfeasibilities_ = value;
263    }
264    // Guessed objective value (for solution)
265    inline double guessedObjectiveValue() const {
266        return guessedObjectiveValue_;
267    }
268    inline void setGuessedObjectiveValue(double value) {
269        guessedObjectiveValue_ = value;
270    }
271    /// Branching object for this node
272    inline const OsiBranchingObject * branchingObject() const {
273        return branch_;
274    }
275    /// Modifiable branching object for this node
276    inline OsiBranchingObject * modifiableBranchingObject() const {
277        return branch_;
278    }
279    /// Set branching object for this node (takes ownership)
280    inline void setBranchingObject(OsiBranchingObject * branchingObject) {
281        branch_ = branchingObject;
282    }
283    /// The node number
284    inline int nodeNumber() const {
285        return nodeNumber_;
286    }
287    inline void setNodeNumber(int node) {
288        nodeNumber_ = node;
289    }
290    /// Returns true if on tree
291    inline bool onTree() const {
292        return (state_&1) != 0;
293    }
294    /// Sets true if on tree
295    inline void setOnTree(bool yesNo) {
296        if (yesNo) state_ |= 1;
297        else state_ &= ~1;
298    }
299    /// Returns true if active
300    inline bool active() const {
301        return (state_&2) != 0;
302    }
303    /// Sets true if active
304    inline void setActive(bool yesNo) {
305        if (yesNo) state_ |= 2;
306        else state_ &= ~2;
307    }
308    /// Print
309    void print() const;
310    /// Debug
311    inline void checkInfo() const {
312        assert (nodeInfo_->numberBranchesLeft() ==
313                branch_->numberBranchesLeft());
314    }
315
316private:
317    // Data
318    /// Information to make basis and bounds
319    CbcNodeInfo * nodeInfo_;
320    /// Objective value
321    double objectiveValue_;
322    /// Guessed satisfied Objective value
323    double guessedObjectiveValue_;
324    /// Sum of "infeasibilities" reported by each object
325    double sumInfeasibilities_;
326    /// Branching object for this node
327    OsiBranchingObject * branch_;
328    /// Depth of the node in the search tree
329    int depth_;
330    /// The number of objects unsatisfied at this node.
331    int numberUnsatisfied_;
332    /// The node number
333    int nodeNumber_;
334    /** State
335        1 - on tree
336        2 - active
337    */
338    int state_;
339};
340
341
342#endif
343
Note: See TracBrowser for help on using the repository browser.