Dip-All  0.91.0
DecompAlgo.h
Go to the documentation of this file.
1 //===========================================================================//
2 // This file is part of the DIP Solver Framework. //
3 // //
4 // DIP is distributed under the Eclipse Public License as part of the //
5 // COIN-OR repository (http://www.coin-or.org). //
6 // //
7 // Author: Matthew Galati, SAS Institute Inc. (matthew.galati@sas.com) //
8 // //
9 // Conceptual Design: Matthew Galati, SAS Institute Inc. //
10 // Ted Ralphs, Lehigh University //
11 // //
12 // Copyright (C) 2002-2015, Lehigh University, Matthew Galati, Ted Ralphs //
13 // All Rights Reserved. //
14 //===========================================================================//
15 
16 
17 //thinking about design - PC/C - most everything is driven by OSI methods
18 //but RC is not, this actually doesn't need OSI at all - either use OsiNull
19 //or, split up there types...
20 
21 //DecompAlgo
22 // now will have a data member DecompInterface * interface
23 // which is allocated to be a DecompOsi or DecompNull depending
24 // on which algo we are talking about
25 // this might also be a way to use Vol directly....
26 
27 
28 //DecompInterface - base class
29 // DecompOsi : public DecompInterface -->
30 // wrapper for all OSI methods (with OSI)
31 // DecompNull : public DecompInterface -->
32 // wrapper for all OSI methods in RC (no OSI)
33 
34 //===========================================================================//
35 #ifndef DecompAlgo_h_
36 #define DecompAlgo_h_
37 
38 //===========================================================================//
44 //===========================================================================//
45 
46 //===========================================================================//
47 #include "Decomp.h"
48 #include "DecompApp.h"
49 #include "DecompParam.h"
50 #include "DecompStats.h"
51 #include "DecompVarPool.h"
52 #include "DecompCutPool.h"
53 #include "DecompMemPool.h"
54 #include "DecompSolution.h"
55 #include "DecompAlgoCGL.h"
56 #include "AlpsDecompTreeNode.h"
58 class OsiSolverInterface;
60 class DecompSolverResult;
61 
62 //===========================================================================//
63 class DecompAlgo {
64 
65 protected:
66 
67  //----------------------------------------------------------------------//
72  //----------------------------------------------------------------------//
76  std::string m_classTag;
77 
82 
87 
92 
97  DecompPhase m_phaseLast;//just before done
99 
104 
110 
115 
119  std::ostream* m_osLog;
120 
122 
128  std::vector<double> m_origColLB;
129  std::vector<double> m_origColUB;
130 
134  //vector<OsiSolverInterface*> m_subprobSI;
135 
143 
144 #ifdef __DECOMP_IP_SYMPHONY__
145  OsiSymSolverInterface* osi_Sym;
146  CoinWarmStart* ws;
147 #endif
148 
157 
158 
159  const double* m_objective;
161  std::map<int, DecompAlgoModel> m_modelRelax;
162  std::map<int, std::vector<DecompAlgoModel> > m_modelRelaxNest;
163 
164 
170 
176 
180  double* m_xhat;
181 
186  double m_cutoffUB;
187  //THINK - use solution pool
188  std::vector<DecompSolution*> m_xhatIPFeas;
190 
191 
192  //for cpx
193  std::vector<double> m_primSolution;
194  std::vector<double> m_dualSolution;
195  std::vector<double> m_reducedCost;
197 
199 
201 
203 
204  //for round robin
207 
208  //
210 
211  //all these are related to master LP - make object
216  std::vector<DecompRowType> m_masterRowType;
217  std::vector<DecompColType> m_masterColType;
218  std::vector<int> m_masterArtCols;
219 
220  //to enforce in subproblems
221  double* m_colLBNode;
222  double* m_colUBNode;
223 
226 
230  double m_relGap;
231 
234  double m_masterObjLast;//last master obj
236 
237 
240  std::map<int, int> m_artColIndToRowInd;
241 
242  double m_globalLB;
243  double m_globalUB;
244 
245  std::vector<double> m_phaseIObj;
246 
247  int m_function;//calling function
250 
252 
253  std:: vector<int> m_masterOnlyCols;
257  std::map<int, int> m_masterOnlyColsMap;
258 
259  // used for setting time limit to solving MIP subproblem
261 
262  // variable dictating whether the branching is implemented
263  // in the master problem or the subproblem
264 
266 
267 
268 
269 public:
273  //-----------------------------------------------------------------------//
278  //-----------------------------------------------------------------------//
282  //virtual void createMasterProblem(DecompVarList & initVars) = 0;
283  virtual void createMasterProblem(DecompVarList& initVars);
285  //need next 2 args? ever different?
286  //DecompAlgoModel & modelCore,
287  //map<int, DecompAlgoModel> & modelRelax,
288  bool doInt = false);
289 
290 
296  //not pure?
297  virtual void recomposeSolution(const double* solution,
298  double* rsolution);
303  //-----------------------------------------------------------------------//
308  //-----------------------------------------------------------------------//
312  virtual DecompStatus processNode(const AlpsDecompTreeNode* node,
313  const double globalLB = -DecompInf,
314  const double globalUB = DecompInf);
315 
321  return m_curNode;
322  };
323 
329  virtual void postProcessNode(DecompStatus decompStatus) {};
330 
336  virtual void postProcessBranch(DecompStatus decompStatus) {};
337 
342  //THINK: belongs in base? PC or...
343  virtual int generateInitVars(DecompVarList& initVars);
344 
348  virtual DecompStatus
349  solutionUpdate(const DecompPhase phase,
350  const bool resolve = true,
351  const int maxInnerIter = COIN_INT_MAX,
352  const int maxOuterIter = COIN_INT_MAX);
353 
357  virtual void phaseUpdate(DecompPhase& phase,
358  DecompStatus& status);
359 
363  virtual void phaseInit(DecompPhase& phase) {
364  if (getNodeIndex() == 0) {
365  phase = PHASE_PRICE1;
366  }
367  }
368 
372  virtual void phaseDone() {};
373 
377  virtual bool updateObjBound(const double mostNegRC = -DecompBigNum);
378 
379 
380  virtual void solutionUpdateAsIP() {}
381 
382  virtual int adjustColumnsEffCnt() {
383  return DecompStatOk;
384  };
385  virtual int compressColumns () {
386  return DecompStatOk;
387  };
391  bool isGapTight() {
392  //TODO: make param
393  double tightGap = m_param.MasterGapLimit;
394 
395  //printf("isGapTight m_relGap = %g\n", m_relGap);
396  if (m_param.LogDebugLevel >= 2) {
397  (*m_osLog) << "DW GAP = " << UtilDblToStr(m_relGap)
398  << " isTight = " << (m_relGap <= tightGap)
399  << "\n";
400  }
401 
402  if (m_relGap <= tightGap) {
403  return true;
404  } else {
405  return false;
406  }
407  }
408 
409 
410 
411  //................................
412  //TODO............................
413  //................................
414 
415 
416 
417 
418  virtual bool isDone() {
420  return false;
421  } else {
422  return true;
423  }
424  }
425 
426  //TODO: should move out to PC
427  //THINK - helper func?, or specific to PC - right? as is genInit
428  std::vector<double*> getDualRays(int maxNumRays);
429  virtual int generateVarsFea(DecompVarList& newVars,
430  double& mostNegReducedCost);
431 
432  virtual int generateVars(const DecompStatus stat,
433  DecompVarList& newVars,
434  double& mostNegReducedCost);
435  virtual int generateCuts(double* xhat,
436  DecompCutList& newCuts);
437 
438  virtual void addVarsToPool(DecompVarList& newVars);
439  virtual void addVarsFromPool();
440  virtual void addCutsToPool(const double* x,
441  DecompCutList& newCuts,
442  int& m_cutsThisCall);
443  virtual int addCutsFromPool();
444 
445  bool isIPFeasible(const double* x,
446  const bool isXSparse = false,
447  const double feasVarTol = 1.0e-6, //0.0001%
448  const double feasConTol = 1.0e-5, //0.001%
449  const double intTol = 1.0e-5); //0.001%
450 
451  bool isLPFeasible(const double* x,
452  const bool isXSparse = false,
453  const double feasVarTol = 1.0e-6, //0.001%
454  const double feasConTol = 1.0e-5); //0.01%
455 
456  //fugly
457  DecompStatus solveRelaxed(const double* redCostX,
458  const double* origCost,
459  const double alpha,
460  const int n_origCols,
461  const bool isNested,
462  DecompAlgoModel& algoModel,
463  DecompSolverResult* solveResult,
464  std::list<DecompVar*>& vars);
465 
466 
467  inline void appendVars(DecompVar* var) {
468  m_vars.push_back(var);
469  }
470  inline void appendVars(DecompVarList& varList) {
471  copy(varList.begin(), varList.end(), back_inserter(m_vars));
472  }
473  virtual void setMasterBounds(const double* lbs,
474  const double* ubs);
475  virtual void setSubProbBounds(const double* lbs,
476  const double* ubs);
477 
478  //int chooseBranchVar(int & branchedOnIndex,
479  // double & branchedOnValue);
480  virtual bool
481  chooseBranchSet(std::vector< std::pair<int, double> >& downBranchLb,
482  std::vector< std::pair<int, double> >& downBranchUb,
483  std::vector< std::pair<int, double> >& upBranchLb,
484  std::vector< std::pair<int, double> >& upBranchUb);
485 
486 
487 
488 
489  //-----------------------------------------------------------------------//
494  //-----------------------------------------------------------------------//
498  void initSetup(UtilParameters* utilParam,
499  std::string& sectionParam);
500  void getModelsFromApp();
501  void createOsiSubProblem(DecompAlgoModel& algoModel);
502 
506  /*double calculateGap(double boundLB,
507  double boundUB) const {
508  double gap = DecompInf;
509  if(boundLB > -DecompInf && boundUB < DecompInf){
510  if(boundLB != 0.0)
511  gap = fabs(boundUB-boundLB)/fabs(boundLB);
512  else
513  gap = fabs(boundUB);
514  }
515  return gap;
516  }*/
517 
518 
523  void checkMasterDualObj();
524  bool checkPointFeasible(const DecompConstraintSet* modelCore,
525  const double* x);
526  bool isDualRayInfProof(const double* dualRay,
527  const CoinPackedMatrix* rowMatrix,
528  const double* colLB,
529  const double* colUB,
530  const double* rowRhs,
531  std::ostream* os);
532  bool isDualRayInfProofCpx(const double* dualRay,
533  const CoinPackedMatrix* rowMatrix,
534  const double* colLB,
535  const double* colUB,
536  const double* rowRhs,
537  std::ostream* os);
538 
540  std::ostream* os);
541 
542 
547  const std::string baseName,
548  const int nodeIndex,
549  const int cutPass,
550  const int pricePass);
551 
553  const std::string baseName,
554  const int nodeIndex,
555  const int cutPass,
556  const int pricePass,
557  const int blockId = -1,
558  const bool printMps = true,//false,
559  const bool printLp = true);
564  const std::string fileName,
565  const bool printMps = true,
566  const bool printLp = true);
567 
571  void printVars(std::ostream* os);
572  void printCuts(std::ostream* os);
573 
577  void createFullMps(const std::string fileName);
578 
582  virtual DecompSolverResult*
583  solveDirect(const DecompSolution* startSol = NULL) {
584  return NULL;
585  }
586 
587 
589  double* colLB,
590  double* colUB,
591  double* objCoeff,
592  std::vector<std::string>& colNames);
593 
594  void masterMatrixAddArtCol(std::vector<CoinBigIndex>& colBeg,
595  std::vector<int >& colInd,
596  std::vector<double >& colVal,
597  char LorG,
598  int rowIndex,
599  int colIndex,
600  DecompColType colType,
601  double& colLB,
602  double& colUB,
603  double& objCoeff);
604 
605  virtual void masterMatrixAddArtCols(CoinPackedMatrix* masterM,
606  double* colLB,
607  double* colUB,
608  double* objCoeff,
609  std::vector<std::string>& colNames,
610  int startRow,
611  int endRow,
612  DecompRowType rowType);
613  void masterPhaseItoII();
614  void masterPhaseIItoI();
615 
616  bool isMasterColMasterOnly(const int index) const {
617  return (m_masterColType[index] == DecompCol_MasterOnly);
618  }
619  bool isMasterColStructural(const int index) const {
620  return (m_masterColType[index] == DecompCol_Structural ||
622  }
623  bool isMasterColArtificial(const int index) const {
624  return (m_masterColType[index] == DecompCol_ArtForRowL ||
632  }
633 
634  void breakOutPartial(const double* xHat,
635  DecompVarList& newVars,
636  const double intTol = 1.0e-5);
637 
642  void generateVarsAdjustDuals(const double* uOld,
643  double* uNew);
648  void generateVarsCalcRedCost(const double* u,
649  double* redCostX);
650 
651 
652 
653 
659  //-----------------------------------------------------------------------//
664  //-----------------------------------------------------------------------//
665  inline const double* getColLBNode() const {
666  return m_colLBNode;
667  }
668  inline const double* getColUBNode() const {
669  return m_colUBNode;
670  }
671  //inline OsiSolverInterface * getSubProbSI(int b){
672  // return m_subprobSI[b];
673  //}
674 
675  inline DecompStats& getStats() {
676  return m_stats;
677  }
678 
679  inline const double* getOrigObjective() const {
680  return m_app->m_objective;
681  }
682  inline const DecompAlgoModel& getModelCore() const {
683  return m_modelCore;
684  }
685 
686  inline const int getAlgo() const {
687  return m_algo;
688  }
689 
690  inline const DecompParam& getParam() const {
691  return m_param;
692  }
693 
695  return m_param;
696  }
697 
699  return m_masterSI;
700  }
701 
702  inline DecompAlgoModel& getModelRelax(const int blockId) {
703  std::map<int, DecompAlgoModel>::iterator mit;
704  mit = m_modelRelax.find(blockId);
705  assert(mit != m_modelRelax.end());
706  return (*mit).second;
707  }
708 
709 
713  inline const double* getXhat() const {
714  return m_xhat;
715  }
716 
717  inline void setCutoffUB(const double thisBound) {
718  m_cutoffUB = thisBound;
719  setObjBoundIP(thisBound);
720  }
721 
722  //TODO
723  inline const DecompSolution* getXhatIPBest() const {
724  return m_xhatIPBest;
725  }
726 
727  inline const std::vector<DecompSolution*>& getXhatIPFeas() const {
728  return m_xhatIPFeas;
729  }
730 
731  inline const double getCutoffUB() const {
732  return m_cutoffUB;
733  }
734 
736  return m_stats;
737  }
738 
739  inline const DecompParam& getDecompParam() const {
740  return m_param;
741  }
742 
743  inline const DecompApp* getDecompApp() const {
744  return m_app;
745  }
747  return m_app;
748  }
749 
750  inline const int getNodeIndex() const {
751  return m_nodeStats.nodeIndex;
752  }
753 
754  inline const int getCutCallsTotal() const {
755  return m_nodeStats.cutCallsTotal;
756  }
757 
758  inline const int getPriceCallsTotal() const {
760  }
761 
765  inline const double* getMasterPrimalSolution() const {
766  return &m_primSolution[0];
767  }
768 
769  inline const double* getMasterColReducedCost() const {
770  return &m_reducedCost[0];
771  }
775  virtual const double* getMasterDualSolution() const {
776  return &m_dualSolution[0];
777  }
778 
782  virtual void adjustMasterDualSolution() {};
783 
784 
785  inline double getMasterObjValue() const {
786  if (!m_masterSI) {
787  return -DecompInf;
788  }
789 
790  //NOTE: be careful that this is always using the PhaseII obj
791  int nc = static_cast<int>(m_primSolution.size());
792  const double* objCoef = m_masterSI->getObjCoefficients();
793  const double* primSol = getMasterPrimalSolution();
794  double retVal = 0.0;
795 
796  for ( int i = 0 ; i < nc ; i++ ) {
797  retVal += objCoef[i] * primSol[i];
798  }
799 
800  return retVal;
801  }
802 
803  inline const int getStopCriteria() const {
804  return m_stopCriteria;
805  }
806 
810  inline const double getGlobalGap() const {
812  }
813 
817  inline const double getNodeIPGap() const {
819  }
820 
824  inline const double getNodeLPGap() const {
825  int nHistorySize
826  = static_cast<int>(m_nodeStats.objHistoryBound.size());
827 
828  if (nHistorySize > 0) {
829  const DecompObjBound& objBound
830  = m_nodeStats.objHistoryBound[nHistorySize - 1];
831  return UtilCalculateGap(getObjBestBoundLB(), objBound.thisBoundUB);
832  } else {
833  return DecompInf;
834  }
835  }
836 
840  inline const double getObjBestBoundLB() const {
841  return m_nodeStats.objBest.first;
842  }
843 
847  inline const void setStrongBranchIter(bool isStrongBranch = true) {
848  m_isStrongBranch = isStrongBranch;
849  }
850 
854  inline const double getObjBestBoundUB() const {
855  return m_nodeStats.objBest.second;
856  }
857 
861  inline const double getMasterRowType(int row) const {
862  return m_masterRowType[row];
863  }
864 
868  virtual void setObjBound(const double thisBound,
869  const double thisBoundUB) {
871  "setObjBound()", m_param.LogDebugLevel, 2);
872 
873  if (thisBound > m_nodeStats.objBest.first) {
874  m_nodeStats.objBest.first = thisBound;
875 
876  if (getNodeIndex() == 0) {
877  m_globalLB = thisBound;
878  }
879  }
880 
881  DecompObjBound objBound;
882  objBound.phase = m_phase == PHASE_PRICE1 ? 1 : 2;
883  objBound.cutPass = m_nodeStats.cutCallsTotal;
885  objBound.thisBound = thisBound;
886  objBound.thisBoundUB = thisBoundUB;
887  objBound.bestBound = m_nodeStats.objBest.first;
888  objBound.bestBoundIP = m_nodeStats.objBest.second;
889 #ifdef UTIL_USE_TIMERS
890  objBound.timeStamp = globalTimer.getRealTime();
891 #else
892  objBound.timeStamp = -1;
893 #endif
894  m_nodeStats.objHistoryBound.push_back(objBound);
896  "setObjBound()", m_param.LogDebugLevel, 2);
897  }
898 
902  virtual inline void setObjBoundIP(const double thisBound) {
904  "setObjBoundIP()", m_param.LogDebugLevel, 2);
905 
906  if (thisBound < m_nodeStats.objBest.second) {
908  (*m_osLog) << "New Global UB = "
909  << UtilDblToStr(thisBound) << std::endl;);
910  m_nodeStats.objBest.second = thisBound;
911  }
912 
913  //---
914  //--- copy the last continuous history, adjust the time
915  //---
916  DecompObjBound objBoundIP;
917  DecompObjBound* objBoundLP = m_nodeStats.getLastBound();
918 
919  if (objBoundLP) {
920  objBoundIP = *objBoundLP;
921  }
922 
923  objBoundIP.thisBoundIP = thisBound;
924  objBoundIP.bestBoundIP = m_nodeStats.objBest.second;
925 #ifdef UTIL_USE_TIMERS
926  objBoundIP.timeStamp = globalTimer.getRealTime();
927 #else
928  objBoundIP.timeStamp = -1;
929 #endif
930  m_nodeStats.objHistoryBound.push_back(objBoundIP);
932  "setObjBoundIP()", m_param.LogDebugLevel, 2);
933  }
934 
935 
936  bool isTailoffLB(const int changeLen = 10,
937  const double changePerLimit = 0.1);
938 
939 
940  inline int getNumRowType(DecompRowType rowType) {
941  int nRowsType = 0;
942  std::vector<DecompRowType>::iterator vi;
943 
944  for (vi = m_masterRowType.begin(); vi != m_masterRowType.end(); vi++) {
945  if (*vi == rowType) {
946  nRowsType++;
947  }
948  }
949 
950  return nRowsType;
951  }
952 
953  void checkBlocksColumns();
954 
955 
960  //TODO:
961  //be careful here that we don't stop due to mLB>=m_UB in the case where
962  //user gives optimal UB as cutoff, but we don't yet have integral solution
963 
964 
965 
966 
967  //-----------------------------------------------------------------------//
972  //-----------------------------------------------------------------------//
973 public:
978  DecompApp* app,
979  UtilParameters* utilParam):
980  m_classTag ("D-ALGO"),
981  m_param (),
982  m_algo (algo),
987  m_app (app),
988  m_stats (),
989  m_nodeStats (),
990  m_memPool (),
991  m_osLog (&std::cout),
992  m_cgl (0),
993  m_origColLB (),
994  m_origColUB (),
995  m_masterSI (0),
996  m_cutgenSI (NULL),
997  m_cutgenObjCutInd(-1),
998  m_auxSI (NULL),
999  m_vars (),
1000  m_varpool (),
1001  m_cuts (),
1002  m_cutpool (),
1003  m_xhat (0),
1004  m_cutoffUB (DecompInf),
1005  m_xhatIPFeas (),
1006  m_xhatIPBest (NULL),
1007  m_isColGenExact(false),
1008  m_utilParam (utilParam),
1009  m_numConvexCon (1),
1010  m_rrLastBlock (-1),
1011  m_rrIterSinceAll(0),
1012 
1013  m_colLBNode(NULL),
1014  m_colUBNode(NULL),
1015  m_relGap(DecompInf),
1017  m_masterObjLast(DecompInf),
1018  m_firstPhase2Call(false),
1019  m_isStrongBranch(false),
1020  m_masterOnlyCols(),
1021  tempTimeLimit(0),
1023  m_app->m_decompAlgo = this;
1024  }
1025 
1026 
1030  virtual ~DecompAlgo() {
1031  //UtilDeleteVectorPtr(m_subprobSI);
1036  UTIL_DELPTR(m_cgl);
1042  }
1049 };
1050 
1051 #endif
DecompColType
Definition: Decomp.h:241
std::vector< double > m_origColUB
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:129
std::list< DecompCut * > DecompCutList
Definition: Decomp.h:55
virtual void createMasterProblem(DecompVarList &initVars)
Create the master problem (all algorithms must define this function).
virtual void addVarsFromPool()
void UtilDeleteVectorPtr(vector< T * > &vectorPtr, typename vector< T * >::iterator first, typename vector< T * >::iterator last)
Definition: UtilMacros.h:288
virtual int adjustColumnsEffCnt()
The main DECOMP process loop for a node.
Definition: DecompAlgo.h:382
double thisBoundUB
The recorded continuous upper bound.
Definition: DecompStats.h:51
DecompAlgoStop m_stopCriteria
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:232
std::vector< int > m_masterOnlyCols
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:253
virtual void phaseDone()
Run the done phase for processing node.
Definition: DecompAlgo.h:372
DecompStats m_stats
Storage of statistics for run and node.
Definition: DecompAlgo.h:108
std::map< int, std::vector< DecompAlgoModel > > m_modelRelaxNest
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:162
bool m_isColGenExact
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:198
const int getNodeIndex() const
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:750
const double getNodeIPGap() const
Get the current node (integrality) gap.
Definition: DecompAlgo.h:817
virtual int generateVarsFea(DecompVarList &newVars, double &mostNegReducedCost)
std::vector< DecompObjBound > objHistoryBound
Storage of the bounds.
Definition: DecompStats.h:115
bool checkPointFeasible(const DecompConstraintSet *modelCore, const double *x)
Initial setup of algorithm structures and solver interfaces.
int m_numCols
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:196
bool isMasterColArtificial(const int index) const
Initial setup of algorithm structures and solver interfaces.
Definition: DecompAlgo.h:623
int m_nRowsOrig
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:212
int nodeIndex
The node index (in the branch-and-bound tree).
Definition: DecompStats.h:125
double m_masterObjLast
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:234
DecompApp * getDecompAppMutable()
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:746
double thisBoundIP
The recorded integer upper bound.
Definition: DecompStats.h:60
std::vector< int > m_masterArtCols
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:218
DecompAlgo * m_decompAlgo
Pointer to the base algorithmic object.
Definition: DecompApp.h:108
virtual void postProcessNode(DecompStatus decompStatus)
Do some information sending after the current node has been processed.
Definition: DecompAlgo.h:329
virtual void postProcessBranch(DecompStatus decompStatus)
Do some information sending after the current node has been branched.
Definition: DecompAlgo.h:336
DecompStatus
Definition: Decomp.h:146
DecompParam m_param
DIP is distributed under the Eclipse Public License as part of the //.
Definition: DecompAlgo.h:81
std::string UtilDblToStr(const double x, const int precision=-1, const double tooBig=UtilSmallerThanTooBig)
Definition: UtilMacros.h:564
void printCurrentProblem(const OsiSolverInterface *si, const std::string baseName, const int nodeIndex, const int cutPass, const int pricePass, const int blockId=-1, const bool printMps=true, const bool printLp=true)
Initial setup of algorithm structures and solver interfaces.
double * m_colUBNode
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:222
virtual void recomposeSolution(const double *solution, double *rsolution)
Compose solution in x-space from current space.
int m_compressColsLastNumCols
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:225
virtual void phaseInit(DecompPhase &phase)
Run the initial phase for processing node.
Definition: DecompAlgo.h:363
std::vector< double > m_primSolution
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:193
int LogDebugLevel
0: print nothing 1: print the node objective history
Definition: DecompParam.h:40
const double * m_objective
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:159
double UtilCalculateGap(const double boundLB, const double boundUB)
Calculate gap: |(ub-lb)|/|lb|.
void masterPhaseItoII()
Initial setup of algorithm structures and solver interfaces.
DecompAlgoModel & getModelRelax(const int blockId)
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:702
OsiSolverInterface * getMasterOSI()
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:698
virtual bool updateObjBound(const double mostNegRC=-DecompBigNum)
Calculate the current LB and update best/history.
void masterMatrixAddArtCol(std::vector< CoinBigIndex > &colBeg, std::vector< int > &colInd, std::vector< double > &colVal, char LorG, int rowIndex, int colIndex, DecompColType colType, double &colLB, double &colUB, double &objCoeff)
Initial setup of algorithm structures and solver interfaces.
double m_globalUB
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:243
void checkMasterDualObj()
Initial setup of algorithm structures and solver interfaces.
std::vector< double > m_phaseIObj
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:245
const DecompApp * getDecompApp() const
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:743
void breakOutPartial(const double *xHat, DecompVarList &newVars, const double intTol=1.0e-5)
Initial setup of algorithm structures and solver interfaces.
bool isDualRayInfProofCpx(const double *dualRay, const CoinPackedMatrix *rowMatrix, const double *colLB, const double *colUB, const double *rowRhs, std::ostream *os)
Initial setup of algorithm structures and solver interfaces.
DecompCutList m_cuts
Containers for cuts (current and pool).
Definition: DecompAlgo.h:174
static UtilTimer globalTimer
int m_function
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:247
DecompPhase m_phaseLast
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:97
void generateVarsAdjustDuals(const double *uOld, double *uNew)
Create an adjusted dual vector with the duals from the convexity constraints removed.
virtual const double * getMasterDualSolution() const
Get current dual solution for master problem.
Definition: DecompAlgo.h:775
bool m_isStrongBranch
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:249
virtual const double * getObjCoefficients() const =0
Get a pointer to an array[getNumCols()] of objective function coefficients.
bool isMasterColMasterOnly(const int index) const
Initial setup of algorithm structures and solver interfaces.
Definition: DecompAlgo.h:616
#define UTIL_DELARR(x)
Definition: UtilMacros.h:29
const DecompSolution * getXhatIPBest() const
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:723
An interface to CGL cut generator library.
Definition: DecompAlgoCGL.h:42
const double * getXhat() const
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:713
virtual void masterMatrixAddArtCols(CoinPackedMatrix *masterM, double *colLB, double *colUB, double *objCoeff, std::vector< std::string > &colNames, int startRow, int endRow, DecompRowType rowType)
Initial setup of algorithm structures and solver interfaces.
DecompAlgoModel m_modelCore
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:160
Sparse Matrix Base Class.
double MasterGapLimit
0: print nothing 1: print the node objective history
Definition: DecompParam.h:83
DecompVarList m_vars
Containers for variables (current and pool).
Definition: DecompAlgo.h:168
virtual void adjustMasterDualSolution()
Adjust the current dual solution for master problem.
Definition: DecompAlgo.h:782
int m_colIndexUnique
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:233
const double * getOrigObjective() const
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:679
std::map< int, int > m_masterOnlyColsMap
Map from original index to master index for master-only vars.
Definition: DecompAlgo.h:257
void generateVarsCalcRedCost(const double *u, double *redCostX)
Calculated reduced cost vector (over vars in compact space) for a given dual vector.
void initSetup(UtilParameters *utilParam, std::string &sectionParam)
Initial setup of algorithm structures and solver interfaces.
DecompStatus m_status
The current algorithm status.
Definition: DecompAlgo.h:91
std::vector< double * > getDualRays(int maxNumRays)
const DecompAlgoModel & getModelCore() const
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:682
int m_nRowsBranch
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:213
DecompAlgoStop
Definition: Decomp.h:103
double m_globalLB
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:242
std::vector< DecompSolution * > m_xhatIPFeas
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:188
DecompParam & getMutableParam()
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:694
int cutCallsTotal
Number of cut calls in this node in total.
Definition: DecompStats.h:150
int cutPass
The cut pass when bound was recorded.
Definition: DecompStats.h:35
#define UTIL_MSG(param, level, x)
Definition: UtilMacros.h:80
const int getStopCriteria() const
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:803
virtual void addCutsToPool(const double *x, DecompCutList &newCuts, int &m_cutsThisCall)
void createOsiSubProblem(DecompAlgoModel &algoModel)
Initial setup of algorithm structures and solver interfaces.
int cutsThisCall
Number of cuts generated in this particular cut call.
Definition: DecompStats.h:140
int m_compressColsLastPrice
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:224
const int COIN_INT_MAX
Definition: CoinFinite.hpp:19
const double getObjBestBoundUB() const
Get the current best UB.
Definition: DecompAlgo.h:854
void appendVars(DecompVarList &varList)
Definition: DecompAlgo.h:470
DecompPhase m_phase
The current algorithm phase.
Definition: DecompAlgo.h:96
DecompBranchingImplementation
Definition: Decomp.h:282
void loadSIFromModel(OsiSolverInterface *si, bool doInt=false)
Create the master problem (all algorithms must define this function).
const double getObjBestBoundLB() const
Get the current best LB.
Definition: DecompAlgo.h:840
bool m_firstPhase2Call
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:248
virtual DecompSolverResult * solveDirect(const DecompSolution *startSol=NULL)
Initial setup of algorithm structures and solver interfaces.
Definition: DecompAlgo.h:583
virtual bool isDone()
Definition: DecompAlgo.h:418
int getNumRowType(DecompRowType rowType)
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:940
const double * m_objective
Model data: objective function.
Definition: DecompApp.h:86
const double * getMasterPrimalSolution() const
Get current primal solution for master problem.
Definition: DecompAlgo.h:765
UtilParameters * m_utilParam
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:200
int m_numConvexCon
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:202
void UtilDeleteListPtr(list< T * > &listPtr, typename list< T * >::iterator first, typename list< T * >::iterator last)
Definition: UtilMacros.h:308
double bestBoundIP
The best recorded integer upper bound.
Definition: DecompStats.h:65
int m_nRowsCuts
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:215
DecompMemPool m_memPool
Memory pool used to reduce the number of allocations needed.
Definition: DecompAlgo.h:114
bool isMasterColStructural(const int index) const
Initial setup of algorithm structures and solver interfaces.
Definition: DecompAlgo.h:619
std::map< int, int > m_artColIndToRowInd
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:240
DecompVarPool m_varpool
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:169
int phase
The phase when bound was recorded.
Definition: DecompStats.h:31
const DecompParam & getDecompParam() const
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:739
DecompStatus solveRelaxed(const double *redCostX, const double *origCost, const double alpha, const int n_origCols, const bool isNested, DecompAlgoModel &algoModel, DecompSolverResult *solveResult, std::list< DecompVar * > &vars)
std::vector< DecompColType > m_masterColType
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:217
void printVars(std::ostream *os)
Initial setup of algorithm structures and solver interfaces.
int priceCallsTotal
Number of price calls in this node in total.
Definition: DecompStats.h:155
double bestBound
The best recorded continuous lower bound.
Definition: DecompStats.h:56
int m_nArtCols
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:209
std::map< int, DecompAlgoModel > m_modelRelax
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:161
double getMasterObjValue() const
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:785
std::pair< double, double > objBest
The global lower (.first) and upper (.second) bound.
Definition: DecompStats.h:120
void setCutoffUB(const double thisBound)
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:717
virtual bool chooseBranchSet(std::vector< std::pair< int, double > > &downBranchLb, std::vector< std::pair< int, double > > &downBranchUb, std::vector< std::pair< int, double > > &upBranchLb, std::vector< std::pair< int, double > > &upBranchUb)
void printBasisInfo(OsiSolverInterface *si, std::ostream *os)
Initial setup of algorithm structures and solver interfaces.
double tempTimeLimit
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:260
const double getCutoffUB() const
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:731
int pricePass
The price pass when bound was recorded.
Definition: DecompStats.h:39
bool isGapTight()
Definition: DecompAlgo.h:391
virtual DecompStatus solutionUpdate(const DecompPhase phase, const bool resolve=true, const int maxInnerIter=COIN_INT_MAX, const int maxOuterIter=COIN_INT_MAX)
Update of the solution vectors (primal and/or dual).
virtual void addVarsToPool(DecompVarList &newVars)
Clp Solver Interface.
const int getPriceCallsTotal() const
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:758
double * m_xhat
Storage for current solution (in x-space).
Definition: DecompAlgo.h:180
double getRealTime()
Get wallClock time.
Definition: UtilTimer.h:75
OsiClpSolverInterface * m_cutgenSI
Solver interface(s) for entire problem (Q&#39;&#39;).
Definition: DecompAlgo.h:154
DecompAlgoType
Definition: Decomp.h:85
void getModelsFromApp()
Initial setup of algorithm structures and solver interfaces.
const double getMasterRowType(int row) const
Get a specific row type.
Definition: DecompAlgo.h:861
const double getNodeLPGap() const
Get the current node (continuous) gap.
Definition: DecompAlgo.h:824
DecompStats & getDecompStats()
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:735
Abstract Base Class for describing an interface to a solver.
const int getCutCallsTotal() const
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:754
virtual int generateVars(const DecompStatus stat, DecompVarList &newVars, double &mostNegReducedCost)
double m_relGap
Current node gap (bestUB-bestLB)/bestLB.
Definition: DecompAlgo.h:230
virtual void setMasterBounds(const double *lbs, const double *ubs)
void printCuts(std::ostream *os)
Initial setup of algorithm structures and solver interfaces.
double timeStamp
The time stamp (from start) when bound was recorded.
Definition: DecompStats.h:43
DecompAlgoType m_algo
Type of algorithm for this instance.
Definition: DecompAlgo.h:86
int m_cutgenObjCutInd
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:155
double m_cutoffUB
User-defined cutoff (global UB) for B&amp;B fathoming and LR.
Definition: DecompAlgo.h:186
bool isLPFeasible(const double *x, const bool isXSparse=false, const double feasVarTol=1.0e-6, const double feasConTol=1.0e-5)
bool isTailoffLB(const int changeLen=10, const double changePerLimit=0.1)
Get a ptr to the current solution (in x-space).
DecompApp * m_app
Pointer to current active DECOMP application.
Definition: DecompAlgo.h:103
const AlpsDecompTreeNode * m_curNode
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:251
const double getGlobalGap() const
Get the current global (integrality) gap.
Definition: DecompAlgo.h:810
const double * getColLBNode() const
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:665
Abstract base class for warm start information.
std::vector< double > m_dualSolution
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:194
virtual int addCutsFromPool()
void coreMatrixAppendColBounds()
Calculate gap: |(ub-lb)|/|lb|.
#define UTIL_DELPTR(x)
Definition: UtilMacros.h:28
OsiSolverInterface * m_auxSI
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:156
virtual int compressColumns()
The main DECOMP process loop for a node.
Definition: DecompAlgo.h:385
int m_rrLastBlock
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:205
virtual DecompStatus processNode(const AlpsDecompTreeNode *node, const double globalLB=-DecompInf, const double globalUB=DecompInf)
The main DECOMP process loop for a node.
DecompBranchingImplementation m_branchingImplementation
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:265
const std::vector< DecompSolution * > & getXhatIPFeas() const
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:727
DecompNodeStats m_nodeStats
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:109
void appendVars(DecompVar *var)
Definition: DecompAlgo.h:467
std::string m_classTag
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:76
virtual ~DecompAlgo()
Destructor.
Definition: DecompAlgo.h:1030
bool isIPFeasible(const double *x, const bool isXSparse=false, const double feasVarTol=1.0e-6, const double feasConTol=1.0e-5, const double intTol=1.0e-5)
virtual void solutionUpdateAsIP()
The main DECOMP process loop for a node.
Definition: DecompAlgo.h:380
const void setStrongBranchIter(bool isStrongBranch=true)
Set the object to be in strong branching mode.
Definition: DecompAlgo.h:847
OsiSolverInterface * m_masterSI
Solver interface(s) for subproblems (P&#39;).
Definition: DecompAlgo.h:142
DecompSolution * m_xhatIPBest
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:189
virtual int generateCuts(double *xhat, DecompCutList &newCuts)
void UtilPrintFuncBegin(std::ostream *os, const std::string &classTag, const std::string &funcName, const int logLevel, const int logLimit)
virtual void setSubProbBounds(const double *lbs, const double *ubs)
DecompParam m_param
Parameters.
Definition: DecompApp.h:81
int m_rrIterSinceAll
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:206
void masterPhaseIItoI()
Initial setup of algorithm structures and solver interfaces.
const DecompParam & getParam() const
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:690
void masterMatrixAddMOCols(CoinPackedMatrix *masterM, double *colLB, double *colUB, double *objCoeff, std::vector< std::string > &colNames)
Initial setup of algorithm structures and solver interfaces.
int varsThisCall
Number of vars generated in this particular price call.
Definition: DecompStats.h:145
int m_nRowsConvex
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:214
void UtilPrintFuncEnd(std::ostream *os, const std::string &classTag, const std::string &funcName, const int logLevel, const int logLimit)
DecompCutPool m_cutpool
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:175
const double * getMasterColReducedCost() const
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:769
virtual void setObjBound(const double thisBound, const double thisBoundUB)
Set the current continuous bounds and update best/history.
Definition: DecompAlgo.h:868
std::vector< double > m_origColLB
Pointer (and label) to current active model core/relax.
Definition: DecompAlgo.h:128
Storage of solver result.
Base class for DECOMP algorithms.
Definition: DecompAlgo.h:63
DecompObjBound * getLastBound()
Definition: DecompStats.h:196
bool isDualRayInfProof(const double *dualRay, const CoinPackedMatrix *rowMatrix, const double *colLB, const double *colUB, const double *rowRhs, std::ostream *os)
Initial setup of algorithm structures and solver interfaces.
DecompRowType
Definition: Decomp.h:212
virtual void phaseUpdate(DecompPhase &phase, DecompStatus &status)
Update of the phase for process loop.
double thisBound
The recorded continuous lower bound.
Definition: DecompStats.h:47
DecompPhase m_phaseForce
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:98
double m_stabEpsilon
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:238
std::ostream * m_osLog
Stream for log file (default to stdout).
Definition: DecompAlgo.h:119
DecompAlgo(const DecompAlgoType algo, DecompApp *app, UtilParameters *utilParam)
Default constructors.
Definition: DecompAlgo.h:977
std::vector< DecompRowType > m_masterRowType
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:216
void printCurrentProblemDual(OsiSolverInterface *si, const std::string baseName, const int nodeIndex, const int cutPass, const int pricePass)
Initial setup of algorithm structures and solver interfaces.
double * m_colLBNode
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:221
virtual int generateInitVars(DecompVarList &initVars)
Generate initial variables for master problem (PC/DC/RC).
bool m_useInitLpDuals
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:239
std::list< DecompVar * > DecompVarList
Definition: Decomp.h:53
DecompPhase
Definition: Decomp.h:127
const AlpsDecompTreeNode * getCurrentNode() const
Provide the current node the algorithm is solving.
Definition: DecompAlgo.h:320
void checkBlocksColumns()
Get a ptr to the current solution (in x-space).
const double DecompBigNum
Definition: Decomp.h:61
DecompStats & getStats()
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:675
virtual void setObjBoundIP(const double thisBound)
Set the current integer bound and update best/history.
Definition: DecompAlgo.h:902
const int getAlgo() const
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:686
std::vector< double > m_reducedCost
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:195
bool m_objNoChange
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:235
DecompAlgoCGL * m_cgl
Store the name of the class (for logging/debugging) - &quot;who am I?&quot;.
Definition: DecompAlgo.h:121
The main application class.
Definition: DecompApp.h:50
int m_cutsThisCall
Definition: DecompAlgo.h:64
const double * getColUBNode() const
Get a ptr to the current solution (in x-space).
Definition: DecompAlgo.h:668
void createFullMps(const std::string fileName)
Initial setup of algorithm structures and solver interfaces.