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                                        *
 *          Aykut Bulut, 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-2019, Lehigh University, Yan Xu, Aykut Bulut, and      *
 *                          Ted Ralphs.                                      *
 * All Rights Reserved.                                                      *
 *===========================================================================*/
 
 
#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;
            }
        }
 
    virtual ~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 AlpsTreeNode * createRoot();
 
    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;
        }
 
  using AlpsKnowledge::encode;
  virtual AlpsReturnStatus encode(AlpsEncoded * encoded) const;
  virtual AlpsReturnStatus decodeToSelf(AlpsEncoded & encoded);
  virtual AlpsKnowledge * decode(AlpsEncoded & encoded) const;
 
private:
  AbcModel(AbcModel const &);
  AbcModel & operator=(AbcModel const &);
 
};
 
//#############################################################################
 
#endif