AbcModel.h

Go to the documentation of this file.

/*===========================================================================*
 * This file is part of the Abstract Library for Parallel Search (ALPS).     *
 *                                                                           *
 * ALPS 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.       *
 *===========================================================================*/

#ifndef AbcModel_h_
#define AbcModel_h_

//#############################################################################
// This file is modified from SbbModel.hpp
//#############################################################################

#include <cmath>

#include "CoinMessageHandler.hpp"
#include "CoinWarmStartBasis.hpp"
#include "OsiCuts.hpp"
#include "OsiSolverInterface.hpp"

#include "AbcBranchActual.h"
#include "AbcCutGenerator.h"
#include "AbcHeuristic.h"
#include "AbcMessage.h"
#include "AlpsModel.h"

#include "AbcParams.h"

class CglCutGenerator;

class AbcBranchDecision;
class AlpsTreeNode;
class AbcNodeDesc;
class AbcTreeNode;

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

class AbcModel : public AlpsModel {
    
 public:
    enum AbcIntParam {
    AbcMaxNumNode=0,
    AbcMaxNumSol,
    AbcFathomDiscipline,
    AbcLastIntParam
    };

    enum AbcDblParam {
    AbcIntegerTolerance = 0,
    AbcInfeasibilityWeight,
    AbcCutoffIncrement,
    AbcAllowableGap,
    AbcMaximumSeconds,
    AbcLastDblParam
    };
    
 private:
    int numberRowsAtContinuous_;
    int numberIntegers_;
    int* integerVariable_;
    CoinWarmStartBasis* sharedBasis_;

    CoinMessageHandler * handler_;

    bool defaultHandler_;

    CoinMessages messages_;

    int intParam_[AbcLastIntParam];

    double dblParam_[AbcLastDblParam];

    OsiSolverInterface* solver_;
    
    bool ourSolver_;

    OsiSolverInterface * continuousSolver_;
    
    CoinWarmStartBasis* basis_;

    CoinWarmStartBasis* lastws_;

    double minimumDrop_;

    double bestObjective_;
    
    double * bestSolution_;

    double * currentSolution_;

    OsiCuts globalCuts_;
    
    int numberNodes_;
    int numberIterations_;
    int status_;
    int currentNumberCuts_;
    int maximumNumberCuts_;
    int howOftenGlobalScan_;

    int maximumDepth_;

    int numberStrong_;
    int numberCutGenerators_;
    // Cut generators
    AbcCutGenerator ** generator_;
    int numberHeuristics_;
    // Heuristic solvers
    AbcHeuristic ** heuristic_;

    int maximumCutPassesAtRoot_;
    int maximumCutPasses_;

    AbcBranchDecision * branchingMethod_;
    int numberSolutions_;  
    int numberHeuristicSolutions_;
    int * priority_;
    AbcPseudocost **pseudoList_;
    int *pseudoIndices_;

    AbcParams *AbcPar_;
    
 public:
    AbcModel() 
    {
        init();
    }
    
    AbcModel(const OsiSolverInterface &rhs)
    {   
        init();
        solver_ = rhs.clone();
        ourSolver_ = true ;
        continuousSolver_ = 0;
        int numberColumns = solver_->getNumCols();
        int iColumn;
        if (numberColumns) {
        // Space for current solution
        currentSolution_ = new double[numberColumns];
        for (iColumn = 0; iColumn < numberColumns; ++iColumn) {
            if( solver_->isInteger(iColumn)) 
            numberIntegers_++;
        }
        } else {
        // empty model
        currentSolution_=NULL;
        }
        if (numberIntegers_) {
        integerVariable_ = new int [numberIntegers_];
        numberIntegers_=0;
        for (iColumn=0;iColumn<numberColumns;iColumn++) {
            if( solver_->isInteger(iColumn)) 
            integerVariable_[numberIntegers_++]=iColumn;
        }
        } else {
        integerVariable_ = NULL;
        }
    }
   
    ~AbcModel() 
    {
        if ( handler_ != 0){
        delete handler_;
        handler_ = 0;
        }
        if (priority_ != 0) {
        delete [] priority_;
        priority_ = 0;
        }
        if (currentSolution_ != 0) {
        delete [] currentSolution_;
        currentSolution_ = 0;
        }
        if (bestSolution_ != 0) {
        delete [] bestSolution_;
        bestSolution_ = 0;
        }
        if (generator_ != 0) {
        for (int i = 0; i < numberCutGenerators_; ++i)
            delete generator_[i];
        delete [] generator_;
        generator_ = 0;
        }
        if (heuristic_ != 0) {
        //for (int i = 0; i < numberHeuristics_; ++i) {
        //  if (heuristic_[i] != 0) {
        //delete heuristic_[i];
        //heuristic_[i] = 0;
        //  }
        //}
        delete [] heuristic_;
        heuristic_ = 0;
        }

        if (integerVariable_ != 0) {
        delete [] integerVariable_;
        integerVariable_ = 0;
        }
        if (sharedBasis_ != 0) {
        delete sharedBasis_;
        sharedBasis_ = 0;
        }
        if (basis_ != 0) {
        delete basis_;
        basis_ = 0;
        }
        if (pseudoList_ != NULL) {
                int i = getNumCols() - 1;
        for (; i >= 0; --i) {
                    //printf("i = %d\n", i);
            delete pseudoList_[i];
        }
        delete [] pseudoList_;
        }
        if (pseudoIndices_ != NULL) {
        delete [] pseudoIndices_;
        }
        /* Last thing is to delete solver */
        if (ourSolver_) {
        delete solver_ ;
        solver_ = 0;
        }
        if (continuousSolver_ != 0) {
        delete continuousSolver_ ;
        continuousSolver_ = 0;
        }
        delete AbcPar_;
    }
    
    void init()
    {
        numberRowsAtContinuous_ = 0;
        numberIntegers_ = 0;
        integerVariable_ = NULL;
        sharedBasis_ = NULL;
        handler_ = new CoinMessageHandler();
        handler_->setLogLevel(2);
        defaultHandler_ = true;
        messages_ = AbcMessage();
        solver_ = NULL;
        ourSolver_ = false;
        basis_ = 0;
        minimumDrop_ = 1.0e-4;
        bestObjective_ = 1.0e100;
        bestSolution_ = 0;
        currentSolution_ = 0;
        numberNodes_ = 0;
        numberIterations_ = 0;
        status_ = 0;
        currentNumberCuts_ = 0;
        maximumNumberCuts_ = 1000;
        howOftenGlobalScan_ = 1;
        numberStrong_ = 0;
        numberCutGenerators_ =0;
        generator_ = NULL;
        numberHeuristics_ = 0;
        heuristic_ = NULL;
        maximumCutPassesAtRoot_ = 20;
        maximumCutPasses_ = 10;
        branchingMethod_ = NULL;
        numberSolutions_ = 0;
        numberHeuristicSolutions_ = 0;
        priority_ = NULL;
        pseudoList_ = NULL;
        pseudoIndices_ = NULL;
        
        continuousSolver_ = 0;

        // Set values for parameters
        intParam_[AbcMaxNumNode] = 9999999;
        intParam_[AbcMaxNumSol] = 9999999;
        intParam_[AbcFathomDiscipline] = 0;
        
        dblParam_[AbcIntegerTolerance] = 1e-6;
        dblParam_[AbcInfeasibilityWeight] = 0.0;
        dblParam_[AbcCutoffIncrement] = 1e-5;
        dblParam_[AbcAllowableGap] = 1.0e-10;
        dblParam_[AbcMaximumSeconds] = 1.0e100;
        AbcPar_ = new AbcParams;
    }
    
    virtual void readInstance(const char* dataFile) 
    {
        solver()->readMps(dataFile, "");
    }

    void readParameters(const int argnum, const char * const * arglist) {
    std::cout << "Reading in ALPS parameters ..." << std::endl;
        AlpsPar_->readFromArglist(argnum, arglist);
    std::cout << "Reading in ABC parameters ..." << std::endl;
        AbcPar_->readFromArglist(argnum, arglist);
    } 
    
    AbcParams *AbcPar() { return AbcPar_; }
    
    OsiSolverInterface * solver() const
    { return solver_; }
    
    void assignSolver(OsiSolverInterface *&solver);

    CoinWarmStartBasis *getEmptyBasis(int ns = 0, int na = 0) const;

    inline int numberIntegers() const
    { return numberIntegers_; }
    
    inline const int * integerVariable() const 
    { return integerVariable_; }
    
    //-------------------------------------------------------------------------


    void initialSolve(); 

    bool solveWithCuts( OsiCuts & cuts, int numberTries, 
            AbcTreeNode * node, int & numberOldActiveCuts, 
            int & numberNewCuts, int & maximumWhich, 
            int *& whichGenerator, const bool cutDuringRampup,
            int & found );

    bool resolve();
    
    //-------------------------------------------------------------------------

    bool isAbandoned() const;
    bool isProvenOptimal() const;
    bool isProvenInfeasible() const;
    bool isNodeLimitReached() const;
    bool isSolutionLimitReached() const;
    int getIterationCount() const
    { return solver_->getIterationCount(); }
    int getNodeCount() const
    { return numberNodes_; }
    void incrementNodeCount(int s = 1) 
    { numberNodes_ += s; }
    
    inline int status() const
    { return status_; }

    //-------------------------------------------------------------------------
    int numberRowsAtContinuous() const
    { return numberRowsAtContinuous_; }

    void setNumberRowsAtContinous(const int value)
    {
        numberRowsAtContinuous_ = value;
    }
    
    
    int getNumCols() const
    { return solver_->getNumCols(); }
    
    int getNumRows() const
    { return solver_->getNumRows(); }
    
    int getNumElements() const
    { return solver_->getNumElements(); }
    
    const double * getColLower() const
    { return solver_->getColLower(); }
  
    const double * getColUpper() const
    { return solver_->getColUpper(); }
    
    const char * getRowSense() const
    { return solver_->getRowSense(); }
    
    const double * getRightHandSide() const
    { return solver_->getRightHandSide(); }
  
    const double * getRowRange() const
    { return solver_->getRowRange(); }
    
    const double * getRowLower() const
    { return solver_->getRowLower(); }
    
    const double * getRowUpper() const
    { return solver_->getRowUpper(); }
    
    const double * getObjCoefficients() const
    { return solver_->getObjCoefficients(); }
  
    double getObjSense() const
    { return solver_->getObjSense(); }
    AbcPseudocost ** getPseudoList() { return pseudoList_; }
    
    int *getPseudoIndices() { return pseudoIndices_; }
    
    bool isContinuous(int colIndex) const
    { return solver_->isContinuous(colIndex); }
    
    bool isBinary(int colIndex) const
    { return solver_->isBinary(colIndex); }
  
    bool isInteger(int colIndex) const
    { return solver_->isInteger(colIndex); }
    
    bool isIntegerNonBinary(int colIndex) const
    { return solver_->isIntegerNonBinary(colIndex); }
  
    bool isFreeBinary(int colIndex) const
    { return solver_->isFreeBinary(colIndex); }
  
    const CoinPackedMatrix * getMatrixByRow() const
    { return solver_->getMatrixByRow(); }
    
    const CoinPackedMatrix * getMatrixByCol() const
    { return solver_->getMatrixByCol(); }
    
    double getInfinity() const
    { return solver_->getInfinity(); }
    
    double checkSolution(double cutoff, 
             const double * solution,
             bool fixVariables);
    
    bool setBestSolution(ABC_Message how,
             double & objectiveValue, 
             const double *solution,
             bool fixVariables = false);

    bool feasibleSolution(int & numberIntegerInfeasibilities);

    inline double * currentSolution() const
    { return currentSolution_; }

    const double * getColSolution() const
    { return solver_->getColSolution(); }
  
    const double * getRowPrice() const
    { return solver_->getRowPrice(); }
  
    const double * getReducedCost() const
    { return solver_->getReducedCost(); }
  
    const double * getRowActivity() const
    { return solver_->getRowActivity(); }
  
    double getCurrentObjValue() const
    { return solver_->getObjValue(); }

    double getObjValue() const
    { return bestObjective_; }

    void setObjValue(double obj) 
    { bestObjective_ = obj; }
  
    const double * bestSolution() const
    { return bestSolution_; }
  
    int getSolutionCount() const
    { return numberSolutions_; }
  
    void setSolutionCount(int value) 
    { numberSolutions_=value; }

    int getNumberHeuristicSolutions() const 
    { return numberHeuristicSolutions_; }

    void setObjSense(double s) { solver_->setObjSense(s); }

    inline void setMaximumCutPassesAtRoot(int value)
    {maximumCutPassesAtRoot_ = value; }
    inline int getMaximumCutPassesAtRoot() const
    { return maximumCutPassesAtRoot_; }
    
    inline void setMaximumCutPasses(int value)
    { maximumCutPasses_ = value; }
    inline int getMaximumCutPasses() const
    { return maximumCutPasses_; }
    int currentNumberCuts() const
    { return currentNumberCuts_; }
    void setCurrentNumberCuts(int value) 
    {
        currentNumberCuts_ += value;
    }
    

    //-------------------------------------------------------------------------

    inline AbcBranchDecision * branchingMethod() const
    { return branchingMethod_; }
    inline void setBranchingMethod(AbcBranchDecision * method)
    { branchingMethod_ = method; }
    inline void setBranchingMethod(AbcBranchDecision & method)
    { branchingMethod_ = &method; }

    //-------------------------------------------------------------------------

    void passInMessageHandler(CoinMessageHandler * handler)
    {
        if (defaultHandler_) {
        delete handler_;
        handler_ = NULL;
        }
        defaultHandler_ = false;
        handler_ = handler;
    }
    
    void newLanguage(CoinMessages::Language language) 
    { messages_ = AbcMessage(language); }
    void setLanguage(CoinMessages::Language language)
    { newLanguage(language); }
    CoinMessageHandler * messageHandler() const
    { return handler_; }
    CoinMessages messages() 
    { return messages_; }
    CoinMessages * messagesPointer() 
    { return &messages_; }

    //-------------------------------------------------------------------------

    bool checkInteger(double value) const
    {
        double integerTolerance =
        getDblParam(AbcModel::AbcIntegerTolerance);
        double nearest = floor(value + 0.5);
        if (fabs(value - nearest) <= integerTolerance) 
        return true;
        else 
        return false;
    }

    void findIntegers(bool startAgain);

    void addCutGenerator(CglCutGenerator * generator,
             int howOften=1, const char * name=NULL,
             bool normal=true, bool atSolution=false, 
             bool infeasible=false);
    void addHeuristic(AbcHeuristic * generator);

    void reducedCostFix() ;

    //void takeOffCuts(OsiCuts &cuts, int *whichGenerator,
//           int &numberOldActiveCuts, int &numberNewCuts,
    //       bool allowResolve);
    void takeOffCuts();

    inline bool setIntParam(AbcIntParam key, int value) {
    intParam_[key] = value;
    return true;
    }

    inline bool setDblParam(AbcDblParam key, double value) {
    dblParam_[key] = value;
    return true;
    }

    inline int getIntParam(AbcIntParam key) const {
    return intParam_[key];
    }

    inline double getDblParam(AbcDblParam key) const {
    return dblParam_[key];
    }

    void setCutoff(double value);

    inline double getCutoff() const
    { 
        double value ;
        solver_->getDblParam(OsiDualObjectiveLimit, value) ;
        return value * solver_->getObjSense() ; 
    }

    inline bool setMaximumNodes( int value)
    { return setIntParam(AbcMaxNumNode,value); }

    inline int getMaximumNodes() const
    { return getIntParam(AbcMaxNumNode); }

    inline bool setMaximumSolutions( int value) {
    return setIntParam(AbcMaxNumSol,value);
    }
    inline int getMaximumSolutions() const {
    return getIntParam(AbcMaxNumSol);
    }
    
    inline bool setIntegerTolerance( double value) {
    return setDblParam(AbcIntegerTolerance,value);
    }
    inline double getIntegerTolerance() const {
    return getDblParam(AbcIntegerTolerance);
    }

    inline bool setInfeasibilityWeight( double value) {
    return setDblParam(AbcInfeasibilityWeight,value);
    }
    inline double getInfeasibilityWeight() const {
    return getDblParam(AbcInfeasibilityWeight);
    }
    
    inline bool setAllowableGap( double value) {
    return setDblParam(AbcAllowableGap,value);
    }
    inline double getAllowableGap() const {
    return getDblParam(AbcAllowableGap);
    }

    inline void setMinimumDrop(double value)
    { minimumDrop_=value; }
    inline double getMinimumDrop() const
    { return minimumDrop_; }

    //-------------------------------------------------------------------------

    virtual bool setupSelf();

    int numberStrong() const
    { return numberStrong_; }
    
    void setNumberStrong(int number)
    {
        if (number<0)
        numberStrong_=0;
        else
        numberStrong_=number;
    }

    inline const int * priority() const { return priority_;}

    inline int priority(int sequence) const
    { 
        if (priority_)
        return priority_[sequence];
        else
        return 1000;
    }
    
    virtual AlpsEncoded* encode() const;
  
    virtual void decodeToSelf(AlpsEncoded&);
    
};

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

#endif