CbcHeuristic.hpp

Go to the documentation of this file.

/* $Id$ */
// Copyright (C) 2002, International Business Machines
// Corporation and others.  All Rights Reserved.
// This code is licensed under the terms of the Eclipse Public License (EPL).
 
#ifndef CbcHeuristic_H
#define CbcHeuristic_H
 
#include <string>
#include <vector>
#include "CoinPackedMatrix.hpp"
#include "OsiCuts.hpp"
#include "CoinHelperFunctions.hpp"
#include "OsiBranchingObject.hpp"
#include "CbcModel.hpp"
 
class OsiSolverInterface;
 
class CbcModel;
#ifdef COIN_HAS_CLP
#include "OsiClpSolverInterface.hpp"
#endif
//#############################################################################
 
class CbcHeuristicNodeList;
class CbcBranchingObject;
 
class CbcHeuristicNode {
private:
  void gutsOfConstructor(CbcModel &model);
  CbcHeuristicNode();
  CbcHeuristicNode &operator=(const CbcHeuristicNode &);
 
private:
  int numObjects_;
  CbcBranchingObject **brObj_;
 
public:
  CbcHeuristicNode(CbcModel &model);
 
  CbcHeuristicNode(const CbcHeuristicNode &rhs);
  ~CbcHeuristicNode();
  double distance(const CbcHeuristicNode *node) const;
  double minDistance(const CbcHeuristicNodeList &nodeList) const;
  bool minDistanceIsSmall(const CbcHeuristicNodeList &nodeList,
    const double threshold) const;
  double avgDistance(const CbcHeuristicNodeList &nodeList) const;
};
 
class CbcHeuristicNodeList {
private:
  void gutsOfDelete();
  void gutsOfCopy(const CbcHeuristicNodeList &rhs);
 
private:
  std::vector< CbcHeuristicNode * > nodes_;
 
public:
  CbcHeuristicNodeList() {}
  CbcHeuristicNodeList(const CbcHeuristicNodeList &rhs);
  CbcHeuristicNodeList &operator=(const CbcHeuristicNodeList &rhs);
  ~CbcHeuristicNodeList();
 
  void append(CbcHeuristicNode *&node);
  void append(const CbcHeuristicNodeList &nodes);
  inline const CbcHeuristicNode *node(int i) const
  {
    return nodes_[i];
  }
  inline int size() const
  {
    return static_cast< int >(nodes_.size());
  }
};
 
//#############################################################################
class CbcHeuristic {
private:
  void gutsOfDelete() {}
  void gutsOfCopy(const CbcHeuristic &rhs);
 
public:
  // Default Constructor
  CbcHeuristic();
 
  // Constructor with model - assumed before cuts
  CbcHeuristic(CbcModel &model);
 
  // Copy constructor
  CbcHeuristic(const CbcHeuristic &);
 
  virtual ~CbcHeuristic();
 
  virtual CbcHeuristic *clone() const = 0;
 
  CbcHeuristic &operator=(const CbcHeuristic &rhs);
 
  virtual void setModel(CbcModel *model);
 
  virtual void resetModel(CbcModel *model) = 0;
 
  virtual int solution(double &objectiveValue,
    double *newSolution)
    = 0;
 
  virtual int solution2(double & /*objectiveValue*/,
    double * /*newSolution*/,
    OsiCuts & /*cs*/)
  {
    return 0;
  }
 
  virtual void validate() {}
 
  inline void setWhen(int value)
  {
    when_ = value;
  }
  inline int when() const
  {
    return when_;
  }
 
  inline void setNumberNodes(int value)
  {
    numberNodes_ = value;
  }
  inline int numberNodes() const
  {
    return numberNodes_;
  }
  inline void setSwitches(int value)
  {
    switches_ = value;
  }
  inline int switches() const
  {
    return switches_;
  }
  bool exitNow(double bestObjective) const;
  inline void setFeasibilityPumpOptions(int value)
  {
    feasibilityPumpOptions_ = value;
  }
  inline int feasibilityPumpOptions() const
  {
    return feasibilityPumpOptions_;
  }
  inline void setModelOnly(CbcModel *model)
  {
    model_ = model;
  }
 
  inline void setFractionSmall(double value)
  {
    fractionSmall_ = value;
  }
  inline double fractionSmall() const
  {
    return fractionSmall_;
  }
  inline int numberSolutionsFound() const
  {
    return numberSolutionsFound_;
  }
  inline void incrementNumberSolutionsFound()
  {
    numberSolutionsFound_++;
  }
 
  int smallBranchAndBound(OsiSolverInterface *solver, int numberNodes,
    double *newSolution, double &newSolutionValue,
    double cutoff, std::string name) const;
  virtual void generateCpp(FILE *) {}
  void generateCpp(FILE *fp, const char *heuristic);
  virtual bool canDealWithOdd() const
  {
    return false;
  }
  inline const char *heuristicName() const
  {
    return heuristicName_.c_str();
  }
  inline void setHeuristicName(const char *name)
  {
    heuristicName_ = name;
  }
  void setSeed(int value);
  int getSeed() const;
  inline void setDecayFactor(double value)
  {
    decayFactor_ = value;
  }
  void setInputSolution(const double *solution, double objValue);
  /* Runs if bit set
        0 - before cuts at root node (or from doHeuristics)
        1 - during cuts at root
        2 - after root node cuts
        3 - after cuts at other nodes
        4 - during cuts at other nodes
            8 added if previous heuristic in loop found solution
     */
  inline void setWhereFrom(int value)
  {
    whereFrom_ = value;
  }
  inline int whereFrom() const
  {
    return whereFrom_;
  }
  inline void setShallowDepth(int value)
  {
    shallowDepth_ = value;
  }
  inline void setHowOftenShallow(int value)
  {
    howOftenShallow_ = value;
  }
  inline void setMinDistanceToRun(int value)
  {
    minDistanceToRun_ = value;
  }
 
  virtual bool shouldHeurRun(int whereFrom);
  bool shouldHeurRun_randomChoice();
  void debugNodes();
  void printDistanceToNodes();
  inline int numRuns() const
  {
    return numRuns_;
  }
 
  inline int numCouldRun() const
  {
    return numCouldRun_;
  }
  inline double trueObjValue(double value) const
  {
    return (model_->moreSpecialOptions2()&67108864)==0 ? value : -value;
  }
#ifdef COIN_HAS_CLP
  inline bool isHeuristicInteger(const OsiSolverInterface *solver, int iColumn) const
  {
    const OsiClpSolverInterface *clpSolver
      = dynamic_cast< const OsiClpSolverInterface * >(solver);
    if (clpSolver)
      return clpSolver->isHeuristicInteger(iColumn);
    else
      return solver->isInteger(iColumn);
  }
#else
  inline bool isHeuristicInteger(const OsiSolverInterface *solver, int iColumn)
  {
    return solver->isInteger(iColumn);
  }
#endif
 
  OsiSolverInterface *cloneBut(int type);
 
protected:
  CbcModel *model_;
  int when_;
  int numberNodes_;
  int feasibilityPumpOptions_;
  mutable double fractionSmall_;
  CoinThreadRandom randomNumberGenerator_;
  std::string heuristicName_;
 
  mutable int howOften_;
  double decayFactor_;
  mutable int switches_;
  /* Runs if bit set
        0 - before cuts at root node (or from doHeuristics)
        1 - during cuts at root
        2 - after root node cuts
        3 - after cuts at other nodes
        4 - during cuts at other nodes
            8 added if previous heuristic in loop found solution
     */
  int whereFrom_;
  int shallowDepth_;
  int howOftenShallow_;
  int numInvocationsInShallow_;
  int numInvocationsInDeep_;
  int lastRunDeep_;
  int numRuns_;
  int minDistanceToRun_;
 
  CbcHeuristicNodeList runNodes_;
 
  int numCouldRun_;
 
  int numberSolutionsFound_;
 
  mutable int numberNodesDone_;
 
  // Input solution - so can be used as seed
  double *inputSolution_;
 
#ifdef JJF_ZERO
  double *lowerBoundLastNode_;
  double *upperBoundLastNode_;
#endif
};
class CbcRounding : public CbcHeuristic {
public:
  // Default Constructor
  CbcRounding();
 
  // Constructor with model - assumed before cuts
  CbcRounding(CbcModel &model);
 
  // Copy constructor
  CbcRounding(const CbcRounding &);
 
  // Destructor
  ~CbcRounding();
 
  CbcRounding &operator=(const CbcRounding &rhs);
 
  virtual CbcHeuristic *clone() const;
  virtual void generateCpp(FILE *fp);
 
  virtual void resetModel(CbcModel *model);
 
  virtual void setModel(CbcModel *model);
 
  using CbcHeuristic::solution;
  virtual int solution(double &objectiveValue,
    double *newSolution);
  virtual int solution(double &objectiveValue,
    double *newSolution,
    double solutionValue);
  virtual void validate();
 
  void setSeed(int value)
  {
    seed_ = value;
  }
  virtual bool shouldHeurRun(int whereFrom);
 
protected:
  // Data
 
  // Original matrix by column
  CoinPackedMatrix matrix_;
 
  // Original matrix by
  CoinPackedMatrix matrixByRow_;
 
  // Down locks
  unsigned short *down_;
 
  // Up locks
  unsigned short *up_;
 
  // Equality locks
  unsigned short *equal_;
 
  // Seed for random stuff
  int seed_;
};
 
class CbcHeuristicPartial : public CbcHeuristic {
public:
  // Default Constructor
  CbcHeuristicPartial();
 
  CbcHeuristicPartial(CbcModel &model, int fixPriority = 10000, int numberNodes = 200);
 
  // Copy constructor
  CbcHeuristicPartial(const CbcHeuristicPartial &);
 
  // Destructor
  ~CbcHeuristicPartial();
 
  CbcHeuristicPartial &operator=(const CbcHeuristicPartial &rhs);
 
  virtual CbcHeuristic *clone() const;
  virtual void generateCpp(FILE *fp);
 
  virtual void resetModel(CbcModel *model);
 
  virtual void setModel(CbcModel *model);
 
  using CbcHeuristic::solution;
  virtual int solution(double &objectiveValue,
    double *newSolution);
  virtual void validate();
 
  void setFixPriority(int value)
  {
    fixPriority_ = value;
  }
 
  virtual bool shouldHeurRun(int whereFrom);
 
protected:
  // Data
 
  // All variables with abs priority <= this will be fixed
  int fixPriority_;
};
 
class CbcSerendipity : public CbcHeuristic {
public:
  // Default Constructor
  CbcSerendipity();
 
  /* Constructor with model
    */
  CbcSerendipity(CbcModel &model);
 
  // Copy constructor
  CbcSerendipity(const CbcSerendipity &);
 
  // Destructor
  ~CbcSerendipity();
 
  CbcSerendipity &operator=(const CbcSerendipity &rhs);
 
  virtual CbcHeuristic *clone() const;
  virtual void generateCpp(FILE *fp);
 
  virtual void setModel(CbcModel *model);
 
  using CbcHeuristic::solution;
  virtual int solution(double &objectiveValue,
    double *newSolution);
  virtual void resetModel(CbcModel *model);
 
protected:
};
 
class CbcHeuristicJustOne : public CbcHeuristic {
public:
  // Default Constructor
  CbcHeuristicJustOne();
 
  // Constructor with model - assumed before cuts
  CbcHeuristicJustOne(CbcModel &model);
 
  // Copy constructor
  CbcHeuristicJustOne(const CbcHeuristicJustOne &);
 
  // Destructor
  ~CbcHeuristicJustOne();
 
  virtual CbcHeuristicJustOne *clone() const;
 
  CbcHeuristicJustOne &operator=(const CbcHeuristicJustOne &rhs);
 
  virtual void generateCpp(FILE *fp);
 
  virtual int solution(double &objectiveValue,
    double *newSolution);
  virtual void resetModel(CbcModel *model);
 
  virtual void setModel(CbcModel *model);
 
  virtual bool selectVariableToBranch(OsiSolverInterface * /*solver*/,
    const double * /*newSolution*/,
    int & /*bestColumn*/,
    int & /*bestRound*/)
  {
    return true;
  }
  virtual void validate();
  void addHeuristic(const CbcHeuristic *heuristic, double probability);
  void normalizeProbabilities();
 
protected:
  // Data
 
  // Probability of running a heuristic
  double *probabilities_;
 
  // Heuristics
  CbcHeuristic **heuristic_;
 
  // Number of heuristics
  int numberHeuristics_;
};
#endif
 
/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
*/