master.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/lib/abacus/global.h>
#include <ogdf/lib/abacus/optsense.h>
 
#include <ogdf/lib/abacus/hash.h>
#include <ogdf/basic/Stopwatch.h>
 
 
class OsiSolverInterface;
 
namespace abacus {
 
 
class Sub;
class BranchRule;
class Variable;
class Constraint;
 
class History;
class OpenSub;
class FixCand;
class LpMasterOsi;
 
template<class BaseType, class CoType> class StandardPool;
 
 
 
class OGDF_EXPORT Master : public AbacusGlobal {
 
    friend class Sub;
    friend class FixCand;
 
public:
 
    enum STATUS {
        Optimal,        
        Error,          
        OutOfMemory,
        Unprocessed,    
        Processing,     
        Guaranteed,     
        MaxLevel,       
        MaxCpuTime,     
        MaxNSub,        
        MaxCowTime,     
        ExceptionFathom 
    };
 
 
    static const char* STATUS_[];
 
 
    enum ENUMSTRAT {
        BestFirst,      
        BreadthFirst,   
        DepthFirst,     
        DiveAndBest     
    };
 
 
    static const char *ENUMSTRAT_[];
 
    enum BRANCHINGSTRAT {
        CloseHalf,          
        CloseHalfExpensive  
    };
 
 
    static const char *BRANCHINGSTRAT_[];
 
 
    enum PRIMALBOUNDMODE {
        NoPrimalBound,  
        Optimum,        
        OptimumOne      
    };
 
 
    static const char* PRIMALBOUNDMODE_[];
 
    enum SKIPPINGMODE{
        SkipByNode, 
        SkipByLevel 
    };
 
 
    static const char* SKIPPINGMODE_[];
 
    enum CONELIMMODE {
        NoConElim,  
        NonBinding, 
        Basic       
    };
 
 
 
    static const char* CONELIMMODE_[];
 
    enum VARELIMMODE {
        NoVarElim,  
        ReducedCost 
    };
 
 
    static const char* VARELIMMODE_[];
 
    enum VBCMODE {
        NoVbc,  
        File,   
        Pipe    
    };
 
 
    static const char* VBCMODE_[];
 
 
 
    enum OSISOLVER { Cbc, Clp, CPLEX, DyLP, FortMP, GLPK, MOSEK, OSL, SoPlex, SYMPHONY, XPRESS_MP, Gurobi, Csdp };
 
    static const char* OSISOLVER_[];
 
 
    Master(const char *problemName, bool cutting, bool pricing,
        OptSense::SENSE optSense = OptSense::Unknown,
        double eps = 1.0e-4, double machineEps = 1.0e-7,
        double infinity = 1.0e30,
        bool readParamFromFile = false);
 
    virtual ~Master();
 
 
    STATUS optimize();
 
 
    double lowerBound() const;
 
    double upperBound() const;
 
 
    double primalBound() const { return primalBound_; }
 
 
    void primalBound(double x);
 
 
    double dualBound() const { return dualBound_; }
 
 
    void dualBound(double x);
 
 
    bool betterDual(double x) const;
 
 
    bool primalViolated(double x) const;
 
 
    bool betterPrimal(double x) const;
 
    double rootDualBound() const { return rootDualBound_; }
 
    /***
     * This function is only correct if any primal bound better than plus/minus infinity corresponds
     * to a feasible solution.
     *
     * \return true If a feasible solution of the optimization problem has been found, false otherwise.
     */
    bool feasibleFound() const;
 
    ENUMSTRAT enumerationStrategy() const { return enumerationStrategy_; }
 
 
    void enumerationStrategy(ENUMSTRAT strat) { enumerationStrategy_ = strat; }
 
    virtual int enumerationStrategy(const Sub *s1, const Sub *s2);
 
 
    bool guaranteed() const;
 
 
    double guarantee() const;
 
 
    void printGuarantee() const;
 
 
    bool check() const;
 
    bool knownOptimum(double &optVal) const;
 
    virtual void output() const { }
 
    bool cutting() const { return cutting_; }
 
    bool pricing() const { return pricing_; }
 
    const OptSense *optSense() const { return &optSense_; }
 
    History *history() const { return history_; }
 
    OpenSub *openSub() const { return openSub_; }
 
    StandardPool<Constraint, Variable> *conPool() const { return conPool_; }
 
    StandardPool<Constraint, Variable> *cutPool() const { return cutPool_; }
 
    StandardPool<Variable, Constraint> *varPool() const { return varPool_; }
 
 
    Sub *root() const { return root_; }
 
    Sub *rRoot() const { return rRoot_; }
 
    STATUS status() const { return status_; }
 
    const string &problemName() const { return problemName_; }
 
    const ogdf::StopwatchWallClock *totalCowTime() const { return &totalCowTime_; }
 
    inline bool solveApprox() const { return solveApprox_; }
 
    const ogdf::StopwatchCPU *totalTime() const { return &totalTime_; }
 
    const ogdf::StopwatchCPU *lpTime() const { return &lpTime_; }
 
    const ogdf::StopwatchCPU *lpSolverTime() const { return &lpSolverTime_; }
 
    const ogdf::StopwatchCPU *separationTime() const { return &separationTime_; }
 
    const ogdf::StopwatchCPU *improveTime() const { return &improveTime_; }
 
    const ogdf::StopwatchCPU *pricingTime() const { return &pricingTime_; }
 
    const ogdf::StopwatchCPU *branchingTime() const { return &branchingTime_; }
 
    int nSub() const { return nSub_; }
 
    int nLp() const { return nLp_; }
 
    int highestLevel() const { return highestLevel_; }
 
    int nNewRoot() const { return nNewRoot_; }
 
    int nSubSelected() const { return nSubSelected_; }
 
    void printParameters() const;
 
    BRANCHINGSTRAT branchingStrategy() const { return branchingStrategy_; }
 
 
    void branchingStrategy(BRANCHINGSTRAT strat) { branchingStrategy_ = strat; }
 
    OSISOLVER defaultLpSolver() const { return defaultLpSolver_; }
 
 
    void defaultLpSolver(OSISOLVER osiSolver) { defaultLpSolver_ = osiSolver; }
 
    LpMasterOsi *lpMasterOsi() const { return lpMasterOsi_; }
 
    int nBranchingVariableCandidates() const { return nBranchingVariableCandidates_; }
 
 
    void nBranchingVariableCandidates(int n);
 
    int nStrongBranchingIterations() const { return nStrongBranchingIterations_; }
 
 
    void nStrongBranchingIterations(int n);
 
    double requiredGuarantee() const { return requiredGuarantee_; }
 
 
    void requiredGuarantee(double g);
 
 
    int maxLevel() const { return maxLevel_; }
 
 
    void maxLevel(int ml);
 
 
    int maxNSub() const { return maxNSub_; }
 
 
    void maxNSub(int ml);
 
    int64_t maxCpuTime() const { return maxCpuTime_; }
 
    string maxCpuTimeAsString() const;
 
 
    void maxCpuTime(const string &t);
 
    void maxCpuTime(int64_t seconds) { maxCpuTime_ = seconds; }
 
    void maxCpuTime(int hour, int min, int sec);
 
    int64_t maxCowTime() const { return maxCowTime_; }
 
    string maxCowTimeAsString() const;
 
    void maxCowTime(int64_t seconds) { maxCowTime_ = seconds; }
 
 
    void maxCowTime(const string &t);
 
    bool objInteger() const { return objInteger_; }
 
 
    void objInteger(bool b) { objInteger_ = b; }
 
    int tailOffNLp() const { return tailOffNLp_; }
 
 
    void tailOffNLp(int n) { tailOffNLp_ = n; }
 
    double tailOffPercent() const { return tailOffPercent_; }
 
 
    void tailOffPercent(double p);
 
 
    bool delayedBranching(int nOpt) const;
 
 
    void dbThreshold(int threshold) { dbThreshold_ = threshold; }
 
 
    int dbThreshold() const { return dbThreshold_; }
 
 
    int minDormantRounds() const { return minDormantRounds_; }
 
 
    void minDormantRounds(int nRounds) { minDormantRounds_ = nRounds; }
 
    PRIMALBOUNDMODE pbMode() const { return pbMode_; }
 
 
    void pbMode(PRIMALBOUNDMODE mode) { pbMode_ = mode; }
 
 
    int pricingFreq() const { return pricingFreq_; }
 
 
    void pricingFreq(int f);
 
    int skipFactor() const { return skipFactor_; }
 
 
    void skipFactor(int f);
 
 
    void skippingMode(SKIPPINGMODE mode) { skippingMode_ = mode; }
 
    SKIPPINGMODE skippingMode() const { return skippingMode_; }
 
    CONELIMMODE conElimMode() const { return conElimMode_; }
 
 
    void conElimMode(CONELIMMODE mode) { conElimMode_ = mode; }
 
    VARELIMMODE varElimMode() const { return varElimMode_; }
 
 
    void varElimMode(VARELIMMODE mode) { varElimMode_ = mode; }
 
    double conElimEps() const { return conElimEps_; }
 
 
    void conElimEps(double eps) { conElimEps_ = eps; }
 
    double varElimEps() const { return varElimEps_; }
 
 
    void varElimEps(double eps) { varElimEps_ = eps; }
 
    int varElimAge() const { return varElimAge_; }
 
 
    void varElimAge(int age) { varElimAge_ = age; }
 
    int conElimAge() const { return conElimAge_; }
 
 
    void conElimAge(int age) { conElimAge_ = age; }
 
    bool fixSetByRedCost() const { return fixSetByRedCost_; }
 
 
    void fixSetByRedCost(bool on) { fixSetByRedCost_ = on; }
 
    bool printLP() const { return printLP_; }
 
 
    void printLP(bool on) { printLP_ = on; }
 
    int maxConAdd() const { return maxConAdd_; }
 
    /***
     * \param max The maximal number of constraints.
     */
    void maxConAdd(int max) { maxConAdd_ = max; }
 
    int maxConBuffered() const { return maxConBuffered_; }
 
 
    void maxConBuffered(int max) { maxConBuffered_ = max; }
 
    int maxVarAdd() const { return maxVarAdd_; }
 
 
    void maxVarAdd(int max) { maxVarAdd_ = max; }
 
    int maxVarBuffered() const { return maxVarBuffered_; }
 
 
    void maxVarBuffered(int max) { maxVarBuffered_ = max; }
 
    int maxIterations() const { return maxIterations_; }
 
 
    void maxIterations(int max) { maxIterations_ = max; }
 
    bool eliminateFixedSet() const { return eliminateFixedSet_; }
 
 
    void eliminateFixedSet(bool turnOn) { eliminateFixedSet_ = turnOn; }
 
    bool newRootReOptimize() const { return newRootReOptimize_; }
 
 
    void newRootReOptimize(bool on) { newRootReOptimize_ = on; }
 
    const string &optimumFileName() const { return optimumFileName_; }
 
 
    void optimumFileName(const char *name) { optimumFileName_ = name; }
 
    bool showAverageCutDistance() const { return showAverageCutDistance_; }
 
 
    void showAverageCutDistance(bool on) { showAverageCutDistance_ = on; }
 
    VBCMODE vbcLog() const { return VbcLog_; }
 
 
    void vbcLog(VBCMODE mode) { VbcLog_ = mode; }
 
 
    virtual bool setSolverParameters(OsiSolverInterface* interface, bool solverIsApprox);
 
protected:
 
 
    virtual void initializePools(
        ArrayBuffer<Constraint*> &constraints,
        ArrayBuffer<Variable*> &variables,
        int varPoolSize,
        int cutPoolSize,
        bool dynamicCutPool = false);
 
 
    virtual void initializePools(
        ArrayBuffer<Constraint*> &constraints,
        ArrayBuffer<Constraint*> &cuts,
        ArrayBuffer<Variable*> &variables,
        int varPoolSize,
        int cutPoolSize,
        bool dynamicCutPool = false);
 
    void initializeOptSense(OptSense::SENSE sense) { optSense_.sense(sense); }
 
 
    int bestFirstSearch(const Sub* s1, const Sub* s2) const;
 
    virtual int equalSubCompare(const Sub *s1, const Sub *s2) const;
 
 
    int depthFirstSearch(const Sub* s1, const Sub* s2) const;
 
 
    int breadthFirstSearch(const Sub* s1, const Sub* s2) const;
 
 
 
    int diveAndBestFirstSearch(const Sub *s1, const Sub* s2) const;
 
    virtual void initializeParameters() { }
 
 
    virtual Sub *firstSub() = 0;
 
    virtual void initializeOptimization() { }
 
    virtual void terminateOptimization() { }
 
    virtual void assignParameters();
 
private:
 
 
    void _initializeParameters();
 
    void _createLpMasters();
    void _deleteLpMasters();
    void _initializeLpParameters();
 
 
    void _setDefaultLpParameters();
 
 
    void _printLpParameters() const;
 
 
    void _outputLpStatistics() const;
 
 
    Sub   *select();
 
    int initLP();
 
 
    void writeTreeInterface(const string &info, bool time = true) const;
 
    void treeInterfaceNewNode(Sub *sub) const;
 
    void treeInterfacePaintNode(int id, int color) const;
 
    void treeInterfaceLowerBound(double lb) const;
 
    void treeInterfaceUpperBound(double ub) const;
 
    void treeInterfaceNodeBounds(int id, double lb, double ub);
 
 
    void newSub(int level);
 
    void countLp() { ++nLp_; }
 
    void newFixed(int n) { nFixed_ += n; }
 
    void addCons(int n) { nAddCons_ += n; }
 
    void removeCons(int n) { nRemCons_ += n; }
 
    void addVars(int n) { nAddVars_ += n; }
 
    void removeVars(int n) { nRemVars_ += n; }
 
    FixCand *fixCand() const { return fixCand_; }
 
 
    void rRoot(Sub *newRoot, bool reoptimize);
 
    void status(STATUS stat) { status_ = stat; }
 
 
    void rootDualBound(double x);
 
    void theFuture();
 
    string problemName_;
 
    bool readParamFromFile_;
 
    OptSense optSense_;
 
    Sub *root_;
 
    Sub *rRoot_;
 
    OpenSub *openSub_;
 
    History *history_;
 
    ENUMSTRAT enumerationStrategy_;
 
    BRANCHINGSTRAT branchingStrategy_;
 
    int nBranchingVariableCandidates_;
 
    int nStrongBranchingIterations_;
 
    OSISOLVER defaultLpSolver_;
 
    LpMasterOsi *lpMasterOsi_;
 
    StandardPool<Constraint, Variable> *conPool_;
 
 
    StandardPool<Constraint, Variable> *cutPool_;
 
    StandardPool<Variable, Constraint> *varPool_;
 
    double primalBound_;
 
    double dualBound_;
 
    double rootDualBound_;
 
    FixCand *fixCand_;
 
    bool cutting_;
 
    bool pricing_;
 
    bool solveApprox_;
 
    int nSubSelected_;
 
    VBCMODE VbcLog_;
 
    std::ostream *treeStream_;
 
 
    double requiredGuarantee_;
 
 
    int maxLevel_;
 
 
    int maxNSub_;
 
    int64_t maxCpuTime_;
 
    int64_t maxCowTime_;
 
    bool objInteger_;
 
    int tailOffNLp_;
 
    double tailOffPercent_;
 
    int dbThreshold_;
 
    int minDormantRounds_;
 
    PRIMALBOUNDMODE pbMode_;
 
    int pricingFreq_;
 
    int skipFactor_;
 
    SKIPPINGMODE skippingMode_;
 
    bool fixSetByRedCost_;
 
    bool printLP_;
 
    int maxConAdd_;
 
    int maxConBuffered_;
 
    int maxVarAdd_;
 
    int maxVarBuffered_;
 
    int maxIterations_;
 
    bool eliminateFixedSet_;
 
    bool newRootReOptimize_;
 
    string optimumFileName_;
 
    bool showAverageCutDistance_;
 
    CONELIMMODE conElimMode_;
 
    VARELIMMODE varElimMode_;
 
    double conElimEps_;
 
    double varElimEps_;
 
    int conElimAge_;
 
    int varElimAge_;
 
    STATUS status_;
 
    ogdf::StopwatchWallClock totalCowTime_;
 
    ogdf::StopwatchCPU totalTime_;
 
    ogdf::StopwatchCPU lpTime_;
 
    ogdf::StopwatchCPU lpSolverTime_;
 
    ogdf::StopwatchCPU separationTime_;
 
    ogdf::StopwatchCPU improveTime_;
 
    ogdf::StopwatchCPU pricingTime_;
 
    ogdf::StopwatchCPU branchingTime_;
 
    int nSub_;
 
    int nLp_;
 
    int highestLevel_;
 
    int nFixed_;
 
    int nAddCons_;
 
    int nRemCons_;
 
    int nAddVars_;
 
    int nRemVars_;
 
    int nNewRoot_;
 
    Master(const Master &rhs);
    const Master &operator=(const Master& rhs);
};
 
 
inline double Master::lowerBound() const
{
    if (optSense_.max()) return primalBound_;
    else                 return dualBound_;
}
 
inline double Master::upperBound() const
{
    if (optSense_.max()) return dualBound_;
    else                 return primalBound_;
}
 
}