source: branches/devel/Cbc/src/CbcNode.hpp @ 417

Last change on this file since 417 was 416, checked in by forrest, 13 years ago

for allCuts

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