teshsuite/surf/lmm_usage/lmm_solve.cpp

   1 /* Copyright (c) 2019. 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 #include "src/include/catch.hpp"
   7 #include "src/kernel/lmm/maxmin.hpp"
   8 #include "src/surf/surf_interface.hpp"
   9 #include "xbt/log.h"
  10
  11 namespace lmm = simgrid::kernel::lmm;
  12
  13 TEST_CASE("kernel::lmm Single constraint shared systems", "[kernel-lmm-shared-single-sys]")
  14 {
  15   lmm::System* Sys = lmm::make_new_maxmin_system(false);
  16
  17   SECTION("Variable weight")
  18   {
  19     /*
  20      * System under consideration:
  21      * 1\times\rho_1^{1} + 1\times\rho_2^{2} + 1\times\rho_3^{3} \le 10
  22      * Expectations:
  23      *  - \rho_1 should have twice the resources of \rho_2
  24      *  - \rho_1 should have thrice the resources of \rho_3
  25      */
  26
  27     lmm::Constraint* sys_cnst = Sys->constraint_new(nullptr, 10);
  28     lmm::Variable* sys_var_1  = Sys->variable_new(nullptr, 1, 0.0, 1);
  29     lmm::Variable* sys_var_2  = Sys->variable_new(nullptr, 2, 0.0, 1);
  30     lmm::Variable* sys_var_3  = Sys->variable_new(nullptr, 3, 0.0, 1);
  31
  32     Sys->expand(sys_cnst, sys_var_1, 1);
  33     Sys->expand(sys_cnst, sys_var_2, 1);
  34     Sys->expand(sys_cnst, sys_var_3, 1);
  35     Sys->solve();
  36
  37     REQUIRE(double_equals(sys_var_1->get_value(), 5.45455, sg_maxmin_precision));
  38     REQUIRE(double_equals(sys_var_2->get_value(), 2.72727, sg_maxmin_precision));
  39     REQUIRE(double_equals(sys_var_3->get_value(), 1.81818, sg_maxmin_precision));
  40   }
  41
  42   SECTION("Consumption weight")
  43   {
  44     /*
  45      * System under consideration:
  46      * 1\times\rho_1^{1} + 2\times\rho_2^{1} + 3\times\rho_3^{1} \le 10
  47      * Expectations:
  48      *  - All variable should have the same amount of resources
  49      *  - This amount should be equal to \frac{10}{\sum{\text{consumption weight}}}
  50      */
  51
  52     lmm::Constraint* sys_cnst = Sys->constraint_new(nullptr, 10);
  53     lmm::Variable* sys_var_1  = Sys->variable_new(nullptr, 1, 0.0, 1);
  54     lmm::Variable* sys_var_2  = Sys->variable_new(nullptr, 1, 0.0, 1);
  55     lmm::Variable* sys_var_3  = Sys->variable_new(nullptr, 1, 0.0, 1);
  56
  57     Sys->expand(sys_cnst, sys_var_1, 1);
  58     Sys->expand(sys_cnst, sys_var_2, 2);
  59     Sys->expand(sys_cnst, sys_var_3, 3);
  60     Sys->solve();
  61
  62     REQUIRE(double_equals(sys_var_1->get_value(), 1.666667, sg_maxmin_precision));
  63     REQUIRE(double_equals(sys_var_2->get_value(), 1.666667, sg_maxmin_precision));
  64     REQUIRE(double_equals(sys_var_3->get_value(), 1.666667, sg_maxmin_precision));
  65   }
  66
  67   SECTION("Consumption weight + variable weight")
  68   {
  69     /*
  70      * Strange system under consideration:
  71      * 56\times\rho_1^{74} + 21\times\rho_2^{6} + 2\times\rho_3^{2} \le 123
  72      * Expectations:
  73      *  - This test combine variable weight and consumption weight
  74      *  - Thus, we expect that \rho_j=\frac{\frac{10}{\sum{\frac{a_i}{w_i}}}}{w_j}
  75      */
  76
  77     lmm::Constraint* sys_cnst = Sys->constraint_new(nullptr, 123);
  78     lmm::Variable* sys_var_1  = Sys->variable_new(nullptr, 56, 0.0, 1);
  79     lmm::Variable* sys_var_2  = Sys->variable_new(nullptr, 21, 0.0, 1);
  80     lmm::Variable* sys_var_3  = Sys->variable_new(nullptr, 3, 0.0, 1);
  81
  82     Sys->expand(sys_cnst, sys_var_1, 74);
  83     Sys->expand(sys_cnst, sys_var_2, 6);
  84     Sys->expand(sys_cnst, sys_var_3, 2);
  85     Sys->solve();
  86
  87     REQUIRE(double_equals(sys_var_1->get_value(), 0.9659686, sg_maxmin_precision));
  88     REQUIRE(double_equals(sys_var_2->get_value(), 2.575916, sg_maxmin_precision));
  89     REQUIRE(double_equals(sys_var_3->get_value(), 18.03141, sg_maxmin_precision));
  90   }
  91
  92   Sys->variable_free_all();
  93   delete Sys;
  94 }
  95
  96 TEST_CASE("kernel::lmm Multiple constraint shared systems", "[kernel-lmm-shared-multiple-sys]")
  97 {
  98   lmm::System* Sys = lmm::make_new_maxmin_system(false);
  99
 100   SECTION("3 Constraints system")
 101   {
 102
 103     /*
 104      * System under consideration:
 105      * 4\times\rho_1^{5.1} + 2.6\times\rho_2^{7} + 1.2\times\rho_3^{8.5} \le 14.6 \\
 106      * 5\times\rho_4^{6.2} + 2\times\rho_2^{7}   + 4.1\times\rho_3^{8.5} \le 40.7 \\
 107      * 6\times\rho_5^1                                                   \le 7
 108      * Expectation:
 109      *  - Order of inequation solving: 3, 1 and 2
 110      *  - Variable values are fixed using: \rho_j=\frac{\frac{C_r}{\sum{\frac{a_{r,i}}{w_i}}}}{w_j}
 111      */
 112
 113     lmm::Constraint* sys_cnst_1 = Sys->constraint_new(nullptr, 14.6);
 114     lmm::Constraint* sys_cnst_2 = Sys->constraint_new(nullptr, 10.7);
 115     lmm::Constraint* sys_cnst_3 = Sys->constraint_new(nullptr, 7);
 116
 117     lmm::Variable* sys_var_1 = Sys->variable_new(nullptr, 5.1, 0.0, 1);
 118     lmm::Variable* sys_var_2 = Sys->variable_new(nullptr, 7, 0.0, 2);
 119     lmm::Variable* sys_var_3 = Sys->variable_new(nullptr, 8.5, 0.0, 2);
 120     lmm::Variable* sys_var_4 = Sys->variable_new(nullptr, 6.2, 0.0, 1);
 121     lmm::Variable* sys_var_5 = Sys->variable_new(nullptr, 1, 0.0, 1);
 122
 123     // Constraint 1
 124     Sys->expand(sys_cnst_1, sys_var_1, 4);
 125     Sys->expand(sys_cnst_1, sys_var_2, 2.6);
 126     Sys->expand(sys_cnst_1, sys_var_3, 1.2);
 127     // Constraint 2
 128     Sys->expand(sys_cnst_2, sys_var_4, 5);
 129     Sys->expand(sys_cnst_2, sys_var_2, 2);
 130     Sys->expand(sys_cnst_2, sys_var_3, 4.1);
 131     // Constraint 3
 132     Sys->expand(sys_cnst_3, sys_var_5, 6);
 133     Sys->solve();
 134
 135     REQUIRE(double_equals(sys_var_1->get_value(), 2.779119, sg_maxmin_precision));
 136     REQUIRE(double_equals(sys_var_2->get_value(), 0.9708181, sg_maxmin_precision));
 137     REQUIRE(double_equals(sys_var_3->get_value(), 0.7994973, sg_maxmin_precision));
 138     REQUIRE(double_equals(sys_var_4->get_value(), 1.096085, sg_maxmin_precision));
 139     REQUIRE(double_equals(sys_var_5->get_value(), 1.166667, sg_maxmin_precision));
 140   }
 141
 142   Sys->variable_free_all();
 143   delete Sys;
 144 }
 145
 146 TEST_CASE("kernel::lmm Single constraint unshared systems", "[kernel-lmm-unshared-single-sys]")
 147 {
 148   lmm::System* Sys = lmm::make_new_maxmin_system(false);
 149
 150   SECTION("Variable weight")
 151   {
 152     /*
 153      * System under consideration:
 154      * 1\times\rho_1^{1} + 1\times\rho_2^{2} + 1\times\rho_3^{3} \le 10
 155      * Expectation:
 156      *  - Variables are fixed using: \rho_j=\frac{\frac{10}{\frac{1}{1}}}{w_j}
 157      */
 158
 159     lmm::Constraint* sys_cnst = Sys->constraint_new(nullptr, 10);
 160     sys_cnst->unshare(); // FATPIPE
 161     lmm::Variable* sys_var_1 = Sys->variable_new(nullptr, 1, 0.0, 1);
 162     lmm::Variable* sys_var_2 = Sys->variable_new(nullptr, 2, 0.0, 1);
 163     lmm::Variable* sys_var_3 = Sys->variable_new(nullptr, 3, 0.0, 1);
 164
 165     Sys->expand(sys_cnst, sys_var_1, 1);
 166     Sys->expand(sys_cnst, sys_var_2, 1);
 167     Sys->expand(sys_cnst, sys_var_3, 1);
 168     Sys->solve();
 169
 170     REQUIRE(double_equals(sys_var_1->get_value(), 10, sg_maxmin_precision));
 171     REQUIRE(double_equals(sys_var_2->get_value(), 5, sg_maxmin_precision));
 172     REQUIRE(double_equals(sys_var_3->get_value(), 3.333333, sg_maxmin_precision));
 173   }
 174
 175   SECTION("Consumption weight")
 176   {
 177     /*
 178      * System under consideration:
 179      * 1\times\rho_1^{1} + 2\times\rho_2^{1} + 3\times\rho_3^{1} \le 10
 180      * Expectations:
 181      *  - Variables are fixed using: \rho_j=\frac{\frac{10}{\frac{3}{1}}}{w_j}
 182      */
 183
 184     lmm::Constraint* sys_cnst = Sys->constraint_new(nullptr, 10);
 185     sys_cnst->unshare();
 186     lmm::Variable* sys_var_1 = Sys->variable_new(nullptr, 1, 0.0, 1);
 187     lmm::Variable* sys_var_2 = Sys->variable_new(nullptr, 1, 0.0, 1);
 188     lmm::Variable* sys_var_3 = Sys->variable_new(nullptr, 1, 0.0, 1);
 189
 190     Sys->expand(sys_cnst, sys_var_1, 1);
 191     Sys->expand(sys_cnst, sys_var_2, 2);
 192     Sys->expand(sys_cnst, sys_var_3, 3);
 193     Sys->solve();
 194
 195     REQUIRE(double_equals(sys_var_1->get_value(), 3.333333, sg_maxmin_precision));
 196     REQUIRE(double_equals(sys_var_2->get_value(), 3.333333, sg_maxmin_precision));
 197     REQUIRE(double_equals(sys_var_3->get_value(), 3.333333, sg_maxmin_precision));
 198   }
 199
 200   SECTION("Consumption weight + variable weight")
 201   {
 202     /*
 203      * Strange system under consideration:
 204      * 56\times\rho_1^{74} + 21\times\rho_2^{6} + 2\times\rho_3^{2} \le 123
 205      * Expectation:
 206      *  - Variables are fixed using: \rho_j=\frac{\frac{123}{\frac{74}{56}}}{w_j}
 207      */
 208
 209     lmm::Constraint* sys_cnst = Sys->constraint_new(nullptr, 123);
 210     sys_cnst->unshare();
 211     lmm::Variable* sys_var_1 = Sys->variable_new(nullptr, 56, 0.0, 1);
 212     lmm::Variable* sys_var_2 = Sys->variable_new(nullptr, 21, 0.0, 1);
 213     lmm::Variable* sys_var_3 = Sys->variable_new(nullptr, 3, 0.0, 1);
 214
 215     Sys->expand(sys_cnst, sys_var_1, 74);
 216     Sys->expand(sys_cnst, sys_var_2, 6);
 217     Sys->expand(sys_cnst, sys_var_3, 2);
 218     Sys->solve();
 219
 220     REQUIRE(double_equals(sys_var_1->get_value(), 1.662162, sg_maxmin_precision));
 221     REQUIRE(double_equals(sys_var_2->get_value(), 4.432432, sg_maxmin_precision));
 222     REQUIRE(double_equals(sys_var_3->get_value(), 31.02703, sg_maxmin_precision));
 223   }
 224
 225   Sys->variable_free_all();
 226   delete Sys;
 227 }
 228
 229 TEST_CASE("kernel::lmm Multiple constraint unshared systems", "[kernel-lmm-unshared-multiple-sys]")
 230 {
 231   lmm::System* Sys = lmm::make_new_maxmin_system(false);
 232
 233   SECTION("3 Constraints system")
 234   {
 235
 236     /*
 237      * System under consideration:
 238      * 4\times\rho_1^{5.1} + 2.6\times\rho_2^{7} + 1.2\times\rho_3^{8.5} \le 14.6 \\
 239      * 5\times\rho_4^{6.2} + 2\times\rho_2^{7}   + 4.1\times\rho_3^{8.5} \le 40.7 \\
 240      * 6\times\rho_5^1                                                   \le 7
 241      * Expectations:
 242      *  - Variable are fixed using: \rho_j=\frac{\frac{C_r}{max\left(\frac{a_{r},i}{w_i}\right)}}{w_j}
 243      *  - The order of inequation solving is expected to be: 3, 2 and 1
 244      */
 245
 246     lmm::Constraint* sys_cnst_1 = Sys->constraint_new(nullptr, 14.6);
 247     sys_cnst_1->unshare();
 248     lmm::Constraint* sys_cnst_2 = Sys->constraint_new(nullptr, 10.7);
 249     sys_cnst_2->unshare();
 250     lmm::Constraint* sys_cnst_3 = Sys->constraint_new(nullptr, 7);
 251     sys_cnst_3->unshare();
 252
 253     lmm::Variable* sys_var_1 = Sys->variable_new(nullptr, 5.1, 0.0, 1);
 254     lmm::Variable* sys_var_2 = Sys->variable_new(nullptr, 7, 0.0, 2);
 255     lmm::Variable* sys_var_3 = Sys->variable_new(nullptr, 8.5, 0.0, 2);
 256     lmm::Variable* sys_var_4 = Sys->variable_new(nullptr, 6.2, 0.0, 1);
 257     lmm::Variable* sys_var_5 = Sys->variable_new(nullptr, 1, 0.0, 1);
 258
 259     // Constraint 1
 260     Sys->expand(sys_cnst_1, sys_var_1, 4);
 261     Sys->expand(sys_cnst_1, sys_var_2, 2.6);
 262     Sys->expand(sys_cnst_1, sys_var_3, 1.2);
 263     // Constraint 2
 264     Sys->expand(sys_cnst_2, sys_var_4, 5);
 265     Sys->expand(sys_cnst_2, sys_var_2, 2);
 266     Sys->expand(sys_cnst_2, sys_var_3, 4.1);
 267     // Constraint 3
 268     Sys->expand(sys_cnst_3, sys_var_5, 6);
 269     Sys->solve();
 270
 271     REQUIRE(double_equals(sys_var_1->get_value(), 3.65, sg_maxmin_precision));
 272     REQUIRE(double_equals(sys_var_2->get_value(), 1.895429, sg_maxmin_precision));
 273     REQUIRE(double_equals(sys_var_3->get_value(), 1.560941, sg_maxmin_precision));
 274     REQUIRE(double_equals(sys_var_4->get_value(), 2.14, sg_maxmin_precision));
 275     REQUIRE(double_equals(sys_var_5->get_value(), 1.166667, sg_maxmin_precision));
 276   }
 277
 278   Sys->variable_free_all();
 279   delete Sys;
 280 }