return true;
}
- int n_resources = A_.rows();
+ auto n_resources = A_.rows();
size_t idx = 0;
while (idx < alloc_.size()) {
alloc_[idx] = (++alloc_[idx]) % n_resources;
std::vector<int> BmfSolver::alloc_map_to_vector(const allocation_map_t& alloc) const
{
std::vector<int> alloc_by_player(A_.cols(), -1);
- for (auto it : alloc) {
+ for (const auto& it : alloc) {
for (auto p : it.second) {
alloc_by_player[p] = it.first;
}
Eigen::VectorXd BmfSolver::equilibrium(const allocation_map_t& alloc) const
{
- int n_players = A_.cols();
+ auto n_players = A_.cols();
Eigen::MatrixXd A_p = Eigen::MatrixXd::Zero(n_players, n_players); // square matrix with number of players
Eigen::VectorXd C_p = Eigen::VectorXd::Zero(n_players);
for (const auto& e : alloc) {
// add one row for the resource with A[r,]
int cur_resource = e.first;
+ /* bounded players, nothing to do */
if (cur_resource == NO_RESOURCE)
continue;
-
- if (C_shared_[cur_resource]) {
- /* shared resource: fairly share it between players */
- A_p.row(row) = A_.row(cur_resource);
- C_p[row] = get_resource_capacity(cur_resource, bounded_players);
- row++;
- if (e.second.size() > 1) {
- // if 2 players have chosen the same resource
- // they must have a fair sharing of this resource, adjust A_p and C_p accordingly
- auto it = e.second.begin();
- int i = *it; // first player
- /* for each other player sharing this resource */
- for (++it; it != e.second.end(); ++it) {
- /* player i and k on this resource j: so maxA_ji*rho_i - maxA_jk*rho_k = 0 */
- int k = *it;
- C_p[row] = 0;
- A_p(row, i) = maxA_(cur_resource, i);
- A_p(row, k) = -maxA_(cur_resource, k);
- row++;
- }
- }
- } else {
- /* not shared resource, each player can receive the full capacity of the resource */
+ /* not shared resource, each player can receive the full capacity of the resource */
+ if (not C_shared_[cur_resource]) {
for (int i : e.second) {
C_p[row] = get_resource_capacity(cur_resource, bounded_players);
A_p(row, i) = A_(cur_resource, i);
row++;
}
+ continue;
+ }
+
+ /* shared resource: fairly share it between players */
+ A_p.row(row) = A_.row(cur_resource);
+ C_p[row] = get_resource_capacity(cur_resource, bounded_players);
+ row++;
+ if (e.second.size() > 1) {
+ // if 2 players have chosen the same resource
+ // they must have a fair sharing of this resource, adjust A_p and C_p accordingly
+ auto it = e.second.begin();
+ int i = *it; // first player
+ /* for each other player sharing this resource */
+ for (++it; it != e.second.end(); ++it) {
+ /* player i and k on this resource j: so maxA_ji*rho_i - maxA_jk*rho_k = 0 */
+ int k = *it;
+ C_p[row] = 0;
+ A_p(row, i) = maxA_(cur_resource, i);
+ A_p(row, k) = -maxA_(cur_resource, k);
+ row++;
+ }
}
}
/* clear players which are externally bounded */
double consumption_r = A_.row(r) * rho;
double_update(&consumption_r, C_[r], sg_maxmin_precision);
if (consumption_r > 0.0) {
- int n_players = (A_.row(r).array() > 0).count();
+ auto n_players = (A_.row(r).array() > 0).count();
fair_sharing[r] = C_[r] / n_players;
} else {
fair_sharing[r] = get_resource_capacity(r, bounded_players);
Eigen::MatrixXi player_max_share =
((usage.array().colwise() - max_share.array()).abs() <= sg_maxmin_precision).cast<int>();
// but only saturated resources must be considered
- Eigen::VectorXi saturated = ((remaining.array().abs() <= sg_maxmin_precision)).cast<int>();
+ Eigen::VectorXi saturated = (remaining.array().abs() <= sg_maxmin_precision).cast<int>();
XBT_DEBUG("Saturated_j resources:\n%s", debug_eigen(saturated).c_str());
player_max_share.array().colwise() *= saturated.array();
XBT_DEBUG("Player_ji usage of saturated resources:\n%s", debug_eigen(player_max_share).c_str());
// for all columns(players) it has to be the max at least in 1
- bmf = bmf && (player_max_share.colwise().sum().all() >= 1);
+ bmf = bmf && (player_max_share.colwise().sum().array() >= 1).all();
return bmf;
}
auto fair_sharing = C_;
/* BMF allocation for each player (current and last one) stop when are equal */
- allocation_map_t last_alloc, cur_alloc;
+ allocation_map_t last_alloc;
+ allocation_map_t cur_alloc;
Eigen::VectorXd rho;
while (it < max_iteration_ && not get_alloc(fair_sharing, last_alloc, cur_alloc, it == 0)) {
/*****************************************************************************/
-void BmfSystem::get_flows_data(int number_cnsts, Eigen::MatrixXd& A, Eigen::MatrixXd& maxA, Eigen::VectorXd& phi)
+void BmfSystem::get_flows_data(Eigen::Index number_cnsts, Eigen::MatrixXd& A, Eigen::MatrixXd& maxA,
+ Eigen::VectorXd& phi)
{
A.resize(number_cnsts, variable_set.size());
A.setZero();
bool active = false;
bool linked = false; // variable is linked to some constraint (specially for selective_update)
for (const Element& elem : var.cnsts_) {
- boost::intrusive::list_member_hook<>& cnst_hook = selective_update_active
- ? elem.constraint->modified_constraint_set_hook_
- : elem.constraint->active_constraint_set_hook_;
+ const boost::intrusive::list_member_hook<>& cnst_hook = selective_update_active
+ ? elem.constraint->modified_constraint_set_hook_
+ : elem.constraint->active_constraint_set_hook_;
if (not cnst_hook.is_linked())
continue;
/* active and linked variable, lets check its consumption */
/* initialize players' weight and constraint matrices */
idx2Var_.clear();
cnst2idx_.clear();
- Eigen::MatrixXd A, maxA;
- Eigen::VectorXd C, bounds;
+ Eigen::MatrixXd A;
+ Eigen::MatrixXd maxA;
+ Eigen::VectorXd C;
+ Eigen::VectorXd bounds;
std::vector<bool> shared;
get_constraint_data(cnst_list, C, shared);
get_flows_data(C.size(), A, maxA, bounds);
* o rho1 + rho2 = C (because all weights are 1)
*/
- lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
+ lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
lmm::Variable* rho_2 = Sys.variable_new(nullptr, 2);
Sys.expand(sys_cnst, rho_2, 1);
Sys.solve();
- REQUIRE(double_equals(rho_1->get_value(), 2, sg_maxmin_precision));
- REQUIRE(double_equals(rho_2->get_value(), 1, sg_maxmin_precision));
+ REQUIRE(double_equals(rho_1->get_value(), 2.0 / 3.0, sg_maxmin_precision));
+ REQUIRE(double_equals(rho_2->get_value(), 1.0 / 3.0, sg_maxmin_precision));
}
SECTION("Disable variable doesn't count")
{
/*
- * Two flows sharing a single resource, but only disabled
+ * Two flows sharing a single resource, but one is disabled
*
* In details:
* o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
* o a1*rho1 = C
*/
- lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
+ lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
lmm::Variable* rho_2 = Sys.variable_new(nullptr, 0);
Sys.expand(sys_cnst, rho_2, 10);
Sys.solve();
- REQUIRE(double_equals(rho_1->get_value(), 3.0, sg_maxmin_precision));
+ REQUIRE(double_equals(rho_1->get_value(), 1.0, sg_maxmin_precision));
REQUIRE(double_equals(rho_2->get_value(), 0.0, sg_maxmin_precision));
}
sys_cnst.push_back(Sys.constraint_new(nullptr, c));
}
std::vector<lmm::Variable*> vars;
- for (size_t i = 0; i < A[0].size(); i++) {
- vars.push_back(Sys.variable_new(nullptr, 1, -1, A.size()));
- }
+ std::for_each(A[0].begin(), A[0].end(),
+ [&vars, &Sys, &A](const auto&) { vars.push_back(Sys.variable_new(nullptr, 1, -1, A.size())); });
for (size_t j = 0; j < A.size(); j++) {
for (size_t i = 0; i < A[j].size(); i++) {
Sys.expand_add(sys_cnst[j], vars[i], A[j][i]);
}
Sys.solve();
- for (auto* rho : vars) {
+ for (const auto* rho : vars) {
REQUIRE(double_positive(rho->get_value(), sg_maxmin_precision));
}
}
{
lmm::BmfSystem Sys(false);
- SECTION("Random consumptions - independent flows")
+ auto create_cnsts = [&Sys](int C, int capacity) -> auto
{
- int C = 5;
- int N = 2;
- auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0))));
std::vector<lmm::Constraint*> sys_cnst;
for (int i = 0; i < C; i++) {
- sys_cnst.push_back(Sys.constraint_new(nullptr, 1));
+ sys_cnst.push_back(Sys.constraint_new(nullptr, capacity));
}
+ return sys_cnst;
+ };
+
+ auto test_shared = [&Sys, &create_cnsts](int C, int N, int capacity, const auto& data) {
+ auto sys_cnst = create_cnsts(C, capacity);
for (int j = 0; j < N; j++) {
+ lmm::Variable* rho = Sys.variable_new(nullptr, 1, -1, C);
for (int i = 0; i < C; i++) {
- lmm::Variable* rho = Sys.variable_new(nullptr, 1);
Sys.expand_add(sys_cnst[i], rho, data[i * j + j]);
}
}
Sys.solve();
- }
+ };
- SECTION("Random consumptions - flows sharing resources")
+ SECTION("Random consumptions - independent flows")
{
- int C = 5;
- int N = 10;
- auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0))));
-
- std::vector<lmm::Constraint*> sys_cnst;
- for (int i = 0; i < C; i++) {
- sys_cnst.push_back(Sys.constraint_new(nullptr, 1));
- }
+ int C = 5;
+ int N = 2;
+ auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0))));
+ auto sys_cnst = create_cnsts(C, 1);
for (int j = 0; j < N; j++) {
- lmm::Variable* rho = Sys.variable_new(nullptr, 1, -1, C);
for (int i = 0; i < C; i++) {
+ lmm::Variable* rho = Sys.variable_new(nullptr, 1);
Sys.expand_add(sys_cnst[i], rho, data[i * j + j]);
}
}
-
Sys.solve();
}
+ SECTION("Random consumptions - flows sharing resources")
+ {
+ int C = 5;
+ int N = 10;
+ auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0))));
+ test_shared(C, N, 1, data);
+ }
+
SECTION("Random integer consumptions - flows sharing resources")
{
int C = 5;
int N = 10;
auto data = GENERATE_COPY(chunk(C * N, take(100000, random(1, 10))));
-
- std::vector<lmm::Constraint*> sys_cnst;
- for (int i = 0; i < C; i++) {
- sys_cnst.push_back(Sys.constraint_new(nullptr, 10));
- }
- for (int j = 0; j < N; j++) {
- lmm::Variable* rho = Sys.variable_new(nullptr, 1, -1, C);
- for (int i = 0; i < C; i++) {
- Sys.expand_add(sys_cnst[i], rho, data[i * j + j]);
- }
- }
- Sys.solve();
+ test_shared(C, N, 10, data);
}
SECTION("Random consumptions - high number of constraints")
int C = 500;
int N = 10;
auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0))));
-
- std::vector<lmm::Constraint*> sys_cnst;
- for (int i = 0; i < C; i++) {
- sys_cnst.push_back(Sys.constraint_new(nullptr, 1));
- }
- for (int j = 0; j < N; j++) {
- lmm::Variable* rho = Sys.variable_new(nullptr, 1, -1, C);
- for (int i = 0; i < C; i++) {
- Sys.expand_add(sys_cnst[i], rho, data[i * j + j]);
- }
- }
- Sys.solve();
+ test_shared(C, N, 1, data);
}
SECTION("Random integer consumptions - high number of constraints")
int C = 500;
int N = 10;
auto data = GENERATE_COPY(chunk(C * N, take(100000, random(1, 10))));
-
- std::vector<lmm::Constraint*> sys_cnst;
- for (int i = 0; i < C; i++) {
- sys_cnst.push_back(Sys.constraint_new(nullptr, 10));
- }
- for (int j = 0; j < N; j++) {
- lmm::Variable* rho = Sys.variable_new(nullptr, 1, -1, C);
- for (int i = 0; i < C; i++) {
- Sys.expand_add(sys_cnst[i], rho, data[i * j + j]);
- }
- }
- Sys.solve();
+ test_shared(C, N, 10, data);
}
Sys.variable_free_all();
