sub.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/lib/abacus/lp.h>
#include <ogdf/lib/abacus/fsvarstat.h>
#include <ogdf/lib/abacus/vartype.h>
 
#include <ogdf/basic/Stopwatch.h>
 
 
#pragma GCC visibility push(default)
namespace abacus {
 
class LpSub;
class TailOff;
class BranchRule;
class LPVARSTAT;
class Variable;
class Master;
class InfeasCon;
class Constraint;
 
template<class BaseType, class CoType> class CutBuffer;
template<class BaseType, class CoType> class Active;
template<class BaseType, class CoType> class Pool;
template<class BaseType, class CoType> class PoolSlot;
template<class BaseType, class CoType> class LpSolution;
 
 
 
class OGDF_EXPORT Sub : public AbacusRoot {
 
    friend class Master;
    friend class BoundBranchRule;
    friend class OpenSub;
    friend class LpSolution<Constraint, Variable>;
    friend class LpSolution<Variable, Constraint>;
 
public:
 
    enum STATUS {
        Unprocessed,    
        ActiveSub,      
        Dormant,        
        Processed,      
        Fathomed        
    };
 
    enum PHASE {
        Done,       
        Cutting,    
        Branching,  
        Fathoming   
    };
 
 
    Sub(
        Master *master,
        double conRes,
        double varRes,
        double nnzRes,
        bool relativeRes = true,
        ArrayBuffer<PoolSlot<Constraint, Variable> *> *constraints = nullptr,
        ArrayBuffer<PoolSlot<Variable, Constraint> *> *variables = nullptr);
 
 
    Sub(Master *master, Sub *father, BranchRule *branchRule);
 
 
    virtual ~Sub();
 
    bool forceExactSolver() const { return forceExactSolver_; }
 
    int level() const { return level_; }
 
    int id() const { return id_; }
 
    STATUS status() const { return status_; }
 
    int nVar() const;
 
    int maxVar() const;
 
    int nCon() const;
 
    int maxCon() const;
 
    double lowerBound() const;
 
    double upperBound() const;
 
 
    double dualBound() const { return dualBound_; }
 
 
    void dualBound(double x);
 
    const Sub *father() const { return father_; }
 
    LpSub *lp() const { return lp_; }
 
 
    void maxIterations(int max);
 
    Active<Constraint, Variable> *actCon() const { return actCon_; }
 
    Active<Variable, Constraint> *actVar() const { return actVar_; }
 
 
    Constraint *constraint(int i) const;
 
 
    SlackStat *slackStat(int i) const { return (*slackStat_)[i]; }
 
 
    Variable *variable(int i) const;
 
 
    double lBound(int i) const { return (*lBound_)[i]; }
 
 
    void lBound(int i, double l);
 
 
    double uBound(int i) const { return (*uBound_)[i]; }
 
 
    void uBound(int i, double u);
 
 
    FSVarStat *fsVarStat(int i) const { return (*fsVarStat_)[i]; }
 
 
    LPVARSTAT *lpVarStat(int i) const { return (*lpVarStat_)[i]; }
 
 
    double xVal(int i) const { return xVal_[i]; }
 
 
    double yVal(int i) const { return yVal_[i]; }
 
 
    bool ancestor(const Sub *sub) const;
 
    Master *master() { return master_; }
 
    const Master *master() const { return master_; }
 
 
    void removeVars(ArrayBuffer<int> &remove);
 
 
    void removeVar(int i) { removeVarBuffer_->push(i); }
 
    double nnzReserve() const { return nnzReserve_; }
 
    bool relativeReserve() const { return relativeReserve_; }
 
    BranchRule *branchRule() const { return branchRule_; }
 
 
    bool objAllInteger() const;
 
 
    virtual void removeCons(ArrayBuffer<int> &remove);
 
 
    virtual void removeCon(int i);
 
 
    int addConBufferSpace() const;
 
 
    int addVarBufferSpace() const;
 
    int nDormantRounds() const { return nDormantRounds_; }
 
 
    void ignoreInTailingOff();
 
 
    virtual int addBranchingConstraint(PoolSlot<Constraint, Variable> *slot);
 
protected:
 
 
    virtual int addCons(ArrayBuffer<Constraint*> &constraints,
        Pool<Constraint, Variable> *pool = nullptr,
        ArrayBuffer<bool> *keepInPool = nullptr,
        ArrayBuffer<double> *rank = nullptr);
 
 
    virtual int addCons(
        ArrayBuffer<PoolSlot<Constraint, Variable>*> &newCons);
 
 
    virtual int addVars(ArrayBuffer<Variable*> &variables,
        Pool<Variable, Constraint> *pool = nullptr,
        ArrayBuffer<bool> *keepInPool = nullptr,
        ArrayBuffer<double> *rank = nullptr);
 
 
    virtual int addVars(
        ArrayBuffer<PoolSlot<Variable, Constraint>*> &newVars);
 
 
    virtual int variablePoolSeparation(
        int ranking = 0,
        Pool<Variable, Constraint> *pool = nullptr,
        double minViolation = 0.001);
 
 
    virtual int constraintPoolSeparation(
        int ranking = 0,
        Pool<Constraint, Variable> *pool = nullptr,
        double minViolation = 0.001);
 
 
    virtual void activate() { }
 
 
    virtual void deactivate () { }
 
 
    virtual int generateBranchRules(ArrayBuffer<BranchRule*> &rules) {
        return branchingOnVariable(rules);
    }
 
 
    virtual int branchingOnVariable(ArrayBuffer<BranchRule*> &rules);
 
 
    virtual int selectBranchingVariable(int &variable);
 
 
    virtual int selectBranchingVariableCandidates(ArrayBuffer<int> &candidates);
 
 
    virtual int selectBestBranchingSample(int nSamples,
        ArrayBuffer<BranchRule*> **samples);
 
 
    virtual void rankBranchingSample(ArrayBuffer<BranchRule*> &sample,
        Array<double> &rank);
 
 
    virtual double rankBranchingRule(BranchRule *branchRule);
 
 
    double lpRankBranchingRule(BranchRule *branchRule, int iterLimit = -1);
 
 
    virtual int compareBranchingSampleRanks(Array<double> &rank1,
        Array<double> &rank2);
 
 
    int closeHalfExpensive(int &branchVar, VarType::TYPE branchVarType);
 
    /***
     * Those variables with fractional part close to \f$0.5\f$ and high absolute objective function
     * coefficient are selected..
     *
     * \param variables     Holds the numbers of possible branching variables if
     *                      at least one is found. We try to find as many
     *                      candidates as fit into this buffer. We abort
     *                      the function with a fatal error if the size
     *                      of the buffer is 0.
     * \param branchVarType The type of the branching variable can be restricted either
     *                      to VarType::Binary or VarType::Integer.
     *
     * \return 0 If at least one branching variable is found, 1 otherwise.
     */
    int closeHalfExpensive(ArrayBuffer<int> &variables,
        VarType::TYPE branchVarType);
 
 
    int closeHalf(int &branchVar, VarType::TYPE branchVarType);
 
 
    int closeHalf(ArrayBuffer<int> &branchVar, VarType::TYPE branchVarType);
 
 
    int findNonFixedSet(ArrayBuffer<int> &branchVar,
        VarType::TYPE branchVarType);
 
 
    int findNonFixedSet(int &branchVar, VarType::TYPE branchVarType);
 
 
    virtual int initMakeFeas(
        ArrayBuffer<InfeasCon*> &infeasCon,
        ArrayBuffer<Variable*> &newVars,
        Pool<Variable, Constraint> **pool)
    {
        return 1;
    }
 
 
    virtual int makeFeasible() { return 1; }
 
    virtual bool goodCol(Column &col, Array<double> &row,
        double x, double lb, double ub);
 
 
    virtual void setByLogImp(ArrayBuffer<int> &variable,
        ArrayBuffer<FSVarStat*> &status) { }
 
 
    virtual bool feasible() = 0;
 
 
    bool integerFeasible();
 
 
    virtual bool primalSeparation();
 
 
    virtual int separate();
 
 
    virtual void conEliminate(ArrayBuffer<int> &remove);
 
 
    virtual void nonBindingConEliminate(ArrayBuffer<int> &remove);
 
 
    virtual void basicConEliminate(ArrayBuffer<int> &remove);
 
 
    virtual void varEliminate(ArrayBuffer<int> &remove);
 
 
    void redCostVarEliminate(ArrayBuffer<int> &remove);
 
 
    virtual int pricing() { return 0; }
 
 
    virtual int improve(double &primalValue);
 
 
    virtual Sub *generateSon(BranchRule *rule) = 0;
 
    bool boundCrash()    const;
 
    virtual bool pausing() { return false; }
 
    bool infeasible();
 
 
    virtual void varRealloc(int newSize);
 
 
    virtual void conRealloc(int newSize);
 
 
    virtual LP::METHOD chooseLpMethod(int nVarRemoved, int nConRemoved,
        int nVarAdded, int nConAdded);
 
 
    virtual bool tailingOff() { return true; }
 
    bool betterDual(double x) const;
 
 
    virtual void selectVars() { }
 
 
    virtual void selectCons() { }
 
 
    virtual int fixByRedCost(bool &newValues, bool saveCand);
 
    /***
     * The default implementation of \a fixByLogImp() does nothing. This
     * function has to be redefined if variables should be fixed by logical
     * implications in derived classes.
     *
     * \param variables The variables which should be fixed.
     * \param status    The statuses these variables should be fixed to.
     */
    virtual void fixByLogImp(ArrayBuffer<int> &variables,
        ArrayBuffer<FSVarStat*> &status) { }
 
 
    virtual int fixAndSet(bool &newValues);
 
 
    virtual int fixing(bool &newValues, bool saveCand = false);
 
 
    virtual int setting(bool &newValues);
 
 
    virtual int setByRedCost();
 
 
    virtual void fathom(bool reoptimize);
 
 
    virtual bool fixAndSetTime() { return true; }
 
 
    virtual int fix(int i, FSVarStat *newStat, bool &newValue);
 
 
    virtual int set(int i, FSVarStat *newStat, bool &newValue);
 
 
    virtual int set(int i, FSVarStat::STATUS newStat, bool &newValue);
 
 
    virtual int set(int i, FSVarStat::STATUS newStat, double value,
        bool &newValue);
 
    virtual double dualRound(double x);
 
 
    virtual double guarantee() const;
 
    virtual bool guaranteed() const;
 
    virtual bool removeNonLiftableCons();
 
 
    virtual int prepareBranching(bool &lastIteration);
 
 
    virtual void fathomTheSubTree();
 
 
    virtual int optimize();
 
 
    virtual void reoptimize();
 
 
    virtual void initializeVars(int maxVar);
 
 
    virtual void initializeCons(int maxCon);
 
 
    virtual PHASE branching();
 
 
    virtual PHASE fathoming();
 
 
    virtual PHASE cutting();
 
 
    virtual LpSub *generateLp();
 
 
    virtual int initializeLp();
 
 
    virtual int solveLp();
 
 
    virtual bool exceptionFathom() { return false; }
 
 
    virtual bool exceptionBranch() { return false; }
 
    virtual bool solveApproxNow() { return false; }
 
 
    Master *master_;
 
    Active<Constraint, Variable> *actCon_;
 
    Active<Variable, Constraint> *actVar_;
 
    Sub *father_;
 
    LpSub *lp_;
 
 
    Array<FSVarStat*> *fsVarStat_;
 
    Array<LPVARSTAT*> *lpVarStat_;
 
    Array<double> *lBound_;
 
    Array<double> *uBound_;
 
    Array<SlackStat*> *slackStat_;
 
    TailOff *tailOff_;
 
    double dualBound_;
 
    int nIter_;
 
    int lastIterConAdd_;
 
    int lastIterVarAdd_;
 
    BranchRule *branchRule_;
 
    bool allBranchOnSetVars_;
 
    LP::METHOD lpMethod_;
 
    CutBuffer<Variable, Constraint> *addVarBuffer_;
 
    CutBuffer<Constraint, Variable> *addConBuffer_;
 
    ArrayBuffer<int> *removeVarBuffer_;
 
    ArrayBuffer<int> *removeConBuffer_;
 
    double *xVal_;
 
    double *yVal_;
 
    double *bInvRow_;
 
    int infeasCon_;
 
    int infeasVar_;
 
    bool genNonLiftCons_;
 
private:
 
    virtual int _separate();
 
 
    virtual int _conEliminate();
 
 
    virtual int _varEliminate();
 
    virtual int _pricing(bool &newValues, bool doFixSet = true);
 
 
    virtual int _improve(double &primalValue);
 
 
    virtual int _fixByLogImp(bool &newValues);
 
 
    virtual void updateBoundInLp(int i);
 
    virtual double fixSetNewBound(int i);
 
 
    virtual void newDormantRound() { ++nDormantRounds_; }
 
 
    virtual PHASE _activate();
 
 
    virtual void _deactivate();
 
 
    virtual int _initMakeFeas();
 
    virtual int _makeFeasible();
 
 
    virtual int _setByLogImp(bool &newValues);
 
 
    virtual void infeasibleSub();
 
    virtual void getBase();
 
 
    virtual void activateVars(ArrayBuffer<PoolSlot<Variable, Constraint>*> &newVars);
 
 
    virtual void addVarsToLp(ArrayBuffer<PoolSlot<Variable, Constraint>*> &newVars,
        ArrayBuffer<FSVarStat*> *localStatus = nullptr);
 
 
    virtual void _selectVars(ArrayBuffer<PoolSlot<Variable, Constraint>*> &newVars);
 
    virtual void _selectCons(ArrayBuffer<PoolSlot<Constraint, Variable>*> &newCons);
 
    virtual int _removeVars(ArrayBuffer<int> &remove);
 
    virtual int _removeCons(ArrayBuffer<int> &remove);
 
    bool _atUpperBound(int i);
 
    bool _atLowerBound(int i);
 
 
    int level_;
 
    int id_;
 
    STATUS status_;
 
    ArrayBuffer<Sub*> *sons_;
 
    int maxIterations_;
 
    int nOpt_;
 
    bool relativeReserve_;
 
    double varReserve_;
 
    double conReserve_;
 
    double nnzReserve_;
 
    int nDormantRounds_;
 
 
    bool activated_;
 
 
    bool ignoreInTailingOff_;
 
    LP::METHOD lastLP_;
 
    ogdf::StopwatchCPU localTimer_;
 
    bool forceExactSolver_;
 
    Sub(const Sub &rhs);
    const Sub &operator=(const Sub &rhs);
};
 
}
#pragma GCC visibility pop
 
// NOW declaration of sub is complete. its definitions below need full declarations of the below types...
 
#include <ogdf/lib/abacus/variable.h>
#include <ogdf/lib/abacus/constraint.h>
#include <ogdf/lib/abacus/active.h>
#include <ogdf/lib/abacus/cutbuffer.h>
#include <ogdf/lib/abacus/lpsub.h>
 
#pragma GCC visibility push(default)
namespace abacus {
 
inline int Sub::addBranchingConstraint(PoolSlot<Constraint, Variable> *slot)
{
    return addConBuffer_->insert(slot, true);
}
 
inline int Sub::addConBufferSpace() const
{
    return addConBuffer_->space();
}
 
inline int Sub::addVarBufferSpace() const
{
    return addVarBuffer_->space();
}
 
inline int Sub::nVar() const
{
    return actVar_->number();
}
 
inline int Sub::nCon() const
{
    return actCon_->number();
}
 
inline int Sub::maxVar() const
{
    return actVar_->max();
}
 
inline int Sub::maxCon() const
{
    return actCon_->max();
}
 
inline Constraint *Sub::constraint(int i) const
{
    return (*actCon_)[i];
}
 
inline Variable *Sub::variable(int i) const
{
    return (*actVar_)[i];
}
 
inline double Sub::rankBranchingRule(BranchRule *branchRule)
{
    return lpRankBranchingRule(branchRule, master_->nStrongBranchingIterations());
}
 
inline double Sub::lowerBound() const
{
    if (master_->optSense()->max())
        return master_->primalBound();
    else
        return dualBound_;
}
 
inline double Sub::upperBound() const
{
    if (master_->optSense()->min())
        return master_->primalBound();
    else
        return dualBound_;
}
 
inline bool Sub::betterDual(double x) const
{
    if (master_->optSense()->max())
        return x < dualBound_ ? true : false;
    else
        return x > dualBound_ ? true : false;
}
 
inline bool Sub::boundCrash() const
{
    return(master_->primalViolated(dualBound_));
}
 
inline void Sub::removeCon(int i)
{
    removeConBuffer_->push(i);
}
 
inline void Sub::lBound(int i, double l)
{
    (*lBound_)[i] = l;
    if (lp_)
        lp_->changeLBound(i, l);
}
 
inline void Sub::uBound(int i, double u)
{
    (*uBound_)[i] = u;
    if (lp_)
        lp_->changeUBound(i, u);
}
 
}
#pragma GCC visibility pop