HierarchicalLeastSquareSolver.h

Go to the documentation of this file.

/* Copyright 2017-2020 CNRS-AIST JRL and CNRS-UM LIRMM */
 
#pragma once
 
#include <tvm/api.h>
#include <tvm/defs.h>
 
#include <tvm/hint/internal/Substitutions.h>
#include <tvm/scheme/internal/Assignment.h>
#include <tvm/solver/internal/Option.h>
#include <tvm/solver/internal/SolverEvents.h>
#include <tvm/utils/internal/map.h>
 
namespace tvm
{
 
namespace solver
{
 
namespace abstract
{
class TVM_DLLAPI HierarchicalLeastSquareSolver
{
public:
  HierarchicalLeastSquareSolver(bool verbose = false);
  HierarchicalLeastSquareSolver(const HierarchicalLeastSquareSolver &) = delete;
  HierarchicalLeastSquareSolver & operator=(const HierarchicalLeastSquareSolver &) = delete;
  virtual ~HierarchicalLeastSquareSolver() = default;
  void startBuild(const VariableVector & x,
                  const std::vector<int> & nEq,
                  const std::vector<int> & nIneq,
                  bool useBounds,
                  const hint::internal::Substitutions * const subs = nullptr);
  void finalizeBuild();
 
  void addBound(LinearConstraintPtr bound);
 
  void addConstraint(LinearConstraintPtr cstr, SolvingRequirementsPtr req);
 
  void setMinimumNorm();
 
  bool solve();
 
  const Eigen::VectorXd & result() const;
 
  int constraintSize(const constraint::abstract::LinearConstraint & c) const;
 
  void process(const internal::SolverEvents & se);
 
  int numberOfLevels() const { return useBounds_ ? static_cast<int>(nEq_.size()) + 1 : static_cast<int>(nEq_.size()); }
 
protected:
  struct ImpactFromChanges
  {
    ImpactFromChanges(int nLvl);
    ImpactFromChanges(const std::vector<bool> & eq, std::vector<bool> & ineq, bool bounds);
 
    std::vector<bool> equalityConstraints_;
    std::vector<bool> inequalityConstraints_;
    bool bounds_ = false;
    int newLevels_ = 0;
 
    template<typename Derived>
    static bool willReallocate(const Eigen::DenseBase<Derived> & M, int rows, int cols = 1);
 
    ImpactFromChanges operator||(bool b);
    ImpactFromChanges operator||(const ImpactFromChanges & other);
    ImpactFromChanges & orAssign(const ImpactFromChanges & other);
 
    bool any() const
    {
      return std::any_of(equalityConstraints_.begin(), equalityConstraints_.end(), [](bool b) { return b; })
             || std::any_of(inequalityConstraints_.begin(), inequalityConstraints_.end(), [](bool b) { return b; })
             || bounds_;
    }
  };
 
  virtual void initializeBuild_(const std::vector<int> & nEq, const std::vector<int> & nIneq, bool useBounds) = 0;
  virtual ImpactFromChanges resize_(const std::vector<int> & nEq, const std::vector<int> & nIneq, bool useBounds) = 0;
  virtual void addBound_(LinearConstraintPtr bound, RangePtr range, bool first) = 0;
  virtual void addEqualityConstraint_(LinearConstraintPtr cstr, SolvingRequirementsPtr req) = 0;
  virtual void addIneqalityConstraint_(LinearConstraintPtr cstr, SolvingRequirementsPtr req) = 0;
  virtual void setMinimumNorm_() = 0;
  virtual void resetBounds_() = 0;
  virtual void preAssignmentProcess_() {}
  virtual void postAssignmentProcess_() {}
  virtual bool solve_() = 0;
  virtual const Eigen::VectorXd & result_() const = 0;
  virtual bool handleDoubleSidedConstraint_() const = 0;
  virtual Range nextEqualityConstraintRange_(int lvl, const constraint::abstract::LinearConstraint & cstr) const = 0;
  virtual Range nextInequalityConstraintRange_(int lvl, const constraint::abstract::LinearConstraint & cstr) const = 0;
  virtual void removeBounds_(const Range & range) = 0;
  virtual void updateEqualityTargetData(int lvl, scheme::internal::AssignmentTarget & target) = 0;
  virtual void updateInequalityTargetData(int lvl, scheme::internal::AssignmentTarget & target) = 0;
  virtual void updateBoundTargetData(scheme::internal::AssignmentTarget & target) = 0;
 
  virtual void applyImpactLogic(ImpactFromChanges & impact);
 
  virtual void printProblemData_() const = 0;
  virtual void printDiagnostic_() const = 0;
 
  const VariableVector & variables() const { return *variables_; }
  const hint::internal::Substitutions * substitutions() const { return subs_; }
 
  template<typename... Args>
  void addAssignement(Args &&... args);
 
private:
  void updateWeights(const internal::SolverEvents & se);
  bool updateVariables(const internal::SolverEvents & se);
  ImpactFromChanges processRemovedConstraints(const internal::SolverEvents & se);
  ImpactFromChanges previewAddedConstraints(const internal::SolverEvents & se);
  void processAddedConstraints(const internal::SolverEvents & se);
 
public:
  struct MarkedAssignment
  {
    template<typename... Args>
    MarkedAssignment(Args &&... args) : assignment(std::forward<Args>(args)...), markedForRemoval(false)
    {}
    scheme::internal::Assignment assignment;
    bool markedForRemoval;
  };
  template<typename K, typename T>
  using map = utils::internal::map<K, T>;
  using AssignmentVector = std::vector<std::unique_ptr<MarkedAssignment>>;
  using AssignmentPtrVector = std::vector<MarkedAssignment *>;
  using MapToAssignment = map<constraint::abstract::LinearConstraint *, AssignmentPtrVector>;
 
protected:
  bool useBounds_ = false;
  std::vector<int> nEq_;
  std::vector<int> nIneq_;
  std::vector<int> eqSize_;
  std::vector<int> ineqSize_;
 
private:
  bool buildInProgress_;
  bool verbose_;
  VariableVector const * variables_;
  AssignmentVector assignments_;
  std::vector<MapToAssignment> equalityConstraintToAssignments_;
  std::vector<MapToAssignment> inequalityConstraintToAssignments_;
  MapToAssignment boundToAssignments_;
  const hint::internal::Substitutions * subs_;
};
 
class TVM_DLLAPI HLSSolverFactory
{
protected:
  HLSSolverFactory(const std::string & solverName) : solverName_(solverName) {}
 
public:
  virtual ~HLSSolverFactory() = default;
 
  virtual std::unique_ptr<HLSSolverFactory> clone() const = 0;
  virtual std::unique_ptr<HierarchicalLeastSquareSolver> createSolver() const = 0;
 
private:
  std::string solverName_;
};
 
template<typename... Args>
inline void HierarchicalLeastSquareSolver::addAssignement(Args &&... args)
{ assignments_.emplace_back(new MarkedAssignment(std::forward<Args>(args)...)); }
 
template<typename Derived>
inline bool HierarchicalLeastSquareSolver::ImpactFromChanges::willReallocate(const Eigen::DenseBase<Derived> & M,
                                                                             int rows,
                                                                             int cols)
{ return M.rows() * M.cols() != rows * cols; }
 
} // namespace abstract
 
} // namespace solver
 
} // namespace tvm