File: CbcNode.hpp

package info (click to toggle)
coinor-cbc 2.9.9+repack1-1
  • links: PTS, VCS
  • area: main
  • in suites: buster
  • size: 7,848 kB
  • ctags: 5,787
  • sloc: cpp: 104,337; sh: 8,921; xml: 2,950; makefile: 520; ansic: 491; awk: 197
file content (351 lines) | stat: -rw-r--r-- 11,885 bytes parent folder | download | duplicates (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
/* $Id: CbcNode.hpp 1957 2013-08-27 15:19:55Z forrest $ */
// Copyright (C) 2002, International Business Machines
// Corporation and others.  All Rights Reserved.
// This code is licensed under the terms of the Eclipse Public License (EPL).

#ifndef CbcNode_H
#define CbcNode_H

#include <string>
#include <vector>

#include "CoinWarmStartBasis.hpp"
#include "CoinSearchTree.hpp"
#include "CbcBranchBase.hpp"
#include "CbcNodeInfo.hpp"
#include "CbcFullNodeInfo.hpp"
#include "CbcPartialNodeInfo.hpp"

class OsiSolverInterface;
class OsiSolverBranch;

class OsiCuts;
class OsiRowCut;
class OsiRowCutDebugger;
class CoinWarmStartBasis;
class CbcCountRowCut;
class CbcModel;
class CbcNode;
class CbcSubProblem;
class CbcGeneralBranchingObject;

/** Information required while the node is live

  When a subproblem is initially created, it is represented by an CbcNode
  object and an attached CbcNodeInfo object.

  The CbcNode contains information (depth, branching instructions), that's
  needed while the subproblem remains `live', <i>i.e.</i>, while the
  subproblem is not fathomed and there are branch arms still be be
  evaluated.  The CbcNode is deleted when the last branch arm has been
  evaluated.

  The CbcNodeInfo object contains the information needed to maintain the
  search tree and recreate the subproblem for the node. It remains in
  existence until there are no nodes remaining in the subtree rooted at this
  node.
*/

class CbcNode : public CoinTreeNode {

public:

    /// Default Constructor
    CbcNode ();

    /// Construct and increment parent reference count
    CbcNode (CbcModel * model, CbcNode * lastNode);

    /// Copy constructor
    CbcNode (const CbcNode &);

    /// Assignment operator
    CbcNode & operator= (const CbcNode& rhs);

    /// Destructor
    ~CbcNode ();

    /** Create a description of the subproblem at this node

      The CbcNodeInfo structure holds the information (basis & variable bounds)
      required to recreate the subproblem for this node. It also links the node
      to its parent (via the parent's CbcNodeInfo object).

      If lastNode == NULL, a CbcFullNodeInfo object will be created. All
      parameters except \p model are unused.

      If lastNode != NULL, a CbcPartialNodeInfo object will be created. Basis and
      bounds information will be stored in the form of differences between the
      parent subproblem and this subproblem.
      (More precisely, \p lastws, \p lastUpper, \p lastLower,
      \p numberOldActiveCuts, and \p numberNewCuts are used.)
    */
    void
    createInfo(CbcModel * model,
               CbcNode * lastNode,
               const CoinWarmStartBasis *lastws,
               const double * lastLower, const double * lastUpper,
               int numberOldActiveCuts, int numberNewCuts);

    /** Create a branching object for the node

      The routine scans the object list of the model and selects a set of
      unsatisfied objects as candidates for branching. The candidates are
      evaluated, and an appropriate branch object is installed.

      The numberPassesLeft is decremented to stop fixing one variable each time
      and going on and on (e.g. for stock cutting, air crew scheduling)

      If evaluation determines that an object is monotone or infeasible,
      the routine returns immediately. In the case of a monotone object,
      the branch object has already been called to modify the model.

      Return value:
      <ul>
        <li>  0: A branching object has been installed
        <li> -1: A monotone object was discovered
        <li> -2: An infeasible object was discovered
      </ul>
    */
    int chooseBranch (CbcModel * model,
                      CbcNode * lastNode,
                      int numberPassesLeft);
    /** Create a branching object for the node - when dynamic pseudo costs

      The routine scans the object list of the model and selects a set of
      unsatisfied objects as candidates for branching. The candidates are
      evaluated, and an appropriate branch object is installed.
      This version gives preference in evaluation to variables which
      have not been evaluated many times.  It also uses numberStrong
      to say give up if last few tries have not changed incumbent.
      See Achterberg, Koch and Martin.

      The numberPassesLeft is decremented to stop fixing one variable each time
      and going on and on (e.g. for stock cutting, air crew scheduling)

      If evaluation determines that an object is monotone or infeasible,
      the routine returns immediately. In the case of a monotone object,
      the branch object has already been called to modify the model.

      Return value:
      <ul>
        <li>  0: A branching object has been installed
        <li> -1: A monotone object was discovered
        <li> -2: An infeasible object was discovered
        <li> >0: Number of quich branching objects (and branches will be non NULL)
      </ul>
    */
    int chooseDynamicBranch (CbcModel * model,
                             CbcNode * lastNode,
                             OsiSolverBranch * & branches,
                             int numberPassesLeft);
    /** Create a branching object for the node

      The routine scans the object list of the model and selects a set of
      unsatisfied objects as candidates for branching. The candidates are
      evaluated, and an appropriate branch object is installed.

      The numberPassesLeft is decremented to stop fixing one variable each time
      and going on and on (e.g. for stock cutting, air crew scheduling)

      If evaluation determines that an object is monotone or infeasible,
      the routine returns immediately. In the case of a monotone object,
      the branch object has already been called to modify the model.

      Return value:
      <ul>
        <li>  0: A branching object has been installed
        <li> -1: A monotone object was discovered
        <li> -2: An infeasible object was discovered
      </ul>
      Branch state:
      <ul>
        <li> -1: start
        <li> -1: A monotone object was discovered
        <li> -2: An infeasible object was discovered
      </ul>
    */
    int chooseOsiBranch (CbcModel * model,
                         CbcNode * lastNode,
                         OsiBranchingInformation * usefulInfo,
                         int branchState);
    /** Create a branching object for the node

      The routine scans the object list of the model and selects a set of
      unsatisfied objects as candidates for branching. It then solves a
      series of problems and a CbcGeneral branch object is installed.

      If evaluation determines that an object is infeasible,
      the routine returns immediately.

      Return value:
      <ul>
        <li>  0: A branching object has been installed
        <li> -2: An infeasible object was discovered
      </ul>
    */
    int chooseClpBranch (CbcModel * model,
                         CbcNode * lastNode);
    int analyze(CbcModel * model, double * results);
    /// Decrement active cut counts
    void decrementCuts(int change = 1);

    /// Decrement all active cut counts in chain starting at parent
    void decrementParentCuts(CbcModel * model, int change = 1);

    /// Nulls out node info
    void nullNodeInfo();
    /** Initialize reference counts in attached CbcNodeInfo

      This is a convenience routine, which will initialize the reference counts
      in the attached CbcNodeInfo object based on the attached
      OsiBranchingObject.

      \sa CbcNodeInfo::initializeInfo(int).
    */
    void initializeInfo();

    /// Does next branch and updates state
    int branch(OsiSolverInterface * solver);

    /** Double checks in case node can change its mind!
        Returns objective value
        Can change objective etc */
    double checkIsCutoff(double cutoff);
    // Information to make basis and bounds
    inline CbcNodeInfo * nodeInfo() const {
        return nodeInfo_;
    }

    // Objective value
    inline double objectiveValue() const {
        return objectiveValue_;
    }
    inline void setObjectiveValue(double value) {
        objectiveValue_ = value;
    }
    /// Number of arms defined for the attached OsiBranchingObject.
    inline int numberBranches() const {
        if (branch_)
            return (branch_->numberBranches()) ;
        else
            return (-1) ;
    }

    /* Active arm of the attached OsiBranchingObject.

     In the simplest instance, coded -1 for the down arm of the branch, +1 for
     the up arm. But see OsiBranchingObject::way()
       Use nodeInfo--.numberBranchesLeft_ to see how active
    */
    int way() const;
    /// Depth in branch-and-cut search tree
    inline int depth() const {
        return depth_;
    }
    /// Set depth in branch-and-cut search tree
    inline void setDepth(int value) {
        depth_ = value;
    }
    /// Get the number of objects unsatisfied at this node.
    inline int numberUnsatisfied() const {
        return numberUnsatisfied_;
    }
    /// Set the number of objects unsatisfied at this node.
    inline void setNumberUnsatisfied(int value) {
        numberUnsatisfied_ = value;
    }
    /// Get sum of "infeasibilities" reported by each object
    inline double sumInfeasibilities() const {
        return sumInfeasibilities_;
    }
    /// Set sum of "infeasibilities" reported by each object
    inline void setSumInfeasibilities(double value) {
        sumInfeasibilities_ = value;
    }
    // Guessed objective value (for solution)
    inline double guessedObjectiveValue() const {
        return guessedObjectiveValue_;
    }
    inline void setGuessedObjectiveValue(double value) {
        guessedObjectiveValue_ = value;
    }
    /// Branching object for this node
    inline const OsiBranchingObject * branchingObject() const {
        return branch_;
    }
    /// Modifiable branching object for this node
    inline OsiBranchingObject * modifiableBranchingObject() const {
        return branch_;
    }
    /// Set branching object for this node (takes ownership)
    inline void setBranchingObject(OsiBranchingObject * branchingObject) {
        branch_ = branchingObject;
    }
    /// The node number
    inline int nodeNumber() const {
        return nodeNumber_;
    }
    inline void setNodeNumber(int node) {
        nodeNumber_ = node;
    }
    /// Returns true if on tree
    inline bool onTree() const {
        return (state_&1) != 0;
    }
    /// Sets true if on tree
    inline void setOnTree(bool yesNo) {
        if (yesNo) state_ |= 1;
        else state_ &= ~1;
    }
    /// Returns true if active
    inline bool active() const {
        return (state_&2) != 0;
    }
    /// Sets true if active
    inline void setActive(bool yesNo) {
        if (yesNo) state_ |= 2;
        else state_ &= ~2;
    }
    /// Get state (really for debug)
    inline int getState() const
    { return state_;}
    /// Set state (really for debug)
    inline void setState(int value)
    { state_ = value;}
    /// Print
    void print() const;
    /// Debug
    inline void checkInfo() const {
        assert (nodeInfo_->numberBranchesLeft() ==
                branch_->numberBranchesLeft());
    }

private:
    // Data
    /// Information to make basis and bounds
    CbcNodeInfo * nodeInfo_;
    /// Objective value
    double objectiveValue_;
    /// Guessed satisfied Objective value
    double guessedObjectiveValue_;
    /// Sum of "infeasibilities" reported by each object
    double sumInfeasibilities_;
    /// Branching object for this node
    OsiBranchingObject * branch_;
    /// Depth of the node in the search tree
    int depth_;
    /// The number of objects unsatisfied at this node.
    int numberUnsatisfied_;
    /// The node number
    int nodeNumber_;
    /** State
        1 - on tree
        2 - active
    */
    int state_;
};


#endif