ParMINLPDiving.h

Go to the documentation of this file.

//
//     Minotaur -- It's only 1/2 bull  
//
//     (C)opyright 2008 - 2025 The Minotaur Team.
//
 
#ifndef MINOTAURPARMINLPDIVING_H
#define MINOTAURPARMINLPDIVING_H
 
#include "Heuristic.h"
#include <vector>
#include <stack>
#include <sys/time.h>
 
 
namespace Minotaur {
  class LinearHandler;
  class Solution;
  class Timer;
  class VarBoundMod;
  typedef const Solution* ConstSolutionPtr;
  typedef VarBoundMod* VarBoundModPtr;
 
  typedef enum {
    Floor,        
    Ceil,         
    Nearest,      
    Farthest      
  } Direction;
 
  typedef enum {
    Least,     
    Most       
  } Order;
 
  typedef enum {
    Fractional,     
    VectorLength,   
    LexBound,       
    ReducedCost     
  } Scoretype;
 
  struct DivingheurStats {
    UInt numNLPs[4];       
    UInt numInfeas[4];     
    UInt errors[4];        
    UInt numSol[4];        
    double time[4];        
    UInt iterations[4];    
    UInt totalProbs;       
    UInt totalSol;         
    UInt numLocal;         
    double best_obj_value; 
    double totalTime;      
  };
 
  class ParMINLPDiving : public Heuristic {
  public:
 
    ParMINLPDiving(EnvPtr env, ProblemPtr p, EnginePtr e);
 
    ~ParMINLPDiving();
 
    void solve(NodePtr node, RelaxationPtr rel, SolutionPoolPtr s_pool); 
 
    void writeStats(std::ostream &out) const;
 
    void writeParStats(std::ostream &out, DivingheurStats *stats,
                       double wallTime) const;
 
    virtual std::string getDirectionString(UInt i);
 
    virtual std::string getScoreString(UInt i);
 
    virtual std::string getOrderString(UInt i);
 
    void setAltEngine(EnginePtr nlpe) { nlpe_ = nlpe; }
 
    void setOrigProb(ProblemPtr minlp) { minlp_ = minlp; }
 
    void solveNLP(ConstSolutionPtr sol, bool *solFound,
                             ProblemPtr minlp, EnginePtr nlpe);
 
    void fixInts(const double *x,
                            std::stack<Modification *> &nlpMods,
                            ProblemPtr minlp);
 
    //Unfix integer variables
    void unfixInts(std::stack<Modification *> &nlpMods,
                              ProblemPtr minlp);
 
   double getWallTime() {
     struct timeval time;
     if (gettimeofday(&time,NULL)) {
       // Handle error
       return 0;
     }
     return (double)time.tv_sec + (double)time.tv_usec * .000001;
   }
 
  protected:
 
    const static std::string me_;
 
    //DoubleVector avgDual_;
 
    EnginePtr e_;
 
    EnginePtr nlpe_;
 
    EnvPtr env_;
 
    //double* gradientObj_;
 
    double intTol_;
 
    //ModVector lastNodeMods_;
 
    //LinearHandler *lh_;
 
    LoggerPtr logger_;
 
    UInt maxProbs_;
 
    UInt maxSol_;
 
    //std::stack<VarBoundModPtr> mods_;
 
    UInt nSelector_;
 
    UInt numThreads_;
 
    ProblemPtr minlp_;
 
    ProblemPtr p_;
 
    //DoubleVector score_;
 
    DivingheurStats *stats_;
 
    Timer* timer_;
 
    //UIntVector violated_;
 
    double wallTimeStart_;
 
    UInt numLevels_;
    
    typedef UInt (ParMINLPDiving::*FuncPtr) (UInt numfrac, const double* x,
                                             Direction d, Order o,
                                             ProblemPtr p,
                                             UIntVector& violated,
                                             std::stack<VarBoundModPtr>& mods,
                                             LinearHandler* lh,
                                             ModVector& lastNodeMods,
                                             DoubleVector& score,
                                             DoubleVector& avgDual,
                                             double* gradientObj);
 
    //void backtrack_(UInt n_flipped);
    void backtrack_(UInt n_moded, ModVector& lastNodeMods, ProblemPtr p,
                    std::stack<VarBoundModPtr>& mods);
    //UInt FracBounds_(UInt numfrac, const double* x, 
                     //Direction d, Order o);
 
 
    UInt FracBounds_(UInt numfrac, const double* x, Direction d, Order o,
                     ProblemPtr p, UIntVector& violated,
                     std::stack<VarBoundModPtr>& mods, LinearHandler* lh,
                     ModVector& lastNodesMods, DoubleVector& score,
                     DoubleVector& avgDual, double* gradientObj);
    //void getScore_(const double* x, Scoretype s);
 
    void getScore_(const double* x, Scoretype s, DoubleVector& score,
                   ProblemPtr p, DoubleVector& avgDual,
                   double* gradientObj);
    //void implementDive_(int i, const double*x, SolutionPoolPtr s_pool);
    void implementDive_(int i, const double* x, SolutionPoolPtr s_pool,
                        ModVector& lastNodesMods, EnginePtr e, ProblemPtr p,
                        DoubleVector& avgDual, UIntVector& violated,
                        std::stack<VarBoundModPtr>& mods, LinearHandler* lh,
                        DoubleVector& score, double* gradientObj,
                        DivingheurStats* stats);
    //UInt isFrac_(const double* x);
    UInt isFrac_(const double* x, UIntVector& violated, ProblemPtr p);
 
    UInt LexBounds_(UInt numfrac, const double* x, Direction d, Order o,
                    ProblemPtr p, UIntVector& violated,
                    std::stack<VarBoundModPtr>& mods, LinearHandler* lh,
                    ModVector& lastNodesMods, DoubleVector& score,
                    DoubleVector& avgDual, double* gradientObj);
 
    UInt ReducedCost_(UInt numfrac, const double* x, Direction d, Order o,
                      ProblemPtr p, UIntVector& violated,
                      std::stack<VarBoundModPtr>& mods, LinearHandler* lh,
                      ModVector& lastNodesMods, DoubleVector& score,
                      DoubleVector& avgDual, double* gradientObj);
    void restoreBounds_(double* LB_copy, double* UB_copy, UInt vars,
                        ProblemPtr p);
 
    double rounding_(double value, Direction d);
 
    void saveBounds_(double* LB_copy, double* UB_copy, UInt vars);
 
    FuncPtr selectHeur_(int i, Direction &d, Order &o);
 
    bool shouldDive_();
 
    void sort_(UInt left, UInt right, DoubleVector& score,
               UIntVector& violated);
 
    void updateAvgDual_(ConstSolutionPtr sol, DoubleVector& avgDual,
                        DivingheurStats* stats);
 
    UInt VectorLength_(UInt numfrac, const double* x, Direction d, Order o,
                       ProblemPtr p, UIntVector& violated,
                       std::stack<VarBoundModPtr>& mods, LinearHandler* lh,
                       ModVector& lastNodesMods, DoubleVector& score,
                       DoubleVector& avgDual, double* gradientObj);
 
    bool vectorFlag_(UInt min_vlength, ProblemPtr p);
 
  };
 
  typedef ParMINLPDiving* ParMINLPDivingPtr;
}
#endif