00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
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
00025 class DecompApp;
00026 class ClpModel;
00027
00028
00029 #include "OsiSolverInterface.hpp"
00030 #include "DecompConstants.h"
00031
00032
00033
00034
00035
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;
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
00071
00072
00073 map<int, OsiSolverInterface*> m_subprobSI;
00074
00075
00076 OsiSolverInterface* m_masterSI;
00077
00078 #ifdef __DECOMP_LP_CLP__
00079
00080
00081 ClpModel* m_masterCLP;
00082 #endif
00083
00084
00085
00086
00087
00088
00089 DecompVarList m_vars;
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;
00098
00099 double* m_xhat;
00100
00101
00102
00103 vector<DecompSolution*> m_xhatIPFeas;
00104 DecompSolution* m_xhatIPBest;
00105
00106 int m_numOrigCols;
00107
00108 vector< vector<double> > m_optPoint;
00109
00110
00111 double* m_piEstimate;
00112 vector<bool> isStab;
00113
00114 public:
00115
00116 DecompConstraintSet* m_modelCore;
00117 DecompConstraintSet* m_modelRelax;
00118
00119 DecompStats m_stats;
00120
00121 public:
00122
00123 OsiSolverInterface* initSolverInterface();
00124
00125
00126 void startupLog();
00127 void initSetup(int whichModel = 1);
00128
00129
00130
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
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
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
00198
00199
00200
00201
00202 virtual void createMasterProblem(DecompVarList& initVars) = 0;
00203
00204
00205
00206
00207
00208 virtual decompStat solutionUpdate(const decompPhase phase,
00209 const int maxInnerIter,
00210 const int maxOuterIter);
00211
00212
00213 virtual decompPhase phaseUpdate(const decompPhase phase,
00214 const decompStat stat);
00215
00216 public:
00217
00218
00219
00220
00221
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];
00249
00250 }
00251 virtual const char* getRowSense() const {
00252 return &m_modelCore->rowSense[0];
00253
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
00266
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
00279
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
00292 virtual void addCutsToPool(const double* x,
00293 DecompCutList& newCuts,
00294 int& n_newCuts);
00295 virtual int addCutsFromPool();
00296
00297
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
00304
00305
00306
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),
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
00373
00374
00375
00376 UtilDeleteListPtr(m_cuts);
00377 UtilDeleteListPtr(m_vars);
00378
00379
00380
00381
00382 };
00383 };
00384
00385 #endif
00386