OBOE 0.1
Manager.h
Go to the documentation of this file.
00001 // Copyright (c) 2004-2007 University of Geneva, HEC, Logilab
00002 //
00003 // OBOE is published under the Common Public License.
00004 //
00005 // Authors :
00006 // Nidhi Sawhney <nsawhney@yahoo.com>
00007 // The OBOE team
00008 //
00009 
00010 #ifndef MANAGER_H
00011 #define MANAGER_H
00012 
00013 #include "AccpmDynMatrix.h"
00014 #include "Parameters.h"
00015 #include "ExitCode.h"
00016 #include "AccpmGenMatrix.h"
00017 
00018 #include <map>
00019 using std::map;
00020 
00021 #ifdef SERIALIZATION
00022 #include <boost/archive/text_iarchive.hpp>
00023 #include <boost/archive/text_oarchive.hpp>
00024 #include <boost/serialization/base_object.hpp>
00025 #endif
00026 
00037 namespace Accpm 
00038 {
00039  
00045   class PointGen {
00046   
00047   public :
00048     PointGen(const Parameters &param);
00049     ~PointGen() {};
00050     void setRho(double rho) { _rho = rho; }
00051 
00052     void updateATQA(SymmetricMatrix &H);
00053 
00054     AccpmVector _s;
00055     AccpmVector _sOld;
00056     AccpmVector _ds;
00057     AccpmVector _x;
00058     AccpmVector _xScaled;
00059     
00060     double _ws;// Ref GAC: omega
00061     double _zs; // Ref GAC: tau
00062     double _ss; // Ref: GAC: sigma
00063     AccpmVector _q;
00064     double _rho; // Ref: MATLAB code to replace PointGenS.rhoOld
00065     AccpmGenMatrix _ATQA; 
00066 
00067 #ifdef SERIALIZATION
00068 
00069     friend class boost::serialization::access;
00070     template<class Archive> 
00071       void serialize(Archive &ar, const unsigned int file_version)
00072       {
00073     ar & _s;
00074     ar & _sOld;
00075     ar & _ds;
00076     ar & _x;
00077     ar & _xScaled;
00078     ar & _ws & _zs & _ss & _q & _rho;
00079       }
00080 #endif
00081   };
00082 
00083    typedef std::pair<const AccpmVector *, int> AccpmVectorIntPair;
00089   class Manager {
00090  
00091  
00092 #ifdef SERIALIZATION
00093     friend class boost::serialization::access;
00094     template<class Archive> 
00095       void save(Archive &ar, const unsigned int file_version) const
00096       {
00097     std::cout << "Serializing Manager..." << std::endl;
00098     ar & _phase2 & _prevPhase2;
00099     ar & _rho & _objectiveFunction & _objLB & _objUB;
00100     ar & _relativeGap & _weightEpigraphCut;
00101     ar & _currentPointy & _bestPointy & _currentPointz;
00102     ar & _rhsCoef & _subProblemIndex & _cutOccurrence &_activeCutNorm;
00103     ar & _activeCuts;
00104     ar & _pointGen;
00105     ar & _sizeOfs & _numCuts & _hasSmoothOracle;
00106       }
00107 
00108     template<class Archive> 
00109       void load(Archive &ar, const unsigned int file_version)
00110       {
00111     std::cout << "Unserializing Manager..." << std::endl;
00112     ar & _phase2 & _prevPhase2;
00113     ar & _rho & _objectiveFunction & _objLB & _objUB;
00114     ar & _relativeGap & _weightEpigraphCut;
00115     ar & _currentPointy & _bestPointy & _currentPointz;
00116     ar & _rhsCoef & _subProblemIndex & _cutOccurrence & _activeCutNorm;
00117     ar & _activeCuts;
00118     ar & _pointGen;
00119     ar & _sizeOfs & _numCuts & _hasSmoothOracle;
00120     postprocess();
00121       }
00122 
00123     BOOST_SERIALIZATION_SPLIT_MEMBER()
00124 
00125     virtual void postprocess() {
00126       _activeCutsM = _activeCuts.getM();
00127       assert (_numCuts == _activeCutsM.size(1));
00128       assert (_numCuts == _subProblemIndex.size());
00129       assert (_numCuts == _cutOccurrence.size());
00130       assert (_numCuts == _rhsCoef.size());
00131       for (int i = 0; i < _numCuts; ++i) {
00132     AccpmVector *cut = new AccpmVector(_activeCutsM.getColumn(i));
00133     AccpmVectorIntPair *cutp = new AccpmVectorIntPair(cut,(int) _subProblemIndex(i));
00134     _cutSet[cutp] = ++_currentCutId;
00135       }
00136     }
00137 
00138 #endif
00139      
00140   protected:
00141     
00142     struct ltAccpmVectorPair
00143     {
00144       bool findFirstSmallerIndex(const AccpmVector *v1, const AccpmVector *v2) const
00145       {
00146         for (int i = 0; i < v1->size(); ++i) {
00147           if (DBL_LT((*v1)(i), (*v2)(i))) {
00148             return true;
00149           }
00150           if (DBL_LT((*v2)(i), (*v1)(i))) {
00151             return false;
00152           }
00153         }
00154         return false;
00155       }
00156 
00157       bool operator()(const AccpmVectorIntPair *v1, const AccpmVectorIntPair *v2) const
00158       {
00159           //check the subproblem index
00160           int v1s = v1->second;
00161           int v2s = v2->second;
00162           
00163           if (v1s < v2s) {
00164             return true;
00165           }
00166           if (v1s > v2s) {
00167             return false;
00168           }
00169           v1s = v1->first->size();
00170           v2s = v2->first->size();
00171 
00172           if (v1s < v2s) {
00173             return true;
00174           }
00175           if (v1s > v2s) {
00176             return false;
00177           }
00178           return findFirstSmallerIndex(v1->first, v2->first);
00179       }
00180     };
00181    
00182     typedef map<const AccpmVectorIntPair *, int,  ltAccpmVectorPair> CutSet;  
00183     const Parameters *_param;
00184 
00185     bool _phase2;
00186     bool _prevPhase2;
00187     bool _currentPointIsFeasible;
00192     int _numOuterIteration; 
00193     
00200     int _numInnerIteration; // It is the total number of inner iterations
00201     
00202     ExitCode _exitCode;
00203     double _rho;
00204     double _objectiveFunction;
00205     double _objLB;
00206     double _objUB;
00207     double _relativeGap;
00208     double _weightEpigraphCut;
00209 
00210     AccpmVector _currentPointy;
00211     AccpmVector _bestPointy;
00212     AccpmVector _currentPointz;
00213     
00214     AccpmVector _rhsCoef;
00215     AccpmVector _subProblemIndex;
00216     AccpmVector _cutOccurrence;
00217     AccpmVector  _activeCutNorm;
00218     AccpmDynMatrix _activeCuts;
00219     AccpmGenMatrix _activeCutsM;
00220     PointGen _pointGen;
00221     
00222     double _f2; //smoothObjFunctionVal;
00223     AccpmVector *_b; 
00224     AccpmVector *_df2; //smoothGrad; 
00225     AccpmGenMatrix *_d2f2; // smoothHessian;
00226     //bool _diagHessian;
00227 
00228     int _sizeOfs;
00229     int _numCuts;
00230     bool _hasSmoothOracle;
00231 
00232     /*
00233      * Hash for the cuts to help filtering duplicate cuts
00234      */
00235     CutSet _cutSet;
00236     int _currentCutId;
00237 
00238     virtual void init(void);
00239     virtual void update();
00240     virtual double convexityFix(const AccpmVector &functionValue,const AccpmGenMatrix &subGradients, 
00241             const AccpmVector &subProblemIndex,
00242             const AccpmVector &upperFunctionValues);
00243     virtual void updateRhs(const AccpmVector &functionValue, const AccpmGenMatrix &subGradients);
00244     virtual void updateRho(void);
00245     virtual void updateEpigraphWeight(void);
00246     
00247     virtual int addCut(const AccpmVectorIntPair *cut, int subProblemIndex, double weight, double rhs);
00248     int findCut(const AccpmVectorIntPair &v) const;
00249     virtual int processCuts(const AccpmVector &functionValue, const AccpmGenMatrix &newCuts, 
00250             const AccpmVector &subProblemIndex, const AccpmVector &upperFunctionValues);
00251     virtual void updateQ();
00252     void updateRelativeGap();
00253 
00254   public:
00255     Manager(const Parameters *param);
00256     virtual ~Manager();
00257     virtual const AccpmVector& getCurrentY() const;
00258     virtual const AccpmVector& getActiveY() const;
00259     virtual int getActiveCuts(AccpmGenMatrix &cuts, bool activeVar = false) const;
00260     virtual int getActiveCuts(const AccpmGenMatrix *&cuts, bool activeVar = false) const;
00261 
00262     virtual const AccpmVector& getBestY(bool activeVar = false) const;
00263     inline const AccpmVector& getCurrentZ() const { return _currentPointz; }
00264     inline const AccpmVector& getRhsCoef() const { return _rhsCoef; }
00265     inline const AccpmVector& getSubProblemIndex() const { return _subProblemIndex; }
00266     inline const AccpmVector& getCutOccurrence() const { return _cutOccurrence; }
00267     inline const AccpmVector& getActiveCutNorm() const { return _activeCutNorm; }
00268 
00269     inline const AccpmVector& getCurrentX() const { return _pointGen._xScaled; }
00270            
00271     inline PointGen &getPointGen() { return _pointGen; }
00272     inline const PointGen &getPointGen() const { return _pointGen; }
00273     inline const AccpmGenMatrix &getATQA() const { return _pointGen._ATQA; }
00274     inline AccpmGenMatrix &getATQA() { return _pointGen._ATQA; }
00275     
00276     inline double getObjLB() const { return _objLB; }
00277     inline double getObjUB() const { return _objUB; }
00278     double getRelativeGap() const;
00279 
00280     inline double getWtEpigraphCut() const { return _weightEpigraphCut; }
00281 
00282     virtual double getSmoothObj(bool activeVar = false) const;
00283     virtual const AccpmVector *getSmoothGradient(bool activeVar = false) const;
00284     virtual const AccpmGenMatrix *getSmoothHessian(bool activeVar = false) const;
00285      
00286     inline bool inPhase2() const { return _phase2; }
00287     inline bool previousPhase2() const { return _prevPhase2; }
00288     inline void updatePreviousPhase2() { _prevPhase2 = _phase2; }
00289     inline bool isCurrentPointFeasible() const { return _currentPointIsFeasible; }
00290     inline ExitCode getExitCode() const { return _exitCode; }
00291     inline void setExitCode(ExitCode e) { _exitCode = e; }
00292    
00293     inline double getRho() const { return _rho; }
00294     inline int getSizeOfs() const { return _sizeOfs; }
00295     inline void setSizeOfs(int n) { _sizeOfs = n; }
00296     
00297     virtual int update1(const AccpmVector &functionValue, const AccpmGenMatrix &subGradients, 
00298         const AccpmGenMatrix &subProblemIndex,
00299         const AccpmVector *upperFunctionValues = 0);
00300     virtual int update2(double functionValue, const AccpmGenMatrix &subGradients, 
00301         const AccpmGenMatrix &hessian);
00302     
00303     double computeBallConstraint(const AccpmVector &y) const;
00304     void computeBallConstraint(const AccpmVector &y, AccpmVector &result) const;
00305     void computeBox1Constraint(const AccpmVector &y, AccpmVector &result) const;
00306     void computeBox2Constraint(const AccpmVector &y, AccpmVector &result) const;
00307     
00308     virtual void updateVariables(const AccpmVector &y, const AccpmVector &z, const AccpmVector &s,
00309                  double zs, double s0, double ss,
00310                  const AccpmVector &sOld, double sOld0,
00311                  const AccpmVector &ds, double ds0);
00312     virtual void updateY(const AccpmVector &y);
00313 
00314     int getNumOuterIteration() const { return _numOuterIteration; }
00315 
00316     void updateInnerIterations(int n) { _numInnerIteration += n; }
00317     int getNumInnerIterations() const { return _numInnerIteration; }
00318 
00319     virtual void updateLB(double lBound);
00320 
00321     virtual const AccpmVector *getVariableLB(bool activeVar = false) const;
00322     virtual const AccpmVector *getVariableUB(bool activeVar = false) const;
00323     virtual const AccpmVector *getB(bool activeVar = false) const; 
00324     virtual const AccpmVector *getCenterBall(bool activeVar = false) const; 
00325     virtual double getRadiusBall() const;
00326 
00327     virtual const AccpmVector *getQ(bool activeVar = false) const;
00328     virtual int computeSmoothComponent(bool hessian = true);
00329     int callSmoothOracle(const AccpmVector &y, double &f2, 
00330              AccpmVector &df2, AccpmGenMatrix *d2f2) const;
00331 
00332     virtual void updateActiveVariables();
00333     virtual void updateActiveVariablesForF2();
00334 
00335     virtual int getNumCuts() const;
00336     
00337     virtual void output(std::ostream &os) const;
00338        
00339     void check();
00340   };
00341 }
00342 
00343 #endif