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, bool initial) const;
  26   double get_resource_capacity(int resource, const std::vector<int>& bounded_players) const;
  27   Eigen::VectorXd equilibrium(const std::unordered_map<int, std::vector<int>>& alloc) const;
  28
  29   void set_fair_sharing(const std::unordered_map<int, std::vector<int>>& alloc, const Eigen::VectorXd& rho,
  30                         Eigen::VectorXd& fair_sharing) const;
  31
  32   template <typename T> std::string debug_eigen(const T& obj) const;
  33   template <typename T> std::string debug_vector(const std::vector<T>& vector) const;
  34   std::string debug_alloc(const std::unordered_map<int, std::vector<int>>& alloc) const;
  35   /**
  36    * @brief Check if allocation is BMF
  37    *
  38    * To be a bmf allocation it must:
  39    * - respect the capacity of all resources
  40    * - saturate at least 1 resource
  41    * - every player receives maximum share in at least 1 saturated resource
  42    * @param rho Allocation
  43    * @return true if BMF false otherwise
  44    */
  45   bool is_bmf(const Eigen::VectorXd& rho) const;
  46
  47   int max_iteration_ = 10;
  48   Eigen::MatrixXd A_;
  49   Eigen::MatrixXd maxA_;
  50   std::unordered_map<int, Variable*> idx2Var_;
  51   Eigen::VectorXd C_;
  52   std::unordered_map<const Constraint*, int> cnst2idx_;
  53   static constexpr int NO_RESOURCE = -1; //!< flag to indicate player has selected no resource
  54 };
  55
  56 } // namespace lmm
  57 } // namespace kernel
  58 } // namespace simgrid
  59
  60 #endif