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

- File List
- File Members

# /home/coin/SVN-release/Blis-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 "CoinPackedMatrix.hpp"
    00035
    00036 #include "CglCutGenerator.hpp"
    00037
    00038 #include "OsiCuts.hpp"
    00039 #include "OsiSolverInterface.hpp"
    00040
    00041 #include "AlpsEnumProcessT.h"
    00042 #include "AlpsParams.h"
    00043 #include "AlpsTreeNode.h"
    00044
    00045 #include "BcpsBranchStrategy.h"
    00046 #include "BcpsObject.h"
    00047 #include "BcpsObjectPool.h"
    00048 #include "BcpsModel.h"
    00049
    00050 #include "Blis.h"
    00051 #include "BlisConGenerator.h"
    00052 #include "BlisHeuristic.h"
    00053 #include "BlisMessage.h"
    00054 #include "BlisParams.h"
    00055 #include "BlisPseudo.h"
    00056 #include "BlisPresolve.h"
    00057
    00058 //#############################################################################
    00059
    00060 class BlisConstraint;
    00061 class BlisSolution;
    00062 class BcpsVariable;
    00063 class BlisVariable;
    00064
    00065 //#############################################################################
    00066
    00067 /* Declare a BLIS model */
    00068 class BlisModel : public BcpsModel {
    00069
    00070 protected:
    00071
    00072     //------------------------------------------------------
    00073     // LP SOLVER.
    00074     //------------------------------------------------------
    00075
    00077     OsiSolverInterface *origLpSolver_;
    00079     OsiSolverInterface *presolvedLpSolver_;
    00082     OsiSolverInterface *lpSolver_;
    00083
    00084     //------------------------------------------------------
    00085     // PROBLEM DATA. Populate when loadProblem(),
    00086     //------------------------------------------------------
    00087
    00089     CoinPackedMatrix *colMatrix_;
    00090
    00093     double *varLB_;
    00094     double *varUB_;
    00095     double *conLB_;
    00096     double *conUB_;
    00098
    00101     int numCols_;
    00102     int numRows_;
    00103     int numElems_;
    00105
    00108     double objSense_;
    00109     double *objCoef_;
    00111
    00114     int numIntObjects_;
    00115     int *intColIndices_;  // size of numIntObjects_
    00117
    00120     std::vector<BcpsVariable *> inputVar_;
    00121     std::vector<BcpsConstraint *> inputCon_;
    00123
    00124     //------------------------------------------------------
    00125     // PRESOLVE
    00126     //------------------------------------------------------
    00127
    00128     BlisPresolve *presolve_;
    00129
    00130     //------------------------------------------------------
    00131     // SOLUTION.
    00132     //------------------------------------------------------
    00133
    00134     int numSolutions_;
    00135     int numHeurSolutions_;
    00136
    00138     double incObjValue_;
    00139
    00141     double *incumbent_;
    00142
    00144     double cutoff_;
    00145
    00147     double cutoffInc_;
    00148
    00149     //------------------------------------------------------
    00150     // SEARCHING.
    00151     //------------------------------------------------------
    00152
    00153     int *intObjIndices_; // size of numCols_
    00154     char *colType_;
    00155
    00158     double *startVarLB_;
    00159     double *startVarUB_;
    00160     double *startConLB_;
    00161     double *startConUB_;
    00163
    00165     BcpsBranchStrategy * branchStrategy_;
    00166     BcpsBranchStrategy * rampUpBranchStrategy_;
    00167
    00168     // Hotstart strategy 0 = off,
    00169     // 1 = branch if incorrect,
    00170     // 2 = branch even if correct, ....
    00171     BlisHotStartStrategy hotstartStrategy_;
    00172
    00174     int numObjects_;
    00175
    00177     BcpsObject **objects_;
    00178
    00180     char *sharedObjectMark_;
    00181
    00183     int *priority_;
    00184
    00186     AlpsTreeNode *activeNode_;
    00187
    00189     int numStrong_;
    00190
    00191     // Not used.
    00192     double nodeWeight_;
    00193
    00195     int numBranchResolve_;
    00196
    00197     //------------------------------------------------------
    00198     // HEURISTICS.
    00199     //------------------------------------------------------
    00200
    00202     int numHeuristics_;
    00203
    00205     BlisHeuristic **heuristics_;
    00206
    00207     //------------------------------------------------------
    00208     // CONSTRAINTS.
    00209     //------------------------------------------------------
    00210
    00212     BlisCutStrategy cutStrategy_;
    00213
    00215     int cutGenerationFrequency_;
    00216
    00218     int numCutGenerators_;
    00219
    00221     int maxNumCons_;
    00222
    00224     BlisConGenerator **generators_;
    00225
    00227     BcpsConstraintPool *constraintPool_;
    00228
    00230     BlisConstraint **oldConstraints_;
    00231
    00233     int oldConstraintsSize_;
    00234
    00236     int numOldConstraints_;
    00237
    00239     double *conRandoms_;
    00240
    00242     int denseConCutoff_;
    00243
    00244     //------------------------------------------------------
    00245     // PARAMETERS, STATISTICS, and MESSAGE
    00246     //------------------------------------------------------
    00247
    00249     BlisParams *BlisPar_;
    00250
    00252     CoinMessageHandler *blisMessageHandler_;
    00253
    00255     CoinMessages blisMessages_;
    00256
    00258     int numNodes_;
    00259
    00261     int numIterations_;
    00262
    00264     int aveIterations_;
    00265
    00266     //------------------------------------------------------
    00267     // TEMPORARY STORAGE
    00268     //------------------------------------------------------
    00269
    00272     int *tempVarLBPos_;
    00273     int *tempVarUBPos_;
    00274     int *tempConLBPos_;
    00275     int *tempConUBPos_;
    00277
    00278     //------------------------------------------------------
    00279     // Knowledge shared
    00280     //------------------------------------------------------
    00281
    00283     BcpsConstraintPool *constraintPoolSend_;
    00284
    00286     BcpsConstraintPool *constraintPoolReceive_;
    00287
    00288  public:
    00289
    00291     bool isRoot_;
    00292
    00294     int boundingPass_;
    00295
    00297     double integerTol_;
    00298
    00300     double optimalRelGap_;
    00301
    00303     double optimalAbsGap_;
    00304
    00306     double currRelGap_;
    00307
    00309     double currAbsGap_;
    00310
    00312     BlisHeurStrategy heurStrategy_;
    00313
    00315     int heurCallFrequency_;
    00316
    00318     OsiCuts newCutPool_;
    00319
    00321     std::vector<AlpsTreeNode *> leafToRootPath;
    00322
    00323  protected:
    00324
    00326     void init();
    00327
    00329     void createObjects();
    00330
    00331  public:
    00332
    00334     BlisModel()
    00335     {
    00336         init();
    00337     }
    00338
    00340     virtual ~BlisModel();
    00341
    00343     void gutsOfDestructor();
    00344
    00345     //------------------------------------------------------
    00346     // SETUP, LP SOLVER
    00347     //------------------------------------------------------
    00348
    00350     void setColMatrix(CoinPackedMatrix *mat){ colMatrix_ = mat; }
    00351
    00353     void setNumCons(int num){ numRows_ = num; }
    00354
    00356     void setNumVars(int num){ numCols_ = num; }
    00357
    00359     void setNumElems(int num){ numElems_ = num; }
    00360
    00362     void setConLb(double *cl){ conLB_ = cl; }
    00363
    00365     void setConUb(double *cu){ conUB_ = cu; }
    00366
    00368     void setVarLb(double *lb){ varLB_ = lb; }
    00369
    00371     void setVarUb(double *ub){ varUB_ = ub; }
    00372
    00374     void setColType(char *colType){
    00375         colType_ = colType;
    00376     }
    00377
    00379     void setObjCoef(double *obj){ objCoef_ = obj; }
    00380
    00390     virtual void readInstance(const char* dataFile);
    00391
    00403     virtual void importModel(std::vector<BlisVariable *> vars,
    00404                              std::vector<BlisConstraint *> cons);
    00405
    00407     virtual void readParameters(const int argnum, const char * const *arglist);
    00408
    00410     virtual void writeParameters(std::ostream& outstream) const;
    00411
    00415     virtual AlpsTreeNode * createRoot();
    00416
    00426     virtual bool setupSelf();
    00427
    00429     virtual void preprocess();
    00430
    00432     virtual void postprocess();
    00433
    00435     virtual void setSolver(OsiSolverInterface *si) { origLpSolver_ = si; }
    00436
    00438     virtual OsiSolverInterface *getSolver() { return origLpSolver_; }
    00439
    00441     virtual OsiSolverInterface *solver() { return lpSolver_; }
    00442
    00444     bool resolve();
    00445
    00447     void setActiveNode(AlpsTreeNode *node) { activeNode_ = node; }
    00448
    00450     void setSolEstimate(double est) { activeNode_->setSolEstimate(est); }
    00451
    00453     int getNumStrong() { return numStrong_; }
    00454
    00456     void addNumStrong(int num=1) { numStrong_ += num; }
    00457
    00459     int getNumBranchResolve() { return numBranchResolve_; }
    00460
    00462     void setNumBranchResolve(int num) { numBranchResolve_ = num; }
    00463
    00464     //------------------------------------------------------
    00465     // PROBLEM DATA
    00466     //------------------------------------------------------
    00467
    00469     double* getObjCoef() const { return objCoef_; }
    00470
    00472     const double * getColLower() { return lpSolver_->getColLower(); }
    00473
    00475     const double * getColUpper() { return lpSolver_->getColUpper(); }
    00476
    00478     int getNumCols() { return lpSolver_->getNumCols(); }
    00479
    00481     int getNumRows() { return lpSolver_->getNumRows(); }
    00482
    00484     double *varLB() { return varLB_; }
    00485     double *varUB() { return varUB_; }
    00486
    00488     double *conLB() { return conLB_; }
    00489     double *conUB() { return conUB_; }
    00490
    00492     double *startVarLB() { return startVarLB_; }
    00493     double *startVarUB() { return startVarUB_; }
    00494
    00496     double *startConLB() { return startConLB_; }
    00497     double *startConUB() { return startConUB_; }
    00498
    00500     int *tempVarLBPos() { return tempVarLBPos_; }
    00501     int *tempVarUBPos() { return tempVarUBPos_; }
    00502     int *tempConLBPos() { return tempConLBPos_; }
    00503     int *tempConUBPos() { return tempConUBPos_; }
    00504
    00505     //------------------------------------------------------
    00506     // LP SOLUTION
    00507     //------------------------------------------------------
    00508
    00510     double getLpObjValue() const { return lpSolver_->getObjValue(); }
    00511
    00513     const double * getLpSolution() const { return lpSolver_->getColSolution();}
    00514
    00515     //------------------------------------------------------
    00516     // MILP SOLUTION
    00517     //------------------------------------------------------
    00518
    00520     int getNumSolutions() const { return numSolutions_; }
    00521
    00523     int getNumHeurSolutions() const { return numHeurSolutions_;}
    00524
    00526     double * incumbent() { return incumbent_; }
    00527
    00529     int storeSolution(BlisSolutionType how, BlisSolution* sol);
    00530
    00532     inline double getCutoff() const { return cutoff_;  }
    00533
    00535     inline void setCutoff(double co) {
    00536         double inc = BlisPar_->entry(BlisParams::cutoffInc);
    00537 #if 0
    00538         std::cout << "3. cutoff_ = "<< cutoff_
    00539                   << "; inc = " << inc << std::endl;
    00540 #endif
    00541         co += inc;
    00542         if (co < cutoff_) {
    00543             cutoff_ = co;
    00544             lpSolver_->setDblParam(OsiDualObjectiveLimit, co);
    00545         }
    00546     }
    00547
    00549     BlisSolution *feasibleSolutionHeur(const double *solution);
    00550
    00555     virtual BlisSolution *feasibleSolution(int & numIntegerInfs,
    00556                                            int & numObjectInfs);
    00557
    00566     virtual BlisSolution *userFeasibleSolution(const double * solution,
    00567                                                bool &feasible) {
    00568         BlisSolution *sol = NULL;
    00569         feasible = true; // Feasible by default
    00570         return sol;
    00571     }
    00572
    00573     //------------------------------------------------------
    00574     // BRANCHING
    00575     //------------------------------------------------------
    00576
    00582     inline BcpsBranchStrategy * branchStrategy() const
    00583         { return branchStrategy_; }
    00584
    00586     inline void setBranchingMethod(BcpsBranchStrategy * method) {
    00587         if (branchStrategy_) delete branchStrategy_;
    00588         branchStrategy_ = method;
    00589     }
    00590
    00592     inline void setBranchingMethod(BcpsBranchStrategy & method) {
    00593         if (branchStrategy_) delete branchStrategy_;
    00594         branchStrategy_ = &method;
    00595     }
    00596     inline BcpsBranchStrategy * rampUpBranchStrategy() const
    00597         { return rampUpBranchStrategy_; }
    00599
    00604     inline int numObjects() const { return numObjects_; }
    00605
    00607     inline void setNumObjects(int num) { numObjects_ = num; }
    00608
    00610     inline BcpsObject ** objects() { return objects_;}
    00611
    00613     inline BcpsObject * objects(int which) { return objects_[which]; }
    00614
    00616     void setSharedObjectMark(int i) { sharedObjectMark_[i] = 1; }
    00617
    00619     void clearSharedObjectMark() {
    00620         for (int k = 0; k < numIntObjects_; ++k) {
    00621             sharedObjectMark_[k] = 0;
    00622         }
    00623     }
    00624
    00626     void deleteObjects();
    00627
    00630     void addObjects(int numObjects, BcpsObject ** objects);
    00632
    00634     void createIntgerObjects(bool startAgain);
    00635
    00637     int* getIntObjIndices() const { return intObjIndices_; }
    00638
    00640     int getNumIntObjects() const { return numIntObjects_; }
    00641
    00643     int* getIntColIndices() const { return intColIndices_; }
    00644
    00646     bool checkInteger(double value) const {
    00647         double integerTolerance = 1.0e-5;
    00648         double nearest = floor(value + 0.5);
    00649         if (fabs(value - nearest) <= integerTolerance) {
    00650             return true;
    00651         }
    00652         else {
    00653             return false;
    00654         }
    00655     }
    00656
    00657     void analyzeObjective();
    00658
    00659     //------------------------------------------------------
    00660     // HEURISTICS.
    00661     //------------------------------------------------------
    00662
    00664     void addHeuristic(BlisHeuristic * heur);
    00665
    00667     BlisHeuristic * heuristics(int i) const { return heuristics_[i]; }
    00668
    00670     int numHeuristics() const { return numHeuristics_; }
    00671
    00672     //------------------------------------------------------
    00673     // CONSTRAINTS.
    00674     //------------------------------------------------------
    00675
    00677     void addCutGenerator(BlisConGenerator * generator);
    00678
    00680     void addCutGenerator(CglCutGenerator * generator,
    00681                          const char * name = NULL,
    00682                          BlisCutStrategy strategy = BlisCutStrategyAuto,
    00683                          int cutGenerationFrequency = 1,
    00684                          bool normal = true,
    00685                          bool atSolution = false,
    00686                          bool whenInfeasible = false);
    00687
    00689     BlisConGenerator *cutGenerators(int i) const { return generators_[i]; }
    00690
    00692     int numCutGenerators() const { return numCutGenerators_; }
    00693
    00695     int getMaxNumCons() const { return maxNumCons_; }
    00696
    00698     void setMaxNumCons(int m) { maxNumCons_ = m; }
    00699
    00701     BcpsConstraintPool *constraintPool() { return constraintPool_; }
    00702
    00704     BcpsConstraintPool *constraintPoolReceive()
    00705         { return constraintPoolReceive_; }
    00706
    00708     BcpsConstraintPool *constraintPoolSend() { return constraintPoolSend_; }
    00709
    00711
    00712     int getNumOldConstraints() const { return numOldConstraints_; }
    00713
    00715     void setNumOldConstraints(int num) { numOldConstraints_ = num; }
    00716
    00718     int getOldConstraintsSize() const { return oldConstraintsSize_; }
    00719
    00721     void setOldConstraintsSize(int num) { oldConstraintsSize_ = num; }
    00722
    00724     BlisConstraint **oldConstraints() { return oldConstraints_; }
    00725
    00727     void setOldConstraints(BlisConstraint **old) { oldConstraints_ = old; }
    00728
    00730     void delOldConstraints() {
    00731         delete [] oldConstraints_;
    00732         oldConstraints_ = NULL;
    00733     }
    00735
    00737     BlisCutStrategy getCutStrategy() const {
    00738         return cutStrategy_;
    00739     }
    00740
    00742     void setCutStrategy(BlisCutStrategy u) { cutStrategy_ = u; }
    00743
    00745     int getCutGenerationFrequency() const { return cutGenerationFrequency_; }
    00746
    00748     void setCutStrategy(int f) { cutGenerationFrequency_ = f; }
    00749
    00751     int getDenseConCutoff() const { return denseConCutoff_; }
    00752
    00754     void setDenseConCutoff(int cutoff) { denseConCutoff_ = cutoff; }
    00755
    00757     double *getConRandoms() const { return conRandoms_; }
    00758
    00759     //------------------------------------------------------
    00760     // PRIORITY AND WEITGHT.
    00761     //------------------------------------------------------
    00762
    00777     void passInPriorities(const int * priorities,
    00778                           bool ifNotSimpleIntegers,
    00779                           int defaultValue = 1000);
    00780
    00782     inline const int * priority() const { return priority_; }
    00783
    00785     inline int priority(int sequence) const {
    00786         if (priority_) return priority_[sequence];
    00787         else return 1000;
    00788     }
    00789
    00790     inline double getNodeWeight() const { return nodeWeight_; }
    00791
    00792     inline void setNodeWeight(double nw) { nodeWeight_ = nw; }
    00794
    00795     //------------------------------------------------------
    00796     // STATISTICS.
    00797     //------------------------------------------------------
    00798
    00800     virtual void modelLog();
    00801
    00803     int getNumNodes() const { return numNodes_; }
    00804
    00806     int getNumIterations() const { return numIterations_; }
    00807
    00809     int getAveIterations() const { return aveIterations_; }
    00810
    00812     void addNumNodes(int newNodes = 1) { numNodes_ += newNodes; }
    00813
    00815     void addNumIterations(int newIter) {
    00816         numIterations_ += newIter;
    00817         aveIterations_ = numIterations_ / numNodes_;
    00818     }
    00819
    00821     CoinMessageHandler * blisMessageHandler() const
    00822     { return blisMessageHandler_; }
    00823
    00825     CoinMessages blisMessages() { return blisMessages_; }
    00826
    00829     BlisParams * BlisPar() { return BlisPar_; }
    00831
    00833     virtual void nodeLog(AlpsTreeNode *node, bool force);
    00834
    00836     virtual bool fathomAllNodes();
    00837
    00838     //------------------------------------------------------
    00839     // PARALLEL
    00840     //------------------------------------------------------
    00841
    00842  protected:
    00843
    00845     AlpsReturnStatus encodeBlis(AlpsEncoded *encoded) const;
    00846
    00848     AlpsReturnStatus decodeBlis(AlpsEncoded &encoded);
    00849
    00851     void packSharedPseudocost(AlpsEncoded *encoded, int numToShare);
    00852
    00854     void unpackSharedPseudocost(AlpsEncoded &encoded);
    00855
    00857     void packSharedConstraints(AlpsEncoded *encoded);
    00858
    00860     void unpackSharedConstraints(AlpsEncoded &encoded);
    00861
    00863     void packSharedVariables(AlpsEncoded *encoded);
    00864
    00866     void unpackSharedVariables(AlpsEncoded &encoded);
    00867
    00868  public:
    00869
    00872     virtual void registerKnowledge();
    00873
    00874     using AlpsKnowledge::encode ;
    00876     virtual AlpsEncoded* encode() const;
    00877
    00879     virtual void decodeToSelf(AlpsEncoded&);
    00880
    00883     virtual AlpsEncoded* packSharedKnowlege();
    00884
    00886     virtual void unpackSharedKnowledge(AlpsEncoded&);
    00887 };
    00888
    00889 #endif /* End of file */