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

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

for nonlinear and start moving to OsiTree?
afor n

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