coinor-libcbc-dev 2.5.0-2.3 / usr / include / coin / CbcNode.hpp

/* $Id: CbcNode.hpp 1400 2009-12-11 14:14:06Z lou $ */
// Copyright (C) 2002, International Business Machines
// Corporation and others.  All Rights Reserved.
#ifndef CbcNode_H
#define CbcNode_H

#include <string>
#include <vector>

#include "CoinWarmStartBasis.hpp"
#include "CoinSearchTree.hpp"
#include "CbcBranchBase.hpp"
#include "CbcNodeInfo.hpp"
#include "CbcFullNodeInfo.hpp"
#include "CbcPartialNodeInfo.hpp"

class OsiSolverInterface;
class OsiSolverBranch;

class OsiCuts;
class OsiRowCut;
class OsiRowCutDebugger;
class CoinWarmStartBasis;
class CbcCountRowCut;
class CbcModel;
class CbcNode;
class CbcSubProblem;
class CbcGeneralBranchingObject;

/** Information required while the node is live

  When a subproblem is initially created, it is represented by an CbcNode
  object and an attached CbcNodeInfo object.

  The CbcNode contains information (depth, branching instructions), that's
  needed while the subproblem remains `live', <i>i.e.</i>, while the
  subproblem is not fathomed and there are branch arms still be be
  evaluated.  The CbcNode is deleted when the last branch arm has been
  evaluated.

  The CbcNodeInfo object contains the information needed to maintain the
  search tree and recreate the subproblem for the node. It remains in
  existence until there are no nodes remaining in the subtree rooted at this
  node.
*/

class CbcNode : public CoinTreeNode {

public:

    /// Default Constructor
    CbcNode ();

    /// Construct and increment parent reference count
    CbcNode (CbcModel * model, CbcNode * lastNode);

    /// Copy constructor
    CbcNode (const CbcNode &);

    /// Assignment operator
    CbcNode & operator= (const CbcNode& rhs);

    /// Destructor
    ~CbcNode ();

    /** Create a description of the subproblem at this node

      The CbcNodeInfo structure holds the information (basis & variable bounds)
      required to recreate the subproblem for this node. It also links the node
      to its parent (via the parent's CbcNodeInfo object).

      If lastNode == NULL, a CbcFullNodeInfo object will be created. All
      parameters except \p model are unused.

      If lastNode != NULL, a CbcPartialNodeInfo object will be created. Basis and
      bounds information will be stored in the form of differences between the
      parent subproblem and this subproblem.
      (More precisely, \p lastws, \p lastUpper, \p lastLower,
      \p numberOldActiveCuts, and \p numberNewCuts are used.)
    */
    void
    createInfo(CbcModel * model,
               CbcNode * lastNode,
               const CoinWarmStartBasis *lastws,
               const double * lastLower, const double * lastUpper,
               int numberOldActiveCuts, int numberNewCuts);

    /** Create a branching object for the node

      The routine scans the object list of the model and selects a set of
      unsatisfied objects as candidates for branching. The candidates are
      evaluated, and an appropriate branch object is installed.

      The numberPassesLeft is decremented to stop fixing one variable each time
      and going on and on (e.g. for stock cutting, air crew scheduling)

      If evaluation determines that an object is monotone or infeasible,
      the routine returns immediately. In the case of a monotone object,
      the branch object has already been called to modify the model.

      Return value:
      <ul>
        <li>  0: A branching object has been installed
        <li> -1: A monotone object was discovered
        <li> -2: An infeasible object was discovered
      </ul>
    */
    int chooseBranch (CbcModel * model,
                      CbcNode * lastNode,
                      int numberPassesLeft);
    /** Create a branching object for the node - when dynamic pseudo costs

      The routine scans the object list of the model and selects a set of
      unsatisfied objects as candidates for branching. The candidates are
      evaluated, and an appropriate branch object is installed.
      This version gives preference in evaluation to variables which
      have not been evaluated many times.  It also uses numberStrong
      to say give up if last few tries have not changed incumbent.
      See Achterberg, Koch and Martin.

      The numberPassesLeft is decremented to stop fixing one variable each time
      and going on and on (e.g. for stock cutting, air crew scheduling)

      If evaluation determines that an object is monotone or infeasible,
      the routine returns immediately. In the case of a monotone object,
      the branch object has already been called to modify the model.

      Return value:
      <ul>
        <li>  0: A branching object has been installed
        <li> -1: A monotone object was discovered
        <li> -2: An infeasible object was discovered
        <li> >0: Number of quich branching objects (and branches will be non NULL)
      </ul>
    */
    int chooseDynamicBranch (CbcModel * model,
                             CbcNode * lastNode,
                             OsiSolverBranch * & branches,
                             int numberPassesLeft);
    /** Create a branching object for the node

      The routine scans the object list of the model and selects a set of
      unsatisfied objects as candidates for branching. The candidates are
      evaluated, and an appropriate branch object is installed.

      The numberPassesLeft is decremented to stop fixing one variable each time
      and going on and on (e.g. for stock cutting, air crew scheduling)

      If evaluation determines that an object is monotone or infeasible,
      the routine returns immediately. In the case of a monotone object,
      the branch object has already been called to modify the model.

      Return value:
      <ul>
        <li>  0: A branching object has been installed
        <li> -1: A monotone object was discovered
        <li> -2: An infeasible object was discovered
      </ul>
      Branch state:
      <ul>
        <li> -1: start
        <li> -1: A monotone object was discovered
        <li> -2: An infeasible object was discovered
      </ul>
    */
    int chooseOsiBranch (CbcModel * model,
                         CbcNode * lastNode,
                         OsiBranchingInformation * usefulInfo,
                         int branchState);
    /** Create a branching object for the node

      The routine scans the object list of the model and selects a set of
      unsatisfied objects as candidates for branching. It then solves a
      series of problems and a CbcGeneral branch object is installed.

      If evaluation determines that an object is infeasible,
      the routine returns immediately.

      Return value:
      <ul>
        <li>  0: A branching object has been installed
        <li> -2: An infeasible object was discovered
      </ul>
    */
    int chooseClpBranch (CbcModel * model,
                         CbcNode * lastNode);
    int analyze(CbcModel * model, double * results);
    /// Decrement active cut counts
    void decrementCuts(int change = 1);

    /// Decrement all active cut counts in chain starting at parent
    void decrementParentCuts(CbcModel * model, int change = 1);

    /// Nulls out node info
    void nullNodeInfo();
    /** Initialize reference counts in attached CbcNodeInfo

      This is a convenience routine, which will initialize the reference counts
      in the attached CbcNodeInfo object based on the attached
      OsiBranchingObject.

      \sa CbcNodeInfo::initializeInfo(int).
    */
    void initializeInfo();

    /// Does next branch and updates state
    int branch(OsiSolverInterface * solver);

    /** Double checks in case node can change its mind!
        Returns objective value
        Can change objective etc */
    double checkIsCutoff(double cutoff);
    // Information to make basis and bounds
    inline CbcNodeInfo * nodeInfo() const {
        return nodeInfo_;
    }

    // Objective value
    inline double objectiveValue() const {
        return objectiveValue_;
    }
    inline void setObjectiveValue(double value) {
        objectiveValue_ = value;
    }
    /// Number of arms defined for the attached OsiBranchingObject.
    inline int numberBranches() const {
        if (branch_)
            return (branch_->numberBranches()) ;
        else
            return (-1) ;
    }

    /* Active arm of the attached OsiBranchingObject.

     In the simplest instance, coded -1 for the down arm of the branch, +1 for
     the up arm. But see OsiBranchingObject::way()
       Use nodeInfo--.numberBranchesLeft_ to see how active
    */
    int way() const;
    /// Depth in branch-and-cut search tree
    inline int depth() const {
        return depth_;
    }
    /// Set depth in branch-and-cut search tree
    inline void setDepth(int value) {
        depth_ = value;
    }
    /// Get the number of objects unsatisfied at this node.
    inline int numberUnsatisfied() const {
        return numberUnsatisfied_;
    }
    /// Set the number of objects unsatisfied at this node.
    inline void setNumberUnsatisfied(int value) {
        numberUnsatisfied_ = value;
    }
    /// Get sum of "infeasibilities" reported by each object
    inline double sumInfeasibilities() const {
        return sumInfeasibilities_;
    }
    /// Set sum of "infeasibilities" reported by each object
    inline void setSumInfeasibilities(double value) {
        sumInfeasibilities_ = value;
    }
    // Guessed objective value (for solution)
    inline double guessedObjectiveValue() const {
        return guessedObjectiveValue_;
    }
    inline void setGuessedObjectiveValue(double value) {
        guessedObjectiveValue_ = value;
    }
    /// Branching object for this node
    inline const OsiBranchingObject * branchingObject() const {
        return branch_;
    }
    /// Modifiable branching object for this node
    inline OsiBranchingObject * modifiableBranchingObject() const {
        return branch_;
    }
    /// Set branching object for this node (takes ownership)
    inline void setBranchingObject(OsiBranchingObject * branchingObject) {
        branch_ = branchingObject;
    }
    /// The node number
    inline int nodeNumber() const {
        return nodeNumber_;
    }
    inline void setNodeNumber(int node) {
        nodeNumber_ = node;
    }
    /// Returns true if on tree
    inline bool onTree() const {
        return (state_&1) != 0;
    }
    /// Sets true if on tree
    inline void setOnTree(bool yesNo) {
        if (yesNo) state_ |= 1;
        else state_ &= ~1;
    }
    /// Returns true if active
    inline bool active() const {
        return (state_&2) != 0;
    }
    /// Sets true if active
    inline void setActive(bool yesNo) {
        if (yesNo) state_ |= 2;
        else state_ &= ~2;
    }
    /// Print
    void print() const;
    /// Debug
    inline void checkInfo() const {
        assert (nodeInfo_->numberBranchesLeft() ==
                branch_->numberBranchesLeft());
    }

private:
    // Data
    /// Information to make basis and bounds
    CbcNodeInfo * nodeInfo_;
    /// Objective value
    double objectiveValue_;
    /// Guessed satisfied Objective value
    double guessedObjectiveValue_;
    /// Sum of "infeasibilities" reported by each object
    double sumInfeasibilities_;
    /// Branching object for this node
    OsiBranchingObject * branch_;
    /// Depth of the node in the search tree
    int depth_;
    /// The number of objects unsatisfied at this node.
    int numberUnsatisfied_;
    /// The node number
    int nodeNumber_;
    /** State
        1 - on tree
        2 - active
    */
    int state_;
};


#endif