56 #include "OsiClpSolverInterface.hpp" 57 class OsiSolverInterface;
309 const double globalLB,
310 const double globalUB);
346 const bool resolve =
true,
347 const int maxInnerIter = COIN_INT_MAX,
348 const int maxOuterIter = COIN_INT_MAX);
394 <<
" isTight = " << (
m_relGap <= tightGap)
431 double& mostNegReducedCost);
444 const bool isXSparse =
false,
445 const double feasVarTol = 1.0e-6,
446 const double feasConTol = 1.0e-5,
447 const double intTol = 1.0e-5);
450 const bool isXSparse =
false,
451 const double feasVarTol = 1.0e-6,
452 const double feasConTol = 1.0e-5);
456 const double* origCost,
458 const int n_origCols,
462 std::list<DecompVar*>& vars,
470 copy(varList.begin(), varList.end(), back_inserter(
m_vars));
481 std::vector< std::pair<int, double> >& downBranchUb,
482 std::vector< std::pair<int, double> >& upBranchLb,
483 std::vector< std::pair<int, double> >& upBranchUb);
527 const CoinPackedMatrix* rowMatrix,
530 const double* rowRhs,
533 const CoinPackedMatrix* rowMatrix,
536 const double* rowRhs,
547 const std::string baseName,
550 const int pricePass);
553 const std::string baseName,
557 const int blockId = -1,
558 const bool printMps =
true,
559 const bool printLp =
true);
564 const std::string fileName,
565 const bool printMps =
true,
566 const bool printLp =
true);
594 std::vector<std::string>& colNames);
597 std::vector<int >& colInd,
598 std::vector<double >& colVal,
611 std::vector<std::string>& colNames,
638 const double intTol = 1.0e-5);
705 std::map<int, DecompSubModel>::iterator mit;
708 return (*mit).second;
794 const double* objCoef =
m_masterSI->getObjCoefficients();
798 for (
int i = 0 ; i < nc ; i++ ) {
799 retVal += objCoef[i] * primSol[i];
830 if (nHistorySize > 0) {
871 const double thisBoundUB) {
891 #ifdef UTIL_USE_TIMERS 910 (*
m_osLog) <<
"New Global UB = " 922 objBoundIP = *objBoundLP;
927 #ifdef UTIL_USE_TIMERS 939 const double changePerLimit = 0.1);
944 std::vector<DecompRowType>::iterator vi;
947 if (*vi == rowType) {
982 bool doSetup =
true) :
1041 throw UtilException(
"Branching Implementation should be set correctly",
1042 "initSetup",
"DecompAlgo");
int varsThisCall
Number of vars generated in this particular price call.
bool isMasterColStructural(const int index) const
const DecompApp * getDecompApp() const
virtual DecompStatus processNode(const AlpsDecompTreeNode *node, const double globalLB, const double globalUB)
The main DECOMP process loop for a node.
bool checkPointFeasible(const DecompConstraintSet *modelCore, const double *x)
const double * getXhat() const
Get a ptr to the current solution (in x-space).
std::vector< DecompColType > m_masterColType
void UtilPrintFuncEnd(std::ostream *os, const std::string &classTag, const std::string &funcName, const int logLevel, const int logLimit)
OsiSolverInterface * getOsiIpSolverInterface()
double m_relGap
Current node gap (bestUB-bestLB)/bestLB.
DecompBranchingImplementation
virtual bool updateObjBound(const double mostNegRC=-DecompBigNum)
Calculate the current LB and update best/history.
virtual void setMasterBounds(const double *lbs, const double *ubs)
void breakOutPartial(const double *xHat, DecompVarList &newVars, const double intTol=1.0e-5)
void printVars(std::ostream *os)
virtual void phaseDone()
Run the done phase for processing node.
const double * getMasterPrimalSolution() const
Get current primal solution for master problem.
std::vector< double > m_origColUB
DecompApp * getDecompAppMutable()
virtual void adjustMasterDualSolution()
Adjust the current dual solution for master problem.
std::vector< DecompSolution * > m_xhatIPFeas
void createFullMps(const std::string fileName)
DecompStats m_stats
Storage of statistics for run and node.
virtual void setObjBoundIP(const double thisBound)
Set the current integer bound and update best/history.
bool isMasterColArtificial(const int index) const
void appendVars(DecompVarList &varList)
const void setStrongBranchIter(bool isStrongBranch=true)
Set the object to be in strong branching mode.
double thisBoundUB
The recorded continuous upper bound.
OsiSolverInterface * getMasterOSI()
bool isDualRayInfProofCpx(const double *dualRay, const CoinPackedMatrix *rowMatrix, const double *colLB, const double *colUB, const double *rowRhs, std::ostream *os)
const double getObjBestBoundLB() const
Get the current best LB.
double UtilCalculateGap(const double boundLB, const double boundUB, double infinity)
Calculate gap: |(ub-lb)|/|lb|.
std::map< int, DecompSubModel > m_modelRelax
double getRealTime()
Get wallClock time.
const DecompParam & getDecompParam() const
virtual void createMasterProblem(DecompVarList &initVars)
Create the master problem (all algorithms must define this function).
DecompApp * m_app
Pointer to current active DECOMP application.
std::vector< int > m_masterArtCols
const int getNodeIndex() const
DecompAlgo * m_decompAlgo
Pointer to the base algorithmic object.
std::vector< double > m_primSolution
virtual ~DecompAlgo()
Destructor.
virtual void masterMatrixAddArtCols(CoinPackedMatrix *masterM, double *colLB, double *colUB, double *objCoeff, std::vector< std::string > &colNames, int startRow, int endRow, DecompRowType rowType)
DecompParam m_param
Parameters.
std::vector< double * > getDualRaysCpx(int maxNumRays)
virtual void addVarsFromPool()
std::string UtilDblToStr(const double x, const int precision=-1, const double tooBig=UtilSmallerThanTooBig)
int cutPass
The cut pass when bound was recorded.
std::map< int, int > m_artColIndToRowInd
int priceCallsTotal
Number of price calls in this node in total.
DecompCutList m_cuts
Containers for cuts (current and pool).
void loadSIFromModel(OsiSolverInterface *si, bool doInt=false)
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)
std::list< DecompCut * > DecompCutList
void coreMatrixAppendColBounds()
Calculate gap: |(ub-lb)|/|lb|.
const AlpsDecompTreeNode * getCurrentNode() const
Provide the current node the algorithm is solving.
bool BranchEnforceInMaster
std::list< DecompVar * > DecompVarList
void dumpSettings(const std::string &sec, std::ostream *os=&std::cout)
virtual int generateCuts(double *xhat, DecompCutList &newCuts)
DecompPhase m_phase
The current algorithm phase.
void printBasisInfo(OsiSolverInterface *si, std::ostream *os)
const DecompSolution * getXhatIPBest() const
DecompAlgo(const DecompAlgoType algo, DecompApp *app, UtilParameters &utilParam, bool doSetup=true)
Default constructors.
std::vector< double > m_origColLB
Pointer (and label) to current active model core/relax.
virtual const double * getMasterDualSolution() const
Get current dual solution for master problem.
std::vector< double * > getDualRays(int maxNumRays)
UtilParameters * m_utilParam
DecompSubModel & getModelRelax(const int blockId)
virtual int generateVars(DecompVarList &newVars, double &mostNegReducedCost)
static UtilTimer globalTimer
const double DecompBigNum
OsiSolverInterface * getOsiLpSolverInterface()
const double getObjBestBoundUB() const
Get the current best UB.
std::string m_classTag
Store the name of the class (for logging/debugging) - "who am I?".
std::vector< double > m_reducedCost
virtual void setSubProbBounds(const double *lbs, const double *ubs)
void setCutoffUB(const double thisBound)
const int getAlgo() const
int m_compressColsLastPrice
#define UTIL_MSG(param, level, x)
DecompAlgoStop m_stopCriteria
virtual void postProcessBranch(DecompStatus decompStatus)
Do some information sending after the current node has been branched.
void checkMasterDualObj()
std::vector< double > m_dualSolution
double getInfinity()
Return the value of infinity.
DecompSolution * m_xhatIPBest
double bestBound
The best recorded continuous lower bound.
const double * getMasterColReducedCost() const
const double * m_objective
Model data: objective function.
std::pair< double, double > objBest
The global lower (.first) and upper (.second) bound.
double m_infinity
The value of "infinity".
virtual void setObjBound(const double thisBound, const double thisBoundUB)
Set the current continuous bounds and update best/history.
OsiClpSolverInterface * m_cutgenSI
Solver interface(s) for entire problem (Q'').
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).
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)
double * m_xhat
Storage for current solution (in x-space).
virtual int addCutsFromPool()
std::vector< int > m_masterOnlyCols
const DecompSubModel & getModelCore() const
void checkReducedCost(const double *u, const double *u_adjusted)
const double getNodeLPGap() const
Get the current node (continuous) gap.
const double * getOrigObjective() const
const double * getColUBNode() const
virtual void phaseInit(DecompPhase &phase)
Run the initial phase for processing node.
void UtilPrintFuncBegin(std::ostream *os, const std::string &classTag, const std::string &funcName, const int logLevel, const int logLimit)
virtual void addCutsToPool(const double *x, DecompCutList &newCuts, int &m_cutsThisCall)
DecompVarList m_vars
Containers for variables (current and pool).
#define UtilException(msg, methodN, classN)
bool BranchEnforceInSubProb
void checkBlocksColumns()
bool isLPFeasible(const double *x, const bool isXSparse=false, const double feasVarTol=1.0e-6, const double feasConTol=1.0e-5)
virtual void phaseUpdate(DecompPhase &phase, DecompStatus &status)
Update of the phase for process loop.
std::vector< DecompObjBound > objHistoryBound
Storage of the bounds.
void printCuts(std::ostream *os)
double getMasterObjValue() const
virtual DecompSolverResult * solveDirect(const DecompSolution *startSol=NULL)
const double * getColLBNode() const
const std::string DecompAlgoStr[5]
const std::vector< DecompSolution * > & getXhatIPFeas() const
double bestBoundIP
The best recorded integer upper bound.
void createOsiSubProblem(DecompSubModel &subModel)
Storage of solver result.
void initSetup()
Initial setup of algorithm structures and solver interfaces.
DecompParam m_param
Parameters.
DecompParam & getMutableParam()
std::vector< double * > getDualRaysOsi(int maxNumRays)
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)
std::vector< double > m_phaseIObj
std::vector< DecompRowType > m_masterRowType
double thisBound
The recorded continuous lower bound.
DecompNodeStats m_nodeStats
std::map< int, int > m_masterOnlyColsMap
Map from original index to master index for master-only vars.
DecompStats & getDecompStats()
void generateVarsAdjustDuals(const double *uOld, double *uNew)
Create an adjusted dual vector with the duals from the convexity constraints removed.
void masterMatrixAddMOCols(CoinPackedMatrix *masterM, double *colLB, double *colUB, double *objCoeff, std::vector< std::string > &colNames)
An interface to CGL cut generator library.
DecompSubModel m_modelCore
const double getGlobalGap() const
Get the current global (integrality) gap.
virtual int generateInitVars(DecompVarList &initVars)
Generate initial variables for master problem (PC/DC/RC).
DecompObjBound * getLastBound()
const double getCutoffUB() const
const double getNodeIPGap() const
Get the current node (integrality) gap.
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)
virtual void addVarsToPool(DecompVarList &newVars)
void getSettings(UtilParameters ¶m)
int cutCallsTotal
Number of cut calls in this node in total.
const AlpsDecompTreeNode * m_curNode
virtual void solveMasterAsMIP()
void UtilDeleteVectorPtr(vector< T *> &vectorPtr, typename vector< T *>::iterator first, typename vector< T *>::iterator last)
bool isTailoffLB(const int changeLen=10, const double changePerLimit=0.1)
OsiSolverInterface * m_auxSI
void appendVars(DecompVar *var)
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)
The main application class.
double thisBoundIP
The recorded integer upper bound.
std::ostream * m_osLog
Stream for log file (default to stdout).
OsiSolverInterface * m_masterSI
Solver interface(s) for subproblems (P').
Base class for DECOMP algorithms.
const int getStopCriteria() const
DecompBranchingImplementation m_branchingImplementation
void UtilDeleteListPtr(list< T *> &listPtr, typename list< T *>::iterator first, typename list< T *>::iterator last)
bool isMasterColMasterOnly(const int index) const
const int getCutCallsTotal() const
int nodeIndex
The node index (in the branch-and-bound tree).
virtual void postProcessNode(DecompStatus decompStatus)
Do some information sending after the current node has been processed.
void printCurrentProblemDual(OsiSolverInterface *si, const std::string baseName, const int nodeIndex, const int cutPass, const int pricePass)
const int getPriceCallsTotal() const
DecompAlgoType m_algo
Type of algorithm for this instance.
int getNumRowType(DecompRowType rowType)
double timeStamp
The time stamp (from start) when bound was recorded.
virtual int adjustColumnsEffCnt()
int phase
The phase when bound was recorded.
const DecompParam & getParam() const
virtual void recomposeSolution(const double *solution, double *rsolution)
Compose solution in x-space from current space.
const double * m_objective
std::map< int, std::vector< DecompSubModel > > m_modelRelaxNest
DecompMemPool m_memPool
Memory pool used to reduce the number of allocations needed.
const double getMasterRowType(int row) const
Get a specific row type.
void generateVarsCalcRedCost(const double *u, double *redCostX)
Calculated reduced cost vector (over vars in compact space) for a given dual vector.
virtual int compressColumns()
int cutsThisCall
Number of cuts generated in this particular cut call.
int pricePass
The price pass when bound was recorded.
double m_cutoffUB
User-defined cutoff (global UB) for B&B fathoming and LR.
int m_compressColsLastNumCols
bool isDualRayInfProof(const double *dualRay, const CoinPackedMatrix *rowMatrix, const double *colLB, const double *colUB, const double *rowRhs, std::ostream *os)
DecompStatus m_status
The current algorithm status.