source: trunk/Cbc/src/CbcNode.hpp @ 483

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

isContinuousUnbounded

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