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 "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 class BlisModel : public BcpsModel {
00068
00069 protected:
00070
00071
00072
00073
00074
00076 OsiSolverInterface *origLpSolver_;
00078 OsiSolverInterface *presolvedLpSolver_;
00081 OsiSolverInterface *lpSolver_;
00082
00083
00084
00085
00086
00088 CoinPackedMatrix *colMatrix_;
00089
00092 double *varLB_;
00093 double *varUB_;
00094 double *conLB_;
00095 double *conUB_;
00097
00100 int numCols_;
00101 int numRows_;
00102 int numElems_;
00104
00107 double objSense_;
00108 double *objCoef_;
00110
00113 int numIntObjects_;
00114 int *intColIndices_;
00116
00119 std::vector<BcpsVariable *> inputVar_;
00120 std::vector<BcpsConstraint *> inputCon_;
00122
00123
00124
00125
00126
00127 BlisPresolve *presolve_;
00128
00129
00130
00131
00132
00133 int numSolutions_;
00134 int numHeurSolutions_;
00135
00137 double incObjValue_;
00138
00140 double *incumbent_;
00141
00143 double cutoff_;
00144
00146 double cutoffInc_;
00147
00148
00149
00150
00151
00152 int *intObjIndices_;
00153 char *colType_;
00154
00157 double *startVarLB_;
00158 double *startVarUB_;
00159 double *startConLB_;
00160 double *startConUB_;
00162
00164 BcpsBranchStrategy * branchStrategy_;
00165 BcpsBranchStrategy * rampUpBranchStrategy_;
00166
00167
00168
00169
00170 BlisHotStartStrategy hotstartStrategy_;
00171
00173 int numObjects_;
00174
00176 BcpsObject **objects_;
00177
00179 char *sharedObjectMark_;
00180
00182 int *priority_;
00183
00185 AlpsTreeNode *activeNode_;
00186
00188 int numStrong_;
00189
00190
00191 double nodeWeight_;
00192
00194 int numBranchResolve_;
00195
00196
00197
00198
00199
00201 int numHeuristics_;
00202
00204 BlisHeuristic **heuristics_;
00205
00206
00207
00208
00209
00211 BlisCutStrategy cutStrategy_;
00212
00214 int cutGenerationFrequency_;
00215
00217 int numCutGenerators_;
00218
00220 int maxNumCons_;
00221
00223 BlisConGenerator **generators_;
00224
00226 BcpsConstraintPool *constraintPool_;
00227
00229 BlisConstraint **oldConstraints_;
00230
00232 int oldConstraintsSize_;
00233
00235 int numOldConstraints_;
00236
00238 double *conRandoms_;
00239
00241 int denseConCutoff_;
00242
00243
00244
00245
00246
00248 BlisParams *BlisPar_;
00249
00251 CoinMessageHandler *blisMessageHandler_;
00252
00254 CoinMessages blisMessages_;
00255
00257 int numNodes_;
00258
00260 int numIterations_;
00261
00263 int aveIterations_;
00264
00265
00266
00267
00268
00271 int *tempVarLBPos_;
00272 int *tempVarUBPos_;
00273 int *tempConLBPos_;
00274 int *tempConUBPos_;
00276
00277
00278
00279
00280
00282 BcpsConstraintPool *constraintPoolSend_;
00283
00285 BcpsConstraintPool *constraintPoolReceive_;
00286
00287 public:
00288
00290 bool isRoot_;
00291
00293 int boundingPass_;
00294
00296 double integerTol_;
00297
00299 double optimalRelGap_;
00300
00302 double optimalAbsGap_;
00303
00305 BlisHeurStrategy heurStrategy_;
00306
00308 int heurCallFrequency_;
00309
00311 OsiCuts newCutPool_;
00312
00314 std::vector<AlpsTreeNode *> leafToRootPath;
00315
00316 protected:
00317
00319 void init();
00320
00322 void createObjects();
00323
00324 public:
00325
00327 BlisModel()
00328 {
00329 init();
00330 }
00331
00333 virtual ~BlisModel();
00334
00336 void gutsOfDestructor();
00337
00338
00339
00340
00341
00343 void setColMatrix(CoinPackedMatrix *mat){ colMatrix_ = mat; }
00344
00346 void setNumCons(int num){ numRows_ = num; }
00347
00349 void setNumVars(int num){ numCols_ = num; }
00350
00352 void setNumElems(int num){ numElems_ = num; }
00353
00355 void setConLb(double *cl){ conLB_ = cl; }
00356
00358 void setConUb(double *cu){ conUB_ = cu; }
00359
00361 void setVarLb(double *lb){ varLB_ = lb; }
00362
00364 void setVarUb(double *ub){ varUB_ = ub; }
00365
00367 void setColType(char *colType){
00368 colType_ = colType;
00369 }
00370
00372 void setObjCoef(double *obj){ objCoef_ = obj; }
00373
00383 virtual void readInstance(const char* dataFile);
00384
00396 virtual void importModel(std::vector<BlisVariable *> vars,
00397 std::vector<BlisConstraint *> cons);
00398
00400 virtual void readParameters(const int argnum, const char * const *arglist);
00401
00403 virtual void writeParameters(std::ostream& outstream) const;
00404
00408 virtual AlpsTreeNode * createRoot();
00409
00419 virtual bool setupSelf();
00420
00422 virtual void preprocess();
00423
00425 virtual void postprocess();
00426
00428 virtual void setSolver(OsiSolverInterface *si) { origLpSolver_ = si; }
00429
00431 virtual OsiSolverInterface *getSolver() { return origLpSolver_; }
00432
00434 virtual OsiSolverInterface *solver() { return lpSolver_; }
00435
00437 bool resolve();
00438
00440 void setActiveNode(AlpsTreeNode *node) { activeNode_ = node; }
00441
00443 void setSolEstimate(double est) { activeNode_->setSolEstimate(est); }
00444
00446 int getNumStrong() { return numStrong_; }
00447
00449 void addNumStrong(int num=1) { numStrong_ += num; }
00450
00452 int getNumBranchResolve() { return numBranchResolve_; }
00453
00455 void setNumBranchResolve(int num) { numBranchResolve_ = num; }
00456
00457
00458
00459
00460
00462 double* getObjCoef() const { return objCoef_; }
00463
00465 const double * getColLower() { return lpSolver_->getColLower(); }
00466
00468 const double * getColUpper() { return lpSolver_->getColUpper(); }
00469
00471 int getNumCols() { return lpSolver_->getNumCols(); }
00472
00474 int getNumRows() { return lpSolver_->getNumRows(); }
00475
00477 double *varLB() { return varLB_; }
00478 double *varUB() { return varUB_; }
00479
00481 double *conLB() { return conLB_; }
00482 double *conUB() { return conUB_; }
00483
00485 double *startVarLB() { return startVarLB_; }
00486 double *startVarUB() { return startVarUB_; }
00487
00489 double *startConLB() { return startConLB_; }
00490 double *startConUB() { return startConUB_; }
00491
00493 int *tempVarLBPos() { return tempVarLBPos_; }
00494 int *tempVarUBPos() { return tempVarUBPos_; }
00495 int *tempConLBPos() { return tempConLBPos_; }
00496 int *tempConUBPos() { return tempConUBPos_; }
00497
00498
00499
00500
00501
00503 double getLpObjValue() const { return lpSolver_->getObjValue(); }
00504
00506 const double * getLpSolution() const { return lpSolver_->getColSolution();}
00507
00508
00509
00510
00511
00513 int getNumSolutions() const { return numSolutions_; }
00514
00516 int getNumHeurSolutions() const { return numHeurSolutions_;}
00517
00519 double * incumbent() { return incumbent_; }
00520
00522 int storeSolution(BlisSolutionType how, BlisSolution* sol);
00523
00525 inline double getCutoff() const { return cutoff_; }
00526
00528 inline void setCutoff(double co) {
00529 double inc = BlisPar_->entry(BlisParams::cutoffInc);
00530 #if 0
00531 std::cout << "3. cutoff_ = "<< cutoff_
00532 << "; inc = " << inc << std::endl;
00533 #endif
00534 co += inc;
00535 if (co < cutoff_) {
00536 cutoff_ = co;
00537 lpSolver_->setDblParam(OsiDualObjectiveLimit, co);
00538 }
00539 }
00540
00542 BlisSolution *feasibleSolutionHeur(const double *solution);
00543
00548 virtual BlisSolution *feasibleSolution(int & numIntegerInfs,
00549 int & numObjectInfs);
00550
00559 virtual BlisSolution *userFeasibleSolution(const double * solution,
00560 bool &feasible) {
00561 BlisSolution *sol = NULL;
00562 feasible = true;
00563 return sol;
00564 }
00565
00566
00567
00568
00569
00575 inline BcpsBranchStrategy * branchStrategy() const
00576 { return branchStrategy_; }
00577
00579 inline void setBranchingMethod(BcpsBranchStrategy * method) {
00580 if (branchStrategy_) delete branchStrategy_;
00581 branchStrategy_ = method;
00582 }
00583
00585 inline void setBranchingMethod(BcpsBranchStrategy & method) {
00586 if (branchStrategy_) delete branchStrategy_;
00587 branchStrategy_ = &method;
00588 }
00589 inline BcpsBranchStrategy * rampUpBranchStrategy() const
00590 { return rampUpBranchStrategy_; }
00592
00597 inline int numObjects() const { return numObjects_; }
00598
00600 inline void setNumObjects(int num) { numObjects_ = num; }
00601
00603 inline BcpsObject ** objects() { return objects_;}
00604
00606 inline BcpsObject * objects(int which) { return objects_[which]; }
00607
00609 void setSharedObjectMark(int i) { sharedObjectMark_[i] = 1; }
00610
00612 void clearSharedObjectMark() {
00613 for (int k = 0; k < numIntObjects_; ++k) {
00614 sharedObjectMark_[k] = 0;
00615 }
00616 }
00617
00619 void deleteObjects();
00620
00623 void addObjects(int numObjects, BcpsObject ** objects);
00625
00627 void createIntgerObjects(bool startAgain);
00628
00630 int* getIntObjIndices() const { return intObjIndices_; }
00631
00633 int getNumIntObjects() const { return numIntObjects_; }
00634
00636 int* getIntColIndices() const { return intColIndices_; }
00637
00639 bool checkInteger(double value) const {
00640 double integerTolerance = 1.0e-5;
00641 double nearest = floor(value + 0.5);
00642 if (fabs(value - nearest) <= integerTolerance) {
00643 return true;
00644 }
00645 else {
00646 return false;
00647 }
00648 }
00649
00650 void analyzeObjective();
00651
00652
00653
00654
00655
00657 void addHeuristic(BlisHeuristic * heur);
00658
00660 BlisHeuristic * heuristics(int i) const { return heuristics_[i]; }
00661
00663 int numHeuristics() const { return numHeuristics_; }
00664
00665
00666
00667
00668
00670 void addCutGenerator(BlisConGenerator * generator);
00671
00673 void addCutGenerator(CglCutGenerator * generator,
00674 const char * name = NULL,
00675 BlisCutStrategy strategy = BlisCutStrategyAuto,
00676 int cutGenerationFrequency = 1,
00677 bool normal = true,
00678 bool atSolution = false,
00679 bool whenInfeasible = false);
00680
00682 BlisConGenerator *cutGenerators(int i) const { return generators_[i]; }
00683
00685 int numCutGenerators() const { return numCutGenerators_; }
00686
00688 int getMaxNumCons() const { return maxNumCons_; }
00689
00691 void setMaxNumCons(int m) { maxNumCons_ = m; }
00692
00694 BcpsConstraintPool *constraintPool() { return constraintPool_; }
00695
00697 BcpsConstraintPool *constraintPoolReceive()
00698 { return constraintPoolReceive_; }
00699
00701 BcpsConstraintPool *constraintPoolSend() { return constraintPoolSend_; }
00702
00704
00705 int getNumOldConstraints() const { return numOldConstraints_; }
00706
00708 void setNumOldConstraints(int num) { numOldConstraints_ = num; }
00709
00711 int getOldConstraintsSize() const { return oldConstraintsSize_; }
00712
00714 void setOldConstraintsSize(int num) { oldConstraintsSize_ = num; }
00715
00717 BlisConstraint **oldConstraints() { return oldConstraints_; }
00718
00720 void setOldConstraints(BlisConstraint **old) { oldConstraints_ = old; }
00721
00723 void delOldConstraints() {
00724 delete [] oldConstraints_;
00725 oldConstraints_ = NULL;
00726 }
00728
00730 BlisCutStrategy getCutStrategy() const {
00731 return cutStrategy_;
00732 }
00733
00735 void setCutStrategy(BlisCutStrategy u) { cutStrategy_ = u; }
00736
00738 int getCutGenerationFrequency() const { return cutGenerationFrequency_; }
00739
00741 void setCutStrategy(int f) { cutGenerationFrequency_ = f; }
00742
00744 int getDenseConCutoff() const { return denseConCutoff_; }
00745
00747 void setDenseConCutoff(int cutoff) { denseConCutoff_ = cutoff; }
00748
00750 double *getConRandoms() const { return conRandoms_; }
00751
00752
00753
00754
00755
00770 void passInPriorities(const int * priorities,
00771 bool ifNotSimpleIntegers,
00772 int defaultValue = 1000);
00773
00775 inline const int * priority() const { return priority_; }
00776
00778 inline int priority(int sequence) const {
00779 if (priority_) return priority_[sequence];
00780 else return 1000;
00781 }
00782
00783 inline double getNodeWeight() const { return nodeWeight_; }
00784
00785 inline void setNodeWeight(double nw) { nodeWeight_ = nw; }
00787
00788
00789
00790
00791
00793 virtual void modelLog();
00794
00796 int getNumNodes() const { return numNodes_; }
00797
00799 int getNumIterations() const { return numIterations_; }
00800
00802 int getAveIterations() const { return aveIterations_; }
00803
00805 void addNumNodes(int newNodes = 1) { numNodes_ += newNodes; }
00806
00808 void addNumIterations(int newIter) {
00809 numIterations_ += newIter;
00810 aveIterations_ = numIterations_ / numNodes_;
00811 }
00812
00814 CoinMessageHandler * blisMessageHandler() const
00815 { return blisMessageHandler_; }
00816
00818 CoinMessages blisMessages() { return blisMessages_; }
00819
00822 BlisParams * BlisPar() { return BlisPar_; }
00824
00826 virtual void nodeLog(AlpsTreeNode *node, bool force);
00827
00828
00829
00830
00831
00832 protected:
00833
00835 AlpsReturnStatus encodeBlis(AlpsEncoded *encoded) const;
00836
00838 AlpsReturnStatus decodeBlis(AlpsEncoded &encoded);
00839
00841 void packSharedPseudocost(AlpsEncoded *encoded, int numToShare);
00842
00844 void unpackSharedPseudocost(AlpsEncoded &encoded);
00845
00847 void packSharedConstraints(AlpsEncoded *encoded);
00848
00850 void unpackSharedConstraints(AlpsEncoded &encoded);
00851
00853 void packSharedVariables(AlpsEncoded *encoded);
00854
00856 void unpackSharedVariables(AlpsEncoded &encoded);
00857
00858 public:
00859
00862 virtual void registerKnowledge();
00863
00864 using AlpsKnowledge::encode ;
00866 virtual AlpsEncoded* encode() const;
00867
00869 virtual void decodeToSelf(AlpsEncoded&);
00870
00873 virtual AlpsEncoded* packSharedKnowlege();
00874
00876 virtual void unpackSharedKnowledge(AlpsEncoded&);
00877 };
00878
00879 #endif