DistParBranchAndBound.h

Go to the documentation of this file.

// 
//     Minotaur -- It's only 1/2 bull
// 
//     (C)opyright 2008 - 2025 The Minotaur Team.
// 
 
#ifndef MINOTAURDISTPARBRANCHANDBOUND_H
#define MINOTAURDISTPARBRANCHANDBOUND_H
 
#include "Types.h"
#include <sys/time.h>
 
namespace Minotaur {
 
  struct  DistParBabOptions;
  struct  DistParBabStats;
  class   Engine;
  class   NodeProcessor;
  class   NodeRelaxer;
  class   ParNodeIncRelaxer;
  class   ParPCBProcessor;
  class   ParTreeManager;
  class   Problem;
  class   Solution;
  class   SolutionPool;
  class   WarmStart;
  class   Timer;
  typedef Engine* EnginePtr;
  typedef DistParBabOptions* DistParBabOptionsPtr;
  typedef NodeProcessor* NodeProcessorPtr;
  typedef NodeRelaxer* NodeRelaxerPtr;
  typedef ParNodeIncRelaxer* ParNodeIncRelaxerPtr;
  typedef ParPCBProcessor* ParPCBProcessorPtr;
  typedef Solution* SolutionPtr;
  typedef SolutionPool* SolutionPoolPtr;
  typedef ParTreeManager* ParTreeManagerPtr;
  typedef WarmStart* WarmStartPtr;
 
  class DistParBranchAndBound {
 
  public:
    DistParBranchAndBound();
 
    DistParBranchAndBound(EnvPtr env, ProblemPtr p, UInt proc_rank, UInt num_procs);
 
    virtual ~DistParBranchAndBound();
 
    void printsomething();
    void addPreRootHeur(HeurPtr h);
 
    double getPerGap();
 
    double getLb();
 
    NodeProcessorPtr getNodeProcessor();
 
    NodeRelaxerPtr getNodeRelaxer(); 
 
    /*
     * \brief Return solution from the last solve. If no solution was found, return
     * NULL.
     */
    SolutionPtr getSolution();
 
    SolveStatus getStatus();
 
    ParTreeManagerPtr getTreeManager(); 
 
    double getUb();
 
    std::vector<std::vector<double> > mapSerialOutput (
      std::vector<std::vector<double> >serVec,
      std::vector<std::vector<double> >parVec);
 
    UInt numProcNodes();
 
    void setLogLevel(LogLevel level);
 
    void setNodeProcessor(NodeProcessorPtr p);
 
    void setNodeRelaxer(NodeRelaxerPtr nr);
 
    void shouldCreateRoot(bool b);
 
    void solve();
 
    int strToInt(std::string str);
 
    void parsolveOppor(ParNodeIncRelaxerPtr parNodeRelaxer[],
                  ParPCBProcessorPtr parPCBProcessor[],
                  UInt nThreads);
    void solveMasterProc_(ParNodeIncRelaxerPtr parNodeRelaxer[],
                  ParPCBProcessorPtr parPCBProcessor[],
                  UInt nThreads);
    void solveWorkerProc_(ParNodeIncRelaxerPtr parNodeRelaxer[],
                  ParPCBProcessorPtr parPCBProcessor[],
                  UInt nThreads);
 
    void print2dvec(std::vector<std::vector<int> > output);
 
    void print2dvec(std::vector<std::vector<double> > output);
 
    std::vector<std::vector<double> > readSerialOutput(const char* inputFile);
 
    double totalTime();
 
    void writeStats(std::ostream & out);
 
    void writeParStats(std::ostream & out,
                       ParPCBProcessorPtr parPCBProcessor[]);
 
    void writeStats();
 
    double getWallTime() {
      struct timeval time;
      if (gettimeofday(&time,NULL)) {
        // Handle error
        return 0;
      }
      return (double)time.tv_sec + (double)time.tv_usec * .000001;
    }
 
  private:
    EnvPtr env_;
 
    LoggerPtr logger_;
 
    static const std::string me_;
 
    void getBoundChanges_(NodePtr node, std::vector<double>& bound_changes);
 
    void updateProcsRunningStatus_(std::vector<int>& proc_running);
    void checkUbUpdates_(const std::vector<int>& proc_running);
    void checkLbUpdatesFromOtherProcs_(double& globalBestLB, std::vector<double>& proc_lb);
    //void checkLbUpdatesFromOtherProcs_(double& globalBestLB, const std::vector<int>& proc_running);
    void distributeNodes_();
 
    void getStartingNode_(bool *shouldWait, bool *shouldRun, std::vector<double>& node_data);
 
    NodeProcessorPtr nodePrcssr_;
 
    NodeRelaxerPtr nodeRlxr_;
 
    DistParBabOptionsPtr options_;
 
    HeurVector preHeurs_;
 
    ProblemPtr problem_;
 
    SolutionPoolPtr solPool_;
 
    DistParBabStats *stats_;
 
    SolveStatus status_;
 
    Timer *timer_;
   
    ParTreeManagerPtr tm_;
 
    int proc_rank_;
 
    int num_procs_;
 
    double best_tree_lb;
 
 
    NodePtr processRoot_(bool *should_prune, bool *should_dive);
 
    // Node to be received to start processing of the assigned sub-tree
    NodePtr getStartingNode_(bool *shouldWait, bool *shouldRun);
    
    void processRoot_(bool *should_prune, bool *should_dive,
                         ParNodeIncRelaxerPtr parNodeRlxr,
                         ParPCBProcessorPtr nodePrcssr, WarmStartPtr ws,
                         NodePtr &node);
 
 
    void sendUbToOtherProcs_(double val, const std::vector<int>& proc_running);
 
    bool shouldPrune_(NodePtr node);
 
    bool shouldStopPar_(double wallStartTime, double treeLb);
 
    void showStatus_(bool current_uncounted);
 
    void showParStatus_(UInt current_uncounted, double treeLb,
                        double wallStartTime);
  };
 
  struct DistParBabStats 
  {
    DistParBabStats();
 
    UInt nodesProc;
 
    double timeUsed;
 
    double updateTime;
  };
 
 
  struct DistParBabOptions
  {
    DistParBabOptions();
 
    DistParBabOptions(EnvPtr env);
    
    bool createRoot;
 
    double logInterval;
 
    UInt nodeLimit;
 
     double perGapLimit;
 
    UInt solLimit;
 
    double timeLimit;
  };
 
  typedef DistParBranchAndBound* DistParBranchAndBoundPtr;
}
#endif