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

- File List
- File Members

# /home/coin/svn-release/Blis-0.93.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 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-2011, 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 */