CbcHeuristic.hpp

Go to the documentation of this file.

/* $Id: CbcHeuristic.hpp 1432 2010-02-07 19:33:53Z bjarni $ */
// Copyright (C) 2002, International Business Machines
// Corporation and others.  All Rights Reserved.
#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 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);
    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 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_;

    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_;

    // 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;
    }

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