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

- File List
- File Members

# /home/coin/SVN-release/Osi-0.98.1/Osi/src/OsiVol/OsiVolSolverInterface.hpp

Go to the documentation of this file.

    00001 // Copyright (C) 2000, International Business Machines
    00002 // Corporation and others.  All Rights Reserved.
    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     // Set an integer parameter
    00083     bool setIntParam(OsiIntParam key, int value);
    00084     // Set an double parameter
    00085     bool setDblParam(OsiDblParam key, double value);
    00086     // Set a string parameter
    00087     bool setStrParam(OsiStrParam key, const std::string & value);
    00088     // Get an integer parameter
    00089     bool getIntParam(OsiIntParam key, int& value) const;
    00090     // Get an double parameter
    00091     bool getDblParam(OsiDblParam key, double& value) const;
    00092     // Get a string parameter
    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         // This does not pass unitTest if getObjValue is called before solve
    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