/home/coin/SVN-release/CoinAll-1.1.0/Cbc/src/CbcBranchBase.hpp

Go to the documentation of this file.

// Copyright (C) 2002, International Business Machines
// Corporation and others.  All Rights Reserved.
#ifndef CbcBranchBase_H
#define CbcBranchBase_H

#include <string>
#include <vector>
#include "OsiBranchingObject.hpp"
class OsiSolverInterface;
class OsiSolverBranch;

class CbcModel;
class CbcNode;
class CbcNodeInfo;
class CbcBranchingObject;
class OsiChooseVariable;
class CbcObjectUpdateData;

//#############################################################################

enum CbcRangeCompare {
  CbcRangeSame,
  CbcRangeDisjoint,
  CbcRangeSubset,
  CbcRangeSuperset,
  CbcRangeOverlap
};

//#############################################################################

// This can be used if object wants to skip strong branching
  typedef struct {
    CbcBranchingObject * possibleBranch; // what a branch would do
    double upMovement; // cost going up (and initial away from feasible)
    double downMovement; // cost going down
    int numIntInfeasUp ; // without odd ones
    int numObjInfeasUp ; // just odd ones
    bool finishedUp; // true if solver finished
    int numItersUp ; // number of iterations in solver
    int numIntInfeasDown ; // without odd ones
    int numObjInfeasDown ; // just odd ones
    bool finishedDown; // true if solver finished
    int numItersDown; // number of iterations in solver
    int objectNumber; // Which object it is
    int fix; // 0 if no fix, 1 if we can fix up, -1 if we can fix down
  } CbcStrongInfo;

class CbcObject : public OsiObject {

public:

  // Default Constructor 
  CbcObject ();

  // Useful constructor
  CbcObject (CbcModel * model);
  
  // Copy constructor 
  CbcObject ( const CbcObject &);
   
  // Assignment operator 
  CbcObject & operator=( const CbcObject& rhs);

  virtual CbcObject * clone() const=0;

  virtual ~CbcObject ();

  virtual double infeasibility(int &preferredWay) const = 0;
  virtual double infeasibility(const OsiBranchingInformation * info,
                               int &preferredWay) const;

  virtual void feasibleRegion() = 0;
  virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;

  virtual CbcBranchingObject * createBranch(int way) = 0;
  
  virtual double infeasibility(const OsiSolverInterface * solver,int &preferredWay) const;
  
  virtual double feasibleRegion(OsiSolverInterface * solver) const ;
  
  virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, int way) const;
  virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver,const OsiBranchingInformation * info, int way) const;
  virtual OsiSolverBranch * solverBranch() const;
  
  virtual CbcBranchingObject * preferredNewFeasible() const 
  { return NULL;}
  
  virtual CbcBranchingObject * notPreferredNewFeasible() const 
  { return NULL;}

  virtual void resetBounds(const OsiSolverInterface * solver) {}
  
  virtual void floorCeiling(double & floorValue, double & ceilingValue, double value,
                            double tolerance) const;

  virtual CbcObjectUpdateData createUpdateInformation(const OsiSolverInterface * solver, 
                                                        const CbcNode * node,
                                                        const CbcBranchingObject * branchingObject);

  virtual void updateInformation(const CbcObjectUpdateData & data) {}

  inline int id() const
  { return id_;}
  
  inline void setModel(CbcModel * model)
  { model_ = model;}
  
  inline CbcModel * model() const
  {return  model_;}

  inline int preferredWay() const
  { return preferredWay_;}
  inline void setPreferredWay(int value)
  { preferredWay_=value;}
  virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns) {}
  
protected:

  CbcModel * model_;
  int id_;
  int preferredWay_;

};

class CbcBranchingObject : public OsiBranchingObject {

public:

  CbcBranchingObject ();

  CbcBranchingObject (CbcModel * model, int variable, int way , double value);
  
  CbcBranchingObject ( const CbcBranchingObject &);
   
  CbcBranchingObject & operator=( const CbcBranchingObject& rhs);

  virtual CbcBranchingObject * clone() const=0;

  virtual ~CbcBranchingObject ();

  virtual int fillStrongInfo( CbcStrongInfo & info) {return 0;}
  inline void resetNumberBranchesLeft()
  { branchIndex_=0;}

  virtual double branch()=0;
  virtual double branch(OsiSolverInterface * solver)
  { return branch();}

  virtual void previousBranch() {
    assert(branchIndex_ > 0);
    branchIndex_--;
    way_ = -way_;
  }

  using OsiBranchingObject::print ;
  virtual void print() const {}

  inline int variable() const
  {return variable_;}

  inline int way() const
  {return way_;}

  inline void way(int way)
  {way_=way;}

  inline void setModel(CbcModel * model)
  { model_ = model;}
  inline CbcModel * model() const
  {return  model_;}

  inline CbcObject * object() const
  {return  originalCbcObject_;}
  inline void setOriginalObject(CbcObject * object)
  {originalCbcObject_=object;}

  // Methods used in heuristics
  
  virtual int type() const = 0;

  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const
  {
    const CbcBranchingObject* br=dynamic_cast<const CbcBranchingObject*>(brObj);
    return variable() - br->variable();
  }

  virtual CbcRangeCompare compareBranchingObject
  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false) = 0;

protected:

  CbcModel * model_;
  CbcObject * originalCbcObject_;

  int variable_;
  // was - Way to branch - -1 down (first), 1 up, -2 down (second), 2 up (second)
  int way_;

};


class CbcBranchDecision {
public:
  CbcBranchDecision ();

  // Copy constructor 
  CbcBranchDecision ( const CbcBranchDecision &);
   
  virtual ~CbcBranchDecision();

  virtual CbcBranchDecision * clone() const = 0;

  virtual void initialize(CbcModel * model) = 0;

  virtual int
  betterBranch (CbcBranchingObject * thisOne,
                CbcBranchingObject * bestSoFar,
                double changeUp, int numberInfeasibilitiesUp,
                double changeDown, int numberInfeasibilitiesDown) = 0 ;

  virtual int
  bestBranch (CbcBranchingObject ** objects, int numberObjects, int numberUnsatisfied,
              double * changeUp, int * numberInfeasibilitiesUp,
              double * changeDown, int * numberInfeasibilitiesDown,
              double objectiveValue) ;

  virtual int whichMethod() {return 2;}

  virtual void saveBranchingObject(OsiBranchingObject * object) {}
  virtual void updateInformation(OsiSolverInterface * solver, 
                                 const CbcNode * node) {}
  virtual void setBestCriterion(double value) {}
  virtual double getBestCriterion() const {return 0.0;}
  virtual void generateCpp( FILE * fp) {}
  inline CbcModel * cbcModel() const
  { return model_;}
  /* If chooseMethod_ id non-null then the rest is fairly pointless
     as choosemethod_ will be doing all work
  */
  OsiChooseVariable * chooseMethod() const
  { return chooseMethod_;}
  void setChooseMethod(const OsiChooseVariable & method);

protected:
  
  // Clone of branching object
  CbcBranchingObject * object_;
  CbcModel * model_;
  /* If chooseMethod_ id non-null then the rest is fairly pointless
     as choosemethod_ will be doing all work
  */
  OsiChooseVariable * chooseMethod_;
private:
  CbcBranchDecision & operator=(const CbcBranchDecision& rhs);
  
};
class CbcConsequence {

public:

  // Default Constructor 
  CbcConsequence ();

  // Copy constructor 
  CbcConsequence ( const CbcConsequence & rhs);
   
  // Assignment operator 
  CbcConsequence & operator=( const CbcConsequence & rhs);

  virtual CbcConsequence * clone() const=0;

  virtual ~CbcConsequence ();

  virtual void applyToSolver(OsiSolverInterface * solver, int state) const=0;
  
protected:
};
/*  This stores data so an object can be updated
 */
class CbcObjectUpdateData {

public:

  CbcObjectUpdateData ();

  CbcObjectUpdateData (CbcObject * object,
                       int way,
                       double change,
                       int status,
                       int intDecrease_,
                       double branchingValue);
  
  CbcObjectUpdateData ( const CbcObjectUpdateData &);
   
  CbcObjectUpdateData & operator=( const CbcObjectUpdateData& rhs);

  virtual ~CbcObjectUpdateData ();

  
public:

  CbcObject * object_;
  int way_;
  int objectNumber_;
  double change_;
  int status_;
  int intDecrease_;
  double branchingValue_;
  double originalObjective_;
  double cutoff_;

};

//##############################################################################

static inline CbcRangeCompare
CbcCompareRanges(double* thisBd, const double* otherBd,
                 const bool replaceIfOverlap)
{
  const double lbDiff = thisBd[0] - otherBd[0];
  if (lbDiff < 0) { // lb of this < lb of other
    if (thisBd[1] >= otherBd[1]) { // ub of this >= ub of other
      return CbcRangeSuperset;
    } else if (thisBd[1] < otherBd[0]) {
      return CbcRangeDisjoint;
    } else {
      // overlap
      if (replaceIfOverlap) {
        thisBd[0] = otherBd[0];
      }
      return CbcRangeOverlap;
    }
  } else if (lbDiff > 0) { // lb of this > lb of other
    if (thisBd[1] <= otherBd[1]) { // ub of this <= ub of other
      return CbcRangeSubset;
    } else if (thisBd[0] > otherBd[1]) {
      return CbcRangeDisjoint;
    } else {
      // overlap
      if (replaceIfOverlap) {
        thisBd[1] = otherBd[1];
      }
      return CbcRangeOverlap;
    }
  } else { // lb of this == lb of other
    if (thisBd[1] == otherBd[1]) {
      return CbcRangeSame;
    }
    return thisBd[1] < otherBd[1] ? CbcRangeSubset : CbcRangeSuperset;
  }

  return CbcRangeSame; // fake return

}

//#############################################################################

#endif

---