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 virtual 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
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
00332 using OsiSolverInterface::setColLower ;
00335 virtual void setColLower( int elementIndex, double elementValue ) {
00336 collower_[elementIndex] = elementValue;
00337 }
00338
00339 using OsiSolverInterface::setColUpper ;
00342 virtual void setColUpper( int elementIndex, double elementValue ) {
00343 colupper_[elementIndex] = elementValue;
00344 }
00345
00347 virtual void setColBounds( int elementIndex,
00348 double lower, double upper ) {
00349 collower_[elementIndex] = lower;
00350 colupper_[elementIndex] = upper;
00351 }
00352
00361 virtual void setColSetBounds(const int* indexFirst,
00362 const int* indexLast,
00363 const double* boundList);
00364
00367 virtual void setRowLower( int elementIndex, double elementValue ) {
00368 rowlower_[elementIndex] = elementValue;
00369 convertBoundToSense(elementValue, rowupper_[elementIndex],
00370 rowsense_[elementIndex], rhs_[elementIndex],
00371 rowrange_[elementIndex]);
00372 }
00373
00376 virtual void setRowUpper( int elementIndex, double elementValue ) {
00377 rowupper_[elementIndex] = elementValue;
00378 convertBoundToSense(rowlower_[elementIndex], elementValue,
00379 rowsense_[elementIndex], rhs_[elementIndex],
00380 rowrange_[elementIndex]);
00381 }
00382
00384 virtual void setRowBounds( int elementIndex,
00385 double lower, double upper ) {
00386 rowlower_[elementIndex] = lower;
00387 rowupper_[elementIndex] = upper;
00388 convertBoundToSense(lower, upper,
00389 rowsense_[elementIndex], rhs_[elementIndex],
00390 rowrange_[elementIndex]);
00391 }
00392
00394 virtual void setRowType(int index, char sense, double rightHandSide,
00395 double range) {
00396 rowsense_[index] = sense;
00397 rhs_[index] = rightHandSide;
00398 rowrange_[index] = range;
00399 convertSenseToBound(sense, rightHandSide, range,
00400 rowlower_[index], rowupper_[index]);
00401 }
00402
00411 virtual void setRowSetBounds(const int* indexFirst,
00412 const int* indexLast,
00413 const double* boundList);
00414
00425 virtual void setRowSetTypes(const int* indexFirst,
00426 const int* indexLast,
00427 const char* senseList,
00428 const double* rhsList,
00429 const double* rangeList);
00431
00432
00436 virtual void setContinuous(int index);
00438 virtual void setInteger(int index);
00441 virtual void setContinuous(const int* indices, int len);
00444 virtual void setInteger(const int* indices, int len);
00446
00447
00449 virtual void setObjSense(double s ) { objsense_ = s < 0 ? -1.0 : 1.0; }
00450
00461 virtual void setColSolution(const double * colsol);
00462
00473 virtual void setRowPrice(const double * rowprice);
00474
00475
00480
00481 using OsiSolverInterface::addCol ;
00483 virtual void addCol(const CoinPackedVectorBase& vec,
00484 const double collb, const double colub,
00485 const double obj);
00486
00487 using OsiSolverInterface::addCols ;
00489 virtual void addCols(const int numcols,
00490 const CoinPackedVectorBase * const * cols,
00491 const double* collb, const double* colub,
00492 const double* obj);
00493 #if 0
00494
00495 virtual void addCols(const CoinPackedMatrix& matrix,
00496 const double* collb, const double* colub,
00497 const double* obj);
00498 #endif
00499
00500 virtual void deleteCols(const int num, const int * colIndices);
00501
00502 using OsiSolverInterface::addRow ;
00504 virtual void addRow(const CoinPackedVectorBase& vec,
00505 const double rowlb, const double rowub);
00507 virtual void addRow(const CoinPackedVectorBase& vec,
00508 const char rowsen, const double rowrhs,
00509 const double rowrng);
00510
00511 using OsiSolverInterface::addRows ;
00513 virtual void addRows(const int numrows,
00514 const CoinPackedVectorBase * const * rows,
00515 const double* rowlb, const double* rowub);
00517 virtual void addRows(const int numrows,
00518 const CoinPackedVectorBase * const * rows,
00519 const char* rowsen, const double* rowrhs,
00520 const double* rowrng);
00521 #if 0
00522
00523 virtual void addRows(const CoinPackedMatrix& matrix,
00524 const double* rowlb, const double* rowub);
00526 virtual void addRows(const CoinPackedMatrix& matrix,
00527 const char* rowsen, const double* rowrhs,
00528 const double* rowrng);
00529 #endif
00530
00531 virtual void deleteRows(const int num, const int * rowIndices);
00532
00533
00534 #if 0
00535
00556 virtual ApplyCutsReturnCode applyCuts(const OsiCuts & cs,
00557 double effectivenessLb = 0.0);
00558 #endif
00559
00560
00561
00562
00563
00564 protected:
00566 void initFromRlbRub(const int rownum,
00567 const double* rowlb, const double* rowub);
00568 void initFromRhsSenseRange(const int rownum, const char* rowsen,
00569 const double* rowrhs, const double* rowrng);
00570 void initFromClbCubObj(const int colnum, const double* collb,
00571 const double* colub, const double* obj);
00572 public:
00573
00587 virtual void loadProblem(const CoinPackedMatrix& matrix,
00588 const double* collb, const double* colub,
00589 const double* obj,
00590 const double* rowlb, const double* rowub);
00591
00599 virtual void assignProblem(CoinPackedMatrix*& matrix,
00600 double*& collb, double*& colub, double*& obj,
00601 double*& rowlb, double*& rowub);
00602
00615 virtual void loadProblem(const CoinPackedMatrix& matrix,
00616 const double* collb, const double* colub,
00617 const double* obj,
00618 const char* rowsen, const double* rowrhs,
00619 const double* rowrng);
00620
00628 virtual void assignProblem(CoinPackedMatrix*& matrix,
00629 double*& collb, double*& colub, double*& obj,
00630 char*& rowsen, double*& rowrhs,
00631 double*& rowrng);
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 double* rowlb, const double* rowub);
00641
00644 virtual void loadProblem(const int numcols, const int numrows,
00645 const int* start, const int* index,
00646 const double* value,
00647 const double* collb, const double* colub,
00648 const double* obj,
00649 const char* rowsen, const double* rowrhs,
00650 const double* rowrng);
00651
00652 using OsiSolverInterface::readMps ;
00654 virtual int readMps(const char *filename,
00655 const char *extension = "mps");
00656
00661 virtual void writeMps(const char *filename,
00662 const char *extension = "mps",
00663 double objSense=0.0) const;
00665
00666
00667
00670
00671 VOL_problem* volprob() { return &volprob_; }
00673
00674
00675
00678
00679 OsiVolSolverInterface ();
00680
00682 virtual OsiSolverInterface * clone(bool copyData = true) const;
00683
00685 OsiVolSolverInterface (const OsiVolSolverInterface &);
00686
00688 OsiVolSolverInterface & operator=(const OsiVolSolverInterface& rhs);
00689
00691 virtual ~OsiVolSolverInterface ();
00693
00694
00695
00696 protected:
00698
00699
00700 virtual void applyRowCut(const OsiRowCut& rc);
00701
00703 virtual void applyColCut(const OsiColCut& cc);
00705
00706
00707
00708 private:
00711
00712 virtual int compute_rc(const VOL_dvector& u, VOL_dvector& rc);
00714 virtual int solve_subproblem(const VOL_dvector& dual,
00715 const VOL_dvector& rc,
00716 double& lcost, VOL_dvector& x, VOL_dvector& v,
00717 double& pcost);
00720 virtual int heuristics(const VOL_problem& p,
00721 const VOL_dvector& x, double& heur_val) {
00722 heur_val = DBL_MAX;
00723 return 0;
00724 }
00726
00727
00728
00729 private:
00733 void updateRowMatrix_() const;
00735 void updateColMatrix_() const;
00736
00739 void checkData_() const;
00742 void compute_rc_(const double* u, double* rc) const;
00744 void gutsOfDestructor_();
00745
00748 void rowRimAllocator_();
00751 void colRimAllocator_();
00752
00754 void rowRimResize_(const int newSize);
00756 void colRimResize_(const int newSize);
00757
00759 void convertBoundsToSenses_();
00761 void convertSensesToBounds_();
00762
00764 bool test_zero_one_minusone_(const CoinPackedMatrix& m) const;
00766
00767
00768
00769 private:
00770
00771
00775
00776 mutable bool rowMatrixCurrent_;
00778 mutable CoinPackedMatrix rowMatrix_;
00780 mutable bool colMatrixCurrent_;
00782 mutable CoinPackedMatrix colMatrix_;
00784
00785
00788
00789 bool isZeroOneMinusOne_;
00791 OsiVolMatrixOneMinusOne_* rowMatrixOneMinusOne_;
00793 OsiVolMatrixOneMinusOne_* colMatrixOneMinusOne_;
00795
00796
00799
00800 double *colupper_;
00802 double *collower_;
00804 bool *continuous_;
00806 double *rowupper_;
00808 double *rowlower_;
00810 char *rowsense_;
00812 double *rhs_;
00815 double *rowrange_;
00817 double *objcoeffs_;
00819
00820
00822 double objsense_;
00823
00824
00827
00828 double *colsol_;
00830 double *rowprice_;
00832 double *rc_;
00834 double *lhs_;
00836 double lagrangeanCost_;
00838
00839
00842 double *rowpriceHotStart_;
00843
00845 int maxNumrows_;
00847 int maxNumcols_;
00848
00850 VOL_problem volprob_;
00851 };
00852
00853
00861 void
00862 OsiVolSolverInterfaceUnitTest(const std::string & mpsDir, const std::string & netlibDir);
00863
00864 #endif