CbcHeuristic.hpp

Go to the documentation of this file.

/* $Id: CbcHeuristic.hpp 2094 2014-11-18 11:15:36Z forrest $ */
// 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;
 
//#############################################################################
 
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_;
    }
    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