Dip 0.95.0
Loading...
Searching...
No Matches
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// Authors: Matthew Galati, SAS Institute Inc. (matthew.galati@sas.com) //
8// Ted Ralphs, Lehigh University (ted@lehigh.edu) //
9// Jiadong Wang, Lehigh University (jiw408@lehigh.edu) //
10// //
11// Copyright (C) 2002-2019, Lehigh University, Matthew Galati, Ted Ralphs //
12// All Rights Reserved. //
13//===========================================================================//
14
15
16//thinking about design - PC/C - most everything is driven by OSI methods
17//but RC is not, this actually doesn't need OSI at all - either use OsiNull
18//or, split up there types...
19
20//DecompAlgo
21// now will have a data member DecompInterface * interface
22// which is allocated to be a DecompOsi or DecompNull depending
23// on which algo we are talking about
24// this might also be a way to use Vol directly....
25
26
27//DecompInterface - base class
28// DecompOsi : public DecompInterface -->
29// wrapper for all OSI methods (with OSI)
30// DecompNull : public DecompInterface -->
31// wrapper for all OSI methods in RC (no OSI)
32
33//===========================================================================//
34#ifndef DecompAlgo_h_
35#define DecompAlgo_h_
36
37//===========================================================================//
43//===========================================================================//
44
45//===========================================================================//
46#include "Decomp.h"
47#include "DecompApp.h"
48#include "DecompParam.h"
49#include "DecompStats.h"
50#include "DecompVarPool.h"
51#include "DecompCutPool.h"
52#include "DecompMemPool.h"
53#include "DecompSolution.h"
54#include "DecompAlgoCGL.h"
55#include "AlpsDecompTreeNode.h"
60
61//===========================================================================//
63
64protected:
65
66 //----------------------------------------------------------------------//
71 //----------------------------------------------------------------------//
75 std::string m_classTag;
76
82
87
92
96 double m_infinity;
97
102 DecompPhase m_phaseLast;//just before done
104
109
115
120
124 std::ostream* m_osLog;
125
127
133 std::vector<double> m_origColLB;
134 std::vector<double> m_origColUB;
135
139 //vector<OsiSolverInterface*> m_subprobSI;
140
148
158
159
160 const double* m_objective;
162 std::map<int, DecompSubModel> m_modelRelax;
163 std::map<int, std::vector<DecompSubModel> > m_modelRelaxNest;
164
165
171
177
181 double* m_xhat;
182
188 //THINK - use solution pool
189 std::vector<DecompSolution*> m_xhatIPFeas;
191
192
193 //for cpx
194 std::vector<double> m_primSolution;
195 std::vector<double> m_dualSolution;
196 std::vector<double> m_reducedCost;
198
200
202
203 //for round robin
206
207 //
209
210 //all these are related to master LP - make object
215 std::vector<DecompRowType> m_masterRowType;
216 std::vector<DecompColType> m_masterColType;
217 std::vector<int> m_masterArtCols;
218
219 //to enforce in subproblems
220 double* m_colLBNode;
221 double* m_colUBNode;
222
225
229 double m_relGap;
230
233 double m_masterObjLast;//last master obj
235
236
239 std::map<int, int> m_artColIndToRowInd;
240
243
244 std::vector<double> m_phaseIObj;
245
246 int m_function;//calling function
249
251
252 std:: vector<int> m_masterOnlyCols;
256 std::map<int, int> m_masterOnlyColsMap;
257
258 // variable dictating whether the branching is implemented
259 // in the master problem or the subproblem
260
262
263
264
265public:
269 //-----------------------------------------------------------------------//
274 //-----------------------------------------------------------------------//
278 //virtual void createMasterProblem(DecompVarList & initVars) = 0;
279 virtual void createMasterProblem(DecompVarList& initVars);
281 //need next 2 args? ever different?
282 //DecompSubModel & modelCore,
283 //map<int, DecompSubModel> & modelRelax,
284 bool doInt = false);
285
286
292 //not pure?
293 virtual void recomposeSolution(const double* solution,
294 double* rsolution);
299 //-----------------------------------------------------------------------//
304 //-----------------------------------------------------------------------//
309 const double globalLB,
310 const double globalUB);
311
317 return m_curNode;
318 };
319
325 virtual void postProcessNode(DecompStatus decompStatus) {};
326
332 virtual void postProcessBranch(DecompStatus decompStatus) {};
333
338 //THINK: belongs in base? PC or...
339 virtual int generateInitVars(DecompVarList& initVars);
340
344 virtual DecompStatus
346 const bool resolve = true,
347 const int maxInnerIter = COIN_INT_MAX,
348 const int maxOuterIter = COIN_INT_MAX);
349
353 virtual void phaseUpdate(DecompPhase& phase,
354 DecompStatus& status);
355
359 virtual void phaseInit(DecompPhase& phase) {
360 if (getNodeIndex() == 0) {
361 phase = PHASE_PRICE1;
362 }
363 }
364
368 virtual void phaseDone() {};
369
373 virtual bool updateObjBound(const double mostNegRC = -DecompBigNum);
374
375
376 virtual void solveMasterAsMIP() {}
377
378 virtual int adjustColumnsEffCnt() {
379 return DecompStatOk;
380 };
381 virtual int compressColumns () {
382 return DecompStatOk;
383 };
387 bool isGapTight() {
388 //TODO: make param
389 double tightGap = m_param.MasterGapLimit;
390
391 //printf("isGapTight m_relGap = %g\n", m_relGap);
392 if (m_param.LogDebugLevel >= 2) {
393 (*m_osLog) << "DW GAP = " << UtilDblToStr(m_relGap)
394 << " isTight = " << (m_relGap <= tightGap)
395 << "\n";
396 }
397
398 if (m_relGap <= tightGap) {
399 return true;
400 } else {
401 return false;
402 }
403 }
404
408 double getInfinity() {
409 return m_infinity;
410 }
411
412 //................................
413 //TODO............................
414 //................................
415
416 virtual bool isDone() {
418 return false;
419 } else {
420 return true;
421 }
422 }
423
424 //TODO: should move out to PC
425 //THINK - helper func?, or specific to PC - right? as is genInit
426 std::vector<double*> getDualRays(int maxNumRays);
427 std::vector<double*> getDualRaysCpx(int maxNumRays);
428 std::vector<double*> getDualRaysOsi(int maxNumRays);
429
430 virtual int generateVars(DecompVarList& newVars,
431 double& mostNegReducedCost);
432
433 virtual int generateCuts(double* xhat,
434 DecompCutList& newCuts);
435
436 virtual void addVarsToPool(DecompVarList& newVars);
437 virtual void addVarsFromPool();
438 virtual void addCutsToPool(const double* x,
439 DecompCutList& newCuts,
440 int& m_cutsThisCall);
441 virtual int addCutsFromPool();
442
443 bool isIPFeasible(const double* x,
444 const bool isXSparse = false,
445 const double feasVarTol = 1.0e-6, //0.0001%
446 const double feasConTol = 1.0e-5, //0.001%
447 const double intTol = 1.0e-5); //0.001%
448
449 bool isLPFeasible(const double* x,
450 const bool isXSparse = false,
451 const double feasVarTol = 1.0e-6, //0.001%
452 const double feasConTol = 1.0e-5); //0.01%
453
454 //fugly
455 DecompStatus solveRelaxed(const double* redCostX,
456 const double* origCost,
457 const double alpha,
458 const int n_origCols,
459 const bool isNested,
460 DecompSubModel& subModel,
461 DecompSolverResult* solveResult,
462 std::list<DecompVar*>& vars,
463 double timeLimit);
464
465
466 inline void appendVars(DecompVar* var) {
467 m_vars.push_back(var);
468 }
469 inline void appendVars(DecompVarList& varList) {
470 copy(varList.begin(), varList.end(), back_inserter(m_vars));
471 }
472 virtual void setMasterBounds(const double* lbs,
473 const double* ubs);
474 virtual void setSubProbBounds(const double* lbs,
475 const double* ubs);
476
477 //int chooseBranchVar(int & branchedOnIndex,
478 // double & branchedOnValue);
479 virtual bool
480 chooseBranchSet(std::vector< std::pair<int, double> >& downBranchLb,
481 std::vector< std::pair<int, double> >& downBranchUb,
482 std::vector< std::pair<int, double> >& upBranchLb,
483 std::vector< std::pair<int, double> >& upBranchUb);
484
485
486
487
488 //-----------------------------------------------------------------------//
493 //-----------------------------------------------------------------------//
497 void initSetup();
502
506 /*double calculateGap(double boundLB,
507 double boundUB) const {
508 double gap = m_infinity;
509 if(boundLB > -m_infinity && boundUB < m_infinity){
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
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);
574 void checkReducedCost(const double *u, const double *u_adjusted);
575
579 void createFullMps(const std::string fileName);
580
584 virtual DecompSolverResult*
585 solveDirect(const DecompSolution* startSol = NULL) {
586 return NULL;
587 }
588
589
591 double* colLB,
592 double* colUB,
593 double* objCoeff,
594 std::vector<std::string>& colNames);
595
596 void masterMatrixAddArtCol(std::vector<CoinBigIndex>& colBeg,
597 std::vector<int >& colInd,
598 std::vector<double >& colVal,
599 char LorG,
600 int rowIndex,
601 int colIndex,
602 DecompColType colType,
603 double& colLB,
604 double& colUB,
605 double& objCoeff);
606
608 double* colLB,
609 double* colUB,
610 double* objCoeff,
611 std::vector<std::string>& colNames,
612 int startRow,
613 int endRow,
614 DecompRowType rowType);
617
618 bool isMasterColMasterOnly(const int index) const {
619 return (m_masterColType[index] == DecompCol_MasterOnly);
620 }
621 bool isMasterColStructural(const int index) const {
622 return (m_masterColType[index] == DecompCol_Structural ||
624 }
635
636 void breakOutPartial(const double* xHat,
637 DecompVarList& newVars,
638 const double intTol = 1.0e-5);
639
644 void generateVarsAdjustDuals(const double* uOld,
645 double* uNew);
650 void generateVarsCalcRedCost(const double* u,
651 double* redCostX);
652
653
654
655
661 //-----------------------------------------------------------------------//
666 //-----------------------------------------------------------------------//
667 inline const double* getColLBNode() const {
668 return m_colLBNode;
669 }
670 inline const double* getColUBNode() const {
671 return m_colUBNode;
672 }
673 //inline OsiSolverInterface * getSubProbSI(int b){
674 // return m_subprobSI[b];
675 //}
676
678 return m_stats;
679 }
680
681 inline const double* getOrigObjective() const {
682 return m_app->m_objective;
683 }
684 inline const DecompSubModel& getModelCore() const {
685 return m_modelCore;
686 }
687
688 inline const int getAlgo() const {
689 return m_algo;
690 }
691
692 inline const DecompParam& getParam() const {
693 return m_param;
694 }
695
697 return m_param;
698 }
699
701 return m_masterSI;
702 }
703
704 inline DecompSubModel& getModelRelax(const int blockId) {
705 std::map<int, DecompSubModel>::iterator mit;
706 mit = m_modelRelax.find(blockId);
707 assert(mit != m_modelRelax.end());
708 return (*mit).second;
709 }
710
711
715 inline const double* getXhat() const {
716 return m_xhat;
717 }
718
719 inline void setCutoffUB(const double thisBound) {
720 m_cutoffUB = thisBound;
721 setObjBoundIP(thisBound);
722 }
723
724 //TODO
725 inline const DecompSolution* getXhatIPBest() const {
726 return m_xhatIPBest;
727 }
728
729 inline const std::vector<DecompSolution*>& getXhatIPFeas() const {
730 return m_xhatIPFeas;
731 }
732
733 inline const double getCutoffUB() const {
734 return m_cutoffUB;
735 }
736
738 return m_stats;
739 }
740
741 inline const DecompParam& getDecompParam() const {
742 return m_param;
743 }
744
745 inline const DecompApp* getDecompApp() const {
746 return m_app;
747 }
749 return m_app;
750 }
751
752 inline const int getNodeIndex() const {
753 return m_nodeStats.nodeIndex;
754 }
755
756 inline const int getCutCallsTotal() const {
758 }
759
760 inline const int getPriceCallsTotal() const {
762 }
763
767 inline const double* getMasterPrimalSolution() const {
768 return &m_primSolution[0];
769 }
770
771 inline const double* getMasterColReducedCost() const {
772 return &m_reducedCost[0];
773 }
777 virtual const double* getMasterDualSolution() const {
778 return &m_dualSolution[0];
779 }
780
784 virtual void adjustMasterDualSolution() {};
785
786
787 inline double getMasterObjValue() const {
788 if (!m_masterSI) {
789 return -m_infinity;
790 }
791
792 //NOTE: be careful that this is always using the PhaseII obj
793 int nc = static_cast<int>(m_primSolution.size());
794 const double* objCoef = m_masterSI->getObjCoefficients();
795 const double* primSol = getMasterPrimalSolution();
796 double retVal = 0.0;
797
798 for ( int i = 0 ; i < nc ; i++ ) {
799 retVal += objCoef[i] * primSol[i];
800 }
801
802 return retVal;
803 }
804
805 inline const int getStopCriteria() const {
806 return m_stopCriteria;
807 }
808
812 inline const double getGlobalGap() const {
814 }
815
819 inline const double getNodeIPGap() const {
821 }
822
826 inline const double getNodeLPGap() const {
827 int nHistorySize
828 = static_cast<int>(m_nodeStats.objHistoryBound.size());
829
830 if (nHistorySize > 0) {
831 const DecompObjBound& objBound
832 = m_nodeStats.objHistoryBound[nHistorySize - 1];
834 } else {
835 return m_infinity;
836 }
837 }
838
842 inline const double getObjBestBoundLB() const {
843 return m_nodeStats.objBest.first;
844 }
845
849 inline const void setStrongBranchIter(bool isStrongBranch = true) {
850 m_isStrongBranch = isStrongBranch;
851 }
852
856 inline const double getObjBestBoundUB() const {
857 return m_nodeStats.objBest.second;
858 }
859
863 inline const double getMasterRowType(int row) const {
864 return m_masterRowType[row];
865 }
866
870 virtual void setObjBound(const double thisBound,
871 const double thisBoundUB) {
873 "setObjBound()", m_param.LogDebugLevel, 2);
874
875 if (thisBound > m_nodeStats.objBest.first) {
876 m_nodeStats.objBest.first = thisBound;
877
878 if (getNodeIndex() == 0) {
879 m_globalLB = thisBound;
880 }
881 }
882
883 DecompObjBound objBound(m_infinity);
884 objBound.phase = m_phase == PHASE_PRICE1 ? 1 : 2;
887 objBound.thisBound = thisBound;
888 objBound.thisBoundUB = thisBoundUB;
889 objBound.bestBound = m_nodeStats.objBest.first;
890 objBound.bestBoundIP = m_nodeStats.objBest.second;
891#ifdef UTIL_USE_TIMERS
892 objBound.timeStamp = globalTimer.getRealTime();
893#else
894 objBound.timeStamp = -1;
895#endif
896 m_nodeStats.objHistoryBound.push_back(objBound);
898 "setObjBound()", m_param.LogDebugLevel, 2);
899 }
900
904 virtual inline void setObjBoundIP(const double thisBound) {
906 "setObjBoundIP()", m_param.LogDebugLevel, 2);
907
908 if (thisBound < m_nodeStats.objBest.second) {
910 (*m_osLog) << "New Global UB = "
911 << UtilDblToStr(thisBound) << std::endl;);
912 m_nodeStats.objBest.second = thisBound;
913 }
914
915 //---
916 //--- copy the last continuous history, adjust the time
917 //---
918 DecompObjBound objBoundIP(m_infinity);
920
921 if (objBoundLP) {
922 objBoundIP = *objBoundLP;
923 }
924
925 objBoundIP.thisBoundIP = thisBound;
926 objBoundIP.bestBoundIP = m_nodeStats.objBest.second;
927#ifdef UTIL_USE_TIMERS
928 objBoundIP.timeStamp = globalTimer.getRealTime();
929#else
930 objBoundIP.timeStamp = -1;
931#endif
932 m_nodeStats.objHistoryBound.push_back(objBoundIP);
934 "setObjBoundIP()", m_param.LogDebugLevel, 2);
935 }
936
937
938 bool isTailoffLB(const int changeLen = 10,
939 const double changePerLimit = 0.1);
940
941
942 inline int getNumRowType(DecompRowType rowType) {
943 int nRowsType = 0;
944 std::vector<DecompRowType>::iterator vi;
945
946 for (vi = m_masterRowType.begin(); vi != m_masterRowType.end(); vi++) {
947 if (*vi == rowType) {
948 nRowsType++;
949 }
950 }
951
952 return nRowsType;
953 }
954
956
957
962 //TODO:
963 //be careful here that we don't stop due to mLB>=m_UB in the case where
964 //user gives optimal UB as cutoff, but we don't yet have integral solution
965
966
967
968
969 //-----------------------------------------------------------------------//
974 //-----------------------------------------------------------------------//
975public:
980 DecompApp* app,
981 UtilParameters& utilParam,
982 bool doSetup = true) :
983 m_classTag ("D-ALGO"),
984 m_param (),
985 m_utilParam (&utilParam),
986 m_algo (algo),
992 m_app (app),
993 m_stats (),
994 m_nodeStats (),
995 m_memPool (),
996 m_osLog (&std::cout),
997 m_cgl (0),
998 m_origColLB (),
999 m_origColUB (),
1000 m_masterSI (0),
1001 m_cutgenSI (NULL),
1003 m_auxSI (NULL),
1004 m_modelCore (utilParam),
1005 m_vars (),
1006 m_varpool (),
1007 m_cuts (),
1008 m_cutpool (),
1009 m_xhat (0),
1011 m_xhatIPFeas (),
1012 m_xhatIPBest (NULL),
1013 m_isColGenExact(false),
1014 m_numConvexCon (1),
1015 m_rrLastBlock (-1),
1017
1018 m_colLBNode(NULL),
1019 m_colUBNode(NULL),
1023 m_firstPhase2Call(false),
1024 m_isStrongBranch(false),
1027 {
1028 std::string paramSection = DecompAlgoStr[algo];
1029 //---
1030 //--- read in algorithm parameters
1031 //---
1032 m_param.getSettings(utilParam, paramSection);
1033
1035 && m_param.BranchEnforceInMaster == false) {
1036 m_branchingImplementation = DecompBranchInSubproblem;
1037 } else if (m_param.BranchEnforceInMaster == true
1038 && m_param.BranchEnforceInSubProb == false) {
1039 m_branchingImplementation = DecompBranchInMaster;
1040 } else {
1041 throw UtilException("Branching Implementation should be set correctly",
1042 "initSetup", "DecompAlgo");
1043 }
1044
1045 if (m_param.LogLevel > 1) {
1046 m_param.dumpSettings(paramSection, m_osLog);
1047 }
1048
1049 m_app->m_decompAlgo = this;
1050
1051 //---
1052 //--- run init setup
1053 //---
1054 if (doSetup) {
1055 initSetup();
1056 }
1057 }
1058
1059
1082};
1083
1084#endif
const double COIN_DBL_MAX
DecompBranchingImplementation
Definition Decomp.h:320
@ DecompBranchInSubproblem
Definition Decomp.h:321
DecompStatus
Definition Decomp.h:184
@ STAT_UNKNOWN
Definition Decomp.h:188
DecompAlgoStop
Definition Decomp.h:141
@ DecompStopNo
Definition Decomp.h:142
@ DecompStatOk
Definition Decomp.h:218
DecompAlgoType
Definition Decomp.h:123
const std::string DecompAlgoStr[5]
Definition Decomp.h:130
std::list< DecompVar * > DecompVarList
Definition Decomp.h:92
DecompRowType
Definition Decomp.h:250
DecompPhase
Definition Decomp.h:165
@ PHASE_UNKNOWN
Definition Decomp.h:170
@ PHASE_PRICE1
Definition Decomp.h:166
std::list< DecompCut * > DecompCutList
Definition Decomp.h:93
DecompColType
Definition Decomp.h:279
@ DecompCol_ArtForBranchL
Definition Decomp.h:291
@ DecompCol_MasterOnly
Definition Decomp.h:285
@ DecompCol_Structural
Definition Decomp.h:281
@ DecompCol_ArtForBranchG
Definition Decomp.h:293
@ DecompCol_ArtForConvexG
Definition Decomp.h:297
@ DecompCol_ArtForRowL
Definition Decomp.h:287
@ DecompCol_ArtForCutG
Definition Decomp.h:301
@ DecompCol_ArtForRowG
Definition Decomp.h:289
@ DecompCol_Structural_NoDelete
Definition Decomp.h:283
@ DecompCol_ArtForConvexL
Definition Decomp.h:295
@ DecompCol_ArtForCutL
Definition Decomp.h:299
const double DecompBigNum
Definition Decomp.h:99
void UtilPrintFuncEnd(std::ostream *os, const std::string &classTag, const std::string &funcName, const int logLevel, const int logLimit)
void UtilPrintFuncBegin(std::ostream *os, const std::string &classTag, const std::string &funcName, const int logLevel, const int logLimit)
double UtilCalculateGap(const double boundLB, const double boundUB, double infinity)
Calculate gap: |(ub-lb)|/|lb|.
static UtilTimer globalTimer
#define UTIL_MSG(param, level, x)
Definition UtilMacros.h:79
void UtilDeleteVectorPtr(std::vector< T * > &vectorPtr, typename std::vector< T * >::iterator first, typename std::vector< T * >::iterator last)
Definition UtilMacros.h:610
#define UTIL_DELPTR(x)
Definition UtilMacros.h:64
std::string UtilDblToStr(const double x, const int precision=-1, const double tooBig=UtilSmallerThanTooBig)
Definition UtilMacros.h:563
void UtilDeleteListPtr(std::list< T * > &listPtr, typename std::list< T * >::iterator first, typename std::list< T * >::iterator last)
Definition UtilMacros.h:630
#define UTIL_DELARR(x)
Definition UtilMacros.h:65
An interface to CGL cut generator library.
Base class for DECOMP algorithms.
Definition DecompAlgo.h:62
DecompPhase m_phase
The current algorithm phase.
Definition DecompAlgo.h:101
double * m_xhat
Storage for current solution (in x-space).
Definition DecompAlgo.h:181
bool m_isColGenExact
Definition DecompAlgo.h:199
DecompStats & getDecompStats()
Definition DecompAlgo.h:737
virtual void postProcessNode(DecompStatus decompStatus)
Do some information sending after the current node has been processed.
Definition DecompAlgo.h:325
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)
std::vector< double * > getDualRays(int maxNumRays)
DecompSolution * m_xhatIPBest
Definition DecompAlgo.h:190
const double getObjBestBoundLB() const
Get the current best LB.
Definition DecompAlgo.h:842
bool isDualRayInfProof(const double *dualRay, const CoinPackedMatrix *rowMatrix, const double *colLB, const double *colUB, const double *rowRhs, std::ostream *os)
DecompApp * getDecompAppMutable()
Definition DecompAlgo.h:748
const int getCutCallsTotal() const
Definition DecompAlgo.h:756
double * m_colUBNode
Definition DecompAlgo.h:221
virtual DecompStatus processNode(const AlpsDecompTreeNode *node, const double globalLB, const double globalUB)
The main DECOMP process loop for a node.
std::map< int, int > m_artColIndToRowInd
Definition DecompAlgo.h:239
std::vector< double * > getDualRaysOsi(int maxNumRays)
int m_rrLastBlock
Definition DecompAlgo.h:204
double m_globalLB
Definition DecompAlgo.h:241
const int getPriceCallsTotal() const
Definition DecompAlgo.h:760
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)
const AlpsDecompTreeNode * m_curNode
Definition DecompAlgo.h:250
int m_rrIterSinceAll
Definition DecompAlgo.h:205
std::ostream * m_osLog
Stream for log file (default to stdout).
Definition DecompAlgo.h:124
bool isLPFeasible(const double *x, const bool isXSparse=false, const double feasVarTol=1.0e-6, const double feasConTol=1.0e-5)
bool checkPointFeasible(const DecompConstraintSet *modelCore, const double *x)
int m_compressColsLastNumCols
Definition DecompAlgo.h:224
const DecompApp * getDecompApp() const
Definition DecompAlgo.h:745
virtual void setObjBoundIP(const double thisBound)
Set the current integer bound and update best/history.
Definition DecompAlgo.h:904
std::vector< DecompSolution * > m_xhatIPFeas
Definition DecompAlgo.h:189
void printCurrentProblemDual(OsiSolverInterface *si, const std::string baseName, const int nodeIndex, const int cutPass, const int pricePass)
DecompStats m_stats
Storage of statistics for run and node.
Definition DecompAlgo.h:113
std::map< int, std::vector< DecompSubModel > > m_modelRelaxNest
Definition DecompAlgo.h:163
std::string m_classTag
Store the name of the class (for logging/debugging) - "who am I?".
Definition DecompAlgo.h:75
const double getCutoffUB() const
Definition DecompAlgo.h:733
const double getNodeLPGap() const
Get the current node (continuous) gap.
Definition DecompAlgo.h:826
DecompPhase m_phaseForce
Definition DecompAlgo.h:103
void checkMasterDualObj()
void masterMatrixAddMOCols(CoinPackedMatrix *masterM, double *colLB, double *colUB, double *objCoeff, std::vector< std::string > &colNames)
void printBasisInfo(OsiSolverInterface *si, std::ostream *os)
virtual void setObjBound(const double thisBound, const double thisBoundUB)
Set the current continuous bounds and update best/history.
Definition DecompAlgo.h:870
DecompCutList m_cuts
Containers for cuts (current and pool).
Definition DecompAlgo.h:175
virtual int generateVars(DecompVarList &newVars, double &mostNegReducedCost)
const double * m_objective
Definition DecompAlgo.h:160
std::vector< DecompColType > m_masterColType
Definition DecompAlgo.h:216
virtual int compressColumns()
Definition DecompAlgo.h:381
int m_nRowsOrig
Definition DecompAlgo.h:211
std::vector< double > m_dualSolution
Definition DecompAlgo.h:195
bool m_useInitLpDuals
Definition DecompAlgo.h:238
void createOsiSubProblem(DecompSubModel &subModel)
virtual void phaseUpdate(DecompPhase &phase, DecompStatus &status)
Update of the phase for process loop.
virtual void addCutsToPool(const double *x, DecompCutList &newCuts, int &m_cutsThisCall)
virtual void setMasterBounds(const double *lbs, const double *ubs)
OsiSolverInterface * getOsiIpSolverInterface()
const int getStopCriteria() const
Definition DecompAlgo.h:805
void masterPhaseItoII()
std::vector< double > m_origColLB
Pointer (and label) to current active model core/relax.
Definition DecompAlgo.h:133
int m_nRowsBranch
Definition DecompAlgo.h:212
virtual int generateInitVars(DecompVarList &initVars)
Generate initial variables for master problem (PC/DC/RC).
DecompAlgoType m_algo
Type of algorithm for this instance.
Definition DecompAlgo.h:86
DecompStatus solveRelaxed(const double *redCostX, const double *origCost, const double alpha, const int n_origCols, const bool isNested, DecompSubModel &subModel, DecompSolverResult *solveResult, std::list< DecompVar * > &vars, double timeLimit)
DecompCutPool m_cutpool
Definition DecompAlgo.h:176
const int getAlgo() const
Definition DecompAlgo.h:688
bool m_objNoChange
Definition DecompAlgo.h:234
const DecompSolution * getXhatIPBest() const
Definition DecompAlgo.h:725
virtual void solveMasterAsMIP()
Definition DecompAlgo.h:376
const DecompSubModel & getModelCore() const
Definition DecompAlgo.h:684
const DecompParam & getParam() const
Definition DecompAlgo.h:692
bool isDualRayInfProofCpx(const double *dualRay, const CoinPackedMatrix *rowMatrix, const double *colLB, const double *colUB, const double *rowRhs, std::ostream *os)
double m_relGap
Current node gap (bestUB-bestLB)/bestLB.
Definition DecompAlgo.h:229
int m_nRowsCuts
Definition DecompAlgo.h:214
virtual void recomposeSolution(const double *solution, double *rsolution)
Compose solution in x-space from current space.
virtual void masterMatrixAddArtCols(CoinPackedMatrix *masterM, double *colLB, double *colUB, double *objCoeff, std::vector< std::string > &colNames, int startRow, int endRow, DecompRowType rowType)
bool isGapTight()
Definition DecompAlgo.h:387
int m_nRowsConvex
Definition DecompAlgo.h:213
void coreMatrixAppendColBounds()
Calculate gap: |(ub-lb)|/|lb|.
double m_infinity
The value of "infinity".
Definition DecompAlgo.h:96
const double getNodeIPGap() const
Get the current node (integrality) gap.
Definition DecompAlgo.h:819
double getMasterObjValue() const
Definition DecompAlgo.h:787
DecompParam m_param
Parameters.
Definition DecompAlgo.h:80
OsiSolverInterface * getMasterOSI()
Definition DecompAlgo.h:700
void printCurrentProblem(const OsiSolverInterface *si, const std::string fileName, const bool printMps=true, const bool printLp=true)
DecompNodeStats m_nodeStats
Definition DecompAlgo.h:114
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).
DecompVarList m_vars
Containers for variables (current and pool).
Definition DecompAlgo.h:169
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)
DecompSubModel m_modelCore
Definition DecompAlgo.h:161
const double * getColLBNode() const
Definition DecompAlgo.h:667
DecompApp * m_app
Pointer to current active DECOMP application.
Definition DecompAlgo.h:108
const int getNodeIndex() const
Definition DecompAlgo.h:752
void checkBlocksColumns()
int m_colIndexUnique
Definition DecompAlgo.h:232
DecompAlgo(const DecompAlgoType algo, DecompApp *app, UtilParameters &utilParam, bool doSetup=true)
Default constructors.
Definition DecompAlgo.h:979
virtual int generateCuts(double *xhat, DecompCutList &newCuts)
const double * getColUBNode() const
Definition DecompAlgo.h:670
void printCuts(std::ostream *os)
double * m_colLBNode
Definition DecompAlgo.h:220
double m_cutoffUB
User-defined cutoff (global UB) for B&B fathoming and LR.
Definition DecompAlgo.h:187
std::map< int, DecompSubModel > m_modelRelax
Definition DecompAlgo.h:162
const DecompParam & getDecompParam() const
Definition DecompAlgo.h:741
DecompAlgoCGL * m_cgl
Definition DecompAlgo.h:126
bool m_isStrongBranch
Definition DecompAlgo.h:248
void breakOutPartial(const double *xHat, DecompVarList &newVars, const double intTol=1.0e-5)
OsiSolverInterface * m_auxSI
Definition DecompAlgo.h:157
const std::vector< DecompSolution * > & getXhatIPFeas() const
Definition DecompAlgo.h:729
OsiClpSolverInterface * m_cutgenSI
Solver interface(s) for entire problem (Q'').
Definition DecompAlgo.h:155
const AlpsDecompTreeNode * getCurrentNode() const
Provide the current node the algorithm is solving.
Definition DecompAlgo.h:316
double m_stabEpsilon
Definition DecompAlgo.h:237
virtual int addCutsFromPool()
std::vector< double > m_reducedCost
Definition DecompAlgo.h:196
virtual void postProcessBranch(DecompStatus decompStatus)
Do some information sending after the current node has been branched.
Definition DecompAlgo.h:332
virtual void addVarsToPool(DecompVarList &newVars)
void setCutoffUB(const double thisBound)
Definition DecompAlgo.h:719
void checkReducedCost(const double *u, const double *u_adjusted)
const double * getOrigObjective() const
Definition DecompAlgo.h:681
void loadSIFromModel(OsiSolverInterface *si, bool doInt=false)
virtual DecompSolverResult * solveDirect(const DecompSolution *startSol=NULL)
Definition DecompAlgo.h:585
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)
double m_masterObjLast
Definition DecompAlgo.h:233
std::vector< DecompRowType > m_masterRowType
Definition DecompAlgo.h:215
virtual bool isDone()
Definition DecompAlgo.h:416
int getNumRowType(DecompRowType rowType)
Definition DecompAlgo.h:942
std::vector< double > m_origColUB
Definition DecompAlgo.h:134
virtual bool updateObjBound(const double mostNegRC=-DecompBigNum)
Calculate the current LB and update best/history.
bool isMasterColMasterOnly(const int index) const
Definition DecompAlgo.h:618
void generateVarsCalcRedCost(const double *u, double *redCostX)
Calculated reduced cost vector (over vars in compact space) for a given dual vector.
void checkDuals()
virtual const double * getMasterDualSolution() const
Get current dual solution for master problem.
Definition DecompAlgo.h:777
std::vector< double > m_phaseIObj
Definition DecompAlgo.h:244
std::vector< double > m_primSolution
Definition DecompAlgo.h:194
virtual void adjustMasterDualSolution()
Adjust the current dual solution for master problem.
Definition DecompAlgo.h:784
bool isMasterColArtificial(const int index) const
Definition DecompAlgo.h:625
DecompParam & getMutableParam()
Definition DecompAlgo.h:696
void masterPhaseIItoI()
bool isMasterColStructural(const int index) const
Definition DecompAlgo.h:621
virtual ~DecompAlgo()
Destructor.
virtual void setSubProbBounds(const double *lbs, const double *ubs)
virtual void phaseDone()
Run the done phase for processing node.
Definition DecompAlgo.h:368
virtual void phaseInit(DecompPhase &phase)
Run the initial phase for processing node.
Definition DecompAlgo.h:359
const double * getMasterPrimalSolution() const
Get current primal solution for master problem.
Definition DecompAlgo.h:767
const double * getMasterColReducedCost() const
Definition DecompAlgo.h:771
double getInfinity()
Return the value of infinity.
Definition DecompAlgo.h:408
const double * getXhat() const
Get a ptr to the current solution (in x-space).
Definition DecompAlgo.h:715
double m_globalUB
Definition DecompAlgo.h:242
void appendVars(DecompVar *var)
Definition DecompAlgo.h:466
int m_cutgenObjCutInd
Definition DecompAlgo.h:156
std::vector< int > m_masterOnlyCols
Definition DecompAlgo.h:252
const double getObjBestBoundUB() const
Get the current best UB.
Definition DecompAlgo.h:856
virtual int adjustColumnsEffCnt()
Definition DecompAlgo.h:378
void generateVarsAdjustDuals(const double *uOld, double *uNew)
Create an adjusted dual vector with the duals from the convexity constraints removed.
virtual void addVarsFromPool()
DecompSubModel & getModelRelax(const int blockId)
Definition DecompAlgo.h:704
const double getMasterRowType(int row) const
Get a specific row type.
Definition DecompAlgo.h:863
DecompMemPool m_memPool
Memory pool used to reduce the number of allocations needed.
Definition DecompAlgo.h:119
int m_numConvexCon
Definition DecompAlgo.h:201
DecompPhase m_phaseLast
Definition DecompAlgo.h:102
bool isTailoffLB(const int changeLen=10, const double changePerLimit=0.1)
bool m_firstPhase2Call
Definition DecompAlgo.h:247
DecompStatus m_status
The current algorithm status.
Definition DecompAlgo.h:91
OsiSolverInterface * getOsiLpSolverInterface()
UtilParameters * m_utilParam
Definition DecompAlgo.h:81
void initSetup()
Initial setup of algorithm structures and solver interfaces.
void getModelsFromApp()
int m_compressColsLastPrice
Definition DecompAlgo.h:223
DecompBranchingImplementation m_branchingImplementation
Definition DecompAlgo.h:261
DecompStats & getStats()
Definition DecompAlgo.h:677
const void setStrongBranchIter(bool isStrongBranch=true)
Set the object to be in strong branching mode.
Definition DecompAlgo.h:849
void printVars(std::ostream *os)
std::vector< int > m_masterArtCols
Definition DecompAlgo.h:217
DecompVarPool m_varpool
Definition DecompAlgo.h:170
OsiSolverInterface * m_masterSI
Solver interface(s) for subproblems (P').
Definition DecompAlgo.h:147
void appendVars(DecompVarList &varList)
Definition DecompAlgo.h:469
virtual void createMasterProblem(DecompVarList &initVars)
Create the master problem (all algorithms must define this function).
DecompAlgoStop m_stopCriteria
Definition DecompAlgo.h:231
std::map< int, int > m_masterOnlyColsMap
Map from original index to master index for master-only vars.
Definition DecompAlgo.h:256
const double getGlobalGap() const
Get the current global (integrality) gap.
Definition DecompAlgo.h:812
std::vector< double * > getDualRaysCpx(int maxNumRays)
void createFullMps(const std::string fileName)
The main application class.
Definition DecompApp.h:48
DecompAlgo * m_decompAlgo
Pointer to the base algorithmic object.
Definition DecompApp.h:106
DecompParam m_param
Parameters.
Definition DecompApp.h:79
const double * m_objective
Model data: objective function.
Definition DecompApp.h:85
int priceCallsTotal
Number of price calls in this node in total.
int cutCallsTotal
Number of cut calls in this node in total.
int cutsThisCall
Number of cuts generated in this particular cut call.
DecompObjBound * getLastBound()
std::pair< double, double > objBest
The global lower (.first) and upper (.second) bound.
int nodeIndex
The node index (in the branch-and-bound tree).
int varsThisCall
Number of vars generated in this particular price call.
std::vector< DecompObjBound > objHistoryBound
Storage of the bounds.
double thisBoundIP
The recorded integer upper bound.
Definition DecompStats.h:59
int pricePass
The price pass when bound was recorded.
Definition DecompStats.h:38
int phase
The phase when bound was recorded.
Definition DecompStats.h:30
double bestBoundIP
The best recorded integer upper bound.
Definition DecompStats.h:64
double thisBound
The recorded continuous lower bound.
Definition DecompStats.h:46
double thisBoundUB
The recorded continuous upper bound.
Definition DecompStats.h:50
double bestBound
The best recorded continuous lower bound.
Definition DecompStats.h:55
int cutPass
The cut pass when bound was recorded.
Definition DecompStats.h:34
double timeStamp
The time stamp (from start) when bound was recorded.
Definition DecompStats.h:42
void getSettings(UtilParameters &param)
bool BranchEnforceInSubProb
bool BranchEnforceInMaster
double MasterGapLimit
Definition DecompParam.h:81
int LogDebugLevel
Definition DecompParam.h:39
Storage of solver result.
virtual const double * getObjCoefficients() const=0
double getRealTime()
Get wallClock time.
Definition UtilTimer.h:74