BlisModel.h

Go to the documentation of this file.

/*===========================================================================*
 * This file is part of the BiCePS Linear Integer Solver (BLIS).             *
 *                                                                           *
 * BLIS is distributed under the Eclipse Public License as part of the       *
 * COIN-OR repository (http://www.coin-or.org).                              *
 *                                                                           *
 * Authors:                                                                  *
 *                                                                           *
 *          Yan Xu, Lehigh University                                        *
 *          Ted Ralphs, Lehigh University                                    *
 *                                                                           *
 * Conceptual Design:                                                        *
 *                                                                           *
 *          Yan Xu, Lehigh University                                        *
 *          Ted Ralphs, Lehigh University                                    *
 *          Laszlo Ladanyi, IBM T.J. Watson Research Center                  *
 *          Matthew Saltzman, Clemson University                             *
 *                                                                           * 
 *                                                                           *
 * Copyright (C) 2001-2013, Lehigh University, Yan Xu, and Ted Ralphs.       *
 * All Rights Reserved.                                                      *
 *===========================================================================*/

//#############################################################################

#ifndef BlisModel_h_
#define BlisModel_h_

//#############################################################################

#include <vector>

#include "CoinMpsIO.hpp"
#include "CoinLpIO.hpp"
#include "CoinPackedMatrix.hpp"

#include "CglCutGenerator.hpp"

#include "OsiCuts.hpp"
#include "OsiSolverInterface.hpp"

#include "AlpsEnumProcessT.h"
#include "AlpsParams.h"
#include "AlpsTreeNode.h"

#include "BcpsBranchStrategy.h"
#include "BcpsObject.h"
#include "BcpsObjectPool.h"
#include "BcpsModel.h"

#include "Blis.h"
#include "BlisConGenerator.h"
#include "BlisHeuristic.h"
#include "BlisMessage.h"
#include "BlisParams.h"
#include "BlisPseudo.h"
#include "BlisPresolve.h"

//#############################################################################

class BlisConstraint;
class BlisSolution;
class BcpsVariable;
class BlisVariable;

//#############################################################################

/* Declare a BLIS model */
class BlisModel : public BcpsModel {

protected:
    
    //------------------------------------------------------
    // LP SOLVER.
    //------------------------------------------------------
    
    OsiSolverInterface *origLpSolver_;
    OsiSolverInterface *presolvedLpSolver_;
    OsiSolverInterface *lpSolver_;
    
    //------------------------------------------------------
    // PROBLEM DATA. Populate when loadProblem(),
    //------------------------------------------------------
    
    CoinPackedMatrix *colMatrix_;    

    double *varLB_;
    double *varUB_;
    double *conLB_;
    double *conUB_;

    int numCols_;
    int numRows_;
    int numElems_;

    double objSense_;
    double *objCoef_;

    int numIntObjects_;
    int *intColIndices_;  // size of numIntObjects_

    std::vector<BcpsVariable *> inputVar_;
    std::vector<BcpsConstraint *> inputCon_;

    //------------------------------------------------------
    // PRESOLVE
    //------------------------------------------------------

    BlisPresolve *presolve_;
    // AT - Begin
    bool presolved;
    bool problemSetup;
    // AT - End
    
    //------------------------------------------------------
    // SOLUTION.
    //------------------------------------------------------
    
    int numSolutions_;
    int numHeurSolutions_;

    double incObjValue_;

    double *incumbent_;

    double cutoff_;

    double cutoffInc_;
    
    //------------------------------------------------------
    // SEARCHING.
    //------------------------------------------------------

    int *intObjIndices_; // size of numCols_
    char *colType_;

    double *startVarLB_;
    double *startVarUB_;
    double *startConLB_;
    double *startConUB_;

    BcpsBranchStrategy * branchStrategy_;
    BcpsBranchStrategy * rampUpBranchStrategy_;

    // Hotstart strategy 0 = off, 
    // 1 = branch if incorrect,
    // 2 = branch even if correct, ....
    BlisHotStartStrategy hotstartStrategy_;
    
    int numObjects_;

    BcpsObject **objects_;

    char *sharedObjectMark_;

    int *priority_;

    AlpsTreeNode *activeNode_;

    int numStrong_;

    // Not used. 
    double nodeWeight_;

    int numBranchResolve_;
    
    //------------------------------------------------------
    // HEURISTICS.
    //------------------------------------------------------

    int numHeuristics_;

    BlisHeuristic **heuristics_;

    //------------------------------------------------------
    // CONSTRAINTS.
    //------------------------------------------------------

    BlisCutStrategy cutStrategy_; 
    
    int cutGenerationFrequency_; 
    
    int numCutGenerators_;
    
    int maxNumCons_;

    BlisConGenerator **generators_;

    BcpsConstraintPool *constraintPool_;
    
    BlisConstraint **oldConstraints_;
    
    int oldConstraintsSize_;
    
    int numOldConstraints_;

    double *conRandoms_;
    
    int denseConCutoff_;
    
    //------------------------------------------------------
    // PARAMETERS, STATISTICS, and MESSAGE
    //------------------------------------------------------

    BlisParams *BlisPar_;
    
    CoinMessageHandler *blisMessageHandler_;

    CoinMessages blisMessages_;

    int numNodes_;
    
    int numIterations_;

    int aveIterations_;
    
    //------------------------------------------------------
    // TEMPORARY STORAGE
    //------------------------------------------------------
    
    int *tempVarLBPos_;
    int *tempVarUBPos_;
    int *tempConLBPos_;
    int *tempConUBPos_;

    //------------------------------------------------------
    // Knowledge shared
    //------------------------------------------------------

    BcpsConstraintPool *constraintPoolSend_;
    
    BcpsConstraintPool *constraintPoolReceive_;

 public:

    bool isRoot_;

    int boundingPass_;

    double integerTol_;

    double optimalRelGap_;

    double optimalAbsGap_;

    double currRelGap_;

    double currAbsGap_;

    BlisHeurStrategy heurStrategy_;
    
    int heurCallFrequency_;
    
    OsiCuts newCutPool_;
    
    std::vector<AlpsTreeNode *> leafToRootPath;    

 protected:

    void init();

    void createObjects();
    
 public:

    BlisModel() 
    { 
        init();
    }

    virtual ~BlisModel();
    
    void gutsOfDestructor();
    
    //------------------------------------------------------
    // SETUP, LP SOLVER
    //------------------------------------------------------

    void setColMatrix(CoinPackedMatrix *mat){ colMatrix_ = mat; }
    
    void setNumCons(int num){ numRows_ = num; }
    
    void setNumVars(int num){ numCols_ = num; }
    
    void setNumElems(int num){ numElems_ = num; }
    
    void setConLb(double *cl){ conLB_ = cl; }
    
    void setConUb(double *cu){ conUB_ = cu; }
    
    void setVarLb(double *lb){ varLB_ = lb; }
    
    void setVarUb(double *ub){ varUB_ = ub; }
    
    void setColType(char *colType){
        colType_ = colType;
    }
    
    void setObjCoef(double *obj){ objCoef_ = obj; }
    
    virtual void readInstance(const char* dataFile);

    virtual void importModel(std::vector<BlisVariable *> vars,
                             std::vector<BlisConstraint *> cons);
    
    virtual void readParameters(const int argnum, const char * const *arglist);

    virtual void writeParameters(std::ostream& outstream) const;

    virtual AlpsTreeNode * createRoot();
    
    virtual bool setupSelf();

    virtual void preprocess();

    virtual void postprocess();
    
    virtual void setSolver(OsiSolverInterface *si) { origLpSolver_ = si; }
    
    virtual OsiSolverInterface *getSolver() { return origLpSolver_; }

    virtual OsiSolverInterface *solver() { return lpSolver_; }

    bool resolve();

    void setActiveNode(AlpsTreeNode *node) { activeNode_ = node; }

    void setSolEstimate(double est) { activeNode_->setSolEstimate(est); }
    
    int getNumStrong() { return numStrong_; }
    
    void addNumStrong(int num=1) { numStrong_ += num; }

    int getNumBranchResolve() { return numBranchResolve_; }
    
    void setNumBranchResolve(int num) { numBranchResolve_ = num; }

    //------------------------------------------------------
    // PROBLEM DATA
    //------------------------------------------------------

    double* getObjCoef() const { return objCoef_; }

    const double * getColLower() { return lpSolver_->getColLower(); }

    const double * getColUpper() { return lpSolver_->getColUpper(); }

    int getNumCols() { return lpSolver_->getNumCols(); }

    int getNumRows() { return lpSolver_->getNumRows(); }

    double *varLB() { return varLB_; }
    double *varUB() { return varUB_; }

    double *conLB() { return conLB_; }
    double *conUB() { return conUB_; }

    double *startVarLB() { return startVarLB_; }
    double *startVarUB() { return startVarUB_; }

    double *startConLB() { return startConLB_; }
    double *startConUB() { return startConUB_; }

    int *tempVarLBPos() { return tempVarLBPos_; }
    int *tempVarUBPos() { return tempVarUBPos_; }
    int *tempConLBPos() { return tempConLBPos_; }
    int *tempConUBPos() { return tempConUBPos_; }

    //------------------------------------------------------
    // LP SOLUTION
    //------------------------------------------------------

    double getLpObjValue() const { return lpSolver_->getObjValue(); }

    const double * getLpSolution() const { return lpSolver_->getColSolution();}
    
    //------------------------------------------------------
    // MILP SOLUTION
    //------------------------------------------------------

    int getNumSolutions() const { return numSolutions_; }
    
    int getNumHeurSolutions() const { return numHeurSolutions_;}  
    
    double * incumbent() { return incumbent_; }
    
    int storeSolution(BlisSolutionType how, BlisSolution* sol);
    
    inline double getCutoff() const { return cutoff_;  }

    inline void setCutoff(double co) { 
        double inc = BlisPar_->entry(BlisParams::cutoffInc);        
#if 0
        std::cout << "3. cutoff_ = "<< cutoff_ 
                  << "; inc = " << inc << std::endl;
#endif
        co += inc;
        if (co < cutoff_) {
            cutoff_ = co;
            lpSolver_->setDblParam(OsiDualObjectiveLimit, co);
        }
    }

    BlisSolution *feasibleSolutionHeur(const double *solution);

    virtual BlisSolution *feasibleSolution(int & numIntegerInfs, 
                                           int & numObjectInfs);
    
    virtual BlisSolution *userFeasibleSolution(const double * solution, 
                                               bool &feasible) { 
        BlisSolution *sol = NULL;
        feasible = true; // Feasible by default
        return sol; 
    }
    
    //------------------------------------------------------
    // BRANCHING
    //------------------------------------------------------

    inline BcpsBranchStrategy * branchStrategy() const
        { return branchStrategy_; }

    inline void setBranchingMethod(BcpsBranchStrategy * method) {
        if (branchStrategy_) delete branchStrategy_;
        branchStrategy_ = method; 
    }

    inline void setBranchingMethod(BcpsBranchStrategy & method) { 
        if (branchStrategy_) delete branchStrategy_;
        branchStrategy_ = &method;
    }
    inline BcpsBranchStrategy * rampUpBranchStrategy() const
        { return rampUpBranchStrategy_; }

    inline int numObjects() const { return numObjects_; }

    inline void setNumObjects(int num) { numObjects_ = num; }

    inline BcpsObject ** objects() { return objects_;}

    inline BcpsObject * objects(int which) { return objects_[which]; }

    void setSharedObjectMark(int i) { sharedObjectMark_[i] = 1; }
    
    void clearSharedObjectMark() {
        for (int k = 0; k < numIntObjects_; ++k) {
            sharedObjectMark_[k] = 0;
        }
    }
    
    void deleteObjects();

    void addObjects(int numObjects, BcpsObject ** objects);

    void createIntgerObjects(bool startAgain);

    int* getIntObjIndices() const { return intObjIndices_; }

    int getNumIntObjects() const { return numIntObjects_; }

    int* getIntColIndices() const { return intColIndices_; }

    bool checkInteger(double value) const {
        double integerTolerance = 1.0e-5;
        double nearest = floor(value + 0.5);
        if (fabs(value - nearest) <= integerTolerance) {
            return true;
        }
        else {
            return false;
        }
    }

    void analyzeObjective();
    
    //------------------------------------------------------
    // HEURISTICS.
    //------------------------------------------------------

    void addHeuristic(BlisHeuristic * heur);
    
    BlisHeuristic * heuristics(int i) const { return heuristics_[i]; }

    int numHeuristics() const { return numHeuristics_; }

    //------------------------------------------------------
    // CONSTRAINTS.
    //------------------------------------------------------

    void addCutGenerator(BlisConGenerator * generator);

    void addCutGenerator(CglCutGenerator * generator,
                         const char * name = NULL,
                         BlisCutStrategy strategy = BlisCutStrategyAuto,
                         int cutGenerationFrequency = 1,
                         bool normal = true, 
                         bool atSolution = false,
                         bool whenInfeasible = false);
    
    BlisConGenerator *cutGenerators(int i) const { return generators_[i]; }

    int numCutGenerators() const { return numCutGenerators_; }

    int getMaxNumCons() const { return maxNumCons_; }

    void setMaxNumCons(int m) { maxNumCons_ = m; }

    BcpsConstraintPool *constraintPool() { return constraintPool_; }

    BcpsConstraintPool *constraintPoolReceive() 
        { return constraintPoolReceive_; }
    
    BcpsConstraintPool *constraintPoolSend() { return constraintPoolSend_; }
    

    int getNumOldConstraints() const { return numOldConstraints_; }

    void setNumOldConstraints(int num) { numOldConstraints_ = num; }
    
    int getOldConstraintsSize() const { return oldConstraintsSize_; }
    
    void setOldConstraintsSize(int num) { oldConstraintsSize_ = num; }

    BlisConstraint **oldConstraints() { return oldConstraints_; }
    
    void setOldConstraints(BlisConstraint **old) { oldConstraints_ = old; }

    void delOldConstraints() {
        delete [] oldConstraints_; 
        oldConstraints_ = NULL; 
    }
    
    BlisCutStrategy getCutStrategy() const {
        return cutStrategy_; 
    }

    void setCutStrategy(BlisCutStrategy u) { cutStrategy_ = u; }

    int getCutGenerationFrequency() const { return cutGenerationFrequency_; }

    void setCutStrategy(int f) { cutGenerationFrequency_ = f; }

    int getDenseConCutoff() const { return denseConCutoff_; }

    void setDenseConCutoff(int cutoff) { denseConCutoff_ = cutoff; }
    
    double *getConRandoms() const { return conRandoms_; }
    
    //------------------------------------------------------
    // PRIORITY AND WEITGHT.
    //------------------------------------------------------

    void passInPriorities(const int * priorities, 
                          bool ifNotSimpleIntegers,
                          int defaultValue = 1000);
    
    inline const int * priority() const { return priority_; }
    
    inline int priority(int sequence) const { 
        if (priority_) return priority_[sequence];
        else return 1000;
    }
    
    inline double getNodeWeight() const { return nodeWeight_; }

    inline void setNodeWeight(double nw) { nodeWeight_ = nw; }

    //------------------------------------------------------
    // STATISTICS.
    //------------------------------------------------------

    virtual void modelLog();
    
    int getNumNodes() const { return numNodes_; }

    int getNumIterations() const { return numIterations_; }

    int getAveIterations() const { return aveIterations_; }

    void addNumNodes(int newNodes = 1) { numNodes_ += newNodes; }

    void addNumIterations(int newIter) {
        numIterations_ += newIter; 
        aveIterations_ = numIterations_ / numNodes_;
    }

    CoinMessageHandler * blisMessageHandler() const 
    { return blisMessageHandler_; }
    
    CoinMessages blisMessages() { return blisMessages_; }
    
    BlisParams * BlisPar() { return BlisPar_; }

    virtual void nodeLog(AlpsTreeNode *node, bool force);

    virtual bool fathomAllNodes();

    //------------------------------------------------------
    // PARALLEL
    //------------------------------------------------------

 protected:
    
    AlpsReturnStatus encodeBlis(AlpsEncoded *encoded) const;

    AlpsReturnStatus decodeBlis(AlpsEncoded &encoded);  

    void packSharedPseudocost(AlpsEncoded *encoded, int numToShare);

    void unpackSharedPseudocost(AlpsEncoded &encoded);
    
    void packSharedConstraints(AlpsEncoded *encoded);

    void unpackSharedConstraints(AlpsEncoded &encoded);
 
    void packSharedVariables(AlpsEncoded *encoded);

    void unpackSharedVariables(AlpsEncoded &encoded);  

 public:

    virtual void registerKnowledge();  

    using AlpsKnowledge::encode ;
    virtual AlpsEncoded* encode() const;
    
    virtual void decodeToSelf(AlpsEncoded&);
    
    virtual AlpsEncoded* packSharedKnowlege();
    
    virtual void unpackSharedKnowledge(AlpsEncoded&);

    //AT - Begin
    virtual void presolveForTheWholeTree();
    //AT - end
};

#endif /* End of file */