00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #ifndef AbcModel_h_
00024 #define AbcModel_h_
00025
00026
00027
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
00194 AbcCutGenerator ** generator_;
00196 int numberHeuristics_;
00197
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
00237 currentSolution_ = new double[numberColumns];
00238 for (iColumn = 0; iColumn < numberColumns; ++iColumn) {
00239 if( solver_->isInteger(iColumn))
00240 numberIntegers_++;
00241 }
00242 } else {
00243
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
00284
00285
00286
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
00309 delete pseudoList_[i];
00310 }
00311 delete [] pseudoList_;
00312 }
00313 if (pseudoIndices_ != NULL) {
00314 delete [] pseudoIndices_;
00315 }
00316
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
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
00823
00824
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