CbcHeuristic.hpp

Go to the documentation of this file.

/* $Id: CbcHeuristic.hpp 2467 2019-01-03 21:26:29Z unxusr $ */
// 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"

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_;
  }
#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
*/