sub.h

Go to the documentation of this file.

#ifndef ABA_SUB_H
#define ABA_SUB_H
#include <limits.h>

#include "abacus/string.h"
#include "abacus/list.h"
#include "abacus/bstack.h"
#include "abacus/lp.h"
#include "abacus/fsvarstat.h"
#include "abacus/buffer.h"
#include "abacus/vartype.h"
#include "abacus/cputimer.h"

class ABA_LPSUB;
class ABA_TAILOFF;
class ABA_BRANCHRULE;
class ABA_LPVARSTAT;
class ABA_VARIABLE;
class ABA_MASTER;
class ABA_INFEASCON;
class ABA_CONSTRAINT;
template<class BaseType, class CoType> class ABA_CUTBUFFER;
template<class BaseType, class CoType> class ABA_ACTIVE;
template<class BaseType, class CoType> class ABA_POOL;
template<class BaseType, class CoType> class ABA_POOLSLOT;
template<class BaseType, class CoType> class ABA_LPSOLUTION;

#ifdef ABACUS_PARALLEL
#include "abacus/message.h"
#include "abacus/id.h"
#include "abacus/subserver.h"
#endif

  class  ABA_SUB :  public ABA_ABACUSROOT  {
    friend class ABA_MASTER;
    friend class ABA_BOUNDBRANCHRULE;
    friend class ABA_OPENSUB;
    friend class ABA_LPSOLUTION<ABA_CONSTRAINT, ABA_VARIABLE>;
    friend class ABA_LPSOLUTION<ABA_VARIABLE, ABA_CONSTRAINT>;
#ifdef ABACUS_PARALLEL
    friend class ABA_SUBSERVER;
#endif
    public:

      enum STATUS {Unprocessed, Active, Dormant, Processed, Fathomed};

      enum PHASE {Done, Cutting, Branching, Fathoming};

      ABA_SUB(
          ABA_MASTER *master, 
          double conRes, 
          double varRes, 
          double nnzRes,
          bool relativeRes = true,
          ABA_BUFFER<ABA_POOLSLOT<ABA_CONSTRAINT, ABA_VARIABLE> *> *constraints = 0,
          ABA_BUFFER<ABA_POOLSLOT<ABA_VARIABLE, ABA_CONSTRAINT> *> *variables = 0);

      ABA_SUB(ABA_MASTER *master, ABA_SUB *father, ABA_BRANCHRULE *branchRule);

      virtual ~ABA_SUB();
#ifdef ABACUS_PARALLEL

      ABA_SUB(ABA_MASTER *master, ABA_MESSAGE &msg);

      virtual void pack(ABA_MESSAGE &msg) const;
#endif

      inline bool forceExactSolver() const;
      
      int level() const;

      int id() const;
#ifdef ABACUS_PARALLEL
      int fatherId() const;
#endif

      STATUS status() const;

      int nVar() const;

      int maxVar() const;

      int nCon() const;

      int maxCon() const;

      double lowerBound() const;

      double upperBound() const;

      double dualBound() const;

      void dualBound(double x);

      const ABA_SUB *father() const;

      ABA_LPSUB *lp() const;

      void maxIterations(int max);

      ABA_ACTIVE<ABA_CONSTRAINT, ABA_VARIABLE> *actCon() const;

      ABA_ACTIVE<ABA_VARIABLE, ABA_CONSTRAINT> *actVar() const;

      ABA_CONSTRAINT *constraint(int i) const;

      ABA_SLACKSTAT *slackStat(int i) const;

      ABA_VARIABLE *variable(int i) const;

      double lBound(int i) const;

      void lBound(int i, double l);

      double uBound(int i) const;

      void uBound(int i, double u);

      ABA_FSVARSTAT *fsVarStat(int i) const;

      ABA_LPVARSTAT *lpVarStat(int i) const;

      double xVal(int i) const;

      double yVal(int i) const;

      bool ancestor(const ABA_SUB *sub) const;
      ABA_MASTER *master() const;

      void removeVars(ABA_BUFFER<int> &remove);

      void removeVar(int i);

      double nnzReserve() const;

      bool relativeReserve() const;

      ABA_BRANCHRULE *branchRule() const;

      bool objAllInteger();

      virtual void removeCons(ABA_BUFFER<int> &remove);

      virtual void removeCon(int i);

      int addConBufferSpace() const;

      int addVarBufferSpace() const;

      int nDormantRounds() const;

      void ignoreInTailingOff();

      virtual int addBranchingConstraint(
                            ABA_POOLSLOT<ABA_CONSTRAINT, ABA_VARIABLE> *slot);

    protected:

      virtual int addCons(ABA_BUFFER<ABA_CONSTRAINT*> &constraints,
                  ABA_POOL<ABA_CONSTRAINT, ABA_VARIABLE> *pool = 0,
                  ABA_BUFFER<bool> *keepInPool = 0,
                  ABA_BUFFER<double> *rank = 0);

      virtual int addCons(
                   ABA_BUFFER<ABA_POOLSLOT<ABA_CONSTRAINT, ABA_VARIABLE>*> &newCons);

      virtual int addVars(ABA_BUFFER<ABA_VARIABLE*> &variables,
                          ABA_POOL<ABA_VARIABLE, ABA_CONSTRAINT> *pool = 0,
                          ABA_BUFFER<bool> *keepInPool = 0,
                          ABA_BUFFER<double> *rank = 0);

      virtual int addVars(
                    ABA_BUFFER<ABA_POOLSLOT<ABA_VARIABLE, ABA_CONSTRAINT>*> &newVars);

      virtual int variablePoolSeparation(
                              int ranking = 0,
                              ABA_POOL<ABA_VARIABLE, ABA_CONSTRAINT> *pool = 0,
                              double minViolation = 0.001);

      virtual int constraintPoolSeparation(
                              int ranking = 0,
                              ABA_POOL<ABA_CONSTRAINT, ABA_VARIABLE> *pool = 0,
                              double minViolation = 0.001);

      virtual void activate();

      virtual void deactivate ();

      virtual int generateBranchRules(ABA_BUFFER<ABA_BRANCHRULE*> &rules);

      virtual int branchingOnVariable(ABA_BUFFER<ABA_BRANCHRULE*> &rules);

      virtual int selectBranchingVariable(int &variable);

      virtual int selectBranchingVariableCandidates(ABA_BUFFER<int> &candidates);

      virtual int selectBestBranchingSample(int nSamples,
                                            ABA_BUFFER<ABA_BRANCHRULE*> **samples);

      virtual void rankBranchingSample(ABA_BUFFER<ABA_BRANCHRULE*> &sample,
                                       ABA_ARRAY<double> &rank);

      virtual double rankBranchingRule(ABA_BRANCHRULE *branchRule);

      double lpRankBranchingRule(ABA_BRANCHRULE *branchRule, int iterLimit = -1);

      virtual int compareBranchingSampleRanks(ABA_ARRAY<double> &rank1,
                                              ABA_ARRAY<double> &rank2);

      int closeHalfExpensive(int &branchVar, ABA_VARTYPE::TYPE branchVarType);

      int closeHalfExpensive(ABA_BUFFER<int> &variables, 
                             ABA_VARTYPE::TYPE branchVarType);

      int closeHalf(int &branchVar, ABA_VARTYPE::TYPE branchVarType);

      int closeHalf(ABA_BUFFER<int> &branchVar, ABA_VARTYPE::TYPE branchVarType);

      int findNonFixedSet(ABA_BUFFER<int> &branchVar, 
                          ABA_VARTYPE::TYPE branchVarType);

      int findNonFixedSet(int &branchVar, ABA_VARTYPE::TYPE branchVarType);

      virtual int initMakeFeas(ABA_BUFFER<ABA_INFEASCON*> &infeasCon,
                               ABA_BUFFER<ABA_VARIABLE*> &newVars,
                               ABA_POOL<ABA_VARIABLE, ABA_CONSTRAINT> **pool);

      virtual int makeFeasible();

      virtual bool goodCol(ABA_COLUMN &col, ABA_ARRAY<double> &row,
                           double x, double lb, double ub);

      virtual void setByLogImp(ABA_BUFFER<int> &variable, 
                               ABA_BUFFER<ABA_FSVARSTAT*> &status);

      virtual bool feasible() = 0;

      bool integerFeasible();

      virtual bool primalSeparation();

      virtual int separate();

      virtual void conEliminate(ABA_BUFFER<int> &remove);

      virtual void nonBindingConEliminate(ABA_BUFFER<int> &remove);

      virtual void basicConEliminate(ABA_BUFFER<int> &remove);

      virtual void varEliminate(ABA_BUFFER<int> &remove);

      void redCostVarEliminate(ABA_BUFFER<int> &remove);

      virtual int pricing();

      virtual int improve(double &primalValue);

      virtual ABA_SUB *generateSon(ABA_BRANCHRULE *rule) = 0;

      bool boundCrash()    const;

      virtual bool pausing();

      bool infeasible();

      virtual void varRealloc(int newSize);

      virtual void conRealloc(int newSize);

      virtual ABA_LP::METHOD chooseLpMethod(int nVarRemoved, int nConRemoved,
                                            int nVarAdded, int nConAdded);

      virtual bool tailingOff();

      bool betterDual(double x) const;

      virtual void selectVars();

      virtual void selectCons();

      virtual int fixByRedCost(bool &newValues, bool saveCand);

      virtual void fixByLogImp(ABA_BUFFER<int> &variable, 
                               ABA_BUFFER<ABA_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();

      virtual int fix(int i, ABA_FSVARSTAT *newStat, bool &newValue);

      virtual int set(int i, ABA_FSVARSTAT *newStat, bool &newValue);

       virtual int set(int i, ABA_FSVARSTAT::STATUS newStat, bool &newValue);

      virtual int set(int i, ABA_FSVARSTAT::STATUS newStat, double value,
                      bool &newValue);

      virtual double dualRound(double x);

      virtual double guarantee();

      virtual bool guaranteed();

      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 ABA_LPSUB *generateLp();

      virtual int initializeLp();

      virtual int solveLp();

      virtual bool exceptionFathom();

      virtual bool exceptionBranch();

      virtual bool solveApproxNow();

      ABA_MASTER *master_;

      ABA_ACTIVE<ABA_CONSTRAINT, ABA_VARIABLE> *actCon_;

      ABA_ACTIVE<ABA_VARIABLE, ABA_CONSTRAINT> *actVar_;

      ABA_SUB *father_;

      ABA_LPSUB *lp_;

      ABA_ARRAY<ABA_FSVARSTAT*> *fsVarStat_;

      ABA_ARRAY<ABA_LPVARSTAT*> *lpVarStat_;

      ABA_ARRAY<double> *lBound_;

      ABA_ARRAY<double> *uBound_;

      ABA_ARRAY<ABA_SLACKSTAT*> *slackStat_;

      ABA_TAILOFF *tailOff_;

      double dualBound_;

      int nIter_;

      int lastIterConAdd_;

      int lastIterVarAdd_;

      ABA_BRANCHRULE *branchRule_;

      bool allBranchOnSetVars_;

      ABA_LP::METHOD lpMethod_;

      ABA_CUTBUFFER<ABA_VARIABLE, ABA_CONSTRAINT> *addVarBuffer_;

      ABA_CUTBUFFER<ABA_CONSTRAINT, ABA_VARIABLE> *addConBuffer_;

      ABA_BUFFER<int> *removeVarBuffer_;

      ABA_BUFFER<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();

      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(ABA_BUFFER<ABA_POOLSLOT<ABA_VARIABLE, ABA_CONSTRAINT>*> &newVars);

      virtual void addVarsToLp(ABA_BUFFER<ABA_POOLSLOT<ABA_VARIABLE, ABA_CONSTRAINT>*> &newVars,
                              ABA_BUFFER<ABA_FSVARSTAT*> *localStatus = 0);

      virtual void _selectVars(ABA_BUFFER<ABA_POOLSLOT<ABA_VARIABLE, ABA_CONSTRAINT>*> &newVars);

      virtual void _selectCons(ABA_BUFFER<ABA_POOLSLOT<ABA_CONSTRAINT, ABA_VARIABLE>*> &newCons);

/* Removes the variables with numbers \a remove from the set of active variables.
 */
      virtual int _removeVars(ABA_BUFFER<int> &remove);

      virtual int _removeCons(ABA_BUFFER<int> &remove);

      int level_;

      int id_;
#ifdef ABACUS_PARALLEL
      int fatherId_;
#endif

      STATUS status_;

      ABA_BUFFER<ABA_SUB*> *sons_;

      int maxIterations_;

      int nOpt_;

      bool relativeReserve_;

      double varReserve_;

      double conReserve_;

      double nnzReserve_;

      int nDormantRounds_;

      bool activated_;

      bool ignoreInTailingOff_;
      ABA_LP::METHOD lastLP_;

      ABA_CPUTIMER localTimer_;

      bool forceExactSolver_;
 
      ABA_SUB(const ABA_SUB &rhs);
      const ABA_SUB &operator=(const ABA_SUB &rhs);
  };


#include "abacus/constraint.h"
#include "abacus/variable.h"
#include "abacus/active.h"
#include "abacus/lpsub.h"

inline double ABA_SUB::xVal(int i) const
  {
    return xVal_[i];
  }

inline double ABA_SUB::yVal(int i) const
  {
    return yVal_[i];
  }

inline ABA_MASTER *ABA_SUB::master() const
  {
    return master_;
  }

inline void ABA_SUB::removeVar(int i)
  {
    removeVarBuffer_->push(i);
  }

inline double ABA_SUB::nnzReserve() const
  {
    return nnzReserve_;
  }

inline bool ABA_SUB::relativeReserve() const
  {
    return relativeReserve_;
  }

inline ABA_BRANCHRULE *ABA_SUB::branchRule() const
  {
    return branchRule_;
  }

inline int ABA_SUB::addBranchingConstraint(ABA_POOLSLOT<ABA_CONSTRAINT, ABA_VARIABLE> *slot)
  {
    return addConBuffer_->insert(slot, true);
  }

inline int ABA_SUB::addConBufferSpace() const
  {
    return addConBuffer_->space();
  }

inline int ABA_SUB::addVarBufferSpace() const
  {
    return addVarBuffer_->space();
  }

inline int ABA_SUB::nDormantRounds() const
  {
    return nDormantRounds_;
  }

inline void ABA_SUB::newDormantRound()
  {
    ++nDormantRounds_;
  }

inline double ABA_SUB::lBound(int i) const
  {
    return (*lBound_)[i];
  }

inline void ABA_SUB::lBound(int i, double x)
  {
    (*lBound_)[i] = x;
    if (lp_)
      lp_->changeLBound(i, x);
  }

inline double ABA_SUB::uBound(int i) const
  {
    return (*uBound_)[i];
  }

inline void ABA_SUB::uBound(int i, double x)
  {
    (*uBound_)[i] = x;
    if (lp_)
      lp_->changeUBound(i, x);
  }

inline ABA_FSVARSTAT *ABA_SUB::fsVarStat(int i) const
  {
    return (*fsVarStat_)[i];
  }

inline ABA_LPVARSTAT *ABA_SUB::lpVarStat(int i) const
  {
    return (*lpVarStat_)[i];
  }

inline ABA_SLACKSTAT *ABA_SUB::slackStat(int i) const
  {
    return (*slackStat_)[i];
  }

inline bool ABA_SUB::forceExactSolver() const 
{
   return forceExactSolver_;
}

inline int ABA_SUB::level() const
  {
    return level_;
  }

inline int ABA_SUB::id() const
  {
    return id_;
  }

#ifdef ABACUS_PARALLEL
inline int ABA_SUB::fatherId() const
  {
    return fatherId_;
  }
#endif

inline double ABA_SUB::dualBound() const
  {
    return dualBound_;
  }

inline const ABA_SUB *ABA_SUB::father() const
  {
    return father_;
  }

inline ABA_LPSUB *ABA_SUB::lp() const
  {
    return lp_;
  }

inline ABA_SUB::STATUS ABA_SUB::status() const
  {
    return status_;
  }

inline ABA_ACTIVE<ABA_CONSTRAINT, ABA_VARIABLE> *ABA_SUB::actCon() const
  {
    return actCon_;
  }

inline ABA_ACTIVE<ABA_VARIABLE, ABA_CONSTRAINT> *ABA_SUB::actVar() const
  {
    return actVar_;
  }

inline int ABA_SUB::nVar() const
  {
    return actVar_->number();
  }

inline int ABA_SUB::nCon() const
  {
    return actCon_->number();
  }

inline int ABA_SUB::maxVar() const
  {
    return actVar_->max();
  }

inline int ABA_SUB::maxCon() const
  {
    return actCon_->max();
  }


#endif  // ABA_SUB_H

---