bbParaSolverPool.h

Go to the documentation of this file.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*                                                                           */
/*          This file is part of the program and software framework          */
/*                    UG --- Ubquity Generator Framework                     */
/*                                                                           */
/*  Copyright Written by Yuji Shinano <shinano@zib.de>,                      */
/*            Copyright (C) 2021 by Zuse Institute Berlin,                   */
/*            licensed under LGPL version 3 or later.                        */
/*            Commercial licenses are available through <licenses@zib.de>    */
/*                                                                           */
/* This code is free software; you can redistribute it and/or                */
/* modify it under the terms of the GNU Lesser General Public License        */
/* as published by the Free Software Foundation; either version 3            */
/* of the License, or (at your option) any later version.                    */
/*                                                                           */
/* This program is distributed in the hope that it will be useful,           */
/* but WITHOUT ANY WARRANTY; without even the implied warranty of            */
/* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             */
/* GNU Lesser General Public License for more details.                       */
/*                                                                           */
/* You should have received a copy of the GNU Lesser General Public License  */
/* along with this program.  If not, see <http://www.gnu.org/licenses/>.     */
/*                                                                           */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/**@file    paraSolverPool.h
 * @brief   Solver pool.
 * @author  Yuji Shinano
 *
 *
 *
 */

/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/


#ifndef __BB_PARA_SOLVER_POOL_H__
#define __BB_PARA_SOLVER_POOL_H__
#include <cstdlib>
#include <map>
#include "ug/paraTask.h"
#include "ug/paraTimer.h"
#include "ug/paraRacingRampUpParamSet.h"
#include "ug/paraDeterministicTimer.h"
#include "ug/paraSolverPool.h"
#include "bbParaSolverTerminationState.h"
#include "bbParaNodePool.h"

namespace UG
{

class BbParaSolverPoolElement;
typedef BbParaSolverPoolElement * BbParaSolverPoolElementPtr;

// enum SolverStatus {Inactive, Racing, RacingEvaluation, Active, Dead};

// #define SOLVER_POOL_INDEX( rank )   ( rank - originRank )

///
/// class BbParaSolverPoolElement
/// (This class includes information about a Solver status)
///
class BbParaSolverPoolElement
{

   int                   rank;                                ///< rank of the Solver
   SolverStatus          status;                              ///< status of the Solver
   bool                  collectingMode;                      ///< indicate if current Solver is in collecting mode or not
   bool                  candidateOfCollecting;               ///< indicate that this Solver is a candidate of collecting mode Solver
   bool                  generator;                           ///< this Solver can generate subproblems
   bool                  collectingIsProhibited;              ///< collecting is temporary prohibited
   bool                  dualBoundGainTesting;                ///< indicate that dual bound gain is testing or not
   BbParaNode            *currentNode;                        ///< solving node
   BbParaNode            *selfSplitNodes;                     ///< list of nodes generated by self-split ramp-up
   BbParaSolverPoolElementPtr *selectionHeapElement;            ///< pointer to selection heap element
   BbParaSolverPoolElementPtr *collectingModeSolverHeapElement; ///< pointer to collecting mode heap element
   ///------------------------------------------------------------------
   /// the following values are used to make decision for load balancing
   ///------------------------------------------------------------------
   long long            numOfNodesSolved;                     ///< number of nodes solved.
                                                              ///< -1 is the special value which means never updated in racing
   int                  numOfDiffNodesSolved;                 ///< number of nodes solved difference between current number and
                                                              ///< that in the previous notification time
   int                  numOfNodesLeft;                       ///< number of nodes left
   int                  numOfDiffNodesLeft;                   ///< number of nodes left difference between current number
                                                              ///< and that in the previous notification time
   double               bestDualBoundValue;                   ///< best dual bound value of the Solver
   ParaSolverTerminationState *termState;                     ///< Solver termination statistics: for checkpoint

public :

   ///
   /// constructor
   ///
   BbParaSolverPoolElement(
         int inRank
         )
         : rank(inRank),
           status(Inactive),
           collectingMode(false),
           candidateOfCollecting(false),
           generator(true),
           collectingIsProhibited(false),
           dualBoundGainTesting(false),
           currentNode(0),
           selfSplitNodes(0),
           selectionHeapElement(0),
           collectingModeSolverHeapElement(0),
           numOfNodesSolved(0),
           numOfDiffNodesSolved(0),
           numOfNodesLeft(0),
           numOfDiffNodesLeft(0),
           bestDualBoundValue(0.0),
           // racingRampUpParamSet(0),
           termState(0)
   {
   }

   ///
   ///  destractor
   ///
   ~BbParaSolverPoolElement(
         )
   {
      if( currentNode ) delete currentNode;
      if( selfSplitNodes )
      {
         while( selfSplitNodes )
         {
            BbParaNode *temp = selfSplitNodes;
            selfSplitNodes = selfSplitNodes->next;
            delete temp;
         }
      }
      if( termState ) delete termState;
   }

   ///
   /// get rank of the Solver
   /// @return rank of Solver
   ///
   int getRank(
         )
   {
      return rank;
   }

   ///
   /// get current solving BbParaNode
   /// @return pointer to BbParaNode object
   ///
   ParaTask *getCurrentNode(
         )
   {
      return currentNode;
   }

   ///
   /// get a list of nodes which are generated by self-split ramp-up
   /// @return pointer to BbParaNode object
   ///
   BbParaNode *getSelfSplitNodes(
         )
   {
      return selfSplitNodes;
   }

   ///
   /// extract a list of nodes which are generated by self-split ramp-up
   /// @return pointer to BbParaNode object
   ///
   BbParaNode *extractSelfSplitNodes(
         )
   {
      BbParaNode *nodes = selfSplitNodes;
      selfSplitNodes = 0;
      return nodes;
   }

   /*
   ///
   /// remove bounded BbParaNodes by given incumbnet value
   /// @return the number of bounded BbParaNodes
   ///
   int removeBoundedNodes(
         double incumbentValue        ///< incumbent value
         )
   {
      int n;
      BbParaNode *preNode = selfSplitNodes;
      BbParaNode *node = selfSplitNodes;
      while( node )
      {
         if( node->getDualBoundValue() > incumbentValue )
         {
            if( preNode == selfSplitNodes )   // head
            {
               selfSplitNodes = node->next;
               preNode = selfSplitNodes;
               delete node;
               node = selfSplitNodes;
            }
            else
            {
               preNode->next = node->next;
               delete node;
               node = preNode->next;
            }
            n++;
         }
      }
      return n;
   }
   */

   ///
   /// add subtree root node
   ///
   void addSubtreeRoot(
         BbParaNode *inNode      ///< BbParaNode to be added
         )
   {
      assert( !inNode->isRootTask() );
      if( selfSplitNodes )
      {
         /// add the end, since it would be most like to be solved in this order
         BbParaNode *node = selfSplitNodes;
         while( node->next )
         {
            node = node->next;
         }
         node->next = inNode;
      }
      else
      {
         selfSplitNodes = inNode;
      }
   }

   ///
   /// make subtree root node current
   /// @return if the node is removed or not (The last node is not removed)
   ///
   void makeSubtreeRootCurrent(
         BbParaNode *inNode       ///< BbParaNode to become current
         )
   {
      if( selfSplitNodes )
      {
         // assert( currentNode->next );    // can be next = 0
         if(  selfSplitNodes->isSameNodeIdAs( *inNode ) )
         {
            currentNode = selfSplitNodes;
            selfSplitNodes = selfSplitNodes->next;
            currentNode->next = 0;
         }
         else
         {
            if( selfSplitNodes->next )
            {
               BbParaNode *prev = selfSplitNodes;
               BbParaNode *node = selfSplitNodes->next;
               while( node && ! node->isSameNodeIdAs( *inNode ) )
               {
                  prev = node;
                  node = node->next;
               }
               assert( node );
               prev->next = node->next;
               currentNode = node;
               currentNode->next = 0;
            }
            else
            {
               THROW_LOGICAL_ERROR1("Should not be called. If whole subtrees are removed, TagComleation should be sent and should be inactivated.");
            }
         }
      }
      else
      {
         THROW_LOGICAL_ERROR1("Tried to make invalid BbParaNode to become current");
      }
   }

   ///
   /// remove subtree root node in self-split nodes list
   ///
   void removeSubtreeRoot(
         BbParaNode *inNode       ///< BbParaNode to be removed
         )
   {
      assert( selfSplitNodes );

      if(  selfSplitNodes->isSameNodeIdAs( *inNode ) )
      {
         BbParaNode *node = selfSplitNodes;
         selfSplitNodes = selfSplitNodes->next;
         delete node;
         return;
      }
      else
      {
         if( selfSplitNodes->next )
         {
            BbParaNode *prev = selfSplitNodes;
            BbParaNode *node = selfSplitNodes->next;
            while( node && ! node->isSameNodeIdAs( *inNode ) )
            {
               prev = node;
               node = node->next;
            }
            assert( node );
            prev->next = node->next;
            delete node;
            return;
         }
         else
         {
            THROW_LOGICAL_ERROR1("Should not be called. If whole subtrees are removed, TagComleation should be sent and should be inactivated.");
         }
      }
   }

   ///
   /// extract subtree root node
   ///
   BbParaNode *extractSubtreeRoot(
         BbParaNode *inNode       ///< BbParaNode to be removed
         )
   {
      if( selfSplitNodes )
      {
         // assert( currentNode->next );    // can be next = 0
         if(  selfSplitNodes->isSameNodeIdAs( *inNode ) )
         {
            BbParaNode *node = selfSplitNodes;
            selfSplitNodes = selfSplitNodes->next;
            node->next = 0;
            return node;
         }
         else
         {
            if( selfSplitNodes->next )
            {
               BbParaNode *prev = selfSplitNodes;
               BbParaNode *node = selfSplitNodes->next;
               while( node && ! node->isSameNodeIdAs( *inNode ) )
               {
                  prev = node;
                  node = node->next;
               }
               assert( node );
               prev->next = node->next;
               node->next = 0;
               return node;
            }
            else
            {
               THROW_LOGICAL_ERROR1("Should not be called. If whole subtrees are removed, TagComleation should be sent and should be inactivated.");
            }
         }
      }
      else
      {
         THROW_LOGICAL_ERROR1("Tried to remove invalid BbParaNode as a subtree root node");
      }
   }

   ///
   /// extract current solving BbParaNode
   /// @return pointer to BbParaNode object
   ///
   BbParaNode *extractCurrentNode(
         )
   {
      assert( !currentNode->next );
      BbParaNode *node = currentNode;
      currentNode = 0;
      return node;
   }

   ///
   /// delete current solving BbParaNode
   ///
   void deleteCurrentNode(
         )
   {
      assert( !currentNode->next );
      delete currentNode;
      currentNode = 0;
   }


   ///
   /// extract current solving BbParaNode
   /// @return pointer to BbParaNode object
   ///
//   BbParaNode *extractCurrentNodeGeneratedBySelfSplit(
//         )
//   {
//      // assert( currentNode->next );       /// can be next == 0
//      BbParaNode *node = currentNode;
//      currentNode = 0;
//      return node;
//   }

   ///
   /// get selection heap element
   /// @return pointer to BbParaSolverPoolElementPtr
   ///
   BbParaSolverPoolElementPtr *getSelectionHeapElement(
         )
   {
      return selectionHeapElement;
   }

   ///
   /// set selection heap element
   ///
   void setSelectionHeapElement(
         BbParaSolverPoolElementPtr *inSelectionHeapElement   ///< selection heap element
         )
   {
       selectionHeapElement = inSelectionHeapElement;
   }

   ///
   /// get collecting mode Solver heap element
   /// @return pointer to BbParaSolverPoolElementPtr
   ///
   BbParaSolverPoolElementPtr *getCollectingModeSolverHeapElement(
         )
   {
      return collectingModeSolverHeapElement;
   }

   ///
   /// set collecting mode Solver heap element
   ///
   void setCollectingModeSolverHeapElement(
         BbParaSolverPoolElementPtr *inCollectingModeSolverHeapElement ///< collecting mode Solver heap element
         )
   {
      collectingModeSolverHeapElement = inCollectingModeSolverHeapElement;
   }

   ///
   /// get number of nodes solved
   /// @return number of nodes solved
   ///
   long long getNumOfNodesSolved(
         )
   {
      return numOfNodesSolved;
   }

   ///
   /// get number of nodes left
   /// @return number of nodes left
   ///
   int getNumOfNodesLeft(
         )
   {
      return numOfNodesLeft;
   }

   ///
   /// set number of nodes solved
   ///
   void setNumOfNodesSolved(
         long long inNumOfNodesSolved   ///< number of nodes solved
         )
   {
      numOfNodesSolved = inNumOfNodesSolved;
   }

   ///
   /// get number of nodes left difference between current number and that in the previous notification time
   /// @return number of nodes left difference between current number and that in the previous notification time
   ///
   int getNumOfDiffNodesSolved(
         )
   {
      return numOfDiffNodesSolved;
   }

   ///
   /// set number of nodes left difference between current number and that in the previous notification time
   ///
   void setNumOfDiffNodesSolved(
         int inNumOfDiff                ///< number of nodes left difference between current number
                                        ///< and that in the previous notification time
         )
   {
       numOfDiffNodesSolved = inNumOfDiff;
   }

   ///
   /// set number of nodes left
   ///
   void setNumOfNodesLeft(
         int inNumOfNodesLeft           ///< number of nodes left
         )
   {
      numOfNodesLeft = inNumOfNodesLeft;
   }

   ///
   /// set dual bound value on paraNode
   ///
   void setDualBoundValue(
         double dualBoundValue          ///< dual bound value
         )
   {
      dynamic_cast<BbParaNode *>(currentNode)->setDualBoundValue(dualBoundValue);
   }

   ///
   /// get number of nodes left difference between current number and that in the previous notification time
   /// @return number of nodes left difference between current number and that in the previous notification time
   ///
   int getNumOfDiffNodesLeft(
         )
   {
      return numOfDiffNodesLeft;
   }

   ///
   /// set number of nodes left difference between current number and that in the previous notification time
   ///
   void setNumOfDiffNodesLeft(
         int inNumOfDiff                ///< set number of nodes left difference between current number
                                        ///< and that in the previous notification time
         )
   {
       numOfDiffNodesLeft = inNumOfDiff;
   }

   ///
   /// get best dual bound value
   /// @return best dual bound value
   ///
   double getBestDualBoundValue(
         )
   {
      return bestDualBoundValue;
   }

   ///
   /// set best dual bound value
   ///
   void setBestDualBoundValue(
         double inBestDualBoundValue    ///< best dual bound value
         )
   {
      bestDualBoundValue = inBestDualBoundValue;
   }

   ///
   /// activate this Solver
   ///
   void activate(
         BbParaNode *inNode               ///< pointer to BbParaNode object to activate Solver
         )
   {
      status = Active;
      currentNode = inNode;
      if( currentNode )
         bestDualBoundValue = inNode->getDualBoundValue();
      else
         bestDualBoundValue = -DBL_MAX;
      numOfNodesSolved = 0;
      numOfNodesLeft = 1;  // at least 1 node should be left
   }

   ///
   ///  activate this Solver as a racing Solver
   ///
   void racingActivate(
         )
   {
      status = Racing;
      currentNode = 0;
      numOfNodesSolved = -1;
      bestDualBoundValue = -DBL_MAX;
      numOfNodesLeft = 1;  // at least 1 node should be left
   }

   ///
   ///  inactivate this Solver
   ///
   void inactivate(
         )
   {
      status = Inactive;
      if( currentNode )
      {
         delete currentNode;
         currentNode = 0;
      }
      collectingMode = false;
      candidateOfCollecting = false;
      collectingIsProhibited = false;
      dualBoundGainTesting = false;
      /** do not touch "generator" **/
      numOfNodesSolved = 0;
      numOfNodesLeft = 0;
      numOfDiffNodesLeft = 0;
      bestDualBoundValue = 0.0;
   }

   ///
   /// kill this Solver
   /// @return pointer to BbParaNode object assigned to this Solver
   ///
   BbParaNode *died(
         )
   {
      status = Dead;
      collectingMode = false;
      candidateOfCollecting = false;
      collectingIsProhibited = false;
      dualBoundGainTesting = false;
      numOfNodesSolved = 0;
      numOfNodesLeft = 0;
      numOfDiffNodesLeft = 0;
      bestDualBoundValue = 0.0;
      BbParaNode* node = currentNode;
      currentNode = 0;
      return node;
   }

   ///
   /// get Solver status
   /// @return Solver status
   ///
   SolverStatus getStatus(
         )
   {
      return status;
   }

   ///
   /// set TerminateRequseted on Solver status
   ///
   void interruptRequested(
         )
   {
     //      assert( status == Inactive );
      status = InterruptRequested;
   }

   ///
   /// set TerminateRequseted on Solver status
   ///
   void terminateRequested(
         )
   {
     //      assert( status == Inactive );
      status = TerminateRequested;
   }

   ///
   /// set Terminated on Solver status
   ///
   void terminated(
         )
   {
      assert( status == TerminateRequested || status == InterruptRequested || status == Inactive );
      status = Terminated;
   }

   ///
   /// check if this Solver is active or not
   /// @return true if this Solver is active, false otherwise
   ///
   bool isActive(
         )
   {
      return ( status == Active );
   }

   ///
   /// check if this Solver is out of collecting mode or not
   /// @return true if this Solver is out of collecting mode, false otherwise
   ///
   bool isOutCollectingMode(
         )
   {
      return (!collectingMode);
   }

   ///
   /// check if this Solver is in collecting mode or not
   /// @return true if this Solver is in collecting mode, false otherwise
   ///
   bool isInCollectingMode(
         )
   {
      return collectingMode;
   }

   ///
   /// set collecting mode
   ///
   void setCollectingMode(
         bool b                 ///< true or false to be set on collecting mode
        )
   {
      collectingMode = b;
   }

   ///
   /// check if this Solver is candidate of collecting mode Solver
   /// @return true if this Solver is candidate, false otherwise
   ///
   bool isCandidateOfCollecting(
         )
   {
      return candidateOfCollecting;
   }

   ///
   /// set candidate of collecting mode Solver
   ///
   void setCandidateOfCollecting(
         bool b               ///< true or false to be set on candidate flag
         )
   {
      candidateOfCollecting = b;
   }

   ///
   /// set termination state
   ///
   void setTermState(
         ParaSolverTerminationState *inTermState   ///< termination state to be set
         )
   {
      if( termState ) delete termState;
      termState = inTermState;
   }

   ///
   /// get termination state
   /// @return pointer to ParaSolverTerminationState object
   ///
   ParaSolverTerminationState *getTermState(
         )
   {
      return termState;
   }

   ///
   /// switch into evaluation stage
   ///
   void switchIntoEvaluation(
         )
   {
      assert( status == Racing );
      status = RacingEvaluation;
   }

   ///
   ///  switch out of evaluation stage
   ///
   void switchOutEvaluation(
         )
   {
      assert( status == RacingEvaluation );
      status = Racing;
   }

   ///
   /// check if this Solver is in racing stage
   /// @return true if this Solver is in racing stage, false otherwise
   ///
   bool isRacingStage(
         )
   {
      return ( status == Racing );
   }

   ///
   /// check if this Solver is in evaluation stage
   /// @return true if this Solver is in evaluation stage, false otherwise
   ///
   bool isEvaluationStage(
         )
   {
      return ( status == RacingEvaluation );
   }

   ///
   /// make this Solver No generator
   ///
   void setNoGenerator(
         )
   {
      generator = false;
   }

   ///
   /// check if this Solver is generator or not */
   /// @return true if this Solver is generator, false otherwise
   ///
   bool isGenerator(
         )
   {
      return generator;
   }

   ///
   /// prohibits to be in collecting mode
   ///
   void prohibitCollectingMode(
         )
   {
      collectingIsProhibited = true;
   }

   ///
   /// allows to be in collecting mode
   ///
   void setCollectingIsAllowed(
         )
   {
      collectingIsProhibited = false;
   }

   ///
   /// check if this Solver cannot be allowed in collecting mode
   /// @return true if this Solver cannot be allowed in collecting mode, false otherwise
   ///
   bool isCollectingProhibited(
         )
   {
      return collectingIsProhibited;
   }

   ///
   /// check if dual bound gain is testing in this Solver or not
   /// @return true if dual bound gain is testing, false otherwise
   ///
   bool isDualBoundGainTesting(
         )
   {
      return dualBoundGainTesting;
   }

   ///
   /// set dual bound gain is testing value
   ///
   void setDualBoundGainTesting(
         bool value               ///< dual bound gain
         )
   {
      dualBoundGainTesting = value;
   }

};

///
/// class Selection Heap
///
class SelectionHeap
{

public:

   ///
   /// results of insert
   ///
   enum ResultOfInsert
   {
      SUCCEEDED,     ///< SUCCEEDED
      FAILED_BY_FULL ///< FAILED_BY_FULL
   };

   ///
   /// constructor
   ///
   SelectionHeap(
         std::size_t size                   ///< heap size
         );

   ///
   /// destructor
   ///
   virtual ~SelectionHeap(
         );

   ///
   /// insert BbParaSolverPoolElementPtr to Selection Heap
   /// @return succeeded or fail because of full
   ///
   ResultOfInsert insert(
         BbParaSolverPoolElementPtr solver    ///< Solver pool element to be inserted
         );

   ///
   /// obtain top priority BbParaSolverPoolElementPtr
   /// @return top priority BbParaSolverPoolElementPtr
   ///
   BbParaSolverPoolElementPtr top(
         ) const
   {
      return heap[1];
   }

   ///
   /// obtain i-th in heap BbParaSolverPoolElementPtr
   /// @return ith in heap BbParaSolverPoolElementPtr
   ///
   BbParaSolverPoolElementPtr get(
         int i
         ) const
   {
      return heap[i];
   }

   ///
   /// remove top priority BbParaSolverPoolElementPtr from Selection Heap
   /// @return removed top priority BbParaSolverPoolElementPtr
   ///
   BbParaSolverPoolElementPtr remove(
         );

   ///
   /// resize Selection Heap
   ///
   void resize(
         std::size_t size          ///< new size
         );

   ///
   /// get current used heap size
   /// @return used heap size
   ///
   inline std::size_t getHeapSize(
         ) const
   {
      return heapSize;
   }

   ///
   /// get max heap size
   /// @return max heap size
   ///
   inline std::size_t getMaxHeapSize(
         ) const
   {
      return maxHeapSize;
   }

   ///
   /// update selection heap by a new dual bound value of this Solver
   ///
   virtual void updateDualBoundValue(
         BbParaSolverPoolElementPtr solver,    ///< Solver pool element to be updated
         double value                        ///< dual bound value
         ) = 0;

   ///
   /// delete BbParaSolverPoolElementPtr from Selection Heap
   ///
   virtual void deleteElement(
         BbParaSolverPoolElementPtr solver      ///< Solver pool element to be deleted
         ) = 0;

   ///
   /// up heap
   ///
   virtual void upHeap(
         std::size_t pos                      ///< start position to up heap
         ) = 0;

   ///
   /// down heap
   ///
   virtual void downHeap(
         std::size_t pos                      ///< start position to down heap
         ) = 0;

   //------------
   // for debug
   //------------
   ///
   /// stringfy of this object for debugging
   /// @return string to show inside of this object
   ///
   const std::string toString(
         );

protected:

   std::size_t          maxHeapSize;               ///< maximum size of this heap
   std::size_t          heapSize;                  ///< current used heap size
   // long long            currentSequenceNumber;  ///< current sequence number
   BbParaSolverPoolElementPtr *heap;                 ///< heap : contents are BbParaSolverPoolElementPtr

};

///
/// class DescendingSelectionHeap
///
class DescendingSelectionHeap : public SelectionHeap {

public:

   ///
   /// constructor
   ///
   DescendingSelectionHeap(
         std::size_t size                        ///< heap size
         );

   ///
   /// destructor
   ///
   virtual ~DescendingSelectionHeap(
         )
   {
   }

   ///
   /// update selection heap by a new dual bound value of this Solver
   ///
   virtual void updateDualBoundValue(
         BbParaSolverPoolElementPtr solver,    ///< Solver pool element to be updated
         double value                        ///< dual bound value
         );

   ///
   /// delete BbParaSolverPoolElementPtr from Selection Heap
   ///
   virtual void deleteElement(
         BbParaSolverPoolElementPtr solver      ///< Solver pool element to be deleted
         );

   ///
   /// up heap
   ///
   virtual void upHeap(
         std::size_t pos                      ///< start position to up heap
         );
   ///
   /// down heap
   ///
   virtual void downHeap(
         std::size_t pos                      ///< start position to down heap
         );

};

///
/// class AscendingSelectionHeap
///
class AscendingSelectionHeap : public SelectionHeap {
public:

   ///
   /// constructor
   ///
   AscendingSelectionHeap(
         std::size_t size                        ///< heap size
         );

   ///
   /// destructor
   ///
   virtual ~AscendingSelectionHeap(
         )
   {
   }

   ///
   /// update selection heap by a new dual bound value of this Solver
   ///
   virtual void updateDualBoundValue(
         BbParaSolverPoolElementPtr solver,    ///< Solver pool element to be updated
         double value                        ///< dual bound value
         );

   ///
   /// delete BbParaSolverPoolElementPtr from Selection Heap
   ///
   virtual void deleteElement(
         BbParaSolverPoolElementPtr solver      ///< Solver pool element to be deleted
         );

   ///
   /// up heap
   ///
   virtual void upHeap(
         std::size_t pos                      ///< start position to up heap
         );
   ///
   /// down heap
   ///
   virtual void downHeap(
         std::size_t pos                      ///< start position to down heap
         );

};

///
/// class CollectingModeSolverHeap
///
class CollectingModeSolverHeap
{

public:

   ///
   /// results of insert
   ///
   enum ResultOfInsert
   {
      SUCCEEDED,     ///< SUCCEEDED
      FAILED_BY_FULL ///< FAILED_BY_FULL
   };

   ///
   /// constructor
   ///
   CollectingModeSolverHeap(
         std::size_t size                   ///< heap size
         );

   ///
   /// destructor
   ///
   virtual ~CollectingModeSolverHeap(
         );

   ///
   /// insert BbParaSolverPoolElementPtr to CollectingModeSolver Heap
   /// @return succeeded or fail because of full
   ///
   ResultOfInsert insert(
         BbParaSolverPoolElementPtr solver   ///< Solver pool element to be inserted
         );



   ///
   /// obtain top priority BbParaSolverPoolElementPtr
   /// @return top priority BbParaSolverPoolElementPtr
   ///
   BbParaSolverPoolElementPtr top(
         ) const
   {
      return heap[1];
   }

   ///
   /// remove top priority BbParaSolverPoolElementPtr from CollectingModeSolver Heap */
   /// @return  top priority BbParaSolverPoolElementPtr
   ///
   BbParaSolverPoolElementPtr remove(
         );

   ///
   /// resize CollectingModeSolver Heap
   ///
   void resize(
         std::size_t size              ///< new size
         );

   ///
   /// get current used heap size
   /// @return used heap size
   ///
   inline std::size_t getHeapSize(
         ) const
   {
      return heapSize;
   }

   ///
   /// get max heap size
   /// @return max heap size
   ///
   inline std::size_t getMaxHeapSize(
         ) const
   {
      return maxHeapSize;
   }

   ///
   /// update CollectingModeSolver heap by a new dual bound value of this Solver
   ///
   virtual void updateDualBoundValue(
         BbParaSolverPoolElementPtr solver,    ///< Solver pool element to be updated
         double value                        ///< dual bound value
         ) = 0;

   ///
   /// delete BbParaSolverPoolElementPtr from CollectingModeSolver Heap
   ///
   virtual void deleteElement(
         BbParaSolverPoolElementPtr solver      ///< Solver pool element to be deleted
         ) = 0;

   ///
   /// up heap
   ///
   virtual void upHeap(
         std::size_t pos                      ///< start position to up heap
         ) = 0;

   ///
   /// down heap
   ///
   virtual void downHeap(
         std::size_t pos                      ///< start position to down heap
         ) = 0;

   //------------
   // for debug
   //------------
   ///
   /// stringfy of this object for debugging
   /// @return string to show inside of this object
   ///
   const std::string toString();

protected:

   std::size_t          maxHeapSize;               ///< maximum size of this heap
   std::size_t          heapSize;                  ///< current used heap size
   // long long            currentSequenceNumber;  ///< current sequence number
   BbParaSolverPoolElementPtr *heap;                 ///< heap : contents are BbParaSolverPoolElementPtr

};

///
/// class DescendingCollectingModeSolverHeap
///
class DescendingCollectingModeSolverHeap : public CollectingModeSolverHeap {

public:

   ///
   /// constructor
   ///
   DescendingCollectingModeSolverHeap(
         std::size_t size                        ///< heap size
         );

   ///
   /// destructor
   ///
   virtual ~DescendingCollectingModeSolverHeap(
         )
   {
   }

   ///
   /// update CollectingModeSolver heap by a new dual bound value of this Solver
   ///
   virtual void updateDualBoundValue(
         BbParaSolverPoolElementPtr solver,    ///< Solver pool element to be updated
         double value                        ///< dual bound value
         );

   ///
   /// delete BbParaSolverPoolElementPtr from CollectingModeSolver Heap
   ///
   virtual void deleteElement(
         BbParaSolverPoolElementPtr solver      ///< Solver pool element to be deleted
         );

   ///
   /// up heap
   ///
   virtual void upHeap(
         std::size_t pos                      ///< start position to up heap
         );

   ///
   /// down heap
   ///
   virtual void downHeap(
         std::size_t pos                      ///< start position to down heap
         );

};

class AscendingCollectingModeSolverHeap : public CollectingModeSolverHeap {

public:

   ///
   /// constructor
   ///
   AscendingCollectingModeSolverHeap(
         std::size_t size                    ///< heap size
         );

   ///
   /// destructor
   ///
   virtual ~AscendingCollectingModeSolverHeap(
         )
   {
   }

   ///
   /// update CollectingModeSolver heap by a new dual bound value of this Solver
   ///
   virtual void updateDualBoundValue(
         BbParaSolverPoolElementPtr solver,    ///< Solver pool element to be updated
         double value                        ///< dual bound value
         );

   ///
   /// delete BbParaSolverPoolElementPtr from CollectingModeSolver Heap
   ///
   virtual void deleteElement(
         BbParaSolverPoolElementPtr solver      ///< Solver pool element to be deleted
         );

   ///
   /// up heap
   ///
   virtual void upHeap(
         std::size_t pos                      ///< start position to up heap
         );

   ///
   /// down heap
   ///
   virtual void downHeap(
         std::size_t pos                      ///< start position to down heap
         );

};

class BbParaRacingSolverPool;

///
/// class BbParaSolverPool
/// (Solver Pool base class)
///
class BbParaSolverPool : public ParaSolverPool
{

protected:

   bool                                 active;                      ///< indicate if this pool is active or not
   double                               bgap;                        ///< threshold value of gap
   double                               mp;                          ///< multiplier of the threshold value p
   double                               mBgap;                       ///< multiplier of the bgap value
   double                               absoluteGap;                 ///< allowable absolute dual bound gap to the best Solver
   std::size_t                          nGenerator;                  ///< number of generators
   std::size_t                          nCollectingModeSolvers;      ///< number of collecting mode Solvers
   std::size_t                          nMaxCollectingModeSolvers;   ///< maximum number of Solvers that can be in collecting mode
   std::size_t                          nLimitCollectingModeSolvers; ///< limit number of Solvers that can be in collecting mode
   unsigned long long                   nNodesSolvedInSolvers;       ///< number of nodes solved in current running Solvers
   unsigned long long                   nTotalNodesSolved;           ///< number of nodes solved : updated at termination of subtree computation
   unsigned long long                   nNodesInSolvers;             ///< number of nodes in all Solvers
   bool                                 collectingMode;              ///< indicate that this system is in collecting mode or not
   bool                                 breakingFirstSubtree;        ///< breaking the first subtree
   bool                                 beforeInitialCollect;        ///< before initial collecting mode
   bool                                 beforeFinishingFirstCollect; ///< before finishing first collecting mode
   std::map< int, BbParaSolverPoolElementPtr > inactiveSolvers;        ///< pointers to inactive Solvers
   std::map< int, BbParaSolverPoolElementPtr > activeSolvers;          ///< pointers to active Solvers
   std::map< int, BbParaSolverPoolElementPtr > deadSolvers;            ///< pointers to dead Solvers
   std::multimap< double, BbParaSolverPoolElementPtr > candidatesOfCollectingModeSolvers;
                                                                     ///< pointers to candidates of collecting mode Solvers
   BbParaSolverPoolElementPtr             *pool;                       ///< Solver pool indexed by Solver's rank
   SelectionHeap                        *selectionHeap;              ///< pointers to active Solvers in ascending or descending order
   CollectingModeSolverHeap             *collectingModeSolverHeap;   ///< pointers to collecting mode Solvers in ascending or descending order
   double                               switchOutTime;               ///< switch out time
   int                                  mCollectingNodes;            ///< multiplier for the number of collecting BbParaNodes
   int                                  mMaxCollectingNodes;         ///< maximum multiplier for the number of collecting BbParaNodes
   int                                  nDualBoundGainTesting;       ///< the number of dual bound gain testing Solvers

   ///
   /// switch a Solver to be in collecting mode
   ///
   virtual void switchInCollectingToSolver(
         int rank,                    ///< Solver rank to be in collecting mode
         BbParaNodePool *paraNodePool ///< pointer to BbParaNodePool object
         );

public:

   ///
   /// constructor
   ///
   BbParaSolverPool(
         double inMp,                 ///< multiplier of the threshold value p
         double inBgap,               ///< threshold value of gap
         double inMBgap,              ///< multiplier of the bgap value
         int inOriginRank,            ///< origin rank of Solvers managed by this Solver pool
         ParaComm *inParaComm,        ///< communicator used
         ParaParamSet *inParaParams,  ///< paraParamSet used
         ParaTimer *inParaTimer       ///< timer used
         )
         : ParaSolverPool(inOriginRank, inParaComm, inParaParams, inParaTimer),
           active(false),
           bgap(inBgap),
           mp(inMp),
           mBgap(inMBgap),
           nCollectingModeSolvers(0),
           nNodesSolvedInSolvers(0),
           nTotalNodesSolved(0),
           nNodesInSolvers(0),  // rampUpPhase(false),
           collectingMode(false),
           breakingFirstSubtree(false),
           beforeInitialCollect(true),
           beforeFinishingFirstCollect(true),
           selectionHeap(0),
           collectingModeSolverHeap(0),
           switchOutTime(-1.0),
           mCollectingNodes(1),
           mMaxCollectingNodes(1),
           nDualBoundGainTesting(0)
   {
      nSolvers = paraComm->getSize() - inOriginRank;
      nGenerator = nSolvers;

      pool = new BbParaSolverPoolElementPtr[nSolvers];
      for( unsigned int i = 0; i < nSolvers; i++ )
      {
         pool[i] = new BbParaSolverPoolElement(originRank+i);
         if( i >= nGenerator ) pool[i]->setNoGenerator();
         inactiveSolvers.insert(std::make_pair((originRank+i),pool[i]));
      }
      if( paraParams->getIntParamValue(MaxNumberOfCollectingModeSolvers) > 0 )
      {
         nMaxCollectingModeSolvers = std::min(
               (std::size_t)paraParams->getIntParamValue(MaxNumberOfCollectingModeSolvers), nSolvers );
      }
      else if (paraParams->getIntParamValue(MaxNumberOfCollectingModeSolvers) == 0 )
      {
         nMaxCollectingModeSolvers = std::max(nSolvers / 2, (std::size_t)1);  // at least one Solver has to be in collecting mode
      }
      else
      {
         nMaxCollectingModeSolvers = nSolvers;
      }
      nLimitCollectingModeSolvers = paraParams->getIntParamValue(MinNumberOfCollectingModeSolvers);
      absoluteGap = paraParams->getRealParamValue(ABgapForSwitchingToBestSolver);
      if( paraParams->getBoolParamValue(BreakFirstSubtree) )
      {
         breakingFirstSubtree = true;
      }
   }

   ///
   /// constructor
   ///
   BbParaSolverPool(
         double inMp,                 ///< multiplier of the threshold value p
         double inBgap,               ///< threshold value of gap
         double inMBgap,              ///< multiplier of the bgap value
         int inNSolvers,              ///< number of solvers
         int inOriginRank,            ///< origin rank of Solvers managed by this Solver pool
         ParaComm *inParaComm,        ///< communicator used
         ParaParamSet *inParaParams,  ///< paraParamSet used
         ParaTimer *inParaTimer       ///< timer used
         )
         : ParaSolverPool(inOriginRank, inParaComm, inParaParams, inParaTimer),
           active(false),
           bgap(inBgap),
           mp(inMp),
           mBgap(inMBgap),
           nCollectingModeSolvers(0),
           nNodesSolvedInSolvers(0),
           nTotalNodesSolved(0),
           nNodesInSolvers(0),  // rampUpPhase(false),
           collectingMode(false),
           breakingFirstSubtree(false),
           beforeInitialCollect(true),
           beforeFinishingFirstCollect(true),
           selectionHeap(0),
           collectingModeSolverHeap(0),
           switchOutTime(-1.0),
           mCollectingNodes(1),
           mMaxCollectingNodes(1),
           nDualBoundGainTesting(0)
   {
      nSolvers = inNSolvers;
      nGenerator = nSolvers;

      pool = new BbParaSolverPoolElementPtr[nSolvers];
      for( unsigned int i = 0; i < nSolvers; i++ )
      {
         pool[i] = new BbParaSolverPoolElement(originRank+i);
         if( i >= nGenerator ) pool[i]->setNoGenerator();
         inactiveSolvers.insert(std::make_pair((originRank+i),pool[i]));
      }
      if( paraParams->getIntParamValue(MaxNumberOfCollectingModeSolvers) > 0 )
      {
         nMaxCollectingModeSolvers = std::min(
               (std::size_t)paraParams->getIntParamValue(MaxNumberOfCollectingModeSolvers), nSolvers );
      }
      else if (paraParams->getIntParamValue(MaxNumberOfCollectingModeSolvers) == 0 )
      {
         nMaxCollectingModeSolvers = std::max(nSolvers / 2, (std::size_t)1);  // at least one Solver has to be in collecting mode
      }
      else
      {
         nMaxCollectingModeSolvers = nSolvers;
      }
      nLimitCollectingModeSolvers = paraParams->getIntParamValue(MinNumberOfCollectingModeSolvers);
      absoluteGap = paraParams->getRealParamValue(ABgapForSwitchingToBestSolver);
      if( paraParams->getBoolParamValue(BreakFirstSubtree) )
      {
         breakingFirstSubtree = true;
      }
   }

   ///
   ///  destructor
   ///
   virtual ~BbParaSolverPool(
         )
   {
      for( unsigned int i = 0; i < (unsigned int)nSolvers; i++ )
      {
         delete pool[i];
      }
      if( pool ) delete[] pool;
   }

   ///
   /// set the Solver specified by rank is terminate requested
   ///
   virtual void interruptRequested(
         int rank     ///< rank of the Solver
         )
   {
      assert(pool[SOLVER_POOL_INDEX( rank )]->getRank() == rank);
      pool[SOLVER_POOL_INDEX( rank )]->interruptRequested();
   }

   ///
   /// set the Solver specified by rank is terminate requested
   ///
   virtual void terminateRequested(
         int rank     ///< rank of the Solver
         )
   {
      assert(pool[SOLVER_POOL_INDEX( rank )]->getRank() == rank);
      pool[SOLVER_POOL_INDEX( rank )]->terminateRequested();
   }

   ///
   /// check if the Solver specified by rank is interrupt requested or not
   /// @return return true if the Solver is interrupt requested, false otherwise
   ///
   virtual bool isInterruptRequested(
         int rank     ///< rank of the Solver
         )
   {
      return (pool[SOLVER_POOL_INDEX( rank )]->getStatus() == InterruptRequested);
   }

   ///
   /// check if the Solver specified by rank is terminate requested or not
   /// @return return true if the Solver is terminate requested, false otherwise
   ///
   virtual bool isTerminateRequested(
         int rank     ///< rank of the Solver
         )
   {
      return (pool[SOLVER_POOL_INDEX( rank )]->getStatus() == TerminateRequested);
   }

   ///
   /// set the Solver specified by rank is terminated
   ///
   virtual void terminated(
         int rank     ///< rank of the Solver
         )
   {
      assert(pool[SOLVER_POOL_INDEX( rank )]->getRank() == rank);
      if( this->isSolverActive(rank) )  // it looks that node != NULL and inactive could be occurred with timing issue when TimeLimit is specified
      {
         inactivateSolver(rank, -1, 0);  // number of nodes solved should be added when LC receives termination message */
      }
      assert(pool[SOLVER_POOL_INDEX( rank )]->getStatus() == TerminateRequested ||
             pool[SOLVER_POOL_INDEX( rank )]->getStatus() == InterruptRequested ||
             pool[SOLVER_POOL_INDEX( rank )]->getStatus() == Inactive );
      //
      // The following situation could happen, whne terminate or interrupt is requested
      //
      std::map<int, BbParaSolverPoolElementPtr>::iterator p;
      p = activeSolvers.find(rank);
      if( p != activeSolvers.end() )
      {
         activeSolvers.erase(p);
         // inactiveSolvers.insert(std::make_pair(rank,pool[SOLVER_POOL_INDEX( rank )]));   // in order not to assign new Task to this rank of solver
      }
      pool[SOLVER_POOL_INDEX( rank )]->terminated();
   }

   ///
   /// check if the Solver specified by rank is terminated or not
   /// @return return true if the Solver is terminated, false otherwise
   ///
   virtual bool isTerminated(
         int rank     ///< rank of the Solver
         )
   {
      return (pool[SOLVER_POOL_INDEX( rank )]->getStatus() == Terminated);
   }

   ///
   ///  reinitialize to restart
   ///
   virtual void reinitToRestart(
         )
   {
      collectingMode = false;
      nCollectingModeSolvers = 0;
      switchOutTime = -1.0;
      mCollectingNodes = 1;
      nLimitCollectingModeSolvers = paraParams->getIntParamValue(MinNumberOfCollectingModeSolvers);
   }

   ///
   ///  activate this Solver pool
   ///
   virtual void activate(
         )
   {
      active = true;
   }

   ///
   /// check if this Solver pool is active or not
   /// @return true if this Solver pool is active, false otherwise
   ///
   virtual bool isActive(
         )
   {
      return active;
   }

   ///
   /// get number of Solvers in this Solver pool
   /// @return number of Solvers
   ///
   virtual std::size_t getNSolvers(
         )
   {
      return nSolvers;
   }

   ///
   ///  get number of nodes solved in current running Solvers
   ///
   virtual unsigned long long getNnodesSolvedInSolvers(
         )
   {
      return nNodesSolvedInSolvers;
   }

   ///
   /// get number of nodes solved in all Solvers: updated at termination of subtree computation
   ///
   virtual unsigned long long getTotalNodesSolved(
         )
   {
      return nTotalNodesSolved;
   }

   ///
   /// add number of nodes solved in all Solvers
   ///
   virtual void addTotalNodesSolved(
         unsigned long long num       ///< number of nodes solved
         )
   {
      nTotalNodesSolved += num;
   }

   ///
   ///  get number of nodes in all Solvers
   ///
   virtual unsigned long long getNnodesInSolvers(
         )
   {
      return nNodesInSolvers;
   }

   ///
   /// get number of active Solvers
   /// @return number of active Solvers
   ///
   virtual std::size_t getNumActiveSolvers(
         )
   {
      return activeSolvers.size();
   }

   ///
   /// get number of inactive Solvers
   /// @return number of inactive Solvers
   ///
   virtual std::size_t getNumInactiveSolvers(
         )
   {
      return inactiveSolvers.size();
   }

   ///
   /// check if the Solver specified by rank is active or not
   /// @return true if the Solver is active, false otherwise
   ///
   virtual bool isSolverActive(
         int rank     ///< rank of the Solver to be checked
         )
   {
      return pool[SOLVER_POOL_INDEX(rank)]->isActive();
   }

   ///
   /// get current solving BbParaNode in the Solver specified by rank */
   /// @return pointer to BbParaNode object
   ///
   virtual ParaTask *getCurrentTask(
         int rank     ///< rank of the Solver
         )
   {
      return  pool[SOLVER_POOL_INDEX(rank)]->getCurrentNode();
   }

   ///
   /// check if the number of Solvers in collecting mode can be increased or not
   /// @return true if the number can be increased, false otherwise
   ///
   virtual bool canIncreaseLimitNLimitCollectingModeSolvers(
         )
   {
      return (nLimitCollectingModeSolvers < nMaxCollectingModeSolvers);
   }

   ///
   /// get limit number of Solvers that can be in collecting mode
   /// @return limit number of Solvers that can be in collecting mode
   ///
   virtual std::size_t getNLimitCollectingModeSolvers(
         )
   {
      return nLimitCollectingModeSolvers;
   }

   // Node *getCurrentNode(int rank){ return  pool[rank-1]->getCurrentNode(); }

   ///
   /// check if this system is in collecting mode or not
   /// @return true if this system is in collecting mode, false otherwise
   ///
   virtual bool isInCollectingMode(
         )
   {
      return collectingMode;
   }

   ///
   /// get collecting mode of the Solver specified by rank
   /// @return true if the Solver is in collecting mode, false otherwise
   ///
   virtual bool isSolverInCollectingMode(
         int rank     ///< rank of the Solver to be checked
         )
   {
      return pool[SOLVER_POOL_INDEX(rank)]->isInCollectingMode();
   }



   ///
   /// extract current solving BbParaNode in the Solver specified by rank
   /// and inactivate the Solver
   /// @return pointer to BbParaNode object
   ///
   virtual BbParaNode *extractCurrentNodeAndInactivate(
         int rank,                       ///< rank of the Solver to be inactivated
         BbParaNodePool *paraNodePool    ///< pointer to BbParaNodePool to pass it to inactivateSolver routine
         )
   {
      BbParaNode *node = pool[SOLVER_POOL_INDEX(rank)]->extractCurrentNode();
      // for checkpointing, it should be updated always.
      // node->setDualBoundValue( getDualBoundValue(rank) );
      // if( node )   // after racing, could be inactive with timing issue
      if( this->isSolverActive(rank) )  // it looks that node != NULL and inactive could be occurred with timing issue when TimeLimit is specified
      {
         inactivateSolver(rank, -1, paraNodePool);  // number of nodes solved should be added when LC receives termination message */
      }
      return node;
   }

   ///
   /// extract current solving BbParaNode in the Solver specified by rank
   /// and inactivate the Solver
   /// @return pointer to BbParaNode object
   ///
//   BbParaNode *extractCurrentNodeGeneratedBySelfSplitAndInactivate(
//         int rank,                       ///< rank of the Solver to be inactivated
//         BbParaNodePool *paraNodePool    ///< pointer to BbParaNodePool to pass it to inactivateSolver routine
//         )
//   {
//      BbParaNode *node = pool[SOLVER_POOL_INDEX(rank)]->extractCurrentNode();
//      // for checkpointing, it should be updated always.
//      // node->setDualBoundValue( getDualBoundValue(rank) );
//      inactivateSolver(rank, -1, paraNodePool);  // number of nodes solved should be added when LC recives termination message */
//      return node;
//   }

   ///
   /// check if solving BbParaNode in the Solver specified has descendant or not
   /// @return true if the Solver has descendant, false otherwise
   ///
   virtual bool currentSolvingNodehaeDescendant(
         int rank                      ///< solver rank to be checked
         )
   {
      return pool[SOLVER_POOL_INDEX(rank)]->getCurrentNode()->hasDescendant();
   }

   ///
   /// add number of nodes solved
   ///
   virtual void addNumNodesSolved(
         long long numOfNodesSolved                ///< number of nodes solved
         )
   {
      nNodesSolvedInSolvers += numOfNodesSolved;
   }

   ///
   /// get the number of nodes solved by the Solver specified
   /// @return the number of nodes solved
   ///
   virtual long long getNumOfNodesSolved(
         int rank                    ///< rank of the Solver
         )
   {
      assert(isSolverActive(rank) || isTerminateRequested(rank) || isInterruptRequested(rank));
      return pool[SOLVER_POOL_INDEX(rank)]->getNumOfNodesSolved();
   }

   ///
   /// get the number of nodes left by the Solver specified
   /// @return the number of nodes left
   ///
   virtual int getNumOfNodesLeft(
         int rank                    ///< rank of the Solver
         )
   {
      assert(isSolverActive(rank));
      return pool[SOLVER_POOL_INDEX(rank)]->getNumOfNodesLeft();
   }

   ///
   /// get the number of nodes left in the Solver which has the best dual bound value
   /// @return the number of nodes left
   ///
   virtual int getNumOfNodesLeftInBestSolver(
         )
   {
      if( selectionHeap->getHeapSize() > 0 )
      {
         return selectionHeap->top()->getNumOfNodesLeft();
      }
      else
      {
         return 0;   // no nodes exist
      }
   }

   ///
   /// get rank of the Solver which has top priority in selection criteria
   /// @return rank of the Solver
   ///
   virtual int getBestSolver(
         )
   {
      if( selectionHeap->getHeapSize() > 0 )
      {
         return selectionHeap->top()->getRank();
      }
      else
      {
         return -1;   // no nodes exist
      }
   }

   ///
   /// get rank of the Solver which has top priority in selection criteria
   /// @return rank of the Solver
   ///
   virtual int getGoodSolverSolvingEssentialNode(
         )
   {
      if( selectionHeap->getHeapSize() > 0 )
      {
         for(int i = 1; i <= (int)selectionHeap->getHeapSize(); i++ )
         {
            int rank = selectionHeap->get(i)->getRank();
            if( getCurrentTask(rank) &&
                  !(getCurrentTask(rank)->getAncestor()) )
            {
               return rank;
            }
         }
         return -1;  // no nodes exist
      }
      else
      {
         return -1;   // no nodes exist
      }
   }

   ///
   /// get dual bound value of solving BbParaNode by the Solver specified
   /// @return dual bound value
   ///
   virtual double getDualBoundValue(
         int rank          ///< rank of the Solver
         )
   {
      assert(isSolverActive(rank));
      return pool[SOLVER_POOL_INDEX(rank)]->getBestDualBoundValue();
   }

   ///
   /// set SolverTerminationState to the Solver specified
   ///
   virtual void setTermState(
         int rank,                                ///< rank of the Solver
         ParaSolverTerminationState *inTermState  ///< pointer to ParaSolverTerminationState object
         )
   {
      pool[SOLVER_POOL_INDEX(rank)]->setTermState(inTermState);
   }

   ///
   /// get SolverTermination state of the Solver specified
   /// @return pointer to SolverTermination object
   ///
   virtual ParaSolverTerminationState *getTermState(
         int rank                               ///< rank of the Solver
         )
   {
      return pool[SOLVER_POOL_INDEX(rank)]->getTermState();
   }

   ///
   ///  update dual bound values of saving BbParaNodes by their dual bound values for subtrees
   ///
   virtual void updateDualBoundsForSavingNodes(
         )
   {
      for( int i = 1; i < paraComm->getSize(); i++ )
      {
         if( getCurrentTask(i) && getCurrentTask(i)->getAncestor() == 0 )
         {
            dynamic_cast<BbParaNode *>(getCurrentTask(i))->updateInitialDualBoundToSubtreeDualBound();
         }
      }
   }

#ifdef UG_WITH_ZLIB

   ///
   /// write BbParaNodes to checkpoint file
   /// @return the number of BbParaNodes saved
   ///
   virtual int writeParaNodesToCheckpointFile(
         gzstream::ogzstream &out             ///< ogzstream to output
         )
   {
      int n = 0;
      for( int i = 1; i < paraComm->getSize(); i++ )
      {
         // if( getCurrentTask(i) && getCurrentTask(i)->getAncestor() == 0 )
         if( getCurrentTask(i) )
         {
            BbParaNode *node = dynamic_cast<BbParaNode *>(getCurrentTask(i));
            while( node )
            {
               if( node->getAncestor() == 0 )
               {
                  // std::cout << "CHECKPOINT: " << node->toSimpleString() << std::endl;
                  node->write(out);
                  n++;
               }
               node = node->next;
            }
         }
      }
      return n;
   }

   ///
   /// write Solver statistics to checkpoint file
   /// @return the number of Solvers whose statistics were written
   ///
   virtual int writeSolverStatisticsToCheckpointFile(
         gzstream::ogzstream &out           ///< ogzstream to output
         )
   {
      int n = 0;
      for( int i = 1; i < paraComm->getSize(); i++ )
      {
         if( pool[SOLVER_POOL_INDEX(i)]->getTermState() )
         {
            pool[SOLVER_POOL_INDEX(i)]->getTermState()->write(out);
            n++;
         }
      }
      return n;
   }

#endif

   ///
   ///  increase the limit number of Solvers getting into collecting mode
   ///
   virtual void incNLimitCollectingModeSolvers(
         )
   {
      nLimitCollectingModeSolvers = std::min(nLimitCollectingModeSolvers+1,
            std::min(nMaxCollectingModeSolvers, nSolvers));
   }

   ///
   /// set collecting mode is allowed to the Solver specified by rank
   ///
   virtual void setCollectingIsAllowed(
         int rank
         )
   {
      pool[SOLVER_POOL_INDEX(rank)]->setCollectingIsAllowed();
   }

   ///
   /// get an inactive Solver rank
   /// @return rank of inactivate Solver
   ///
   virtual int getInactiveSolverRank(
         )
   {
      std::map<int, BbParaSolverPoolElementPtr>::iterator p;
      p = inactiveSolvers.begin();
      if( p == inactiveSolvers.end() )
      {
         return -1;   // no inactive Solver
      }
      return p->second->getRank();
   }

   ///
   /// activate the Solver specified by rank with specified node which has been sent
   ///
   virtual void activateSolver(
         int rank,                      ///< rank of the Solver to be activated
         BbParaNode *node,              ///< pointer to BbParaNode object to be sent to the Solver
         int nGoodNodesInNodePool,      ///< number of good nodes in BbParaNodePool object
         double averageDualBoundGain    ///< current average dual bound gain
         );


   ///
   /// activate the Solver specified by rank with specified node which has been sent and nNodesLeft
   /// (This method is for the racing winner)
   /// TODO: Need to check how this function is used
   ///
   virtual void activateSolver(
         int rank,                      ///< rank of the Solver to be activated
         BbParaNode *node,              ///< pointer to BbParaNode object to be sent to the Solver
         int nNodesLeft                 ///< the number of nodes left in the Solver
         );

   ///
   /// activate a Solver with specified BbParaNode which is sent within this Solver pool
   /// @return rank of Solver which is activated
   ///
   virtual int activateSolver(
         BbParaNode *node,                             ///< pointer to BbParaNode object to be sent to a Solver
         BbParaRacingSolverPool *paraRacingSolverPool, ///< pointer to paraRacingSolverPool object
                                                     ///< to check if the Solver is not solving root node
         bool rampUpPhase,                           ///< indicate if ramp-up phase or not
         int nGoodNodesInNodePool,                   ///< number of good BbParaNodes in BbParaNodePool
         double averageDualBoundGain                 ///< current average bound gain
         );

   ///
   /// add new subtree root node to the active solver with the specified rank
   ///
   virtual void addNewSubtreeRootNode(
         int rank,                                ///< the active solver rank
         BbParaNode *node                         ///< new subtree root node
         );

   ///
   /// make subtree root node as current task for the specified rank
   ///
   virtual void makeSubtreeRootNodeCurrent(
         int rank,                                ///< the active solver rank
         BbParaNode *node                         ///< subtree root node to make it current
         );

   ///
   /// remove subtree root node from the active solver with the specified rank
   ///
   virtual void removeSubtreeRootNode(
         int rank,                                ///< the active solver rank
         BbParaNode *node                         ///< subtree root node to be removed
         );

//   ///
//   /// remove all subtree root node from the active solver with the specified rank
//   /// @return list of all unprocessed nodes
//   ///
//   BbParaNode *removeAllSubtreeRootNode(
//         int rank,                                ///< the active solver rank
//         BbParaNode *node                         ///< subtree root node to be removed
//         );

   ///
   /// extract self-split subtree root node from the active solver with the specified rank
   ///
   virtual BbParaNode *extractSelfSplitSubtreeRootNode(
         int rank,                                ///< the active solver rank
         BbParaNode *node                         ///< subtree root node to be removed
         );

   ///
   /// get self-split subtree root node from the active solver with the specified rank
   ///
   virtual BbParaNode *getSelfSplitSubtreeRootNodes(
         int rank                                 ///< the active solver rank
         );

   ///
   /// extract self-split subtree root node from the active solver with the specified rank
   ///
   virtual BbParaNode *extractSelfSplitSubtreeRootNodes(
         int rank                                 ///< the active solver rank
         );

   ///
   /// delete current self-split subtree root node from the active solver with the specified rank
   ///
   virtual void deleteCurrentSubtreeRootNode(
         int rank                                 ///< the active solver rank
         );

   ///
   /// inactivate the Solver specified by rank
   ///
   virtual void inactivateSolver(
         int rank,                                  ///< rank of the Solver to be inactivated
         long long numOfNodesSolved,                ///< number of nodes solved
         BbParaNodePool *paraNodePool               ///< pointer to BbParaNodePool to change into collecting mode
         );

   ///
   /// reset counters in the Solver specified by rank
   ///
   virtual void resetCountersInSolver(
         int rank,                                  ///< rank of the Solver to reset counters
         long long numOfNodesSolved,                ///< number of nodes solved
         int numOfSelfSplitNodesLeft,               ///< number of self-split nodes left
         BbParaNodePool *paraNodePool               ///< pointer to BbParaNodePool to change into collecting mode
         );

   ///
   /// kill the Solver specified by rank
   /// @return pointer to BbParaNode object assigned to the Solver
   ///
   virtual BbParaNode *solverDied(
         int rank                                  ///< rank of the Solver
         );

   ///
   ///  switch out collecting mode
   ///
   virtual void switchOutCollectingMode(
         );

   ///
   /// enforced to switch out collecting mode of the Solver specified by rank if it is necessary
   ///
   virtual void enforcedSwitchOutCollectingMode(
         int rank             ///< rank of the Solver
         );

   ///
   /// switch out collecting mode of the Solver specified by rank if it is necessary
   ///
   virtual void sendSwitchOutCollectingModeIfNecessary(
         int rank             ///< rank of the Solver
         );

   ///
   /// get global best dual bound value
   /// @return global best dual bound value
   ///
   virtual double getGlobalBestDualBoundValue(
         ) = 0;

   ///
   /// switch in collecting mode
   ///
   virtual void switchInCollectingMode(
         BbParaNodePool *paraNodePool    ///< pointer to BbParaNodePool object
         ) = 0;

   ///
   /// update Solver status
   ///
   virtual void updateSolverStatus(
         int rank,                     ///< rank of the Solver
         long long numNodesSolved,     ///< number of nodes solved
         int numNodesLeft,             ///< number of nodes left
         double solverLocalBestBound,  ///< best bound value in the Solver
         BbParaNodePool *paraNodePool  ///< pointer to BbParaNodePool object
         ) = 0;

   ///
   /// get multiplier of collecting BbParaNodes
   /// @return multiplier of collecting BbParaNodes
   ///
   virtual int getMCollectingNodes(
         )
   {
      return mCollectingNodes;
   }

   ///
   /// get maximum multiplier for the number of collecting BbParaNodes
   /// @return maximum multiplier for the number of collecting BbParaNodes
   ///
   virtual int getMMaxCollectingNodes(
         )
   {
      return mMaxCollectingNodes;
   }

   ///
   /// the following functions are to omit rebooting collecting mode process
   ///

   ///
   /// get time of switching out collecting mode
   /// @return time of switching out collecting mode
   ///
   virtual double getSwichOutTime(
         )
   {
      return switchOutTime;
   }

   ///
   /// set time of switching out collecting mode
   ///
   virtual void   setSwichOutTime(
         double time           ///< time of switching out collecting mode
         )
   {
      switchOutTime = time;
   }

   ///
   /// check if dual bound gain testing is proceeding or not in the Solver specified
   /// @return true if dual bound gain testing is proceeding, false otherwise
   ///
   virtual bool isDualBounGainTesting(
         int rank              ///< rank of the Solver
         )
   {
      return pool[SOLVER_POOL_INDEX(rank)]->isDualBoundGainTesting();
   }

};

///
/// class BbParaSolverPoolForMinimization
/// (Solver Pool for Minimization Problems)
///
class BbParaSolverPoolForMinimization : public BbParaSolverPool
{

public:

   ///
   /// constructor
   ///
   BbParaSolverPoolForMinimization(
         double inMp,                  ///< multiplier of the threshold value p
         double inBgap,                ///< threshold value of gap
         double inMBgap,               ///< multiplier of the bgap value
         int inOriginRank,             ///< origin rank of Solvers managed by this Solver pool
         ParaComm *inParaComm,         ///< communicator used
         ParaParamSet *inParaParams,   ///< paraParamSet used
         ParaTimer  *inParaTimer       ///< timer used
         )
         : BbParaSolverPool(inMp, inBgap, inMBgap, inOriginRank, inParaComm, inParaParams, inParaTimer)
   {
      selectionHeap = new AscendingSelectionHeap(nSolvers);
      if( paraParams->getIntParamValue(SolverOrderInCollectingMode) == 0) // ordered by dual bound value
      {
         collectingModeSolverHeap = new AscendingCollectingModeSolverHeap(
               std::min( nMaxCollectingModeSolvers * 2, nSolvers ) );       // can be more than nMaxCollectingModeSolvers
      }
   }

   ///
   /// constructor
   ///
   BbParaSolverPoolForMinimization(
         double inMp,                  ///< multiplier of the threshold value p
         double inBgap,                ///< threshold value of gap
         double inMBgap,               ///< multiplier of the bgap value
         int inNSolvers,               ///< number of solvers
         int inOriginRank,             ///< origin rank of Solvers managed by this Solver pool
         ParaComm *inParaComm,         ///< communicator used
         ParaParamSet *inParaParams,   ///< paraParamSet used
         ParaTimer  *inParaTimer       ///< timer used
         )
         : BbParaSolverPool(inMp, inBgap, inMBgap, inNSolvers, inOriginRank, inParaComm, inParaParams, inParaTimer)
   {
      selectionHeap = new AscendingSelectionHeap(nSolvers);
      if( paraParams->getIntParamValue(SolverOrderInCollectingMode) == 0) // ordered by dual bound value
      {
         collectingModeSolverHeap = new AscendingCollectingModeSolverHeap(
               std::min( nMaxCollectingModeSolvers * 2, nSolvers ) );       // can be more than nMaxCollectingModeSolvers
      }
   }

   ///
   ///  destructor
   ///
   virtual ~BbParaSolverPoolForMinimization(
         )
   {
      if( selectionHeap ) delete selectionHeap;
      if( collectingModeSolverHeap ) delete collectingModeSolverHeap;
   }

   ///
   /// get global best dual bound value
   /// @return global best dual bound value
   ///
   virtual double getGlobalBestDualBoundValue(
         )
   {
      if( selectionHeap->getHeapSize() > 0 )
      {
         return selectionHeap->top()->getBestDualBoundValue();
      }
      else
      {
         return DBL_MAX;   // no nodes exist
      }
   }

   ///
   /// switch in collecting mode
   ///
   virtual void switchInCollectingMode(
         BbParaNodePool *paraNodePool      ///< pointer to BbParaNodePool object
         );

   ///
   /// update Solver status
   ///
   virtual void updateSolverStatus(
         int rank,                       ///< rank of the Solver
         long long numNodesSolved,       ///< number of nodes solved
         int numNodesLeft,               ///< number of nodes left
         double solverLocalBestBound,    ///< best bound value in the Solver
         BbParaNodePool *paraNodePool    ///< pointer to BbParaNodePool object
         );

   /*
   ///
   /// remove bounded BbParaNodes by given incumbnet value
   /// @return the number of bounded BbParaNodes
   ///
   int removeBoundedNodes(
         double incumbentValue        ///< incumbent value
         )
   {
      int n = 0;
      for( int rank = originRank; rank < (originRank + static_cast<int>(nSolvers)); rank++ )
      {
          if( pool[SOLVER_POOL_INDEX( rank )]->getSelfSplitNodes() )
          {
             n += pool[SOLVER_POOL_INDEX( rank )]->removeBoundedNodes(incumbentValue);
          }
      }
      return n;
   }
   */

};

///
/// class BbParaRacingSolverPool
/// (Racing Solver Pool)
///
class BbParaRacingSolverPool : public ParaRacingSolverPool
{

protected:

   int                       nEvaluationStage;         ///< number of Solvers that are in evaluation stage
   long long                 nNodesSolvedInBestSolver; ///< number of nodes solved in the best Solver
   long long                 nNodesInBestSolver;       ///< number of nodes in the best Solver
   size_t                    nActiveSolvers;           ///< number of active Solvers
   size_t                    nInactiveSolvers;         ///< number of inactive Solvers
   double                    bestDualBound;            ///< current best dual bound value
   double                    bestDualBoundInSolvers;   ///< best dual bound value in Solvers
   BbParaSolverPoolElementPtr  *pool;                    ///< Solver pool indexed by Solver's rank
   SelectionHeap             *selectionHeap;           ///< pointers to active Solvers in ascending or descending order
   BbParaNode                *rootNode;                ///< root BbParaNode

public:

   ///
   /// constructor
   ///
   BbParaRacingSolverPool(
         int inOriginRank,                          ///< origin rank of Solvers managed by this Solver pool
         ParaComm *inParaComm,                      ///< communicator used
         ParaParamSet *inParaParams,                ///< paraParamSet used
         ParaTimer    *inParaTimer,                 ///< timer used
         ParaDeterministicTimer *inParaDetTimer     ///< deterministic timer used
         )
         : ParaRacingSolverPool(inOriginRank,inParaComm,inParaParams, inParaTimer, inParaDetTimer),
           nEvaluationStage(0),
           nNodesSolvedInBestSolver(0),
           nNodesInBestSolver(0),
           nActiveSolvers(0),
           nInactiveSolvers(0),
           bestDualBound(-DBL_MAX),
           bestDualBoundInSolvers(-DBL_MAX),
           rootNode(0)
   {
       // nSolvers = paraComm->getSize() - inOriginRank;
       pool = new BbParaSolverPoolElementPtr[nSolvers];
       for( int i = 0; i < nSolvers; i++ )
       {
           pool[i] = new BbParaSolverPoolElement(originRank+i);
       }
       selectionHeap = new DescendingSelectionHeap(static_cast<std::size_t>(nSolvers));
   }

   ///
   /// constructor
   ///
   BbParaRacingSolverPool(
         int inNSolvers,                            ///< the number of racing solvers
         int inOriginRank,                          ///< origin rank of Solvers managed by this Solver pool
         ParaComm *inParaComm,                      ///< communicator used
         ParaParamSet *inParaParams,                ///< paraParamSet used
         ParaTimer    *inParaTimer,                 ///< timer used
         ParaDeterministicTimer *inParaDetTimer     ///< deterministic timer used
         )
         : ParaRacingSolverPool(inOriginRank,inParaComm,inParaParams, inParaTimer, inParaDetTimer),
           nEvaluationStage(0),
           nNodesSolvedInBestSolver(0),
           nNodesInBestSolver(0),
           nActiveSolvers(0),
           nInactiveSolvers(0),
           bestDualBound(-DBL_MAX),
           bestDualBoundInSolvers(-DBL_MAX),
           rootNode(0)
   {
       // nSolvers = paraComm->getSize() - inOriginRank;
       nSolvers = inNSolvers;
       pool = new BbParaSolverPoolElementPtr[nSolvers];
       for( int i = 0; i < nSolvers; i++ )
       {
           pool[i] = new BbParaSolverPoolElement(originRank+i);
       }
       selectionHeap = new DescendingSelectionHeap(static_cast<std::size_t>(nSolvers));
   }

   ///
   /// destructor
   ///
   ~BbParaRacingSolverPool(
         )
   {
      if( selectionHeap ) delete selectionHeap;
      for( int i = 0; i < nSolvers; i++ )
      {
         delete pool[i];
      }
      if( pool ) delete[] pool;
      if( rootNode ) delete rootNode;
   }

   ///
   /// set the Solver specified by rank is terminate requested
   ///
   virtual void interruptRequested(
         int rank     ///< rank of the Solver
         )
   {
      assert(pool[SOLVER_POOL_INDEX( rank )]->getRank() == rank);
      pool[SOLVER_POOL_INDEX( rank )]->interruptRequested();
   }

   ///
   /// set the Solver specified by rank is terminate requested
   ///
   virtual void terminateRequested(
         int rank     ///< rank of the Solver
         )
   {
      assert(pool[SOLVER_POOL_INDEX( rank )]->getRank() == rank);
      pool[SOLVER_POOL_INDEX( rank )]->terminateRequested();
   }

   ///
   /// check if the Solver specified by rank is interrupt requested or not
   /// @return return true if the Solver is interrupt requested, false otherwise
   ///
   virtual bool isInterruptRequested(
         int rank     ///< rank of the Solver
         )
   {
      return (pool[SOLVER_POOL_INDEX( rank )]->getStatus() == InterruptRequested);
   }

   ///
   /// check if the Solver specified by rank is terminate requested or not
   /// @return return true if the Solver is terminate requested, false otherwise
   ///
   virtual bool isTerminateRequested(
         int rank     ///< rank of the Solver
         )
   {
      return (pool[SOLVER_POOL_INDEX( rank )]->getStatus() == TerminateRequested);
   }

   ///
   /// set the Solver specified by rank is terminated
   ///
   virtual void terminated(
         int rank     ///< rank of the Solver
         )
   {
      assert(pool[SOLVER_POOL_INDEX( rank )]->getRank() == rank);
      assert( !this->isSolverActive(rank) );  // it looks that node != NULL and inactive could be occurred with timing issue when TimeLimit is specified
      assert(pool[SOLVER_POOL_INDEX( rank )]->getStatus() == TerminateRequested ||
             pool[SOLVER_POOL_INDEX( rank )]->getStatus() == InterruptRequested ||
             pool[SOLVER_POOL_INDEX( rank )]->getStatus() == Inactive );
      pool[SOLVER_POOL_INDEX( rank )]->terminated();
   }

   ///
   /// check if the Solver specified by rank is terminated or not
   /// @return return true if the Solver is terminated, false otherwise
   ///
   virtual bool isTerminated(
         int rank     ///< rank of the Solver
         )
   {
      return (pool[SOLVER_POOL_INDEX( rank )]->getStatus() == Terminated);
   }

   ///
   /// reset racing solver pool
   ///
   virtual void reset(
         )
   {
      nEvaluationStage = 0;
      nNodesSolvedInBestSolver = 0;
      nNodesInBestSolver = 0;
      nActiveSolvers = 0;
      nInactiveSolvers = 0;
      bestDualBound = -DBL_MAX;
      bestDualBoundInSolvers = -DBL_MAX;
      rootNode = 0;
      if( selectionHeap ) delete selectionHeap;
      for( int i = 0; i < nSolvers; i++ )
      {
         delete pool[i];
      }
      if( pool ) delete[] pool;
      if( rootNode ) delete rootNode;
      pool = new BbParaSolverPoolElementPtr[nSolvers];
      for( int i = 0; i < nSolvers; i++ )
      {
          pool[i] = new BbParaSolverPoolElement(originRank+i);
      }
      selectionHeap = new DescendingSelectionHeap(static_cast<std::size_t>(nSolvers));
   }

   ///
   /// extract racing root BbParaNode
   ///
   virtual BbParaNode *extractNode(
         )
   {
      rootNode->setDualBoundValue(getGlobalBestDualBoundValue());
      rootNode->setInitialDualBoundValue(getGlobalBestDualBoundValue());
      return rootNode->clone(paraComm);
   }

   ///
   /// get root BbParaNode object of the Solver specified
   ///
   virtual ParaTask *getCurrentTask(
         int rank          ///< rank of the Solver
         )
   {
      return rootNode;
   }

   ///
   /// get dual bound value of solving BbParaNode in the Solver specified by rank
   /// @return dual bound value
   ///
   virtual double getDualBoundValue(
         int rank         ///< rank of the Solver
         )
   {
      return pool[SOLVER_POOL_INDEX(rank)]->getBestDualBoundValue();
   }

   ///
   /// get number of nodes solved in the Solver specified by rank
   /// @return number of nodes solved
   ///
   virtual  long long getNumOfNodesSolved(
         int rank        ///< rank of the Solver
         )
   {
      return pool[SOLVER_POOL_INDEX(rank)]->getNumOfNodesSolved();
   }

   ///
   /// get number of nodes left in the Solver specified by rank
   /// @return number of nodes left
   ///
   virtual int getNumNodesLeft(
         int rank       ///< rank of the Solver
         )
   {
      return pool[SOLVER_POOL_INDEX(rank)]->getNumOfNodesLeft();
   }

   ///
   /// get global best dual bound value
   /// @return global best dual bound value
   ///
   virtual double getGlobalBestDualBoundValue(
         )
   {
      if( selectionHeap->getHeapSize() > 0 )
      {
         return bestDualBound;
      }
      else
      {
         return -DBL_MAX;   // no nodes exist
      }
   }

   ///
   /// get winner Solver rank
   /// @return rank of the winner Solver
   ///
//   int getWinner(
//         )
//   {
//      // assert( winnerRank > 0 );
//      return winnerRank;   // -1 means that winner is not decided
//   }

   ///
   /// get number of nodes solved in the best Solver
   /// @return number of nodes solved in the best Solver
   ///
   virtual long long getNnodesSolvedInBestSolver(
         )
   {
      return nNodesSolvedInBestSolver;
   }

   ///
   /// get number of nodes left in the best Solver
   /// @return number of nodes left in the best Solver
   ///
   virtual long long getNnodesLeftInBestSolver(
         )
   {
      return nNodesInBestSolver;
   }

   ///
   /// get best dual bound value in inactivated Solvers
   /// @return best dual bound value in inactivated Solvers
   ///
   virtual double getBestDualBoundInInactivatedSolvers(
         )
   {
      return bestDualBoundInSolvers;
   }

   ///
   /// activate racing ramp-up Solver pool with root BbParaNode object
   ///
   virtual void activate(
         BbParaNode *node       ///< pointer to root BbParaNode object
         )
   {
      rootNode = node;
      for( int rank = originRank; rank < (originRank + nSolvers); rank++ )
      {
          pool[SOLVER_POOL_INDEX( rank )]->racingActivate();
//          if( rank != originRank ||
//                ( paraParams->getIntParamValue(UgCplexRunningMode) != 1 ) )
//          if( rank != originRank  )
//          {
             selectionHeap->insert(pool[SOLVER_POOL_INDEX( rank )]);  // this should be called after activate: dual bound value need to be set
//          }
          nActiveSolvers++;
      }
      nInactiveSolvers = 0;
      nNodesInBestSolver = 1;
   }

   ///
   /// check if the specified Solver is active or not
   /// @return true if the specified Solver is active, false otherwise
   ///
   virtual bool isSolverActive(
         int rank        ///< rank of the Solver
         )
   {
      if(pool[SOLVER_POOL_INDEX( rank )]->isRacingStage() ||
            pool[SOLVER_POOL_INDEX( rank )]->isEvaluationStage() )
      {
         return true;
      }
      else
      {
         return false;
      }
   }

   ///
   /// update Solver status
   ///
   virtual void updateSolverStatus(
         int rank,                      ///< rank of the Solver
         long long numNodesSolved,      ///< number of nodes solved
         int numNodesLeft,              ///< number of nodes left
         double solverLocalBestBound    ///< best bound value in the Solver
         );

   ///
   /// check racing termination criteria
   ///
   virtual bool isWinnerDecided(
         bool feasibleSol              ///< indicate if a feasible solution was generagted or not
         );

   ///
   /// inactivate the Solver specified by rank
   ///
   virtual void inactivateSolver(
         int rank                      ///< rank of the Solver
         )
   {
      if(pool[SOLVER_POOL_INDEX( rank )]->isRacingStage() ||
            pool[SOLVER_POOL_INDEX( rank )]->isEvaluationStage() )
      {
         if( pool[SOLVER_POOL_INDEX( rank )]->getBestDualBoundValue() > bestDualBoundInSolvers )
         {
            bestDualBoundInSolvers = pool[SOLVER_POOL_INDEX( rank )]->getBestDualBoundValue();
         }
         pool[SOLVER_POOL_INDEX( rank )]->inactivate();
         nInactiveSolvers++;
         nActiveSolvers--;
      }
      else
      {
          THROW_LOGICAL_ERROR2("Rank = ", rank);
      }
   }

   ///
   /// get number of active Solvers
   /// @return number of active Solvers
   ///
   virtual std::size_t getNumActiveSolvers(
         )
   {
      return nActiveSolvers;
   }

   ///
   /// get number of inactive Solvers
   /// @return number of inactive Solvers
   ///
   virtual std::size_t getNumInactiveSolvers(
         )
   {
      return nInactiveSolvers;
   }

   ///
   /// check if the Solver specified in an argument is evaluation stage or not
   /// @return true if the Solver is evaluation stage, false otherwise
   ///
   virtual bool isEvaluationStage(
         int rank
         )
   {
      return ( pool[SOLVER_POOL_INDEX( rank )]->isEvaluationStage() );
   }

   ///
   /// get active Solver number string
   /// @return string to show active Solver rank
   ///
   virtual std::string getStrActiveSolerNumbers(
         )
   {
      std::ostringstream oss;
      oss << "   ";
      for( int rank = originRank; rank < (originRank + nSolvers); rank++ )
      {
          if( pool[SOLVER_POOL_INDEX( rank )]->isRacingStage() )
          {
             oss << rank << " ";

          }
      }
      return oss.str();
   }

};

}

#endif // __BB_PARA_SOLVER_POOL_H__