/usr/src/RPM/BUILD/CoinBlis-0.91.2/Blis/src/BlisModel.h
Go to the documentation of this file.
00001 /*===========================================================================*
00002  * This file is part of the BiCePS Linear Integer Solver (BLIS).             *
00003  *                                                                           *
00004  * BLIS 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-2010, Lehigh University, Yan Xu, and Ted Ralphs.       *
00021  * All Rights Reserved.                                                      *
00022  *===========================================================================*/
00023 
00024 //#############################################################################
00025 
00026 #ifndef BlisModel_h_
00027 #define BlisModel_h_
00028 
00029 //#############################################################################
00030 
00031 #include <vector>
00032 
00033 #include "CoinMpsIO.hpp"
00034 #include "CoinLpIO.hpp"
00035 #include "CoinPackedMatrix.hpp"
00036 
00037 #include "CglCutGenerator.hpp"
00038 
00039 #include "OsiCuts.hpp"
00040 #include "OsiSolverInterface.hpp"
00041 
00042 #include "AlpsEnumProcessT.h"
00043 #include "AlpsParams.h"
00044 #include "AlpsTreeNode.h"
00045 
00046 #include "BcpsBranchStrategy.h"
00047 #include "BcpsObject.h"
00048 #include "BcpsObjectPool.h"
00049 #include "BcpsModel.h"
00050 
00051 #include "Blis.h"
00052 #include "BlisConGenerator.h"
00053 #include "BlisHeuristic.h"
00054 #include "BlisMessage.h"
00055 #include "BlisParams.h"
00056 #include "BlisPseudo.h"
00057 #include "BlisPresolve.h"
00058 
00059 //#############################################################################
00060 
00061 class BlisConstraint;
00062 class BlisSolution;
00063 class BcpsVariable;
00064 class BlisVariable;
00065 
00066 //#############################################################################
00067 
00068 /* Declare a BLIS model */
00069 class BlisModel : public BcpsModel {
00070 
00071 protected:
00072     
00073     //------------------------------------------------------
00074     // LP SOLVER.
00075     //------------------------------------------------------
00076     
00078     OsiSolverInterface *origLpSolver_;
00080     OsiSolverInterface *presolvedLpSolver_;
00083     OsiSolverInterface *lpSolver_;
00084     
00085     //------------------------------------------------------
00086     // PROBLEM DATA. Populate when loadProblem(),
00087     //------------------------------------------------------
00088     
00090     CoinPackedMatrix *colMatrix_;    
00091 
00094     double *varLB_;
00095     double *varUB_;
00096     double *conLB_;
00097     double *conUB_;
00099 
00102     int numCols_;
00103     int numRows_;
00104     int numElems_;
00106 
00109     double objSense_;
00110     double *objCoef_;
00112 
00115     int numIntObjects_;
00116     int *intColIndices_;  // size of numIntObjects_
00118 
00121     std::vector<BcpsVariable *> inputVar_;
00122     std::vector<BcpsConstraint *> inputCon_;
00124 
00125     //------------------------------------------------------
00126     // PRESOLVE
00127     //------------------------------------------------------
00128 
00129     BlisPresolve *presolve_;
00130     // AT - Begin
00131     bool presolved;
00132     bool problemSetup;
00133     // AT - End
00134     
00135     //------------------------------------------------------
00136     // SOLUTION.
00137     //------------------------------------------------------
00138     
00139     int numSolutions_;
00140     int numHeurSolutions_;
00141 
00143     double incObjValue_;
00144 
00146     double *incumbent_;
00147 
00149     double cutoff_;
00150 
00152     double cutoffInc_;
00153     
00154     //------------------------------------------------------
00155     // SEARCHING.
00156     //------------------------------------------------------
00157 
00158     int *intObjIndices_; // size of numCols_
00159     char *colType_;
00160 
00163     double *startVarLB_;
00164     double *startVarUB_;
00165     double *startConLB_;
00166     double *startConUB_;
00168 
00170     BcpsBranchStrategy * branchStrategy_;
00171     BcpsBranchStrategy * rampUpBranchStrategy_;
00172 
00173     // Hotstart strategy 0 = off, 
00174     // 1 = branch if incorrect,
00175     // 2 = branch even if correct, ....
00176     BlisHotStartStrategy hotstartStrategy_;
00177     
00179     int numObjects_;
00180 
00182     BcpsObject **objects_;
00183 
00185     char *sharedObjectMark_;
00186 
00188     int *priority_;
00189 
00191     AlpsTreeNode *activeNode_;
00192 
00194     int numStrong_;
00195 
00196     // Not used. 
00197     double nodeWeight_;
00198 
00200     int numBranchResolve_;
00201     
00202     //------------------------------------------------------
00203     // HEURISTICS.
00204     //------------------------------------------------------
00205 
00207     int numHeuristics_;
00208 
00210     BlisHeuristic **heuristics_;
00211 
00212     //------------------------------------------------------
00213     // CONSTRAINTS.
00214     //------------------------------------------------------
00215 
00217     BlisCutStrategy cutStrategy_; 
00218     
00220     int cutGenerationFrequency_; 
00221     
00223     int numCutGenerators_;
00224     
00226     int maxNumCons_;
00227 
00229     BlisConGenerator **generators_;
00230 
00232     BcpsConstraintPool *constraintPool_;
00233     
00235     BlisConstraint **oldConstraints_;
00236     
00238     int oldConstraintsSize_;
00239     
00241     int numOldConstraints_;
00242 
00244     double *conRandoms_;
00245     
00247     int denseConCutoff_;
00248     
00249     //------------------------------------------------------
00250     // PARAMETERS, STATISTICS, and MESSAGE
00251     //------------------------------------------------------
00252 
00254     BlisParams *BlisPar_;
00255     
00257     CoinMessageHandler *blisMessageHandler_;
00258 
00260     CoinMessages blisMessages_;
00261 
00263     int numNodes_;
00264     
00266     int numIterations_;
00267 
00269     int aveIterations_;
00270     
00271     //------------------------------------------------------
00272     // TEMPORARY STORAGE
00273     //------------------------------------------------------
00274     
00277     int *tempVarLBPos_;
00278     int *tempVarUBPos_;
00279     int *tempConLBPos_;
00280     int *tempConUBPos_;
00282 
00283     //------------------------------------------------------
00284     // Knowledge shared
00285     //------------------------------------------------------
00286 
00288     BcpsConstraintPool *constraintPoolSend_;
00289     
00291     BcpsConstraintPool *constraintPoolReceive_;
00292 
00293  public:
00294 
00296     bool isRoot_;
00297 
00299     int boundingPass_;
00300 
00302     double integerTol_;
00303 
00305     double optimalRelGap_;
00306 
00308     double optimalAbsGap_;
00309 
00311     double currRelGap_;
00312 
00314     double currAbsGap_;
00315 
00317     BlisHeurStrategy heurStrategy_;
00318     
00320     int heurCallFrequency_;
00321     
00323     OsiCuts newCutPool_;
00324     
00326     std::vector<AlpsTreeNode *> leafToRootPath;    
00327 
00328  protected:
00329 
00331     void init();
00332 
00334     void createObjects();
00335     
00336  public:
00337 
00339     BlisModel() 
00340     { 
00341         init();
00342     }
00343 
00345     virtual ~BlisModel();
00346     
00348     void gutsOfDestructor();
00349     
00350     //------------------------------------------------------
00351     // SETUP, LP SOLVER
00352     //------------------------------------------------------
00353 
00355     void setColMatrix(CoinPackedMatrix *mat){ colMatrix_ = mat; }
00356     
00358     void setNumCons(int num){ numRows_ = num; }
00359     
00361     void setNumVars(int num){ numCols_ = num; }
00362     
00364     void setNumElems(int num){ numElems_ = num; }
00365     
00367     void setConLb(double *cl){ conLB_ = cl; }
00368     
00370     void setConUb(double *cu){ conUB_ = cu; }
00371     
00373     void setVarLb(double *lb){ varLB_ = lb; }
00374     
00376     void setVarUb(double *ub){ varUB_ = ub; }
00377     
00379     void setColType(char *colType){
00380         colType_ = colType;
00381     }
00382     
00384     void setObjCoef(double *obj){ objCoef_ = obj; }
00385     
00395     virtual void readInstance(const char* dataFile);
00396 
00408     virtual void importModel(std::vector<BlisVariable *> vars,
00409                              std::vector<BlisConstraint *> cons);
00410     
00412     virtual void readParameters(const int argnum, const char * const *arglist);
00413 
00415     virtual void writeParameters(std::ostream& outstream) const;
00416 
00420     virtual AlpsTreeNode * createRoot();
00421     
00431     virtual bool setupSelf();
00432 
00434     virtual void preprocess();
00435 
00437     virtual void postprocess();
00438     
00440     virtual void setSolver(OsiSolverInterface *si) { origLpSolver_ = si; }
00441     
00443     virtual OsiSolverInterface *getSolver() { return origLpSolver_; }
00444 
00446     virtual OsiSolverInterface *solver() { return lpSolver_; }
00447 
00449     bool resolve();
00450 
00452     void setActiveNode(AlpsTreeNode *node) { activeNode_ = node; }
00453 
00455     void setSolEstimate(double est) { activeNode_->setSolEstimate(est); }
00456     
00458     int getNumStrong() { return numStrong_; }
00459     
00461     void addNumStrong(int num=1) { numStrong_ += num; }
00462 
00464     int getNumBranchResolve() { return numBranchResolve_; }
00465     
00467     void setNumBranchResolve(int num) { numBranchResolve_ = num; }
00468 
00469     //------------------------------------------------------
00470     // PROBLEM DATA
00471     //------------------------------------------------------
00472 
00474     double* getObjCoef() const { return objCoef_; }
00475 
00477     const double * getColLower() { return lpSolver_->getColLower(); }
00478 
00480     const double * getColUpper() { return lpSolver_->getColUpper(); }
00481 
00483     int getNumCols() { return lpSolver_->getNumCols(); }
00484 
00486     int getNumRows() { return lpSolver_->getNumRows(); }
00487 
00489     double *varLB() { return varLB_; }
00490     double *varUB() { return varUB_; }
00491 
00493     double *conLB() { return conLB_; }
00494     double *conUB() { return conUB_; }
00495 
00497     double *startVarLB() { return startVarLB_; }
00498     double *startVarUB() { return startVarUB_; }
00499 
00501     double *startConLB() { return startConLB_; }
00502     double *startConUB() { return startConUB_; }
00503 
00505     int *tempVarLBPos() { return tempVarLBPos_; }
00506     int *tempVarUBPos() { return tempVarUBPos_; }
00507     int *tempConLBPos() { return tempConLBPos_; }
00508     int *tempConUBPos() { return tempConUBPos_; }
00509 
00510     //------------------------------------------------------
00511     // LP SOLUTION
00512     //------------------------------------------------------
00513 
00515     double getLpObjValue() const { return lpSolver_->getObjValue(); }
00516 
00518     const double * getLpSolution() const { return lpSolver_->getColSolution();}
00519     
00520     //------------------------------------------------------
00521     // MILP SOLUTION
00522     //------------------------------------------------------
00523 
00525     int getNumSolutions() const { return numSolutions_; }
00526     
00528     int getNumHeurSolutions() const { return numHeurSolutions_;}  
00529     
00531     double * incumbent() { return incumbent_; }
00532     
00534     int storeSolution(BlisSolutionType how, BlisSolution* sol);
00535     
00537     inline double getCutoff() const { return cutoff_;  }
00538 
00540     inline void setCutoff(double co) { 
00541         double inc = BlisPar_->entry(BlisParams::cutoffInc);        
00542 #if 0
00543         std::cout << "3. cutoff_ = "<< cutoff_ 
00544                   << "; inc = " << inc << std::endl;
00545 #endif
00546         co += inc;
00547         if (co < cutoff_) {
00548             cutoff_ = co;
00549             lpSolver_->setDblParam(OsiDualObjectiveLimit, co);
00550         }
00551     }
00552 
00554     BlisSolution *feasibleSolutionHeur(const double *solution);
00555 
00560     virtual BlisSolution *feasibleSolution(int & numIntegerInfs, 
00561                                            int & numObjectInfs);
00562     
00571     virtual BlisSolution *userFeasibleSolution(const double * solution, 
00572                                                bool &feasible) { 
00573         BlisSolution *sol = NULL;
00574         feasible = true; // Feasible by default
00575         return sol; 
00576     }
00577     
00578     //------------------------------------------------------
00579     // BRANCHING
00580     //------------------------------------------------------
00581 
00587     inline BcpsBranchStrategy * branchStrategy() const
00588         { return branchStrategy_; }
00589 
00591     inline void setBranchingMethod(BcpsBranchStrategy * method) {
00592         if (branchStrategy_) delete branchStrategy_;
00593         branchStrategy_ = method; 
00594     }
00595 
00597     inline void setBranchingMethod(BcpsBranchStrategy & method) { 
00598         if (branchStrategy_) delete branchStrategy_;
00599         branchStrategy_ = &method;
00600     }
00601     inline BcpsBranchStrategy * rampUpBranchStrategy() const
00602         { return rampUpBranchStrategy_; }
00604 
00609     inline int numObjects() const { return numObjects_; }
00610 
00612     inline void setNumObjects(int num) { numObjects_ = num; }
00613 
00615     inline BcpsObject ** objects() { return objects_;}
00616 
00618     inline BcpsObject * objects(int which) { return objects_[which]; }
00619 
00621     void setSharedObjectMark(int i) { sharedObjectMark_[i] = 1; }
00622     
00624     void clearSharedObjectMark() {
00625         for (int k = 0; k < numIntObjects_; ++k) {
00626             sharedObjectMark_[k] = 0;
00627         }
00628     }
00629     
00631     void deleteObjects();
00632 
00635     void addObjects(int numObjects, BcpsObject ** objects);
00637 
00639     void createIntgerObjects(bool startAgain);
00640 
00642     int* getIntObjIndices() const { return intObjIndices_; }
00643 
00645     int getNumIntObjects() const { return numIntObjects_; }
00646 
00648     int* getIntColIndices() const { return intColIndices_; }
00649 
00651     bool checkInteger(double value) const {
00652         double integerTolerance = 1.0e-5;
00653         double nearest = floor(value + 0.5);
00654         if (fabs(value - nearest) <= integerTolerance) {
00655             return true;
00656         }
00657         else {
00658             return false;
00659         }
00660     }
00661 
00662     void analyzeObjective();
00663     
00664     //------------------------------------------------------
00665     // HEURISTICS.
00666     //------------------------------------------------------
00667 
00669     void addHeuristic(BlisHeuristic * heur);
00670     
00672     BlisHeuristic * heuristics(int i) const { return heuristics_[i]; }
00673 
00675     int numHeuristics() const { return numHeuristics_; }
00676 
00677     //------------------------------------------------------
00678     // CONSTRAINTS.
00679     //------------------------------------------------------
00680 
00682     void addCutGenerator(BlisConGenerator * generator);
00683 
00685     void addCutGenerator(CglCutGenerator * generator,
00686                          const char * name = NULL,
00687                          BlisCutStrategy strategy = BlisCutStrategyAuto,
00688                          int cutGenerationFrequency = 1,
00689                          bool normal = true, 
00690                          bool atSolution = false,
00691                          bool whenInfeasible = false);
00692     
00694     BlisConGenerator *cutGenerators(int i) const { return generators_[i]; }
00695 
00697     int numCutGenerators() const { return numCutGenerators_; }
00698 
00700     int getMaxNumCons() const { return maxNumCons_; }
00701 
00703     void setMaxNumCons(int m) { maxNumCons_ = m; }
00704 
00706     BcpsConstraintPool *constraintPool() { return constraintPool_; }
00707 
00709     BcpsConstraintPool *constraintPoolReceive() 
00710         { return constraintPoolReceive_; }
00711     
00713     BcpsConstraintPool *constraintPoolSend() { return constraintPoolSend_; }
00714     
00716 
00717     int getNumOldConstraints() const { return numOldConstraints_; }
00718 
00720     void setNumOldConstraints(int num) { numOldConstraints_ = num; }
00721     
00723     int getOldConstraintsSize() const { return oldConstraintsSize_; }
00724     
00726     void setOldConstraintsSize(int num) { oldConstraintsSize_ = num; }
00727 
00729     BlisConstraint **oldConstraints() { return oldConstraints_; }
00730     
00732     void setOldConstraints(BlisConstraint **old) { oldConstraints_ = old; }
00733 
00735     void delOldConstraints() {
00736         delete [] oldConstraints_; 
00737         oldConstraints_ = NULL; 
00738     }
00740     
00742     BlisCutStrategy getCutStrategy() const {
00743         return cutStrategy_; 
00744     }
00745 
00747     void setCutStrategy(BlisCutStrategy u) { cutStrategy_ = u; }
00748 
00750     int getCutGenerationFrequency() const { return cutGenerationFrequency_; }
00751 
00753     void setCutStrategy(int f) { cutGenerationFrequency_ = f; }
00754 
00756     int getDenseConCutoff() const { return denseConCutoff_; }
00757 
00759     void setDenseConCutoff(int cutoff) { denseConCutoff_ = cutoff; }
00760     
00762     double *getConRandoms() const { return conRandoms_; }
00763     
00764     //------------------------------------------------------
00765     // PRIORITY AND WEITGHT.
00766     //------------------------------------------------------
00767 
00782     void passInPriorities(const int * priorities, 
00783                           bool ifNotSimpleIntegers,
00784                           int defaultValue = 1000);
00785     
00787     inline const int * priority() const { return priority_; }
00788     
00790     inline int priority(int sequence) const { 
00791         if (priority_) return priority_[sequence];
00792         else return 1000;
00793     }
00794     
00795     inline double getNodeWeight() const { return nodeWeight_; }
00796 
00797     inline void setNodeWeight(double nw) { nodeWeight_ = nw; }
00799 
00800     //------------------------------------------------------
00801     // STATISTICS.
00802     //------------------------------------------------------
00803 
00805     virtual void modelLog();
00806     
00808     int getNumNodes() const { return numNodes_; }
00809 
00811     int getNumIterations() const { return numIterations_; }
00812 
00814     int getAveIterations() const { return aveIterations_; }
00815 
00817     void addNumNodes(int newNodes = 1) { numNodes_ += newNodes; }
00818 
00820     void addNumIterations(int newIter) {
00821         numIterations_ += newIter; 
00822         aveIterations_ = numIterations_ / numNodes_;
00823     }
00824 
00826     CoinMessageHandler * blisMessageHandler() const 
00827     { return blisMessageHandler_; }
00828     
00830     CoinMessages blisMessages() { return blisMessages_; }
00831     
00834     BlisParams * BlisPar() { return BlisPar_; }
00836 
00838     virtual void nodeLog(AlpsTreeNode *node, bool force);
00839 
00841     virtual bool fathomAllNodes();
00842 
00843     //------------------------------------------------------
00844     // PARALLEL
00845     //------------------------------------------------------
00846 
00847  protected:
00848     
00850     AlpsReturnStatus encodeBlis(AlpsEncoded *encoded) const;
00851 
00853     AlpsReturnStatus decodeBlis(AlpsEncoded &encoded);  
00854 
00856     void packSharedPseudocost(AlpsEncoded *encoded, int numToShare);
00857 
00859     void unpackSharedPseudocost(AlpsEncoded &encoded);
00860     
00862     void packSharedConstraints(AlpsEncoded *encoded);
00863 
00865     void unpackSharedConstraints(AlpsEncoded &encoded);
00866  
00868     void packSharedVariables(AlpsEncoded *encoded);
00869 
00871     void unpackSharedVariables(AlpsEncoded &encoded);  
00872 
00873  public:
00874 
00877     virtual void registerKnowledge();  
00878 
00879     using AlpsKnowledge::encode ;
00881     virtual AlpsEncoded* encode() const;
00882     
00884     virtual void decodeToSelf(AlpsEncoded&);
00885     
00888     virtual AlpsEncoded* packSharedKnowlege();
00889     
00891     virtual void unpackSharedKnowledge(AlpsEncoded&);
00892 
00893     //AT - Begin
00894     virtual void presolveForTheWholeTree();
00895     //AT - end
00896 };
00897 
00898 #endif /* End of file */