LeastSquareSolver.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 LeastSquareSolver
{
public:
  LeastSquareSolver(bool verbose = false);
  LeastSquareSolver(const LeastSquareSolver &) = delete;
  LeastSquareSolver & operator=(const LeastSquareSolver &) = delete;
  virtual ~LeastSquareSolver() = default;
  void startBuild(const VariableVector & x,
                  int nObj,
                  int nEq,
                  int nIneq,
                  bool useBounds = true,
                  const hint::internal::Substitutions * const subs = nullptr);
  void finalizeBuild();
 
  void addBound(LinearConstraintPtr bound);
 
  void addConstraint(LinearConstraintPtr cstr);
 
  void addObjective(LinearConstraintPtr obj, SolvingRequirementsPtr req, double additionalWeight = 1);
 
  void setMinimumNorm();
 
  bool solve();
 
  const Eigen::VectorXd & result() const;
 
  int constraintSize(const constraint::abstract::LinearConstraint & c) const;
 
  void process(const internal::SolverEvents & se);
 
protected:
  struct ImpactFromChanges
  {
    bool equalityConstraints_ = false;
    bool inequalityConstraints_ = false;
    bool bounds_ = false;
    bool objectives_ = false;
 
    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 equalityConstraints_ || inequalityConstraints_ || bounds_ || objectives_; }
  };
 
  virtual void initializeBuild_(int nObj, int nEq, int nIneq, bool useBounds) = 0;
  virtual ImpactFromChanges resize_(int nObj, int nEq, int nIneq, bool useBounds) = 0;
  virtual void addBound_(LinearConstraintPtr bound, RangePtr range, bool first) = 0;
  virtual void addEqualityConstraint_(LinearConstraintPtr cstr) = 0;
  virtual void addIneqalityConstraint_(LinearConstraintPtr cstr) = 0;
  virtual void addObjective_(LinearConstraintPtr obj, SolvingRequirementsPtr req, double additionalWeight = 1) = 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_(const constraint::abstract::LinearConstraint & cstr) const = 0;
  virtual Range nextInequalityConstraintRange_(const constraint::abstract::LinearConstraint & cstr) const = 0;
  virtual Range nextObjectiveRange_(const constraint::abstract::LinearConstraint & cstr) const = 0;
  virtual void removeBounds_(const Range & range) = 0;
  virtual void updateEqualityTargetData(scheme::internal::AssignmentTarget & target) = 0;
  virtual void updateInequalityTargetData(scheme::internal::AssignmentTarget & target) = 0;
  virtual void updateBoundTargetData(scheme::internal::AssignmentTarget & target) = 0;
  virtual void updateObjectiveTargetData(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:
  int nEq_;
  int nIneq_;
  int nObj_;
  int objSize_;
  int eqSize_;
  int ineqSize_;
 
private:
  bool buildInProgress_;
  bool verbose_;
  VariableVector const * variables_;
  AssignmentVector assignments_;
  MapToAssignment objectiveToAssignments_;
  MapToAssignment equalityConstraintToAssignments_;
  MapToAssignment inequalityConstraintToAssignments_;
  MapToAssignment boundToAssignments_;
  const hint::internal::Substitutions * subs_;
};
 
class TVM_DLLAPI LSSolverFactory
{
protected:
  LSSolverFactory(const std::string & solverName) : solverName_(solverName) {}
 
public:
  virtual ~LSSolverFactory() = default;
 
  virtual std::unique_ptr<LSSolverFactory> clone() const = 0;
  virtual std::unique_ptr<LeastSquareSolver> createSolver() const = 0;
 
private:
  std::string solverName_;
};
 
template<typename... Args>
inline void LeastSquareSolver::addAssignement(Args &&... args)
{ assignments_.emplace_back(new MarkedAssignment(std::forward<Args>(args)...)); }
 
template<typename Derived>
inline bool LeastSquareSolver::ImpactFromChanges::willReallocate(const Eigen::DenseBase<Derived> & M,
                                                                 int rows,
                                                                 int cols)
{ return M.rows() * M.cols() != rows * cols; }
 
} // namespace abstract
 
} // namespace solver
 
} // namespace tvm