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

Last change on this file since 912 was 912, checked in by ladanyi, 13 years ago

Incorporated changes from branches/heur

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