source: trunk/include/CbcNode.hpp @ 146

Last change on this file since 146 was 146, checked in by forrest, 14 years ago

for node stats

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 17.1 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;};
183  const inline CbcNode * owner() const
184  { return owner_;};
185  /// The node number
186  inline int nodeNumber() const
187  { return nodeNumber_;};
188  inline void setNodeNumber(int node)
189  { nodeNumber_=node;};
190protected:
191
192  /** Number of other nodes pointing to this node.
193
194    Number of existing and potential search tree nodes pointing to this node.
195    `Existing' means referenced by #parent_ of some other CbcNodeInfo.
196    `Potential' means children still to be created (#numberBranchesLeft_ of
197    this CbcNodeInfo).
198  */
199  int numberPointingToThis_;
200
201  /// parent
202  CbcNodeInfo * parent_;
203
204  /// Owner
205  CbcNode * owner_;
206
207  /// Number of row cuts (this node)
208  int numberCuts_;
209
210  /// The node number
211  int nodeNumber_;
212
213  /// Array of pointers to cuts
214  CbcCountRowCut ** cuts_;
215
216  /** Number of rows in problem (before these cuts).  This
217      means that for top of chain it must be rows at continuous */
218  int numberRows_;
219
220  /** Number of branch arms left to explore at this node
221 
222    \todo There seems to be redundancy between this field and
223          CbcBranchingObject::numberBranchesLeft_. It'd be good to sort out if
224          both are necessary.
225  */
226  int numberBranchesLeft_;
227     
228private:
229 
230  /// Illegal Assignment operator
231  CbcNodeInfo & operator=(const CbcNodeInfo& rhs);
232 
233};
234
235/** \brief Holds complete information for recreating a subproblem.
236
237  A CbcFullNodeInfo object contains all necessary information (bounds, basis,
238  and cuts) required to recreate a subproblem.
239
240  \todo While there's no explicit statement, the code often makes the implicit
241        assumption that an CbcFullNodeInfo structure will appear only at the
242        root node of the search tree. Things will break if this assumption
243        is violated.
244*/
245
246class CbcFullNodeInfo : public CbcNodeInfo {
247
248public:
249
250  /** \brief Modify model according to information at node
251
252      The routine modifies the model according to bound information at node,
253      creates a new basis according to information at node, but with the size
254      passed in through basis, and adds any cuts to the addCuts array.
255
256    \note The basis passed in via basis is solely a vehicle for passing in
257          the desired basis size. It will be deleted and a new basis returned.
258  */
259  virtual void applyToModel (CbcModel *model, CoinWarmStartBasis *&basis,
260                             CbcCountRowCut **addCuts,
261                             int &currentNumberCuts) const ;
262
263  /** Builds up row basis backwards (until original model).
264      Returns NULL or previous one to apply .
265      Depends on Free being 0 and impossible for cuts
266  */
267  virtual CbcNodeInfo * buildRowBasis(CoinWarmStartBasis & basis) const ;
268  // Default Constructor
269  CbcFullNodeInfo ();
270
271  /** Constructor from continuous or satisfied
272  */
273  CbcFullNodeInfo (CbcModel * model,
274                   int numberRowsAtContinuous);
275 
276  // Copy constructor
277  CbcFullNodeInfo ( const CbcFullNodeInfo &);
278   
279  // Destructor
280  ~CbcFullNodeInfo ();
281 
282  /// Clone
283  virtual CbcNodeInfo * clone() const;
284protected:
285  // Data
286  /** Full basis
287
288    This MUST BE A POINTER to avoid cutting extra information in derived
289    warm start classes.
290  */
291  CoinWarmStartBasis *basis_;
292  int numberIntegers_;
293  // Bounds stored in full
294  double * lower_;
295  double * upper_;
296private:
297  /// Illegal Assignment operator
298  CbcFullNodeInfo & operator=(const CbcFullNodeInfo& rhs);
299};
300
301
302
303/** \brief Holds information for recreating a subproblem by incremental change
304           from the parent.
305
306  A CbcPartialNodeInfo object contains changes to the bounds and basis, and
307  additional cuts, required to recreate a subproblem by modifying and
308  augmenting the parent subproblem.
309*/
310
311class CbcPartialNodeInfo : public CbcNodeInfo {
312
313public:
314
315  /** \brief Modify model according to information at node
316
317      The routine modifies the model according to bound and basis change
318      information at node and adds any cuts to the addCuts array.
319  */
320  virtual void applyToModel (CbcModel *model, CoinWarmStartBasis *&basis,
321                             CbcCountRowCut **addCuts,
322                             int &currentNumberCuts) const ;
323
324  /** Builds up row basis backwards (until original model).
325      Returns NULL or previous one to apply .
326      Depends on Free being 0 and impossible for cuts
327  */
328  virtual CbcNodeInfo * buildRowBasis(CoinWarmStartBasis & basis ) const ;
329  // Default Constructor
330  CbcPartialNodeInfo ();
331
332  // Constructor from current state
333  CbcPartialNodeInfo (CbcNodeInfo * parent, CbcNode * owner,
334                int numberChangedBounds,const int * variables,
335                const double * boundChanges,
336                const CoinWarmStartDiff *basisDiff) ;
337 
338  // Copy constructor
339  CbcPartialNodeInfo ( const CbcPartialNodeInfo &);
340   
341  // Destructor
342  ~CbcPartialNodeInfo ();
343 
344  /// Clone
345  virtual CbcNodeInfo * clone() const;
346private:
347  /* Data values */
348
349  /// Basis diff information
350  CoinWarmStartDiff *basisDiff_ ;
351  /// Which variable (top bit if upper bound changing)
352  int * variables_;
353  // New bound
354  double * newBounds_;
355  /// Number of bound changes
356  int numberChangedBounds_;
357private:
358 
359  /// Illegal Assignment operator
360  CbcPartialNodeInfo & operator=(const CbcPartialNodeInfo& rhs);
361};
362
363
364
365/** Information required while the node is live
366
367  When a subproblem is initially created, it is represented by an CbcNode
368  object and an attached CbcNodeInfo object.
369
370  The CbcNode contains information (depth, branching instructions), that's
371  needed while the subproblem remains `live', <i>i.e.</i>, while the
372  subproblem is not fathomed and there are branch arms still be be
373  evaluated.  The CbcNode is deleted when the last branch arm has been
374  evaluated.
375
376  The CbcNodeInfo object contains the information needed to maintain the
377  search tree and recreate the subproblem for the node. It remains in
378  existence until there are no nodes remaining in the subtree rooted at this
379  node.
380*/
381
382class CbcNode  {
383 
384public:
385   
386  /// Default Constructor
387  CbcNode ();
388
389  /// Construct and increment parent reference count
390  CbcNode (CbcModel * model, CbcNode * lastNode);
391
392  /// Copy constructor
393  CbcNode (const CbcNode &);
394   
395  /// Assignment operator
396  CbcNode & operator= (const CbcNode& rhs);
397
398  /// Destructor
399  ~CbcNode ();
400
401  /** Create a description of the subproblem at this node
402
403    The CbcNodeInfo structure holds the information (basis & variable bounds)
404    required to recreate the subproblem for this node. It also links the node
405    to its parent (via the parent's CbcNodeInfo object).
406
407    If lastNode == NULL, a CbcFullNodeInfo object will be created. All
408    parameters except \p model are unused.
409
410    If lastNode != NULL, a CbcPartialNodeInfo object will be created. Basis and
411    bounds information will be stored in the form of differences between the
412    parent subproblem and this subproblem.
413    (More precisely, \p lastws, \p lastUpper, \p lastLower,
414    \p numberOldActiveCuts, and \p numberNewCuts are used.)
415  */
416  void
417  createInfo(CbcModel * model,
418             CbcNode * lastNode,
419             const CoinWarmStartBasis *lastws,
420             const double * lastLower, const double * lastUpper,
421             int numberOldActiveCuts,int numberNewCuts);
422 
423  /** Create a branching object for the node
424
425    The routine scans the object list of the model and selects a set of
426    unsatisfied objects as candidates for branching. The candidates are
427    evaluated, and an appropriate branch object is installed.
428
429    The numberPassesLeft is decremented to stop fixing one variable each time
430    and going on and on (e.g. for stock cutting, air crew scheduling)
431
432    If evaluation determines that an object is monotone or infeasible,
433    the routine returns immediately. In the case of a monotone object,
434    the branch object has already been called to modify the model.
435
436    Return value:
437    <ul>
438      <li>  0: A branching object has been installed
439      <li> -1: A monotone object was discovered
440      <li> -2: An infeasible object was discovered
441    </ul>
442  */
443  int chooseBranch (CbcModel * model,
444                    CbcNode * lastNode,
445                    int numberPassesLeft);
446  /** Create a branching object for the node - when dynamic pseudo costs
447
448    The routine scans the object list of the model and selects a set of
449    unsatisfied objects as candidates for branching. The candidates are
450    evaluated, and an appropriate branch object is installed.
451    This version gives preference in evaluation to variables which
452    have not been evaluated many times.  It also uses numberStrong
453    to say give up if last few tries have not changed incumbent.
454    See Achterberg, Koch and Martin.
455
456    The numberPassesLeft is decremented to stop fixing one variable each time
457    and going on and on (e.g. for stock cutting, air crew scheduling)
458
459    If evaluation determines that an object is monotone or infeasible,
460    the routine returns immediately. In the case of a monotone object,
461    the branch object has already been called to modify the model.
462
463    Return value:
464    <ul>
465      <li>  0: A branching object has been installed
466      <li> -1: A monotone object was discovered
467      <li> -2: An infeasible object was discovered
468    </ul>
469  */
470  int chooseDynamicBranch (CbcModel * model,
471                    CbcNode * lastNode,
472                    int numberPassesLeft);
473 
474  /// Decrement active cut counts
475  void decrementCuts(int change=1);
476
477  /// Decrement all active cut counts in chain starting at parent
478  void decrementParentCuts(int change=1);
479
480  /// Nulls out node info
481  void nullNodeInfo();
482  /** Initialize reference counts in attached CbcNodeInfo
483 
484    This is a convenience routine, which will initialize the reference counts
485    in the attached CbcNodeInfo object based on the attached
486    CbcBranchingObject.
487
488    \sa CbcNodeInfo::initializeInfo(int).
489  */
490  void initializeInfo();
491
492  /// Does next branch and updates state
493  int branch();
494
495  // Information to make basis and bounds
496  inline CbcNodeInfo * nodeInfo() const
497  {return nodeInfo_;};
498
499  // Objective value
500  inline double objectiveValue() const
501  { return objectiveValue_;};
502  inline void setObjectiveValue(double value)
503  { objectiveValue_=value;};
504  /// Number of arms defined for the attached CbcBranchingObject.
505  inline int numberBranches() const
506  { if (branch_)
507      return (branch_->numberBranches()) ;
508    else
509      return (-1) ; } ;
510
511  /** Branching `variable' associated with the attached CbcBranchingObject.
512
513    Check CbcBranchingObject::variable() for a longer explanation of
514    `variable'.
515  */
516  inline int variable() const
517  {if (branch_) return branch_->variable();else return -1;};
518
519  /* Active arm of the attached CbcBranchingObject.
520 
521   In the simplest instance, coded -1 for the down arm of the branch, +1 for
522   the up arm. But see CbcBranchingObject::way()
523     Use nodeInfo--.numberBranchesLeft_ to see how active
524  */
525  inline int way() const
526  {if (branch_) return branch_->way();else return 0;};
527  /// Depth in branch-and-cut search tree
528  inline int depth() const
529  {return depth_;};
530  /// Get the number of objects unsatisfied at this node.
531  inline int numberUnsatisfied() const
532  {return numberUnsatisfied_;};
533
534  // Guessed objective value (for solution)
535  inline double guessedObjectiveValue() const
536  {return guessedObjectiveValue_;};
537  inline void setGuessedObjectiveValue(double value)
538  {guessedObjectiveValue_=value;};
539  /// Branching object for this node
540  const CbcBranchingObject * branchingObject() const
541  { return branch_;};
542  /// Modifiable branching object for this node
543  CbcBranchingObject * modifiableBranchingObject() const
544  { return branch_;};
545
546private:
547  // Data
548  /// Information to make basis and bounds
549  CbcNodeInfo * nodeInfo_;
550  // Objective value
551  double objectiveValue_;
552  // Guessed satisfied Objective value
553  double guessedObjectiveValue_;
554  /// Branching object for this node
555  CbcBranchingObject * branch_;
556  /// Depth of the node in the search tree
557  int depth_;
558  /// The number of objects unsatisfied at this node.
559  int numberUnsatisfied_;
560};
561
562
563#endif
Note: See TracBrowser for help on using the repository browser.