source: trunk/include/CbcNode.hpp @ 48

Last change on this file since 48 was 48, checked in by forrest, 16 years ago

skip messages etc

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 15.8 KB
Line 
1// Copyright (C) 2002, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#ifndef CbcNode_H
4#define CbcNode_H
5
6#include <string>
7#include <vector>
8
9#include "CoinWarmStartBasis.hpp"
10#include "CbcBranchBase.hpp"
11
12class OsiSolverInterface;
13
14class OsiCuts;
15class OsiRowCut;
16class OsiRowCutDebugger;
17class CoinWarmStartBasis;
18class CbcCountRowCut;
19class CbcModel;
20class CbcNode;
21
22//#############################################################################
23/** Information required to recreate the subproblem at this node
24
25  When a subproblem is initially created, it is represented by an CbcNode
26  object and an attached CbcNodeInfo object.
27
28  The CbcNode contains information needed while the subproblem remains live.
29  The CbcNode is deleted when the last branch arm has been evaluated.
30
31  The CbcNodeInfo contains information required to maintain the branch-and-cut
32  search tree structure (links and reference counts) and to recreate the
33  subproblem for this node (basis, variable bounds, cutting planes). An
34  CbcNodeInfo object remains in existence until all nodes have been pruned from
35  the subtree rooted at this node.
36
37  The principle used to maintain the reference count is that the reference
38  count is always the sum of all potential and actual children of the node.
39  Specifically,
40  <ul>
41    <li> Once it's determined how the node will branch, the reference count
42         is set to the number of potential children (<i>i.e.</i>, the number
43         of arms of the branch).
44    <li> As each child is created by CbcNode::branch() (converting a potential
45         child to the active subproblem), the reference count is decremented.
46    <li> If the child survives and will become a node in the search tree
47         (converting the active subproblem into an actual child), increment the
48         reference count.
49  </ul>
50  Notice that the active subproblem lives in a sort of limbo, neither a
51  potential or an actual node in the branch-and-cut tree.
52
53  CbcNodeInfo objects come in two flavours. An CbcFullNodeInfo object contains
54  a full record of the information required to recreate a subproblem.
55  An CbcPartialNodeInfo object expresses this information in terms of
56  differences from the parent.
57*/
58
59class CbcNodeInfo {
60
61public:
62
63/** \name Constructors & destructors */
64//@{
65  /** Default Constructor
66
67    Creates an empty NodeInfo object.
68  */
69  CbcNodeInfo ();
70
71  /// Copy constructor
72  CbcNodeInfo ( const CbcNodeInfo &);
73   
74
75  /** Construct with parent
76
77    Creates a NodeInfo object which knows its parent and assumes it will
78    in turn have two children.
79  */
80  CbcNodeInfo (CbcNodeInfo * parent);
81   
82  /** Construct with parent and owner
83
84    As for `construct with parent', and attached to \p owner.
85  */
86  CbcNodeInfo (CbcNodeInfo * parent, CbcNode * owner);
87
88  /** Destructor
89 
90    Note that the destructor will recursively delete the parent if this
91    nodeInfo is the last child.
92  */
93  virtual ~CbcNodeInfo();
94//@}
95
96
97  /** \brief Modify model according to information at node
98
99      The routine modifies the model according to bound and basis
100      information at node and adds any cuts to the addCuts array.
101  */
102  virtual void applyToModel (CbcModel *model, CoinWarmStartBasis *&basis,
103                             CbcCountRowCut **addCuts,
104                             int &currentNumberCuts) const = 0 ;
105
106  /** Builds up row basis backwards (until original model).
107      Returns NULL or previous one to apply .
108      Depends on Free being 0 and impossible for cuts
109  */
110  virtual CbcNodeInfo * buildRowBasis(CoinWarmStartBasis & basis) const = 0;
111  /// Clone
112  virtual CbcNodeInfo * clone() const = 0;
113
114  /// Increment number of references
115  inline void increment(int amount=1)
116  {numberPointingToThis_+=amount;};
117
118  /// Decrement number of references and return number left
119  inline int decrement(int amount=1)
120  {numberPointingToThis_-=amount;return numberPointingToThis_;};
121
122  /** Initialize reference counts
123
124    Initialize the reference counts used for tree maintenance.
125  */
126
127  inline void initializeInfo(int number)
128  {numberPointingToThis_=number;numberBranchesLeft_=number;};
129
130  /// Return number of branches left in object
131  inline int numberBranchesLeft() const
132  {return numberBranchesLeft_;};
133
134  /// Return number of objects pointing to this
135  inline int numberPointingToThis() const
136  {return numberPointingToThis_;};
137
138  /// Say one branch taken
139  inline int branchedOn()
140  {numberPointingToThis_--;numberBranchesLeft_--;return numberBranchesLeft_;};
141
142  /// Say thrown away
143  inline void throwAway()
144  {numberPointingToThis_-=numberBranchesLeft_;numberBranchesLeft_=0;};
145
146  /// Parent of this
147  CbcNodeInfo * parent() const
148  {return parent_;};
149
150  void addCuts(OsiCuts & cuts,int numberToBranch, int * whichGenerator);
151  void addCuts(int numberCuts, CbcCountRowCut ** cuts,int numberToBranch);
152  /** Delete cuts (decrements counts)
153      Slow unless cuts in same order as saved
154  */
155  void deleteCuts(int numberToDelete,CbcCountRowCut ** cuts);
156  void deleteCuts(int numberToDelete,int * which);
157
158  /// Really delete a cut
159  void deleteCut(int whichOne);
160
161  /// Decrement active cut counts
162  void decrementCuts(int change=1);
163
164  /// Decrement all active cut counts in chain starting at parent
165  void decrementParentCuts(int change=1);
166
167  /// Increment all active cut counts in parent chain
168  void incrementParentCuts(int change=1);
169
170  /// Array of pointers to cuts
171  inline CbcCountRowCut ** cuts() const
172  {return cuts_;};
173
174  /// Number of row cuts (this node)
175  inline int numberCuts() const
176  {return numberCuts_;};
177  inline void setNumberCuts(int value)
178  {numberCuts_=value;};
179
180  /// Set owner null
181  inline void nullOwner()
182  { owner_=NULL;};
183protected:
184
185  /** Number of other nodes pointing to this node.
186
187    Number of existing and potential search tree nodes pointing to this node.
188    `Existing' means referenced by #parent_ of some other CbcNodeInfo.
189    `Potential' means children still to be created (#numberBranchesLeft_ of
190    this CbcNodeInfo).
191  */
192  int numberPointingToThis_;
193
194  /// parent
195  CbcNodeInfo * parent_;
196
197  /// Owner
198  CbcNode * owner_;
199
200  /// Number of row cuts (this node)
201  int numberCuts_;
202
203  /// Array of pointers to cuts
204  CbcCountRowCut ** cuts_;
205
206  /** Number of rows in problem (before these cuts).  This
207      means that for top of chain it must be rows at continuous */
208  int numberRows_;
209
210  /** Number of branch arms left to explore at this node
211 
212    \todo There seems to be redundancy between this field and
213          CbcBranchingObject::numberBranchesLeft_. It'd be good to sort out if
214          both are necessary.
215  */
216  int numberBranchesLeft_;
217     
218private:
219 
220  /// Illegal Assignment operator
221  CbcNodeInfo & operator=(const CbcNodeInfo& rhs);
222 
223};
224
225/** \brief Holds complete information for recreating a subproblem.
226
227  A CbcFullNodeInfo object contains all necessary information (bounds, basis,
228  and cuts) required to recreate a subproblem.
229
230  \todo While there's no explicit statement, the code often makes the implicit
231        assumption that an CbcFullNodeInfo structure will appear only at the
232        root node of the search tree. Things will break if this assumption
233        is violated.
234*/
235
236class CbcFullNodeInfo : public CbcNodeInfo {
237
238public:
239
240  /** \brief Modify model according to information at node
241
242      The routine modifies the model according to bound information at node,
243      creates a new basis according to information at node, but with the size
244      passed in through basis, and adds any cuts to the addCuts array.
245
246    \note The basis passed in via basis is solely a vehicle for passing in
247          the desired basis size. It will be deleted and a new basis returned.
248  */
249  virtual void applyToModel (CbcModel *model, CoinWarmStartBasis *&basis,
250                             CbcCountRowCut **addCuts,
251                             int &currentNumberCuts) const ;
252
253  /** Builds up row basis backwards (until original model).
254      Returns NULL or previous one to apply .
255      Depends on Free being 0 and impossible for cuts
256  */
257  virtual CbcNodeInfo * buildRowBasis(CoinWarmStartBasis & basis) const ;
258  // Default Constructor
259  CbcFullNodeInfo ();
260
261  /** Constructor from continuous or satisfied
262  */
263  CbcFullNodeInfo (CbcModel * model,
264                   int numberRowsAtContinuous);
265 
266  // Copy constructor
267  CbcFullNodeInfo ( const CbcFullNodeInfo &);
268   
269  // Destructor
270  ~CbcFullNodeInfo ();
271 
272  /// Clone
273  virtual CbcNodeInfo * clone() const;
274protected:
275  // Data
276  /** Full basis
277
278    This MUST BE A POINTER to avoid cutting extra information in derived
279    warm start classes.
280  */
281  CoinWarmStartBasis *basis_;
282  int numberIntegers_;
283  // Bounds stored in full
284  double * lower_;
285  double * upper_;
286private:
287  /// Illegal Assignment operator
288  CbcFullNodeInfo & operator=(const CbcFullNodeInfo& rhs);
289};
290
291
292
293/** \brief Holds information for recreating a subproblem by incremental change
294           from the parent.
295
296  A CbcPartialNodeInfo object contains changes to the bounds and basis, and
297  additional cuts, required to recreate a subproblem by modifying and
298  augmenting the parent subproblem.
299*/
300
301class CbcPartialNodeInfo : public CbcNodeInfo {
302
303public:
304
305  /** \brief Modify model according to information at node
306
307      The routine modifies the model according to bound and basis change
308      information at node and adds any cuts to the addCuts array.
309  */
310  virtual void applyToModel (CbcModel *model, CoinWarmStartBasis *&basis,
311                             CbcCountRowCut **addCuts,
312                             int &currentNumberCuts) const ;
313
314  /** Builds up row basis backwards (until original model).
315      Returns NULL or previous one to apply .
316      Depends on Free being 0 and impossible for cuts
317  */
318  virtual CbcNodeInfo * buildRowBasis(CoinWarmStartBasis & basis ) const ;
319  // Default Constructor
320  CbcPartialNodeInfo ();
321
322  // Constructor from current state
323  CbcPartialNodeInfo (CbcNodeInfo * parent, CbcNode * owner,
324                int numberChangedBounds,const int * variables,
325                const double * boundChanges,
326                const CoinWarmStartDiff *basisDiff) ;
327 
328  // Copy constructor
329  CbcPartialNodeInfo ( const CbcPartialNodeInfo &);
330   
331  // Destructor
332  ~CbcPartialNodeInfo ();
333 
334  /// Clone
335  virtual CbcNodeInfo * clone() const;
336private:
337  /* Data values */
338
339  /// Basis diff information
340  CoinWarmStartDiff *basisDiff_ ;
341  /// Which variable (top bit if upper bound changing)
342  int * variables_;
343  // New bound
344  double * newBounds_;
345  /// Number of bound changes
346  int numberChangedBounds_;
347private:
348 
349  /// Illegal Assignment operator
350  CbcPartialNodeInfo & operator=(const CbcPartialNodeInfo& rhs);
351};
352
353
354
355/** Information required while the node is live
356
357  When a subproblem is initially created, it is represented by an CbcNode
358  object and an attached CbcNodeInfo object.
359
360  The CbcNode contains information (depth, branching instructions), that's
361  needed while the subproblem remains `live', <i>i.e.</i>, while the
362  subproblem is not fathomed and there are branch arms still be be
363  evaluated.  The CbcNode is deleted when the last branch arm has been
364  evaluated.
365
366  The CbcNodeInfo object contains the information needed to maintain the
367  search tree and recreate the subproblem for the node. It remains in
368  existence until there are no nodes remaining in the subtree rooted at this
369  node.
370*/
371
372class CbcNode  {
373 
374public:
375   
376  /// Default Constructor
377  CbcNode ();
378
379  /// Construct and increment parent reference count
380  CbcNode (CbcModel * model, CbcNode * lastNode);
381
382  /// Copy constructor
383  CbcNode (const CbcNode &);
384   
385  /// Assignment operator
386  CbcNode & operator= (const CbcNode& rhs);
387
388  /// Destructor
389  ~CbcNode ();
390
391  /** Create a description of the subproblem at this node
392
393    The CbcNodeInfo structure holds the information (basis & variable bounds)
394    required to recreate the subproblem for this node. It also links the node
395    to its parent (via the parent's CbcNodeInfo object).
396
397    If lastNode == NULL, a CbcFullNodeInfo object will be created. All
398    parameters except \p model are unused.
399
400    If lastNode != NULL, a CbcPartialNodeInfo object will be created. Basis and
401    bounds information will be stored in the form of differences between the
402    parent subproblem and this subproblem.
403    (More precisely, \p lastws, \p lastUpper, \p lastLower,
404    \p numberOldActiveCuts, and \p numberNewCuts are used.)
405  */
406  void
407  createInfo(CbcModel * model,
408             CbcNode * lastNode,
409             const CoinWarmStartBasis *lastws,
410             const double * lastLower, const double * lastUpper,
411             int numberOldActiveCuts,int numberNewCuts);
412 
413  /** Create a branching object for the node
414
415    The routine scans the object list of the model and selects a set of
416    unsatisfied objects as candidates for branching. The candidates are
417    evaluated, and an appropriate branch object is installed.
418
419    The numberPassesLeft is decremented to stop fixing one variable each time
420    and going on and on (e.g. for stock cutting, air crew scheduling)
421
422    If evaluation determines that an object is monotone or infeasible,
423    the routine returns immediately. In the case of a monotone object,
424    the branch object has already been called to modify the model.
425
426    Return value:
427    <ul>
428      <li>  0: A branching object has been installed
429      <li> -1: A monotone object was discovered
430      <li> -2: An infeasible object was discovered
431    </ul>
432  */
433  int chooseBranch (CbcModel * model,
434                    CbcNode * lastNode,
435                    int numberPassesLeft);
436 
437  /// Decrement active cut counts
438  void decrementCuts(int change=1);
439
440  /// Decrement all active cut counts in chain starting at parent
441  void decrementParentCuts(int change=1);
442
443  /// Nulls out node info
444  void nullNodeInfo();
445  /** Initialize reference counts in attached CbcNodeInfo
446 
447    This is a convenience routine, which will initialize the reference counts
448    in the attached CbcNodeInfo object based on the attached
449    CbcBranchingObject.
450
451    \sa CbcNodeInfo::initializeInfo(int).
452  */
453  void initializeInfo();
454
455  /// Does next branch and updates state
456  int branch();
457
458  // Information to make basis and bounds
459  inline CbcNodeInfo * nodeInfo() const
460  {return nodeInfo_;};
461
462  // Objective value
463  inline double objectiveValue() const
464  { return objectiveValue_;};
465  inline void setObjectiveValue(double value)
466  { objectiveValue_=value;};
467  /// Number of arms defined for the attached CbcBranchingObject.
468  inline int numberBranches() const
469  { if (branch_)
470      return (branch_->numberBranches()) ;
471    else
472      return (-1) ; } ;
473
474  /** Branching `variable' associated with the attached CbcBranchingObject.
475
476    Check CbcBranchingObject::variable() for a longer explanation of
477    `variable'.
478  */
479  inline int variable() const
480  {if (branch_) return branch_->variable();else return -1;};
481
482  /* Active arm of the attached CbcBranchingObject.
483 
484   In the simplest instance, coded -1 for the down arm of the branch, +1 for
485   the up arm. But see CbcBranchingObject::way()
486     Use nodeInfo--.numberBranchesLeft_ to see how active
487  */
488  inline int way() const
489  {if (branch_) return branch_->way();else return 0;};
490  /// Depth in branch-and-cut search tree
491  inline int depth() const
492  {return depth_;};
493  /// Get the number of objects unsatisfied at this node.
494  inline int numberUnsatisfied() const
495  {return numberUnsatisfied_;};
496  /// The node number
497  inline int nodeNumber() const
498  { return nodeNumber_;};
499  inline void setNodeNumber(int node)
500  { nodeNumber_=node;};
501
502  // Guessed objective value (for solution)
503  inline double guessedObjectiveValue() const
504  {return guessedObjectiveValue_;};
505  inline void setGuessedObjectiveValue(double value)
506  {guessedObjectiveValue_=value;};
507  /// Branching object for this node
508  const CbcBranchingObject * branchingObject() const
509  { return branch_;};
510
511private:
512  // Data
513  /// Information to make basis and bounds
514  CbcNodeInfo * nodeInfo_;
515  // Objective value
516  double objectiveValue_;
517  // Guessed satisfied Objective value
518  double guessedObjectiveValue_;
519  /// Branching object for this node
520  CbcBranchingObject * branch_;
521  /// Depth of the node in the search tree
522  int depth_;
523  /// The number of objects unsatisfied at this node.
524  int numberUnsatisfied_;
525  /// The node number
526  int nodeNumber_;
527};
528
529
530#endif
Note: See TracBrowser for help on using the repository browser.