Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
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
00069 class BlisModel : public BcpsModel {
00070
00071 protected:
00072
00073
00074
00075
00076
00078 OsiSolverInterface *origLpSolver_;
00080 OsiSolverInterface *presolvedLpSolver_;
00083 OsiSolverInterface *lpSolver_;
00084
00085
00086
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_;
00118
00121 std::vector<BcpsVariable *> inputVar_;
00122 std::vector<BcpsConstraint *> inputCon_;
00124
00125
00126
00127
00128
00129 BlisPresolve *presolve_;
00130
00131 bool presolved;
00132 bool problemSetup;
00133
00134
00135
00136
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
00156
00157
00158 int *intObjIndices_;
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
00174
00175
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
00197 double nodeWeight_;
00198
00200 int numBranchResolve_;
00201
00202
00203
00204
00205
00207 int numHeuristics_;
00208
00210 BlisHeuristic **heuristics_;
00211
00212
00213
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
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
00273
00274
00277 int *tempVarLBPos_;
00278 int *tempVarUBPos_;
00279 int *tempConLBPos_;
00280 int *tempConUBPos_;
00282
00283
00284
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
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
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
00512
00513
00515 double getLpObjValue() const { return lpSolver_->getObjValue(); }
00516
00518 const double * getLpSolution() const { return lpSolver_->getColSolution();}
00519
00520
00521
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;
00575 return sol;
00576 }
00577
00578
00579
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
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
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
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
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
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
00894 virtual void presolveForTheWholeTree();
00895
00896 };
00897
00898 #endif