source: trunk/Cbc/src/CbcNodeInfo.hpp

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

script to format sources

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 9.8 KB
Line 
1// $Id: CbcNodeInfo.hpp 2465 2019-01-03 19:26:52Z tkr $
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  /** \name Constructors & destructors */
72  //@{
73  /** Default Constructor
74
75      Creates an empty NodeInfo object.
76    */
77  CbcNodeInfo();
78
79  /// Copy constructor
80  CbcNodeInfo(const CbcNodeInfo &);
81
82#ifdef JJF_ZERO
83  /** Construct with parent
84
85      Creates a NodeInfo object which knows its parent and assumes it will
86      in turn have two children.
87    */
88  CbcNodeInfo(CbcNodeInfo *parent);
89#endif
90
91  /** Construct with parent and owner
92
93      As for `construct with parent', and attached to \p owner.
94    */
95  CbcNodeInfo(CbcNodeInfo *parent, CbcNode *owner);
96
97  /** Destructor
98
99      Note that the destructor will recursively delete the parent if this
100      nodeInfo is the last child.
101    */
102  virtual ~CbcNodeInfo();
103  //@}
104
105  /** \brief Modify model according to information at node
106
107        The routine modifies the model according to bound and basis
108        information at node and adds any cuts to the addCuts array.
109    */
110  virtual void applyToModel(CbcModel *model, CoinWarmStartBasis *&basis,
111    CbcCountRowCut **addCuts,
112    int &currentNumberCuts) const = 0;
113  /// Just apply bounds to one variable - force means overwrite by lower,upper (1=>infeasible)
114  virtual int applyBounds(int iColumn, double &lower, double &upper, int force) = 0;
115
116  /** Builds up row basis backwards (until original model).
117        Returns NULL or previous one to apply .
118        Depends on Free being 0 and impossible for cuts
119    */
120  virtual CbcNodeInfo *buildRowBasis(CoinWarmStartBasis &basis) const = 0;
121  /// Clone
122  virtual CbcNodeInfo *clone() const = 0;
123  /// Called when number branches left down to zero
124  virtual void allBranchesGone() {}
125#ifndef JJF_ONE
126  /// Increment number of references
127  inline void increment(int amount = 1)
128  {
129    numberPointingToThis_ += amount; /*printf("CbcNodeInfo %x incremented by %d to %d\n",this,amount,numberPointingToThis_);*/
130  }
131
132  /// Decrement number of references and return number left
133  inline int decrement(int amount = 1)
134  {
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  {
151    numberPointingToThis_ = number;
152    numberBranchesLeft_ = number;
153  }
154
155  /// Return number of branches left in object
156  inline int numberBranchesLeft() const
157  {
158    return numberBranchesLeft_;
159  }
160
161  /// Set number of branches left in object
162  inline void setNumberBranchesLeft(int value)
163  {
164    numberBranchesLeft_ = value;
165  }
166
167  /// Return number of objects pointing to this
168  inline int numberPointingToThis() const
169  {
170    return numberPointingToThis_;
171  }
172
173  /// Set number of objects pointing to this
174  inline void setNumberPointingToThis(int number)
175  {
176    numberPointingToThis_ = number;
177  }
178
179  /// Increment number of objects pointing to this
180  inline void incrementNumberPointingToThis()
181  {
182    numberPointingToThis_++;
183  }
184
185  /// Say one branch taken
186  inline int branchedOn()
187  {
188    numberPointingToThis_--;
189    numberBranchesLeft_--;
190    return numberBranchesLeft_;
191  }
192
193  /// Say thrown away
194  inline void throwAway()
195  {
196    numberPointingToThis_ -= numberBranchesLeft_;
197    numberBranchesLeft_ = 0;
198  }
199
200  /// Parent of this
201  CbcNodeInfo *parent() const
202  {
203    return parent_;
204  }
205  /// Set parent null
206  inline void nullParent()
207  {
208    parent_ = NULL;
209  }
210
211  void addCuts(OsiCuts &cuts, int numberToBranch, //int * whichGenerator,
212    int numberPointingToThis);
213  void addCuts(int numberCuts, CbcCountRowCut **cuts, int numberToBranch);
214  /** Delete cuts (decrements counts)
215        Slow unless cuts in same order as saved
216    */
217  void deleteCuts(int numberToDelete, CbcCountRowCut **cuts);
218  void deleteCuts(int numberToDelete, int *which);
219
220  /// Really delete a cut
221  void deleteCut(int whichOne);
222
223  /// Decrement active cut counts
224  void decrementCuts(int change = 1);
225
226  /// Increment active cut counts
227  void incrementCuts(int change = 1);
228
229  /// Decrement all active cut counts in chain starting at parent
230  void decrementParentCuts(CbcModel *model, int change = 1);
231
232  /// Increment all active cut counts in parent chain
233  void incrementParentCuts(CbcModel *model, int change = 1);
234
235  /// Array of pointers to cuts
236  inline CbcCountRowCut **cuts() const
237  {
238    return cuts_;
239  }
240
241  /// Number of row cuts (this node)
242  inline int numberCuts() const
243  {
244    return numberCuts_;
245  }
246  inline void setNumberCuts(int value)
247  {
248    numberCuts_ = value;
249  }
250
251  /// Set owner null
252  inline void nullOwner()
253  {
254    owner_ = NULL;
255  }
256  const inline CbcNode *owner() const
257  {
258    return owner_;
259  }
260  inline CbcNode *mutableOwner() const
261  {
262    return owner_;
263  }
264  /// The node number
265  inline int nodeNumber() const
266  {
267    return nodeNumber_;
268  }
269  inline void setNodeNumber(int node)
270  {
271    nodeNumber_ = node;
272  }
273  /** Deactivate node information.
274        1 - bounds
275        2 - cuts
276        4 - basis!
277        8 - just marked
278        16 - symmetry branching worked
279    */
280  void deactivate(int mode = 3);
281  /// Say if normal
282  inline bool allActivated() const
283  {
284    return ((active_ & 7) == 7);
285  }
286  /// Say if marked
287  inline bool marked() const
288  {
289    return ((active_ & 8) != 0);
290  }
291  /// Mark
292  inline void mark()
293  {
294    active_ |= 8;
295  }
296  /// Unmark
297  inline void unmark()
298  {
299    active_ &= ~8;
300  }
301  /// Get symmetry value (true worked at this node)
302  inline bool symmetryWorked() const
303  {
304    return (active_ & 16) != 0;
305  }
306  /// Say symmetry worked at this node)
307  inline void setSymmetryWorked()
308  {
309    active_ |= 16;
310  }
311
312  /// Branching object for the parent
313  inline const OsiBranchingObject *parentBranch() const
314  {
315    return parentBranch_;
316  }
317  /// If we need to take off parent based data
318  void unsetParentBasedData();
319
320protected:
321  /** Number of other nodes pointing to this node.
322
323      Number of existing and potential search tree nodes pointing to this node.
324      `Existing' means referenced by #parent_ of some other CbcNodeInfo.
325      `Potential' means children still to be created (#numberBranchesLeft_ of
326      this CbcNodeInfo).
327    */
328  int numberPointingToThis_;
329
330  /// parent
331  CbcNodeInfo *parent_;
332
333  /// Copy of the branching object of the parent when the node is created
334  OsiBranchingObject *parentBranch_;
335
336  /// Owner
337  CbcNode *owner_;
338
339  /// Number of row cuts (this node)
340  int numberCuts_;
341
342  /// The node number
343  int nodeNumber_;
344
345  /// Array of pointers to cuts
346  CbcCountRowCut **cuts_;
347
348  /** Number of rows in problem (before these cuts).  This
349        means that for top of chain it must be rows at continuous */
350  int numberRows_;
351
352  /** Number of branch arms left to explore at this node
353
354      \todo There seems to be redundancy between this field and
355        CbcBranchingObject::numberBranchesLeft_. It'd be good to sort out if
356        both are necessary.
357    */
358  int numberBranchesLeft_;
359  /** Active node information.
360        1 - bounds
361        2 - cuts
362        4 - basis!
363    */
364  int active_;
365
366private:
367  /// Illegal Assignment operator
368  CbcNodeInfo &operator=(const CbcNodeInfo &rhs);
369
370  /// routine common to constructors
371  void setParentBasedData();
372};
373
374#endif // CbcNodeInfo_H
375
376/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
377*/
Note: See TracBrowser for help on using the repository browser.