source: trunk/Cbc/src/CbcNode.hpp

Last change on this file was 2465, checked in by unxusr, 5 months ago

script to format sources

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