source: trunk/include/CbcNode.hpp @ 222

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

towards next version

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