source: trunk/include/CbcNode.hpp @ 5

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

start of nested search and branching cuts

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 15.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;
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    If evaluation determines that an object is monotone or infeasible,
420    the routine returns immediately. In the case of a monotone object,
421    the branch object has already been called to modify the model.
422
423    Return value:
424    <ul>
425      <li>  0: A branching object has been installed
426      <li> -1: A monotone object was discovered
427      <li> -2: An infeasible object was discovered
428    </ul>
429  */
430  int chooseBranch (CbcModel * model,
431                    CbcNode * lastNode);
432 
433  /// Decrement active cut counts
434  void decrementCuts(int change=1);
435
436  /// Decrement all active cut counts in chain starting at parent
437  void decrementParentCuts(int change=1);
438
439  /// Nulls out node info
440  void nullNodeInfo();
441  /** Initialize reference counts in attached CbcNodeInfo
442 
443    This is a convenience routine, which will initialize the reference counts
444    in the attached CbcNodeInfo object based on the attached
445    CbcBranchingObject.
446
447    \sa CbcNodeInfo::initializeInfo(int).
448  */
449  void initializeInfo();
450
451  /// Does next branch and updates state
452  int branch();
453
454  // Information to make basis and bounds
455  inline CbcNodeInfo * nodeInfo() const
456  {return nodeInfo_;};
457
458  // Objective value
459  inline double objectiveValue() const
460  { return objectiveValue_;};
461  inline void setObjectiveValue(double value)
462  { objectiveValue_=value;};
463  /// Number of arms defined for the attached CbcBranchingObject.
464  inline int numberBranches() const
465  { if (branch_)
466      return (branch_->numberBranches()) ;
467    else
468      return (-1) ; } ;
469
470  /** Branching `variable' associated with the attached CbcBranchingObject.
471
472    Check CbcBranchingObject::variable() for a longer explanation of
473    `variable'.
474  */
475  inline int variable() const
476  {if (branch_) return branch_->variable();else return -1;};
477
478  /* Active arm of the attached CbcBranchingObject.
479 
480   In the simplest instance, coded -1 for the down arm of the branch, +1 for
481   the up arm. But see CbcBranchingObject::way()
482     Use nodeInfo--.numberBranchesLeft_ to see how active
483  */
484  inline int way() const
485  {if (branch_) return branch_->way();else return 0;};
486  /// Depth in branch-and-cut search tree
487  inline int depth() const
488  {return depth_;};
489  /// Get the number of objects unsatisfied at this node.
490  inline int numberUnsatisfied() const
491  {return numberUnsatisfied_;};
492  /// The node number
493  inline int nodeNumber() const
494  { return nodeNumber_;};
495  inline void setNodeNumber(int node)
496  { nodeNumber_=node;};
497
498  // Guessed objective value (for solution)
499  inline double guessedObjectiveValue() const
500  {return guessedObjectiveValue_;};
501  inline void setGuessedObjectiveValue(double value)
502  {guessedObjectiveValue_=value;};
503  /// Branching object for this node
504  const CbcBranchingObject * branchingObject() const
505  { return branch_;};
506
507private:
508  // Data
509  /// Information to make basis and bounds
510  CbcNodeInfo * nodeInfo_;
511  // Objective value
512  double objectiveValue_;
513  // Guessed satisfied Objective value
514  double guessedObjectiveValue_;
515  /// Branching object for this node
516  CbcBranchingObject * branch_;
517  /// Depth of the node in the search tree
518  int depth_;
519  /// The number of objects unsatisfied at this node.
520  int numberUnsatisfied_;
521  /// The node number
522  int nodeNumber_;
523};
524
525
526#endif
Note: See TracBrowser for help on using the repository browser.