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