MultilinearHandler.h

Go to the documentation of this file.

//
//     Minotaur -- It's only 1/2 bull
//
//     (C)opyright 2008 - 2025 The Minotaur Team.
//
 
#ifndef MINOTAURMULTILINEARHANDLER_H
#define MINOTAURMULTILINEARHANDLER_H
 
#include "Handler.h"
#include "LPEngine.h"
#include "Types.h"
 
namespace Minotaur {
 
class   Function;
class   PolynomialFunction;
class   QuadraticFunction;
class   Problem;
typedef PolynomialFunction* PolyFunPtr;
typedef QuadraticFunction* QuadraticFunctionPtr;
 
class MultilinearHandler : public Handler {
 
public:
    
  MultilinearHandler(EnvPtr env, ProblemPtr problem); 
        
  virtual ~MultilinearHandler() {};
 
    
  bool findOriginalVariable(ConstVariablePtr rv, ConstVariablePtr &ov) const;
 
  virtual void getBranchingCandidates(RelaxationPtr rel, 
                                      const DoubleVector &x, ModVector &mods, 
                                      BrVarCandSet &cands,
                                      BrCandVector &gencands, bool &is_inf );
    
  bool isFeasible(ConstSolutionPtr, RelaxationPtr, bool &should_prune,
                  double &inf_meas);
    
  void relax(RelaxationPtr relaxation, bool & isInfeasible);
 
  // Does nothing.
  void relaxInitFull(RelaxationPtr, bool *) {} ;
 
  // Does nothing.
  void relaxInitInc(RelaxationPtr, bool *) {};
 
  // Does nothing.
  void relaxNodeFull(NodePtr, RelaxationPtr, bool *)  {};
 
  // Does nothing.
  void relaxNodeInc(NodePtr, RelaxationPtr, bool *) {};
 
  void relaxNode(NodePtr node, RelaxationPtr relaxation, bool & isInfeasible);
 
    
  std::map <std::vector<ConstVariablePtr>, ConstVariablePtr > getRevMlterms() 
  {return rev_mlterms_; }
 
  std::map <ConstVariablePtr, std::vector<ConstVariablePtr> > getMlterms() 
  {return mlterms_; }
 
  std::map <ConstVariablePtr, UInt> getMaxPow() {return max_pow_; }
    
  std::map <ConstVariablePtr, ConstVariablePair> getBlterms() {return blterms_; }
    
  std::map <ConstVariablePair, ConstVariablePtr> getRevBlterms() {return rev_blterms_; }
    
  std::map <VarIntMap, ConstVariablePtr> getMonomialterms() {return monomial_terms_; }
    
  std::map <ConstVariablePtr, ConstVariablePair> getSqterms() {return sqterms_; }    
    
  std::map <ConstVariablePair, ConstVariablePtr> getRevSqterms() {return rev_sqterms_; }    
    
  std::vector<std::vector<ConstVariablePtr> > getGroups() {return groups_; }
    
  std::vector<std::vector<ConstVariablePtr> > getAllLambdas() {return all_lambdas_; }
    
  std::map <ConstVariablePtr, ConstVariablePtr> getOriginalVariablesMap() {return oVars_; }
    
  std::map <ConstVariablePtr, ConstVariablePtr> getRevOriginalVariablesMap() {return rev_oVars_; }
    
  std::map<ConstVariablePtr, std::vector<ConstVariablePtr> > getNewCopyVariables() 
    {return newCopyVariables_; }
    
  std::map <VarIntMap, ConstVariablePtr> getMonomialTerms() {return monomial_terms_; }
    
  std::map <ConstVariablePair, ConstVariablePtr> getRevBilinearTerms() 
    {return rev_blterms_; }
 
 
  void separate(ConstSolutionPtr, NodePtr , RelaxationPtr , CutManager *,  
                SolutionPoolPtr, bool *, SeparationStatus *) {};
    
  virtual ModificationPtr getBrMod(BrCandPtr , DoubleVector &, 
                                   RelaxationPtr , BranchDirection );
    
  virtual Branches getBranches(BrCandPtr cand, DoubleVector &x , 
                               RelaxationPtr rel, SolutionPoolPtr s_pool);
 
  // presolve.
  virtual SolveStatus presolve(PreModQ *, bool *changed, Solution **) {return Finished;};
    
  // Implement Handler::presolveNode()
  virtual bool presolveNode(RelaxationPtr, NodePtr, SolutionPoolPtr, ModVector &,
                    ModVector &)
  {return false;};
 
    
  // Write name
  std::string getName() const;
    
protected:
 
  EnvPtr env_;
 
  // /**
  // The problem for which the handler was created.
  //XXX This should be const!
  // */
  ConstProblemPtr problem_;
 
  ProblemPtr workingProblem_;
    
    
    
private:
    
  LPEnginePtr lp_engine_;
  int linearizationCnt_;
    
  // Whether the objective was nonlinear and was moved to the constraints or not
  bool objModified_;
 
  // (Absolute?) error tolerance for branching.
  double eTol_;
 
  // max_pow maps each variable with its highest power that appears 
  // in the polynomial or quadratic part
  std::map <ConstVariablePtr, UInt> max_pow_;
  std::map <ConstVariablePtr, UInt>::iterator max_pow_it_;
 
  LoggerPtr logger_;
 
  // The map for the original variables and their copy in the relaxation (x, newVar)
  std::map <ConstVariablePtr, ConstVariablePtr> oVars_;
    
  // The map for the original variables and their copy in the relaxation -- reverse map (newVar, x)
  std::map <ConstVariablePtr, ConstVariablePtr> rev_oVars_;
 
  // The square terms <x1,(y,x_1)>
  std::map <ConstVariablePtr, ConstVariablePair> sqterms_;
    
  // The square terms -- reverse map
  std::map <ConstVariablePair, ConstVariablePtr> rev_sqterms_;
    
  // ******
  // The bilinear terms of the original constraints
  std::map <ConstVariablePtr, ConstVariablePair> blterms_cons_;
  std::map <ConstVariablePair, std::vector<double> > blterms_cons_coef_;
 
  // The bilinear terms of the original constraints -- reverse map
  std::map <ConstVariablePair, ConstVariablePtr> rev_blterms_cons_;
 
  // The multilinear terms of the original constraints
  std::map <ConstVariablePtr, std::vector<ConstVariablePtr> > mlterms_cons_;
  std::map <ConstVariablePtr, std::vector<ConstVariablePtr> >::iterator mlterms_cons_it_;
  std::map <std::vector<ConstVariablePtr>, std::vector<double> > mlterms_cons_coef_;
    
  // The multilinear terms of the original constraints -- reverse map
  std::map <std::vector<ConstVariablePtr>, ConstVariablePtr > rev_mlterms_cons_;
  // ******
 
 
  // ******
  // The bilinear terms of the original objective
  std::map <ConstVariablePtr, ConstVariablePair> blterms_obj_;
  std::map <ConstVariablePair, std::vector<double> > blterms_obj_coef_;
 
  // The bilinear terms of the original constraints -- reverse map
  std::map <ConstVariablePair, ConstVariablePtr> rev_blterms_obj_;
 
  // The multilinear terms of the original constraints
  std::map <ConstVariablePtr, std::vector<ConstVariablePtr> > mlterms_obj_;
  std::map <ConstVariablePtr, std::vector<ConstVariablePtr> >::iterator mlterms_obj_it_;
  std::map <std::vector<ConstVariablePtr>, std::vector<double> > mlterms_obj_coef_;
    
  // The multilinear terms of the original constraints -- reverse map
  std::map <std::vector<ConstVariablePtr>, ConstVariablePtr > rev_mlterms_obj_;
  // ******
 
 
  // All the bilinear terms 
  std::map <ConstVariablePtr, ConstVariablePair> blterms_;
  std::map <ConstVariablePair, std::vector<double> > blterms_coef_;
 
  // All the bilinear terms -- reverse map
  std::map <ConstVariablePair, ConstVariablePtr> rev_blterms_;
    
  // All the multilinear terms
  std::map <ConstVariablePtr, std::vector<ConstVariablePtr> > mlterms_;
  std::map <ConstVariablePtr, std::vector<ConstVariablePtr> >::iterator mlterms_it_;
  std::map <std::vector<ConstVariablePtr>, std::vector<double> > mlterms_coef_;
 
  // All the multilinear terms -- reverse map
  std::map <std::vector<ConstVariablePtr>, ConstVariablePtr > rev_mlterms_;
 
  // The monomial terms
  std::map <VarIntMap, ConstVariablePtr> monomial_terms_;
  std::map <VarIntMap, ConstVariablePtr>::iterator monomial_terms_it_;
 
  // The groups
  std::vector<std::vector<ConstVariablePtr> > groups_;
 
  // All the lambda variables
  std::vector<std::vector<ConstVariablePtr> > all_lambdas_;
 
  // The copy variables for the variables with exponent
  std::map<ConstVariablePtr, std::vector<ConstVariablePtr> > newCopyVariables_;
  std::map<ConstVariablePtr, std::vector<ConstVariablePtr> >::iterator newCopyVariables_it_;
 
 
  void clearAllContainers();
 
 
  void makeMcCormick(RelaxationPtr relaxation, bool &isInfeasible);
    
  void makeGroupedConvexHull(RelaxationPtr relaxation, bool &isInfeasible, 
                             int groupStrategy, bool objModified);
    
  void makeGroups(std::map <ConstVariablePtr, ConstVariablePair> blterms, 
                  std::map <ConstVariablePair, ConstVariablePtr> rev_blterms, 
                  std::map <ConstVariablePair, std::vector<double> > blterms_coef,
                  std::map <ConstVariablePtr, std::vector<ConstVariablePtr> > mlterms, 
                  std::map <std::vector<ConstVariablePtr>, ConstVariablePtr> rev_mlterms, 
                  std::map <std::vector<ConstVariablePtr>, std::vector<double> > mlterms_coef,
                  std::map <ConstVariablePtr, ConstVariablePair> blterms_obj, 
                  std::map <ConstVariablePair, ConstVariablePtr> rev_blterms_obj, 
                  std::map <ConstVariablePair, std::vector<double> > blterms_obj_coef,
                  std::map <ConstVariablePtr, std::vector<ConstVariablePtr> > mlterms_obj, 
                  std::map <std::vector<ConstVariablePtr>, ConstVariablePtr> rev_mlterms_obj, 
                  std::map <std::vector<ConstVariablePtr>, std::vector<double> > mlterms_obj_coef,
                  std::map <ConstVariablePtr, ConstVariablePair> blterms_cons, 
                  std::map <ConstVariablePair, ConstVariablePtr> rev_blterms_cons, 
                  std::map <ConstVariablePair, std::vector<double> > blterms_cons_coef,
                  std::map <ConstVariablePtr, std::vector<ConstVariablePtr> > mlterms_cons, 
                  std::map <std::vector<ConstVariablePtr>, ConstVariablePtr> rev_mlterms_cons, 
                  std::map <std::vector<ConstVariablePtr>, std::vector<double> > mlterms_cons_coef,
                  std::vector <std::vector<ConstVariablePtr> > &groups,                               
                  int groupStrategy);
 
 
  void getMultilinearTerms(std::map <ConstVariablePtr, ConstVariablePair> blterms,
                           std::map <ConstVariablePtr, std::vector<ConstVariablePtr> > mlterms,
                           UInt maxGroupSize,
                           std::vector<std::vector<ConstVariablePtr> > &terms);
 
  void getMultilinearTermsCoef(std::map <ConstVariablePair, double> blterms_coef,
                               std::vector<std::vector<ConstVariablePtr> > terms,
                               std::vector<double> &termsCoeff);
 
 
  void getMultilinearVariables(std::map <ConstVariablePtr, ConstVariablePair> blterms,
                               std::map <ConstVariablePtr, std::vector<ConstVariablePtr> > mlterms,
                               std::vector<ConstVariablePtr> &mlVars);
 
  void groupUsingIntersection(UInt gs, double rho,
                              std::vector<std::vector<ConstVariablePtr> > terms,
                              std::vector <std::vector<ConstVariablePtr> > &groups);
 
  void groupUsingIntersection2(UInt gs,
                               std::vector<std::vector<ConstVariablePtr> > terms,
                               std::vector <std::vector<ConstVariablePtr> > &groups);
 
  void groupTermByTerm(std::map <ConstVariablePtr, ConstVariablePair> blterms,
                       std::map <ConstVariablePtr, std::vector<ConstVariablePtr> > mlterms,
                       std::vector <std::vector<ConstVariablePtr> > &groups);
 
  void groupUsingDensest(UInt gs, 
                         std::map <ConstVariablePair, std::vector<double> > bl_coef,
                         std::map <std::vector<ConstVariablePtr>, std::vector<double> > ml_coef,
                         std::vector <ConstVariablePtr> vars,
                         std::vector <std::vector<ConstVariablePtr> > &groups);
      
  void groupUsingDensest2ND(UInt gs, 
                            std::map <ConstVariablePair, std::vector<double> > bl_coef,
                            std::map <std::vector<ConstVariablePtr>, std::vector<double> > ml_coef,
                            std::vector <ConstVariablePtr> vars,
                            std::vector <std::vector<ConstVariablePtr> > &groups,
                            UInt maxGroupsCnt);
 
  void groupUsingCoef(UInt gs,
                      std::map <ConstVariablePair, std::vector<double> > bl_coef,
                      std::map <std::vector<ConstVariablePtr>, std::vector<double> > ml_coef,
                      std::vector <ConstVariablePtr> graphVars,
                      std::vector <std::vector<ConstVariablePtr> > &groups);
 
  void findSubgraphDensity(std::vector<std::vector<ConstVariablePtr> > terms,
                           double** term_var_matrix,
                           std::vector<ConstVariablePtr> nodes,
                           std::vector<int> nodesInd,
                           double &density);
 
  void findDensestSubgraph(UInt gs,
                           std::vector<ConstVariablePtr> vars,
                           std::vector<std::vector<ConstVariablePtr> > terms,
                           double** term_var_matrix,
                           std::vector<int> component,
                           std::vector<ConstVariablePtr> &densest,
                           std::vector<int> &densestInd,
                           bool &isCompEmpty);
 
  void findGraphComponents(int varsCnt,
                           int termsCnt,
                           double** term_var_matrix, 
                           std::vector<std::vector<int> > &components);
 
  void findGroupDensity(std::vector<std::vector<ConstVariablePtr> > terms,
                        std::vector <std::vector<ConstVariablePtr> > groups,
                        std::vector <int> &density);
 
  void findGroupCoef(std::vector<std::vector<ConstVariablePtr> > terms,
                     std::vector <double> termsCoef,
                     std::vector <std::vector<ConstVariablePtr> > groups,
                     std::vector <double> &sumCoef);
 
  void removeSubgraphEdges(int termsCnt,
                           double** &term_var_matrix,
                           std::vector<std::vector<ConstVariablePtr> > terms,
                           std::vector<ConstVariablePtr> nodes,
                           std::vector<int> nodesInd);
 
  void reduceSubgraphEdges(int termsCnt,
                           double** &term_var_matrix,
                           std::vector<std::vector<ConstVariablePtr> > terms,
                           std::vector<ConstVariablePtr> nodes,
                           std::vector<int> nodesInd);
 
  void termsAppearKtimes(std::vector<std::vector<ConstVariablePtr> > terms,
                         std::vector <double> termsCoef,
                         std::vector <std::vector<ConstVariablePtr> > groups,
                         int k,
                         std::vector<std::vector<ConstVariablePtr> > &termsk,
                         std::vector <double> &termsKCoef,
                         std::vector<int> &termRep);
 
  void countTermsAppearance(std::vector<std::vector<ConstVariablePtr> > terms,
                            std::vector <std::vector<ConstVariablePtr> > groups,
                            std::vector<int> &termRep);
 
  void makeBinaryVariablesPowers1(FunctionPtr &f, PolyFunPtr &p, 
                                  QuadraticFunctionPtr &q, LinearFunctionPtr &l);    
    
  /*
 void makeGroupedConvexHull(RelaxationPtr relaxation, bool &isInfeasible, 
 std::vector<bool> & c_list, int groupStrategy);
  */
    
  void allExtreme(std::vector<int> &S, std::vector<double> &lb, 
                  std::vector<double> &ub, 
                  std::vector<std::vector<double> > &E);
    
  void visit(std::vector<int> &S, std::vector<double> &lb, 
             std::vector<double> &ub, UInt ix, std::vector<double> &val, 
             std::vector<std::vector<double> > &E);
    
    
};
typedef MultilinearHandler* MultilinearHandlerPtr;
typedef const MultilinearHandler* MultilinearConstHandlerPtr;
}
#endif