- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# /home/coin/SVN-release/Blis-0.91.2/Alps/examples/Abc/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 Common 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-2008, 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