00001
00002
00003
00004 #ifndef OsiVolSolverInterface_H
00005 #define OsiVolSolverInterface_H
00006
00007 #include <string>
00008
00009 #include "VolVolume.hpp"
00010
00011 #include "CoinPackedMatrix.hpp"
00012
00013 #include "OsiSolverInterface.hpp"
00014
00015 static const double OsiVolInfinity = 1.0e31;
00016
00017
00018
00024 class OsiVolSolverInterface :
00025 public OsiSolverInterface, public VOL_user_hooks {
00026 friend void OsiVolSolverInterfaceUnitTest(const std::string & mpsDir, const std::string & netlibDir);
00027
00028 private:
00029 class OsiVolMatrixOneMinusOne_ {
00030 int majorDim_;
00031 int minorDim_;
00032
00033 int plusSize_;
00034 int * plusInd_;
00035 int * plusStart_;
00036 int * plusLength_;
00037
00038 int minusSize_;
00039 int * minusInd_;
00040 int * minusStart_;
00041 int * minusLength_;
00042
00043 public:
00044 OsiVolMatrixOneMinusOne_(const CoinPackedMatrix& m);
00045 ~OsiVolMatrixOneMinusOne_();
00046 void timesMajor(const double* x, double* y) const;
00047 };
00048
00049 public:
00050
00053
00054 virtual void initialSolve();
00055
00057 virtual void resolve();
00058
00060 virtual void branchAndBound() {
00061 throw CoinError("Sorry, the Volume Algorithm doesn't implement B&B",
00062 "branchAndBound", "OsiVolSolverInterface");
00063 }
00065
00066
00082
00083 bool setIntParam(OsiIntParam key, int value);
00084
00085 bool setDblParam(OsiDblParam key, double value);
00086
00087 bool setStrParam(OsiStrParam key, const std::string & value);
00088
00089 bool getIntParam(OsiIntParam key, int& value) const;
00090
00091 bool getDblParam(OsiDblParam key, double& value) const;
00092
00093 bool getStrParam(OsiStrParam key, std::string& value) const;
00095
00096
00098
00099
00100 virtual bool isAbandoned() const;
00102 virtual bool isProvenOptimal() const;
00104 virtual bool isProvenPrimalInfeasible() const;
00106 virtual bool isProvenDualInfeasible() const;
00108 virtual bool isPrimalObjectiveLimitReached() const;
00110 virtual bool isDualObjectiveLimitReached() const;
00112 virtual bool isIterationLimitReached() const;
00114
00115
00124 virtual CoinWarmStart *getEmptyWarmStart () const ;
00125
00127 virtual CoinWarmStart* getWarmStart() const;
00130 virtual bool setWarmStart(const CoinWarmStart* warmstart);
00132
00133
00140
00141 virtual void markHotStart();
00143 virtual void solveFromHotStart();
00145 virtual void unmarkHotStart();
00147
00148
00163
00164 virtual int getNumCols() const {
00165 return rowMatrixCurrent_?
00166 rowMatrix_.getNumCols() : colMatrix_.getNumCols(); }
00167
00169 virtual int getNumRows() const {
00170 return rowMatrixCurrent_?
00171 rowMatrix_.getNumRows() : colMatrix_.getNumRows(); }
00172
00174 virtual int getNumElements() const {
00175 return rowMatrixCurrent_?
00176 rowMatrix_.getNumElements() : colMatrix_.getNumElements(); }
00177
00179 virtual const double * getColLower() const { return collower_; }
00180
00182 virtual const double * getColUpper() const { return colupper_; }
00183
00193 virtual const char * getRowSense() const { return rowsense_; }
00194
00203 virtual const double * getRightHandSide() const { return rhs_; }
00204
00213 virtual const double * getRowRange() const { return rowrange_; }
00214
00216 virtual const double * getRowLower() const { return rowlower_; }
00217
00219 virtual const double * getRowUpper() const { return rowupper_; }
00220
00222 virtual const double * getObjCoefficients() const { return objcoeffs_; }
00223
00225 virtual double getObjSense() const { return objsense_; }
00226
00228 virtual bool isContinuous(int colNumber) const;
00229
00230 #if 0
00231
00232 virtual bool isBinary(int colNumber) const;
00233
00238 virtual bool isInteger(int colNumber) const;
00239
00241 virtual bool isIntegerNonBinary(int colNumber) const;
00242
00244 virtual bool isFreeBinary(int colNumber) const;
00245 #endif
00246
00248 virtual const CoinPackedMatrix * getMatrixByRow() const;
00249
00251 virtual const CoinPackedMatrix * getMatrixByCol() const;
00252
00254 virtual double getInfinity() const { return OsiVolInfinity; }
00256
00259
00260 virtual const double * getColSolution() const { return colsol_; }
00261
00263 virtual const double * getRowPrice() const { return rowprice_; }
00264
00266 virtual const double * getReducedCost() const { return rc_; }
00267
00270 virtual const double * getRowActivity() const { return lhs_; }
00271
00273 virtual double getObjValue() const {
00274 #if 1
00275
00276 return lagrangeanCost_;
00277 #else
00278 return OsiSolverInterface::getObjValue();
00279 #endif
00280 }
00281
00284 virtual int getIterationCount() const { return volprob_.iter(); }
00285
00297 virtual std::vector<double*> getDualRays(int maxNumRays) const;
00309 virtual std::vector<double*> getPrimalRays(int maxNumRays) const;
00310
00311 #if 0
00312
00314 virtual OsiVectorInt getFractionalIndices(const double etol=1.e-05)
00315 const;
00316 #endif
00317
00318
00319
00320
00321
00324
00328 virtual void setObjCoeff( int elementIndex, double elementValue ) {
00329 objcoeffs_[elementIndex] = elementValue;
00330 }
00331
00334 virtual void setColLower( int elementIndex, double elementValue ) {
00335 collower_[elementIndex] = elementValue;
00336 }
00337
00340 virtual void setColUpper( int elementIndex, double elementValue ) {
00341 colupper_[elementIndex] = elementValue;
00342 }
00343
00345 virtual void setColBounds( int elementIndex,
00346 double lower, double upper ) {
00347 collower_[elementIndex] = lower;
00348 colupper_[elementIndex] = upper;
00349 }
00350
00359 virtual void setColSetBounds(const int* indexFirst,
00360 const int* indexLast,
00361 const double* boundList);
00362
00365 virtual void setRowLower( int elementIndex, double elementValue ) {
00366 rowlower_[elementIndex] = elementValue;
00367 convertBoundToSense(elementValue, rowupper_[elementIndex],
00368 rowsense_[elementIndex], rhs_[elementIndex],
00369 rowrange_[elementIndex]);
00370 }
00371
00374 virtual void setRowUpper( int elementIndex, double elementValue ) {
00375 rowupper_[elementIndex] = elementValue;
00376 convertBoundToSense(rowlower_[elementIndex], elementValue,
00377 rowsense_[elementIndex], rhs_[elementIndex],
00378 rowrange_[elementIndex]);
00379 }
00380
00382 virtual void setRowBounds( int elementIndex,
00383 double lower, double upper ) {
00384 rowlower_[elementIndex] = lower;
00385 rowupper_[elementIndex] = upper;
00386 convertBoundToSense(lower, upper,
00387 rowsense_[elementIndex], rhs_[elementIndex],
00388 rowrange_[elementIndex]);
00389 }
00390
00392 virtual void setRowType(int index, char sense, double rightHandSide,
00393 double range) {
00394 rowsense_[index] = sense;
00395 rhs_[index] = rightHandSide;
00396 rowrange_[index] = range;
00397 convertSenseToBound(sense, rightHandSide, range,
00398 rowlower_[index], rowupper_[index]);
00399 }
00400
00409 virtual void setRowSetBounds(const int* indexFirst,
00410 const int* indexLast,
00411 const double* boundList);
00412
00423 virtual void setRowSetTypes(const int* indexFirst,
00424 const int* indexLast,
00425 const char* senseList,
00426 const double* rhsList,
00427 const double* rangeList);
00429
00430
00434 virtual void setContinuous(int index);
00436 virtual void setInteger(int index);
00439 virtual void setContinuous(const int* indices, int len);
00442 virtual void setInteger(const int* indices, int len);
00444
00445
00447 virtual void setObjSense(double s ) { objsense_ = s < 0 ? -1.0 : 1.0; }
00448
00459 virtual void setColSolution(const double * colsol);
00460
00471 virtual void setRowPrice(const double * rowprice);
00472
00473
00479 virtual void addCol(const CoinPackedVectorBase& vec,
00480 const double collb, const double colub,
00481 const double obj);
00483 virtual void addCols(const int numcols,
00484 const CoinPackedVectorBase * const * cols,
00485 const double* collb, const double* colub,
00486 const double* obj);
00487 #if 0
00488
00489 virtual void addCols(const CoinPackedMatrix& matrix,
00490 const double* collb, const double* colub,
00491 const double* obj);
00492 #endif
00493
00494 virtual void deleteCols(const int num, const int * colIndices);
00495
00497 virtual void addRow(const CoinPackedVectorBase& vec,
00498 const double rowlb, const double rowub);
00500 virtual void addRow(const CoinPackedVectorBase& vec,
00501 const char rowsen, const double rowrhs,
00502 const double rowrng);
00504 virtual void addRows(const int numrows,
00505 const CoinPackedVectorBase * const * rows,
00506 const double* rowlb, const double* rowub);
00508 virtual void addRows(const int numrows,
00509 const CoinPackedVectorBase * const * rows,
00510 const char* rowsen, const double* rowrhs,
00511 const double* rowrng);
00512 #if 0
00513
00514 virtual void addRows(const CoinPackedMatrix& matrix,
00515 const double* rowlb, const double* rowub);
00517 virtual void addRows(const CoinPackedMatrix& matrix,
00518 const char* rowsen, const double* rowrhs,
00519 const double* rowrng);
00520 #endif
00521
00522 virtual void deleteRows(const int num, const int * rowIndices);
00523
00524
00525 #if 0
00526
00547 virtual ApplyCutsReturnCode applyCuts(const OsiCuts & cs,
00548 double effectivenessLb = 0.0);
00549 #endif
00550
00551
00552
00553
00554
00555 protected:
00557 void initFromRlbRub(const int rownum,
00558 const double* rowlb, const double* rowub);
00559 void initFromRhsSenseRange(const int rownum, const char* rowsen,
00560 const double* rowrhs, const double* rowrng);
00561 void initFromClbCubObj(const int colnum, const double* collb,
00562 const double* colub, const double* obj);
00563 public:
00564
00578 virtual void loadProblem(const CoinPackedMatrix& matrix,
00579 const double* collb, const double* colub,
00580 const double* obj,
00581 const double* rowlb, const double* rowub);
00582
00590 virtual void assignProblem(CoinPackedMatrix*& matrix,
00591 double*& collb, double*& colub, double*& obj,
00592 double*& rowlb, double*& rowub);
00593
00606 virtual void loadProblem(const CoinPackedMatrix& matrix,
00607 const double* collb, const double* colub,
00608 const double* obj,
00609 const char* rowsen, const double* rowrhs,
00610 const double* rowrng);
00611
00619 virtual void assignProblem(CoinPackedMatrix*& matrix,
00620 double*& collb, double*& colub, double*& obj,
00621 char*& rowsen, double*& rowrhs,
00622 double*& rowrng);
00623
00626 virtual void loadProblem(const int numcols, const int numrows,
00627 const int* start, const int* index,
00628 const double* value,
00629 const double* collb, const double* colub,
00630 const double* obj,
00631 const double* rowlb, const double* rowub);
00632
00635 virtual void loadProblem(const int numcols, const int numrows,
00636 const int* start, const int* index,
00637 const double* value,
00638 const double* collb, const double* colub,
00639 const double* obj,
00640 const char* rowsen, const double* rowrhs,
00641 const double* rowrng);
00642
00644 virtual int readMps(const char *filename,
00645 const char *extension = "mps");
00646
00651 virtual void writeMps(const char *filename,
00652 const char *extension = "mps",
00653 double objSense=0.0) const;
00655
00656
00657
00660
00661 VOL_problem* volprob() { return &volprob_; }
00663
00664
00665
00668
00669 OsiVolSolverInterface ();
00670
00672 virtual OsiSolverInterface * clone(bool copyData = true) const;
00673
00675 OsiVolSolverInterface (const OsiVolSolverInterface &);
00676
00678 OsiVolSolverInterface & operator=(const OsiVolSolverInterface& rhs);
00679
00681 virtual ~OsiVolSolverInterface ();
00683
00684
00685
00686 protected:
00688
00689
00690 virtual void applyRowCut(const OsiRowCut& rc);
00691
00693 virtual void applyColCut(const OsiColCut& cc);
00695
00696
00697
00698 private:
00701
00702 virtual int compute_rc(const VOL_dvector& u, VOL_dvector& rc);
00704 virtual int solve_subproblem(const VOL_dvector& dual,
00705 const VOL_dvector& rc,
00706 double& lcost, VOL_dvector& x, VOL_dvector& v,
00707 double& pcost);
00710 virtual int heuristics(const VOL_problem& p,
00711 const VOL_dvector& x, double& heur_val) {
00712 heur_val = DBL_MAX;
00713 return 0;
00714 };
00716
00717
00718
00719 private:
00723 void updateRowMatrix_() const;
00725 void updateColMatrix_() const;
00726
00729 void checkData_() const throw(CoinError);
00732 void compute_rc_(const double* u, double* rc) const;
00734 void gutsOfDestructor_();
00735
00738 void rowRimAllocator_();
00741 void colRimAllocator_();
00742
00744 void rowRimResize_(const int newSize);
00746 void colRimResize_(const int newSize);
00747
00749 void convertBoundsToSenses_();
00751 void convertSensesToBounds_();
00752
00754 bool test_zero_one_minusone_(const CoinPackedMatrix& m) const;
00756
00757
00758
00759 private:
00760
00761
00765
00766 mutable bool rowMatrixCurrent_;
00768 mutable CoinPackedMatrix rowMatrix_;
00770 mutable bool colMatrixCurrent_;
00772 mutable CoinPackedMatrix colMatrix_;
00774
00775
00778
00779 bool isZeroOneMinusOne_;
00781 OsiVolMatrixOneMinusOne_* rowMatrixOneMinusOne_;
00783 OsiVolMatrixOneMinusOne_* colMatrixOneMinusOne_;
00785
00786
00789
00790 double *colupper_;
00792 double *collower_;
00794 bool *continuous_;
00796 double *rowupper_;
00798 double *rowlower_;
00800 char *rowsense_;
00802 double *rhs_;
00805 double *rowrange_;
00807 double *objcoeffs_;
00809
00810
00812 double objsense_;
00813
00814
00817
00818 double *colsol_;
00820 double *rowprice_;
00822 double *rc_;
00824 double *lhs_;
00826 double lagrangeanCost_;
00828
00829
00832 double *rowpriceHotStart_;
00833
00835 int maxNumrows_;
00837 int maxNumcols_;
00838
00840 VOL_problem volprob_;
00841 };
00842
00843
00851 void
00852 OsiVolSolverInterfaceUnitTest(const std::string & mpsDir, const std::string & netlibDir);
00853
00854 #endif
