DecompAlgo.h

Go to the documentation of this file.
00001 //===========================================================================//
00002 // This file is part of the Decomp Solver Framework.                         //
00003 //                                                                           //
00004 // Decomp is distributed under the Common Public License as part of the      //
00005 // COIN-OR repository (http://www.coin-or.org).                              //
00006 //                                                                           //
00007 // Author: Matthew Galati, Lehigh University                                 //
00008 //                                                                           //
00009 // Copyright (C) 2002-2007, Lehigh University, Matthew Galati, and Ted Ralphs//
00010 // All Rights Reserved.                                                      //
00011 //===========================================================================//
00012 
00013 #ifndef DECOMP_ALGO_INCLUDED
00014 #define DECOMP_ALGO_INCLUDED
00015 
00016 #define EXPLICIT_BOUNDS
00017 
00018 #include "DecompConstraintSet.h"
00019 #include "DecompSolution.h"
00020 #include "DecompMemPool.h"
00021 #include "DecompVarPool.h"
00022 #include "DecompCutPool.h"
00023 #include "DecompStats.h"
00024 //class DecompStats;
00025 class DecompApp;
00026 class ClpModel;
00027 
00028 
00029 #include "OsiSolverInterface.hpp"
00030 #include "DecompConstants.h"
00031 
00032 //TODO: bundle????
00033 //TODO:
00034 // logfile for app, algo separate? as well as possible to combine?
00035 // might be better just to point this log file to the app log file
00036 
00037 
00038 
00039 // --------------------------------------------------------------------- //
00040 class DecompAlgo {
00041 private:
00042    DecompAlgo(const DecompAlgo&);
00043    DecompAlgo& operator=(const DecompAlgo&);
00044 
00045 private:
00046    static const char* m_classTag;
00047    static const char* versionTag;
00048    decompAlgoType      m_algo;     //"who am i"
00049 
00050 protected:
00051    DecompMemPool         m_auxMemPool;
00052    DecompApp*            m_app;
00053 
00054    int                   m_nodeIndex;
00055    int                   m_whichModel;
00056    int                   m_whichCoreModel;
00057    int                   m_priceCallsRound;
00058    int                   m_priceCallsTotal;
00059    int                   m_cutCallsRound;
00060    int                   m_cutCallsTotal;
00061    int                   m_varsThisRound;
00062    int                   m_cutsThisRound;
00063    int                   m_varsThisCall;
00064    int                   m_cutsThisCall;
00065 
00066    int                   m_isTightenAlgo;
00067 
00068    ostream*              m_osLog;
00069 
00070    //THINK: naming outer, inner?? - will work across all?
00071 
00072    //solver interface for subproblem (P')
00073    map<int, OsiSolverInterface*>   m_subprobSI;
00074 
00075    //solver interface for master (Q")
00076    OsiSolverInterface*           m_masterSI;
00077 
00078 #ifdef __DECOMP_LP_CLP__
00079    //THINK: so we don't freecached when getModelPtr - do once...
00080    //makes it so that we are stuck with CLP - also need to support CPX
00081    ClpModel*                     m_masterCLP;
00082 #endif
00083 
00084 
00085    //m_vars and m_cuts have no destructor, but they are list of ptrs
00086    //the memory they point to needs to be deleted.
00087 
00088    //member of app or member of algo?
00089    DecompVarList           m_vars;          //list of vars added to master
00090    DecompVarList           m_initVars;
00091    DecompCutList           m_cuts;
00092    DecompVarPool           m_varpool;
00093    DecompCutPool           m_cutpool;
00094 
00095    double                  m_tlb;
00096    double                  m_tub;
00097    double                  m_bestUpperBound;//known opt
00098 
00099    double*                   m_xhat;
00100 
00101    //think about do we want a solution pool?
00102    //for now, just keep the best and toss the rest
00103    vector<DecompSolution*>   m_xhatIPFeas;
00104    DecompSolution*           m_xhatIPBest;
00105 
00106    int m_numOrigCols; //DECOMP
00107 
00108    vector< vector<double> > m_optPoint;
00109 
00110    //stabilization techniques
00111    double* m_piEstimate;
00112    vector<bool> isStab;
00113 
00114 public:
00115    //these are just pointers into app
00116    DecompConstraintSet* m_modelCore;
00117    DecompConstraintSet* m_modelRelax;
00118 
00119    DecompStats           m_stats;
00120 
00121 public:
00122    //helper functions
00123    OsiSolverInterface* initSolverInterface();
00124 
00125    //TODO: functions in alphabetical order??
00126    void   startupLog();
00127    void   initSetup(int whichModel = 1);
00128 
00129    //void   solve(DecompApp * app,
00130    //             int         whichModel = 1);
00131    void   tighten(int whichModel);
00132    void   solve(int whichModel = 1);
00133 
00134    inline double   getTrueLowerBound() {
00135       return m_tlb;
00136    }
00137    inline double   getTrueUpperBound() {
00138       return m_tub;
00139    }
00140 
00141    //TODO: should not call these LB UB
00142    void   setTrueLowerBound(const double mostNegReducedCost);
00143    void   setTrueUpperBound(const double ub) {
00144       m_tub = ub;
00145    };
00146    double calcConstant(const int      m,
00147                        const double* u);
00148 
00149    //helper functions - DecompDebug.cpp
00150    bool isDualRayInfProof(const double*            dualRay,
00151                           const CoinPackedMatrix* rowMatrix,
00152                           const double*            colLB,
00153                           const double*            colUB,
00154                           const double*            rowRhs,
00155                           ostream*                 os     = 0);
00156    void printBasisInfo(OsiSolverInterface* si,
00157                        ostream*             os);
00158    void printCurrentProblem(const OsiSolverInterface* si,
00159                             const string               baseName,
00160                             const int                  nodeIndex,
00161                             const int                  cutPass,
00162                             const int                  pricePass,
00163                             const bool                 printMps   = true,
00164                             const bool                 printLp    = true);
00165    void printCurrentProblem(const OsiSolverInterface* si,
00166                             const string               fileName,
00167                             const bool                 printMps   = true,
00168                             const bool                 printLp    = true);
00169 
00170    void   printVars(ostream* os = &cout);
00171    void   printCuts(ostream* os = &cout);
00172 
00173    void   solveBruteForce();
00174    void   createFullMps(const string filename);
00175    vector<double*> getDualRays(int maxNumRays);
00176 
00177    inline void setApp(DecompApp* app) {
00178       m_app = app;
00179    }
00180 
00181 
00182    inline void setBestUpperBound(const double bestUpperBound) {
00183       m_bestUpperBound = bestUpperBound;
00184    }
00185 
00186    decompStat solveRelaxed(const int             whichModel,
00187                            const double*         redCostX,
00188                            const double*         origCost,
00189                            const double          alpha,
00190                            const int             n_origCols,
00191                            const bool            checkRC,
00192                            const bool            checkDup,
00193                            OsiSolverInterface*   m_subprobSI,
00194                            list<DecompVar*>    & vars);
00195 
00196 public:
00197    //pure virtual methods
00198 
00199 
00200 
00201 
00202    virtual void createMasterProblem(DecompVarList& initVars) = 0;
00203 
00204    //possible base is enough here too... think at least for PC and C
00205    //seem to be ok
00206 
00207    //just base is enough for PC and C here
00208    virtual decompStat solutionUpdate(const decompPhase phase,
00209                                      const int         maxInnerIter,
00210                                      const int         maxOuterIter);
00211 
00212    //just base is enough?
00213    virtual decompPhase phaseUpdate(const decompPhase   phase,
00214                                    const decompStat    stat);
00215 
00216 public:
00217    //virtual methods
00218    //all this mess, just so that we don't use m_masterSI for RC??
00219    //doesn't make alot of sense to me... THINK
00220 
00221    //just feed u vector in rowPrice in OSI???
00222 
00223    virtual void setMasterBounds(const double* lbs,
00224                                 const double* ubs);
00225 
00226    OsiSolverInterface* getMasterSolverInterface() {
00227       return m_masterSI;
00228    }
00229 
00230    virtual const double* getRowPrice() const {
00231       return m_masterSI->getRowPrice();
00232    }
00233 
00234    inline const double* getX() {
00235       return m_xhat;
00236    }
00237 
00238    inline DecompApp* getApp() {
00239       return m_app;
00240    }
00241 
00242    inline const DecompSolution* getXhatIPBest() {
00243       return m_xhatIPBest;
00244    }
00245 
00246 #if 1
00247    virtual const double* getRightHandSide() const {
00248       return &m_modelCore->rowRhs[0];//THINK
00249       //return m_masterSI->getRightHandSide();
00250    }
00251    virtual const char* getRowSense() const {
00252       return &m_modelCore->rowSense[0];//THINK - should be SI?
00253       //return m_masterSI->getRowSense();
00254    }
00255 #endif
00256 
00257    int heuristics(const double*             xhat,
00258                   vector<DecompSolution*> & xhatIPFeas);
00259 
00260    virtual int generateVars(const decompStat   stat,
00261                             DecompVarList&     newVars,
00262                             double&            mostNegReducedCost);
00263    virtual int generateCuts(DecompCutList& newCuts);
00264 
00265    //different name? set x vector? and maybe base just memcpy
00266    //while PC does recompose then copies in?
00267    virtual void recomposeSolution(const double* solution,
00268                                   double*        rsolution) {
00269       printf("\nbase recomposeSolution does nothing.");
00270    };
00271 
00272    virtual int  generateInitVars(DecompVarList& initVars);
00273    virtual bool isDone() {
00274       return false;
00275    };
00276 
00277 
00278    //will never get called in C, yet PC specific, do nothing in base
00279    //and move to PC?
00280    void addVarsToPool(DecompVarList& newVars);
00281    void addVarsFromPool();
00282 
00283 
00284    bool isIPFeasible(const double* x,
00285                      const double   feasTol = 1.0e-4,
00286                      const double   intTol  = 1.0e-4);
00287    bool isLPFeasible(const double* x,
00288                      const double   feasTol = 1.0e-4);
00289 
00290 
00291    //different for C and PC, pure virtual for now
00292    virtual void addCutsToPool(const double*    x,
00293                               DecompCutList& newCuts,
00294                               int&            n_newCuts);
00295    virtual int addCutsFromPool();
00296 
00297    //DecompBranch.cpp
00298    int chooseBranchVar(int&     branchedOnIndex,
00299                        double& branchedOnValue);
00300    virtual int branch(int    branchedOnIndex,
00301                       double branchedOnValue);
00302    decompStat processNode(const int nodeIndex = 0);
00303    //process node? or just process?
00304 
00305 
00306    /*helper functions*/
00307    inline void appendVars(DecompVar* var) {
00308       m_vars.push_back(var);
00309    }
00310    inline void appendVars(DecompVarList& varList) {
00311       copy(varList.begin(), varList.end(), back_inserter(m_vars));
00312 #if 0
00313 
00314       if (m_vars.empty()) {
00315          m_vars = varList;
00316       } else {
00317          m_vars.insert(m_vars.end(), varList.begin(), varList.end());
00318       }
00319 
00320 #endif
00321    }
00322 
00323 
00324 
00325 public:
00326    DecompAlgo(const decompAlgoType   algo,
00327               DecompApp*             app) :
00328       m_algo(algo),
00329       m_auxMemPool(),
00330       m_app(app),
00331       m_whichModel(-1),
00332       m_whichCoreModel(-1),
00333       m_nodeIndex(0),
00334       m_priceCallsRound(0),
00335       m_priceCallsTotal(0),
00336       m_cutCallsRound(0),
00337       m_cutCallsTotal(0),
00338       m_varsThisRound(0),
00339       m_cutsThisRound(0),
00340       m_varsThisCall(0),
00341       m_cutsThisCall(0),
00342       m_isTightenAlgo(0),
00343       m_osLog(&cout),//TODO
00344       m_masterSI(0),
00345       m_vars(),
00346       m_initVars(),
00347       m_cuts(),
00348       m_varpool(),
00349       m_cutpool(),
00350       m_tlb(-DecompInf),
00351       m_tub( DecompInf),
00352       m_bestUpperBound(DecompInf),
00353       m_xhat(0),
00354       m_xhatIPBest(0),
00355       m_piEstimate(0) {
00356       (*m_osLog).setf(ios::fixed);
00357    };
00358 
00359    virtual ~DecompAlgo() {
00360       map<int, OsiSolverInterface*>::iterator it;
00361 
00362       for (it = m_subprobSI.begin();
00363             it != m_subprobSI.end(); it++) {
00364          if (it->second) {
00365             UTIL_DELPTR(it->second);
00366          }
00367       }
00368 
00369       UTIL_DELPTR(m_masterSI);
00370       UTIL_DELARR(m_xhat);
00371       UtilDeleteVectorPtr(m_xhatIPFeas);
00372       //THINK - if was class, the std::list<T*> would be cleaner?
00373       //let T's destructor do the work? the way cutpool manages that?
00374       //should m_cuts and m_vars be pools anyway? vector to waiting row
00375       //or list of waiting row pts?
00376       UtilDeleteListPtr(m_cuts);
00377       UtilDeleteListPtr(m_vars);
00378       //THINK - m_initVars always (?) gets pushed into m_vars -
00379       //so if we free here we'll double free?
00380       //UtilDeleteListPtr(m_initVars);
00381       //?? who deletes m_var, m_cuts????
00382    };
00383 };
00384 
00385 #endif
00386 

Generated on 12 Feb 2015 for Dip-All by  doxygen 1.6.1