source: branches/heur/Cbc/src/CbcNode.hpp @ 885

Last change on this file since 885 was 854, checked in by forrest, 12 years ago

try and make a bit faster

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