src/kernel/lmm/bmf.hpp

   1 /* Copyright (c) 2004-2022. The SimGrid Team. All rights reserved.          */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 #ifndef SURF_BMF_HPP
   7 #define SURF_BMF_HPP
   8
   9 #include "src/kernel/lmm/maxmin.hpp"
  10 #include <eigen3/Eigen/Dense>
  11
  12 namespace simgrid {
  13 namespace kernel {
  14 namespace lmm {
  15
  16 class XBT_PUBLIC BmfSystem : public System {
  17 public:
  18   using System::System;
  19   void solve() final { bottleneck_solve(); }
  20
  21 private:
  22   void bottleneck_solve();
  23   void set_matrix_A();
  24   void set_vector_C();
  25   std::unordered_map<int, std::vector<int>> get_alloc(const Eigen::VectorXd& fair_sharing) const;
  26   Eigen::VectorXd equilibrium(const std::unordered_map<int, std::vector<int>>& alloc) const;
  27
  28   void set_fair_sharing(const std::unordered_map<int, std::vector<int>>& alloc, const Eigen::VectorXd& rho,
  29                         Eigen::VectorXd& fair_sharing) const;
  30
  31   template <typename T> std::string debug_eigen(const T& obj) const;
  32   template <typename T> std::string debug_vector(const std::vector<T>& vector) const;
  33   std::string debug_alloc(const std::unordered_map<int, std::vector<int>>& alloc) const;
  34   /**
  35    * @brief Check if allocation is BMF
  36    *
  37    * To be a bmf allocation it must:
  38    * - respect the capacity of all resources
  39    * - saturate at least 1 resource
  40    * - every player receives maximum share in at least 1 saturated resource
  41    * @param rho Allocation
  42    * @return true if BMF false otherwise
  43    */
  44   bool is_bmf(const Eigen::VectorXd& rho) const;
  45
  46   int max_iteration_ = 10;
  47   Eigen::MatrixXd A_;
  48   Eigen::MatrixXd maxA_;
  49   std::unordered_map<int, Variable*> idx2Var_;
  50   Eigen::VectorXd C_;
  51   std::unordered_map<const Constraint*, int> cnst2idx_;
  52 };
  53
  54 } // namespace lmm
  55 } // namespace kernel
  56 } // namespace simgrid
  57
  58 #endif