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

Last change on this file since 1957 was 1957, checked in by forrest, 5 years ago

minor fixes and take out printout

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