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

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

for osibranching

  • 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 "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;/*printf("CbcNodeInfo %x incremented by %d to %d\n",this,amount,numberPointingToThis_);*/};
120
121  /// Decrement number of references and return number left
122  inline int decrement(int amount=1)
123  {numberPointingToThis_-=amount;/*printf("CbcNodeInfo %x decremented by %d to %d\n",this,amount,numberPointingToThis_);*/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  /** Create a branching object for the node
482
483    The routine scans the object list of the model and selects a set of
484    unsatisfied objects as candidates for branching. The candidates are
485    evaluated, and an appropriate branch object is installed.
486
487    The numberPassesLeft is decremented to stop fixing one variable each time
488    and going on and on (e.g. for stock cutting, air crew scheduling)
489
490    If evaluation determines that an object is monotone or infeasible,
491    the routine returns immediately. In the case of a monotone object,
492    the branch object has already been called to modify the model.
493
494    Return value:
495    <ul>
496      <li>  0: A branching object has been installed
497      <li> -1: A monotone object was discovered
498      <li> -2: An infeasible object was discovered
499    </ul>
500    Branch state:
501    <ul>
502      <li> -1: start
503      <li> -1: A monotone object was discovered
504      <li> -2: An infeasible object was discovered
505    </ul>
506  */
507  int chooseOsiBranch (CbcModel * model,
508                       CbcNode * lastNode,
509                       OsiBranchingInformation * usefulInfo,
510                       int branchState);
511  int analyze(CbcModel * model,double * results);
512  /// Decrement active cut counts
513  void decrementCuts(int change=1);
514
515  /// Decrement all active cut counts in chain starting at parent
516  void decrementParentCuts(int change=1);
517
518  /// Nulls out node info
519  void nullNodeInfo();
520  /** Initialize reference counts in attached CbcNodeInfo
521 
522    This is a convenience routine, which will initialize the reference counts
523    in the attached CbcNodeInfo object based on the attached
524    OsiBranchingObject.
525
526    \sa CbcNodeInfo::initializeInfo(int).
527  */
528  void initializeInfo();
529
530  /// Does next branch and updates state
531  int branch(OsiSolverInterface * solver);
532
533  // Information to make basis and bounds
534  inline CbcNodeInfo * nodeInfo() const
535  {return nodeInfo_;};
536
537  // Objective value
538  inline double objectiveValue() const
539  { return objectiveValue_;};
540  inline void setObjectiveValue(double value)
541  { objectiveValue_=value;};
542  /// Number of arms defined for the attached OsiBranchingObject.
543  inline int numberBranches() const
544  { if (branch_)
545      return (branch_->numberBranches()) ;
546    else
547      return (-1) ; } ;
548
549  /* Active arm of the attached OsiBranchingObject.
550 
551   In the simplest instance, coded -1 for the down arm of the branch, +1 for
552   the up arm. But see OsiBranchingObject::way()
553     Use nodeInfo--.numberBranchesLeft_ to see how active
554  */
555  int way() const;
556  /// Depth in branch-and-cut search tree
557  inline int depth() const
558  {return depth_;};
559  /// Get the number of objects unsatisfied at this node.
560  inline int numberUnsatisfied() const
561  {return numberUnsatisfied_;};
562  /// Sum of "infeasibilities" reported by each object
563  inline double sumInfeasibilities() const
564  { return sumInfeasibilities_;};
565  // Guessed objective value (for solution)
566  inline double guessedObjectiveValue() const
567  {return guessedObjectiveValue_;};
568  inline void setGuessedObjectiveValue(double value)
569  {guessedObjectiveValue_=value;};
570  /// Branching object for this node
571  inline const OsiBranchingObject * branchingObject() const
572  { return branch_;};
573  /// Modifiable branching object for this node
574  inline OsiBranchingObject * modifiableBranchingObject() const
575  { return branch_;};
576  /// Set branching object for this node (takes ownership)
577  inline void setBranchingObject(OsiBranchingObject * branchingObject)
578  { branch_ = branchingObject;};
579
580private:
581  // Data
582  /// Information to make basis and bounds
583  CbcNodeInfo * nodeInfo_;
584  /// Objective value
585  double objectiveValue_;
586  /// Guessed satisfied Objective value
587  double guessedObjectiveValue_;
588  /// Sum of "infeasibilities" reported by each object
589  double sumInfeasibilities_;
590  /// Branching object for this node
591  OsiBranchingObject * branch_;
592  /// Depth of the node in the search tree
593  int depth_;
594  /// The number of objects unsatisfied at this node.
595  int numberUnsatisfied_;
596};
597
598
599#endif
Note: See TracBrowser for help on using the repository browser.