AbcModel.h

Go to the documentation of this file.
00001 /*===========================================================================*
00002  * This file is part of the Abstract Library for Parallel Search (ALPS).     *
00003  *                                                                           *
00004  * ALPS is distributed under the Eclipse Public License as part of the       *
00005  * COIN-OR repository (http://www.coin-or.org).                              *
00006  *                                                                           *
00007  * Authors:                                                                  *
00008  *                                                                           *
00009  *          Yan Xu, Lehigh University                                        *
00010  *          Ted Ralphs, Lehigh University                                    *
00011  *                                                                           *
00012  * Conceptual Design:                                                        *
00013  *                                                                           *
00014  *          Yan Xu, Lehigh University                                        *
00015  *          Ted Ralphs, Lehigh University                                    *
00016  *          Laszlo Ladanyi, IBM T.J. Watson Research Center                  *
00017  *          Matthew Saltzman, Clemson University                             *
00018  *                                                                           * 
00019  *                                                                           *
00020  * Copyright (C) 2001-2013, Lehigh University, Yan Xu, and Ted Ralphs.       *
00021  *===========================================================================*/
00022 
00023 #ifndef AbcModel_h_
00024 #define AbcModel_h_
00025 
00026 //#############################################################################
00027 // This file is modified from SbbModel.hpp
00028 //#############################################################################
00029 
00030 #include <cmath>
00031 
00032 #include "CoinMessageHandler.hpp"
00033 #include "CoinWarmStartBasis.hpp"
00034 #include "OsiCuts.hpp"
00035 #include "OsiSolverInterface.hpp"
00036 
00037 #include "AbcBranchActual.h"
00038 #include "AbcCutGenerator.h"
00039 #include "AbcHeuristic.h"
00040 #include "AbcMessage.h"
00041 #include "AlpsModel.h"
00042 
00043 #include "AbcParams.h"
00044 
00045 class CglCutGenerator;
00046 
00047 class AbcBranchDecision;
00048 class AlpsTreeNode;
00049 class AbcNodeDesc;
00050 class AbcTreeNode;
00051 
00052 //#############################################################################
00053 
00055 class AbcModel : public AlpsModel {
00056     
00057  public:
00058     enum AbcIntParam {
00060     AbcMaxNumNode=0,
00062     AbcMaxNumSol,
00070     AbcFathomDiscipline,
00072     AbcLastIntParam
00073     };
00074 
00075     enum AbcDblParam {
00078     AbcIntegerTolerance = 0,
00081     AbcInfeasibilityWeight,
00084     AbcCutoffIncrement,
00091     AbcAllowableGap,
00094     AbcMaximumSeconds,
00096     AbcLastDblParam
00097     };
00098     
00099  private:
00103 
00104 
00105     int numberRowsAtContinuous_;
00107     int numberIntegers_;
00109     int* integerVariable_;
00111     CoinWarmStartBasis* sharedBasis_;
00113 
00115     CoinMessageHandler * handler_;
00116 
00121     bool defaultHandler_;
00122 
00124     CoinMessages messages_;
00125 
00127     int intParam_[AbcLastIntParam];
00128 
00130     double dblParam_[AbcLastDblParam];
00131 
00133     OsiSolverInterface* solver_;
00134     
00139     bool ourSolver_;
00140 
00142     OsiSolverInterface * continuousSolver_;
00143     
00145     CoinWarmStartBasis* basis_;
00146 
00148     CoinWarmStartBasis* lastws_;
00149 
00151     double minimumDrop_;
00152 
00154     double bestObjective_;
00155     
00157     double * bestSolution_;
00158 
00162     double * currentSolution_;
00163 
00165     OsiCuts globalCuts_;
00166     
00168     int numberNodes_;
00170     int numberIterations_;
00172     int status_;
00174     int currentNumberCuts_;
00176     int maximumNumberCuts_;
00178     int howOftenGlobalScan_;
00179 
00184     int maximumDepth_;
00185 
00190     int numberStrong_;
00192     int numberCutGenerators_;
00193     // Cut generators
00194     AbcCutGenerator ** generator_;
00196     int numberHeuristics_;
00197     // Heuristic solvers
00198     AbcHeuristic ** heuristic_;
00199 
00201     int maximumCutPassesAtRoot_;
00203     int maximumCutPasses_;
00204 
00206     AbcBranchDecision * branchingMethod_;
00208     int numberSolutions_;  
00210     int numberHeuristicSolutions_;
00212     int * priority_;
00214     AbcPseudocost **pseudoList_;
00216     int *pseudoIndices_;
00217 
00219     AbcParams *AbcPar_;
00220     
00221  public:
00222     AbcModel() 
00223     {
00224         init();
00225     }
00226     
00227     AbcModel(const OsiSolverInterface &rhs)
00228     {   
00229         init();
00230         solver_ = rhs.clone();
00231         ourSolver_ = true ;
00232         continuousSolver_ = 0;
00233         int numberColumns = solver_->getNumCols();
00234         int iColumn;
00235         if (numberColumns) {
00236         // Space for current solution
00237         currentSolution_ = new double[numberColumns];
00238         for (iColumn = 0; iColumn < numberColumns; ++iColumn) {
00239             if( solver_->isInteger(iColumn)) 
00240             numberIntegers_++;
00241         }
00242         } else {
00243         // empty model
00244         currentSolution_=NULL;
00245         }
00246         if (numberIntegers_) {
00247         integerVariable_ = new int [numberIntegers_];
00248         numberIntegers_=0;
00249         for (iColumn=0;iColumn<numberColumns;iColumn++) {
00250             if( solver_->isInteger(iColumn)) 
00251             integerVariable_[numberIntegers_++]=iColumn;
00252         }
00253         } else {
00254         integerVariable_ = NULL;
00255         }
00256     }
00257    
00258     ~AbcModel() 
00259     {
00260         if ( handler_ != 0){
00261         delete handler_;
00262         handler_ = 0;
00263         }
00264         if (priority_ != 0) {
00265         delete [] priority_;
00266         priority_ = 0;
00267         }
00268         if (currentSolution_ != 0) {
00269         delete [] currentSolution_;
00270         currentSolution_ = 0;
00271         }
00272         if (bestSolution_ != 0) {
00273         delete [] bestSolution_;
00274         bestSolution_ = 0;
00275         }
00276         if (generator_ != 0) {
00277         for (int i = 0; i < numberCutGenerators_; ++i)
00278             delete generator_[i];
00279         delete [] generator_;
00280         generator_ = 0;
00281         }
00282         if (heuristic_ != 0) {
00283         //for (int i = 0; i < numberHeuristics_; ++i) {
00284         //  if (heuristic_[i] != 0) {
00285         //delete heuristic_[i];
00286         //heuristic_[i] = 0;
00287         //  }
00288         //}
00289         delete [] heuristic_;
00290         heuristic_ = 0;
00291         }
00292 
00293         if (integerVariable_ != 0) {
00294         delete [] integerVariable_;
00295         integerVariable_ = 0;
00296         }
00297         if (sharedBasis_ != 0) {
00298         delete sharedBasis_;
00299         sharedBasis_ = 0;
00300         }
00301         if (basis_ != 0) {
00302         delete basis_;
00303         basis_ = 0;
00304         }
00305         if (pseudoList_ != NULL) {
00306                 int i = getNumCols() - 1;
00307         for (; i >= 0; --i) {
00308                     //printf("i = %d\n", i);
00309             delete pseudoList_[i];
00310         }
00311         delete [] pseudoList_;
00312         }
00313         if (pseudoIndices_ != NULL) {
00314         delete [] pseudoIndices_;
00315         }
00316         /* Last thing is to delete solver */
00317         if (ourSolver_) {
00318         delete solver_ ;
00319         solver_ = 0;
00320         }
00321         if (continuousSolver_ != 0) {
00322         delete continuousSolver_ ;
00323         continuousSolver_ = 0;
00324         }
00325         delete AbcPar_;
00326     }
00327     
00329     void init()
00330     {
00331         numberRowsAtContinuous_ = 0;
00332         numberIntegers_ = 0;
00333         integerVariable_ = NULL;
00334         sharedBasis_ = NULL;
00335         handler_ = new CoinMessageHandler();
00336         handler_->setLogLevel(2);
00337         defaultHandler_ = true;
00338         messages_ = AbcMessage();
00339         solver_ = NULL;
00340         ourSolver_ = false;
00341         basis_ = 0;
00342         minimumDrop_ = 1.0e-4;
00343         bestObjective_ = 1.0e100;
00344         bestSolution_ = 0;
00345         currentSolution_ = 0;
00346         numberNodes_ = 0;
00347         numberIterations_ = 0;
00348         status_ = 0;
00349         currentNumberCuts_ = 0;
00350         maximumNumberCuts_ = 1000;
00351         howOftenGlobalScan_ = 1;
00352         numberStrong_ = 0;
00353         numberCutGenerators_ =0;
00354         generator_ = NULL;
00355         numberHeuristics_ = 0;
00356         heuristic_ = NULL;
00357         maximumCutPassesAtRoot_ = 20;
00358         maximumCutPasses_ = 10;
00359         branchingMethod_ = NULL;
00360         numberSolutions_ = 0;
00361         numberHeuristicSolutions_ = 0;
00362         priority_ = NULL;
00363         pseudoList_ = NULL;
00364         pseudoIndices_ = NULL;
00365         
00366         continuousSolver_ = 0;
00367 
00368         // Set values for parameters
00369         intParam_[AbcMaxNumNode] = 9999999;
00370         intParam_[AbcMaxNumSol] = 9999999;
00371         intParam_[AbcFathomDiscipline] = 0;
00372         
00373         dblParam_[AbcIntegerTolerance] = 1e-6;
00374         dblParam_[AbcInfeasibilityWeight] = 0.0;
00375         dblParam_[AbcCutoffIncrement] = 1e-5;
00376         dblParam_[AbcAllowableGap] = 1.0e-10;
00377         dblParam_[AbcMaximumSeconds] = 1.0e100;
00378         AbcPar_ = new AbcParams;
00379     }
00380     
00382     virtual void readInstance(const char* dataFile) 
00383     {
00384         solver()->readMps(dataFile, "");
00385     }
00386 
00388     void readParameters(const int argnum, const char * const * arglist) {
00389     std::cout << "Reading in ALPS parameters ..." << std::endl;
00390         AlpsPar_->readFromArglist(argnum, arglist);
00391     std::cout << "Reading in ABC parameters ..." << std::endl;
00392         AbcPar_->readFromArglist(argnum, arglist);
00393     } 
00394     
00395     AbcParams *AbcPar() { return AbcPar_; }
00396     
00398     OsiSolverInterface * solver() const
00399     { return solver_; }
00400     
00405     void assignSolver(OsiSolverInterface *&solver);
00406 
00411     CoinWarmStartBasis *getEmptyBasis(int ns = 0, int na = 0) const;
00412 
00414     inline int numberIntegers() const
00415     { return numberIntegers_; }
00416     
00418     inline const int * integerVariable() const 
00419     { return integerVariable_; }
00420     
00421     //-------------------------------------------------------------------------
00423 
00424 
00427     void initialSolve(); 
00428 
00435     bool solveWithCuts( OsiCuts & cuts, int numberTries, 
00436             AbcTreeNode * node, int & numberOldActiveCuts, 
00437             int & numberNewCuts, int & maximumWhich, 
00438             int *& whichGenerator, const bool cutDuringRampup,
00439             int & found );
00440 
00444     bool resolve();
00446     
00447     //-------------------------------------------------------------------------
00449 
00450 
00451     bool isAbandoned() const;
00453     bool isProvenOptimal() const;
00455     bool isProvenInfeasible() const;
00457     bool isNodeLimitReached() const;
00459     bool isSolutionLimitReached() const;
00461     int getIterationCount() const
00462     { return solver_->getIterationCount(); }
00464     int getNodeCount() const
00465     { return numberNodes_; }
00467     void incrementNodeCount(int s = 1) 
00468     { numberNodes_ += s; }
00469     
00473     inline int status() const
00474     { return status_; }
00476 
00477     //-------------------------------------------------------------------------
00490 
00491     int numberRowsAtContinuous() const
00492     { return numberRowsAtContinuous_; }
00493 
00494     void setNumberRowsAtContinous(const int value)
00495     {
00496         numberRowsAtContinuous_ = value;
00497     }
00498     
00499     
00501     int getNumCols() const
00502     { return solver_->getNumCols(); }
00503     
00505     int getNumRows() const
00506     { return solver_->getNumRows(); }
00507     
00509     int getNumElements() const
00510     { return solver_->getNumElements(); }
00511     
00513     const double * getColLower() const
00514     { return solver_->getColLower(); }
00515   
00517     const double * getColUpper() const
00518     { return solver_->getColUpper(); }
00519     
00529     const char * getRowSense() const
00530     { return solver_->getRowSense(); }
00531     
00540     const double * getRightHandSide() const
00541     { return solver_->getRightHandSide(); }
00542   
00551     const double * getRowRange() const
00552     { return solver_->getRowRange(); }
00553     
00555     const double * getRowLower() const
00556     { return solver_->getRowLower(); }
00557     
00559     const double * getRowUpper() const
00560     { return solver_->getRowUpper(); }
00561     
00563     const double * getObjCoefficients() const
00564     { return solver_->getObjCoefficients(); }
00565   
00567     double getObjSense() const
00568     { return solver_->getObjSense(); }
00570     AbcPseudocost ** getPseudoList() { return pseudoList_; }
00571     
00573     int *getPseudoIndices() { return pseudoIndices_; }
00574     
00576     bool isContinuous(int colIndex) const
00577     { return solver_->isContinuous(colIndex); }
00578     
00580     bool isBinary(int colIndex) const
00581     { return solver_->isBinary(colIndex); }
00582   
00587     bool isInteger(int colIndex) const
00588     { return solver_->isInteger(colIndex); }
00589     
00591     bool isIntegerNonBinary(int colIndex) const
00592     { return solver_->isIntegerNonBinary(colIndex); }
00593   
00595     bool isFreeBinary(int colIndex) const
00596     { return solver_->isFreeBinary(colIndex); }
00597   
00599     const CoinPackedMatrix * getMatrixByRow() const
00600     { return solver_->getMatrixByRow(); }
00601     
00603     const CoinPackedMatrix * getMatrixByCol() const
00604     { return solver_->getMatrixByCol(); }
00605     
00607     double getInfinity() const
00608     { return solver_->getInfinity(); }
00610     
00618     double checkSolution(double cutoff, 
00619              const double * solution,
00620              bool fixVariables);
00621     
00623     bool setBestSolution(ABC_Message how,
00624              double & objectiveValue, 
00625              const double *solution,
00626              bool fixVariables = false);
00627 
00633     bool feasibleSolution(int & numberIntegerInfeasibilities);
00634 
00639     inline double * currentSolution() const
00640     { return currentSolution_; }
00641 
00643     const double * getColSolution() const
00644     { return solver_->getColSolution(); }
00645   
00647     const double * getRowPrice() const
00648     { return solver_->getRowPrice(); }
00649   
00651     const double * getReducedCost() const
00652     { return solver_->getReducedCost(); }
00653   
00655     const double * getRowActivity() const
00656     { return solver_->getRowActivity(); }
00657   
00659     double getCurrentObjValue() const
00660     { return solver_->getObjValue(); }
00661 
00663     double getObjValue() const
00664     { return bestObjective_; }
00665 
00668     void setObjValue(double obj) 
00669     { bestObjective_ = obj; }
00670   
00676     const double * bestSolution() const
00677     { return bestSolution_; }
00678   
00680     int getSolutionCount() const
00681     { return numberSolutions_; }
00682   
00684     void setSolutionCount(int value) 
00685     { numberSolutions_=value; }
00686 
00688     int getNumberHeuristicSolutions() const 
00689     { return numberHeuristicSolutions_; }
00690 
00692     void setObjSense(double s) { solver_->setObjSense(s); }
00693 
00696     inline void setMaximumCutPassesAtRoot(int value)
00697     {maximumCutPassesAtRoot_ = value; }
00699     inline int getMaximumCutPassesAtRoot() const
00700     { return maximumCutPassesAtRoot_; }
00701     
00704     inline void setMaximumCutPasses(int value)
00705     { maximumCutPasses_ = value; }
00707     inline int getMaximumCutPasses() const
00708     { return maximumCutPasses_; }
00710     int currentNumberCuts() const
00711     { return currentNumberCuts_; }
00712     void setCurrentNumberCuts(int value) 
00713     {
00714         currentNumberCuts_ += value;
00715     }
00716     
00718 
00719     //-------------------------------------------------------------------------
00720 
00726 
00727     inline AbcBranchDecision * branchingMethod() const
00728     { return branchingMethod_; }
00730     inline void setBranchingMethod(AbcBranchDecision * method)
00731     { branchingMethod_ = method; }
00735     inline void setBranchingMethod(AbcBranchDecision & method)
00736     { branchingMethod_ = &method; }
00738 
00739     //-------------------------------------------------------------------------
00740 
00743 
00744     void passInMessageHandler(CoinMessageHandler * handler)
00745     {
00746         if (defaultHandler_) {
00747         delete handler_;
00748         handler_ = NULL;
00749         }
00750         defaultHandler_ = false;
00751         handler_ = handler;
00752     }
00753     
00755     void newLanguage(CoinMessages::Language language) 
00756     { messages_ = AbcMessage(language); }
00757     void setLanguage(CoinMessages::Language language)
00758     { newLanguage(language); }
00760     CoinMessageHandler * messageHandler() const
00761     { return handler_; }
00763     CoinMessages messages() 
00764     { return messages_; }
00766     CoinMessages * messagesPointer() 
00767     { return &messages_; }
00769 
00770     //-------------------------------------------------------------------------
00771 
00772     bool checkInteger(double value) const
00773     {
00774         double integerTolerance =
00775         getDblParam(AbcModel::AbcIntegerTolerance);
00776         double nearest = floor(value + 0.5);
00777         if (fabs(value - nearest) <= integerTolerance) 
00778         return true;
00779         else 
00780         return false;
00781     }
00782 
00789     void findIntegers(bool startAgain);
00790 
00798     void addCutGenerator(CglCutGenerator * generator,
00799              int howOften=1, const char * name=NULL,
00800              bool normal=true, bool atSolution=false, 
00801              bool infeasible=false);
00804 
00805     void addHeuristic(AbcHeuristic * generator);
00807 
00812     void reducedCostFix() ;
00813 
00822     //void takeOffCuts(OsiCuts &cuts, int *whichGenerator,
00823 //           int &numberOldActiveCuts, int &numberNewCuts,
00824     //       bool allowResolve);
00825     void takeOffCuts();
00826 
00828     inline bool setIntParam(AbcIntParam key, int value) {
00829     intParam_[key] = value;
00830     return true;
00831     }
00832 
00834     inline bool setDblParam(AbcDblParam key, double value) {
00835     dblParam_[key] = value;
00836     return true;
00837     }
00838 
00840     inline int getIntParam(AbcIntParam key) const {
00841     return intParam_[key];
00842     }
00843 
00845     inline double getDblParam(AbcDblParam key) const {
00846     return dblParam_[key];
00847     }
00848 
00853     void setCutoff(double value);
00854 
00856     inline double getCutoff() const
00857     { 
00858         double value ;
00859         solver_->getDblParam(OsiDualObjectiveLimit, value) ;
00860         return value * solver_->getObjSense() ; 
00861     }
00862 
00864     inline bool setMaximumNodes( int value)
00865     { return setIntParam(AbcMaxNumNode,value); }
00866 
00868     inline int getMaximumNodes() const
00869     { return getIntParam(AbcMaxNumNode); }
00870 
00875     inline bool setMaximumSolutions( int value) {
00876     return setIntParam(AbcMaxNumSol,value);
00877     }
00882     inline int getMaximumSolutions() const {
00883     return getIntParam(AbcMaxNumSol);
00884     }
00885     
00889     inline bool setIntegerTolerance( double value) {
00890     return setDblParam(AbcIntegerTolerance,value);
00891     }
00895     inline double getIntegerTolerance() const {
00896     return getDblParam(AbcIntegerTolerance);
00897     }
00898 
00903     inline bool setInfeasibilityWeight( double value) {
00904     return setDblParam(AbcInfeasibilityWeight,value);
00905     }
00910     inline double getInfeasibilityWeight() const {
00911     return getDblParam(AbcInfeasibilityWeight);
00912     }
00913     
00917     inline bool setAllowableGap( double value) {
00918     return setDblParam(AbcAllowableGap,value);
00919     }
00923     inline double getAllowableGap() const {
00924     return getDblParam(AbcAllowableGap);
00925     }
00926 
00928     inline void setMinimumDrop(double value)
00929     { minimumDrop_=value; }
00931     inline double getMinimumDrop() const
00932     { return minimumDrop_; }
00933 
00934     //-------------------------------------------------------------------------
00935 
00937     virtual bool setupSelf();
00938 
00939     int numberStrong() const
00940     { return numberStrong_; }
00941     
00942     void setNumberStrong(int number)
00943     {
00944         if (number<0)
00945         numberStrong_=0;
00946         else
00947         numberStrong_=number;
00948     }
00949 
00951     inline const int * priority() const { return priority_;}
00952 
00954     inline int priority(int sequence) const
00955     { 
00956         if (priority_)
00957         return priority_[sequence];
00958         else
00959         return 1000;
00960     }
00961     
00963     virtual AlpsEncoded* encode() const;
00964   
00966     virtual void decodeToSelf(AlpsEncoded&);
00967     
00968 };
00969 
00970 //#############################################################################
00971 
00972 #endif

Generated on 12 Feb 2015 for Dip-All by  doxygen 1.6.1