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 }
625 bool isMasterColArtificial(const int index) const {
626 return (m_masterColType[index] == DecompCol_ArtForRowL ||
634 }
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) {
1037 } else if (m_param.BranchEnforceInMaster == true
1038 && m_param.BranchEnforceInSubProb == false) {
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
1063 virtual ~DecompAlgo() {
1064 //UtilDeleteVectorPtr(m_subprobSI);
1075 }
1082};
1083
1084#endif
const double COIN_DBL_MAX
DecompBranchingImplementation
Definition: Decomp.h:320
@ DecompBranchInMaster
Definition: Decomp.h:322
@ 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|.
#define UtilException(msg, methodN, classN)
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.
Definition: DecompAlgoCGL.h:41
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
int m_function
Definition: DecompAlgo.h:246
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.
int m_numCols
Definition: DecompAlgo.h:197
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.
Definition: DecompAlgo.h:1063
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
int m_nArtCols
Definition: DecompAlgo.h:208
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.
Definition: DecompStats.h:154
int cutCallsTotal
Number of cut calls in this node in total.
Definition: DecompStats.h:149
int cutsThisCall
Number of cuts generated in this particular cut call.
Definition: DecompStats.h:139
DecompObjBound * getLastBound()
Definition: DecompStats.h:200
std::pair< double, double > objBest
The global lower (.first) and upper (.second) bound.
Definition: DecompStats.h:119
int nodeIndex
The node index (in the branch-and-bound tree).
Definition: DecompStats.h:124
int varsThisCall
Number of vars generated in this particular price call.
Definition: DecompStats.h:144
std::vector< DecompObjBound > objHistoryBound
Storage of the bounds.
Definition: DecompStats.h:114
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)
Definition: DecompParam.h:453
void dumpSettings(const std::string &sec, std::ostream *os=&std::cout)
Definition: DecompParam.h:473
bool BranchEnforceInSubProb
Definition: DecompParam.h:191
bool BranchEnforceInMaster
Definition: DecompParam.h:192
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