37 #ifndef __BB_PARA_SOLVER_H__ 38 #define __BB_PARA_SOLVER_H__ 55 #define ENFORCED_THRESHOLD 5 442 std::cerr <<
"********** BbParaSolver does not use this function. **********" << std::endl;
452 int nSelfSplitNodesLeft
461 int nSelfSplitNodesLeft
873 long long nNodesSolved,
875 double bestDualBoundValue,
896 return ( collectingMode || collectingManyNodes );
934 double estimateValue,
945 double estimateValue,
953 double bestDualBoundValue
1023 nParaNodesSolvedAtPreCheck++;
1094 return (nTransferLimit > 0);
1114 return (nTransferredNodes >= nTransferLimit);
1123 targetBound = -DBL_MAX;
1124 nTransferLimit = -1;
1125 nTransferredNodes = -1;
1126 collectingManyNodes =
false;
1146 collectingManyNodes =
true;
1197 collectingManyNodes =
true;
1207 return( collectingManyNodes && (nCollectOnce < 0) );
1248 if( minIisum > sum ) minIisum = sum;
1249 if( maxIisum < sum ) maxIisum = sum;
1250 if( minNii > count ) minNii = count;
1251 if( maxNii < count ) maxNii = count;
1261 nSimplexIterRoot = iter;
1325 enoughGainObtained =
false;
1383 const std::string& filename
1399 std::cout <<
"*** virtual function BbParaSolver::setLightWeightRootNodeProcess is called ***" << std::endl;
1408 std::cout <<
"*** virtual function BbParaSolver::setOriginalRootNodeProcess is called ***" << std::endl;
1461 nTransferredLocalCuts += n;
1462 if( minTransferredLocalCuts > n )
1464 minTransferredLocalCuts = n;
1466 if( maxTransferredLocalCuts < n )
1468 maxTransferredLocalCuts = n;
1479 nTransferredBendersCuts += n;
1480 if( minTransferredBendersCuts > n )
1482 minTransferredBendersCuts = n;
1484 if( maxTransferredBendersCuts < n )
1486 maxTransferredBendersCuts = n;
1568 #endif // __BB_PARA_SOLVER_H__ bool newParaNodeExists()
check if a new ParaNode was received or not
int minNii
minimum number of integer infeasibility
void setOnceBreak()
set once braking procedure worked
bool isOnceBreak()
check if once breaking procedure worked or not
int minTransferredBendersCutsFromSolver
minimum number of benders cuts transferred from this Solver
double rootNodeTime
Times.
virtual void createSubproblem()=0
create subproblem
double minIisum
minimum sum of integer infeasibility
int nTransferredBendersCuts
number of benders cuts transferred from a ParaNode
bool isIterativeBreakDownApplied()
check if iterative break down is applied or not
bool notificationProcessed
if true, notification is issued but not receive the corresponding LCB
double getLcBestDualBoundValue()
get LoadCorrdinator best dual bound value
virtual int processTagSolution(int source, int tag)
process TagSolution
bool isBreaking()
check if Solver is in racing stage or not
static ScipParaCommTh * comm
virtual int processTagNoNodes(int source, int tag)
process TagNoNodes
virtual int processTagTerminateSolvingToRestart(int source, int tag)
process TagTerminateSolvingToRestart
double getBoundGapForStopSolving()
get bound gap for stop solving. This value is not used to decide stop solving. It is used a part of c...
bool isAggressivePresolvingSpecified()
check if aggressive presolving is specified
bool collectingInterrupt
when the solver is interrupted, all nodes are collected to LC
bool racingInterruptIsRequested
indicate a racing interrupt is requested
virtual void restartRacing()
restart racing
virtual double getElapsedTime()=0
get elapsed time
virtual void waitNotificationIdMessage()
wait notification id message to synchronized with LoadCoordinator
ParaParamSet * paraParams
ParaParamSet object.
virtual void run(ParaRacingRampUpParamSet *inRacingRampUpParamSet)
run this Solver with ParaNode object
virtual double getDualBoundValue()=0
get dual bound value
static const int AggressivePresolveStopDepth
void countInPrecheckSolvedParaNodes()
count ParaNode solved at root node in pre-check
int nParaNodesSolvedAtRoot
number of ParaNodes solved at root node
int nTotalRestarts
number of total restarts
void setII(double sum, int count)
set sum and number of integer infeasibility
int maxRestarts
maximum number of restarts
virtual int processTagUbBoundTightened(int source, int tag)
process TagUbBoundTightened
virtual int processTagWinnerRacingRampUpParamSet(int source, int tag)
process TagWinnerRacingRampUpParamSet
void setRootNodeSimplexIter(int iter)
set number of simplex iteration at root node
double getGlobalBestIncumbentValue()
get global best incumbent value
static const int BgapStopSolvingMode
bool isRacingRampUp()
check if this solver is in racing ramp-up or not
virtual void sendCompletionOfCalculation(double stopTime)
send completion of calculation
int minTransferredBendersCuts
minimum number of benders cuts transferred from a ParaNode
int getSubMipDepth()
get depth of sub-MIP root node in global search tree
int maxTransferredLocalCuts
maximum number of local cuts (including conflict cuts) transferred from a ParaNode ...
double globalBestIncumbentValue
global best incumbent value
int getBigDualGapSubtreeHandlingStrategy()
get big dual gap subtree handling strategy
bool isAggressiveCollecting()
check if Solver is in aggressive collecting mode or not
virtual int bcast(ParaComm *comm, int root)=0
broadcast this object
ParaRacingRampUpParamSet * racingParams
ParaRacingRampUpParamSet object. This is also a flag to indicate running with racing ramp-up...
bool isRacingInterruptRequested()
check if racing interrupt was requested or not
double globalBestDualBoundValueAtWarmStart
global best dual bound value which is set when system warm starts
virtual int getNRestarts()
get number of restarts (Derived class for SCIP should override this function)
void updateNTransferredLocalCuts(int n)
update number of transferred local cuts
virtual int processTagTestDualBoundGain(int source, int tag)
process TagTestDualBoundGain
bool lightWeightRootNodeComputation
indicate that fast root node computation is required
virtual int processTagNoWaitModeSend(int source, int tag)
process TagNoWaitModeSend
Base class for deterministic timer.
int getAggresivePresolvingDepth()
get depth to apply aggressive presolving
BbParaNodePool * selfSplitNodePool
Pool in Solver.
virtual int processTagRampUp(int source, int tag)
process TagRampUp
Defines for UG Framework.
int nTightenedInt
the number of tightened integral variable bounds in racing
virtual int processTagNotificationId(int source, int tag)
process TagNotificationId
virtual void issueInterruptSolve()
issue interrupt to solve
void updateNTransferredBendersCuts(int n)
update number of transferred benders cuts
int totalNSolved
Counters related to this BbParaSolver.
virtual bool waitToken(int rank)
wait token when UG runs with deterministic mode
int nSent
number of ParaNodes sent from this subtree rooted from the current ParaNode
virtual void iReceiveMessages()
non-blocking receive messages
virtual long long getSimplexIter()=0
get number of simplex iterations
bool isRacingStage()
check if Solver is in racing stage or not
int maxTransferredLocalCutsFromSolver
maximum number of local cuts transferred from this Solver
int maxNii
maximum number of integer infeasibility
int nSendInCollectingMode
number of nodes need to send in collecting mode
double getTimeStopSolvingMode()
get time to stop solving. This value is not used to decide stop solving. It is used a part of conditi...
virtual void setRootNodeTime()
set root node computing time
void setNotEnoughGain()
set dual bound gain is not enough
double pendingIncumbentValue
incumbent value which is pending to update in case of deterministic runs
bool isCollecingInterrupt()
check if collecting interrupt (interrupt with collecting all nodes) is requested or not ...
class for deterministic timer
static const int TimeStopSolvingMode
bool anotherNodeIsRequested
indicate that another node is requested or not
virtual int processTagCutOffValue(int source, int tag)
process TagCutOffValue
virtual void waitAckCompletion()
wait ack completion to synchronized with LoadCoordinator
static const int NStopSolvingMode
virtual void sendAnotherNodeRequest(double bestDualBoundValue)
send another node request
virtual void changeSearchStrategy(int searchStrategy)
change search strategy
virtual int processTagLCBestBoundValue(int source, int tag)
process TagLCBestBoundValue
virtual void passToken(int rank)
pass token to from the rank to the next
#define PARA_COMM_CALL(paracommcall)
static const int Deterministic
virtual int getRank()=0
get rank of this process or this thread depending on run-time environment
int nTightened
the number of tightened variable bounds in racing
virtual int getNTightened()
get number of tightened variables during racing
virtual void run()=0
run this Solver
virtual int processTagKeepRacing(int source, int tag)
process TagKeepRacing
virtual ~BbParaSolver()
destructor
int getCurrentSolivingNodeMergingStatus()
get current solving node merging status
int getAggresivePresolvingStopDepth()
get depth to stop aggressive presolving
Base class for solver: Generic parallelized solver.
virtual void tryNewSolution(ParaSolution *sol)=0
try to enter solution to base solver environment
virtual long long getNNodesSolved()=0
get number of nodes solved
int nTransferredNodes
keep track number of transferred nodes for breaking
double getGlobalBestDualBoundValueAtWarmStart()
get global best dual bound value at warm start (restart)
double getTargetBound()
get target bound for breaking
double averageDualBoundGain
average dual bound gain
int nSolved
Counters related to the current ParaNode.
int nHandlers
number of valid message handlers
double globalBestCutOffValue
global best cut off value
void passToken(int rank)
pass token to the next process
bool testDualBoundGain
indicate that the dual bound gain needs to test or not
virtual bool updateGlobalBestCutOffValue(double newValue)
update global best cutoff value
virtual int processTagInCollectingMode(int source, int tag)
process TagInCollectingMode
bool isGivenGapReached()
check if given gap is reached or not
static const int BigDualGapSubtreeHandling
virtual void writeSubproblem()=0
write subproblem
double targetBound
target bound value for breaking
double solverDualBound
dual bound value achieved for a subproblem
double getRealParamValue(int param)
for real parameters
ParaTask * getCurrentNode()
get current ParaNode object
virtual int processTagGlobalBestDualBoundValueAtWarmStart(int source, int tag)
process TagGlobalBestDualBoundValueAtWarmStart
virtual int processTagLightWeightRootNodeProcess(int source, int tag)
process TagLightWeightRootNodeProcess
int nParaNodesSolvedAtPreCheck
number of ParaNodes solved at pre-checking of root node solvability
int nParaTasksReceived
Counters related to this ParaSolver.
virtual void sendCompletionOfCalculationWithoutSolving(double stopTime, int tag, int nSelfSplitNodesLeft)
send completion of calculation with arguments
virtual int processTagToken(int source, int tag)
process TagToken
int nTransferredBendersCutsFromSolver
number of benders cuts transferred from this Solver
virtual size_t getNumOfNodes()=0
get number of BbParaNodes in this pool
int minRestarts
minimum number of restarts
virtual void setOriginalRootNodeProcess()
set original root node process
int nSolvedWithNoPreprocesses
number of nodes solved when it is solved with no preprocesses
virtual int processTagCollectAllNodes(int source, int tag)
process TagCollectAllNodes
#define THROW_LOGICAL_ERROR1(msg1)
virtual void freeSubproblem()=0
free subproblem
virtual int processTagTerminateRequest(int source, int tag)
process TagTerminateRequest
virtual void waitMessageIfNecessary()
wait a notification id message if it is needed to synchronize with LoadCoordinaor ...
double getRootNodeTime()
get root node computing time
virtual int processTagRetryRampUp(int source, int tag)
process TagRetryRampUp
virtual int getNNodesLeft()=0
get number of nodes left
Base class of communicator for UG Framework.
virtual void sendLocalSolution()
send solution found in this Solver
virtual bool canGenerateSpecialCutOffValue()
check if base solver can generate special cut off value or not
virtual int getRank()
get rank of this Solver
int maxTransferredBendersCuts
maximum number of benders cuts transferred from a ParaNode
virtual int processTagNoTestDualBoundGain(int source, int tag)
process TagNoTestDualBoundGain
int maxNSolved
maximum number of subtree nodes rooted from ParaNode
ParaTimer * paraTimer
timer for this ParaSolver
virtual int processTagTaskReceived(int source, int tag)
process TagTaskReceived
Base class for racing ramp-up parameter set.
void resetBreakingInfo()
reset breaking information
bool enoughGainObtained
indicate that the root node process improved dual bound enough or not
virtual void solve()=0
solve (sub)problem
virtual int processTagBreaking(int source, int tag)
process TagBreaking
double getCurrentSolvingNodeInitialDualBound()
get initial dual bound of current solving node
virtual void setRacingParams(ParaRacingRampUpParamSet *racingParms, bool winnerParam)=0
set racing parameters
bool isInCollectingMode()
check if Solver is in collecting mode or not
virtual bool updateGlobalBestIncumbentValue(double newValue)
update global best incumbent value
double maxIisum
maximum sum of integer infeasibility
double getPendingIncumbentValue()
get pending incumbent value
bool globalIncumbnetValueUpdateFlag
indicate that global incumbent value is updated in iReceiveMessages() routine
virtual void setOriginalNodeSelectionStrategy()=0
set original node selection strategy
Class for the difference between instance and subproblem.
virtual int ubBoundTightened(int source, int tag)
upper bound of variable tightened
int nTransferredLocalCuts
number of local cuts (including conflict cuts) transferred from a ParaNode
double minRootNodeTime
minimum time consumed by root node process
double getElapsedTimeOfNodeSolving()
the following functions may be called from callback routines of the target Solver ...
virtual bool saveIfImprovedSolutionWasFound(ParaSolution *sol)
save improved solution if it was found in this Solver
BbParaSolver()
constructor
virtual ParaTask * createParaTask()=0
create ParaTask object by default constructor
virtual bool updateGlobalBestIncumbentSolution(ParaSolution *sol)
update global best incumbent solution
virtual int getThresholdValue(int nNodes)
get threshold value to send ParaNodes to LoadCoordinator
ParaTask * currentTask
solving task
double getAverageDualBoundGain()
get average dual bound gain
virtual int processTagOutCollectingMode(int source, int tag)
process TagOutCollectingMode
int getSelfSplitNodesLeft()
get the number of nodes in slef-split node pool
bool givenGapIsReached
indicate that the given gap is reached or not
void globalIncumbnetValueIsReflected()
set global incumbent value is reflected
virtual bool wasTerminatedNormally()=0
check if Solver was terminated normally or not
double getBoundGapForCollectingMode()
get bound gap for collecting mode
static const int BgapCollectingMode
double idleTimeToWaitToken
idle time to wait token
static const int AggressivePresolveDepth
virtual void keepParaNode(long long n, int depth, double dualBound, double estimateValue, ParaDiffSubproblem *diffSubproblem)
keep a branch-and-bound node as ParaNode to LoadCoordinator
double maxRootNodeTime
maximum time consumed by root node process
bool collectingManyNodes
indicate that many nodes collecting is requested by LC
virtual void notifySelfSplitFinished()
notify Self-Split finished
int nTransferLimit
limit number of transferring nodes for breaking
bool isDualBoundGainTestNeeded()
check if dual bound gain needs to be tested or not
static const int RampUpPhaseProcess
bool isCollectingAllNodes()
check if Solver is sending all nodes to LoadCoordinaor or not
virtual bool notificationIsNecessary()
check if a notification message needs to send or not
bool aggressiveCollecting
indicate that if this solver has two nodes, this solver sends one to LC
virtual bool receiveNewTaskAndReactivate()
wait for receiving a new node and reactivate solver
void setKeepRacing(bool value)
set keep racing value
virtual void setWinnerRacingParams(ParaRacingRampUpParamSet *racingParms)=0
set winner racing parameters
void setSendBackAllNodes()
set counter and flag to indicate that all nodes are sent to LoadCooordinator
int maxTransferredBendersCutsFromSolver
maximum number of benders cuts transferred from this Solver
double paraTaskStartTime
start time of current ParaTask
int getNStopSolvingMode()
get number of nodes to stop solving. This number is not used to decide stop solving. It is used a part of conditions.
ParaInstance * getParaInstance()
get ParaInstance object
ParaTask * newTask
new task to solve
bool getNotificaionProcessed()
check if Solver is in notification process or not TODO: function name should be changed ...
bool waitToken(int rank)
wait token for deterministic mode
ParaInstance * paraInstance
root problem instance
double lcBestDualBoundValue
LoadCoordinator best dual bound value.
virtual int processTagWinner(int source, int tag)
process TagWinner
int totalNImprovedIncumbent
accumulated number of improvements of incumbent value in this BbParaSolver
int getIntParamValue(int param)
for int parameters
ParaComm * paraComm
ParaCommunicator object.
virtual int processTagRestart(int source, int tag)
process TagRestart
virtual void setLightWeightRootNodeProcess()
set light weight root node process
virtual int processTagLbBoundTightened(int source, int tag)
process TagLbBoundTightened
virtual void sendSolverState(long long nNodesSolved, int nNodesLeft, double bestDualBoundValue, double detTime)
send Solver state to LoadCoordinator
double totalRootNodeTime
accumulated root node process time solved by this solver so far
bool isGlobalIncumbentUpdated()
check if global incumbent value is updated or not
int nCollectOnce
number of nodes need to collect once
ParaParamSet * getParaParamSet()
get ParaParamSet object
int minTransferredLocalCuts
minimum number of local cuts (including conflict cuts) transferred from a ParaNode ...
virtual bool sendIfImprovedSolutionWasFound(ParaSolution *sol)
send improved solution if it was found in this Solver
int(BbParaSolver::* BbMessageHandlerFunctionPointer)(int, int)
int totalNSent
accumulated number of nodes sent from this BbParaSolver
virtual void sendParaNode(long long n, int depth, double dualBound, double estimateValue, ParaDiffSubproblem *diffSubproblem)
send a branch-and-bound node as ParaNode to LoadCoordinator
class ParaRacingRampUpParamSet (parameter set for racing ramp-up)
int nSimplexIterRoot
number of simplex iteration at root node
int minTransferredLocalCutsFromSolver
minimum number of local cuts transferred from this Solver
virtual int processTagTask(int source, int tag)
Message handlers
bool localIncumbentIsChecked
indicate if a local incumbent solution is checked or not
bool isAnotherNodeIsRequested()
check if another node is requested or not
virtual int processTagGivenGapIsReached(int source, int tag)
process TagGivenGapIsReached
virtual void sendSolverTerminationState()
send Solver termination state
virtual void solveToCheckEffectOfRootNodePreprocesses()
solve to check effect of root node preprocesses
virtual void writeCurrentTaskProblem(const std::string &filename)=0
write current node problem (this method is always useful for debugging, so we should implement this m...
bool noWaitModeSend
indicate that no wait mode sending is applied
Base class of communicator object.
int getNSendInCollectingMode()
get number of ParaNodes already sent in a collecting mode
bool keepRacing
indicate if Solver needs to do racing ramp-up repeatedly in case of warm start
virtual int processTagInterruptRequest(int source, int tag)
process TagInterruptRequest
virtual int lbBoundTightened(int source, int tag)
lower bound of variable tightened
bool collectingMode
indicate whether if this solver is in collecting mode or not
static const int IterativeBreakDown
int minNSolved
minimum number of subtree nodes rooted from ParaNode
virtual int processTagIncumbentValue(int source, int tag)
process TagIncumbentValue
int nTransferredLocalCutsFromSolver
number of local cuts transferred from this Solver
virtual int getNTightenedInt()
get number of tightened integral variables during racing
bool isManyNodesCollectionRequested()
check if many nodes collection was requested or not
bool onceBreak
indicate that the sub-MIP is broken down once
ParaComm * getParaComm()
get paraParaComm
double getCutOffValue()
get cut off value
bool isEnoughGainObtained()
check if dual bound gains enough or not
bool getBoolParamValue(int param)
for bool parameters
bool isTransferLimitReached()
check if the number of ParaNodes sent is reached to transfer limit specified
bool restartingRacing
indicate that this solver is restarting racing