Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
LMM: rename sharing_weight into sharing_penalty for sake of clarity
[simgrid.git] / teshsuite / surf / lmm_usage / lmm_usage.cpp
1 /* A few tests for the maxmin library                                       */
2
3 /* Copyright (c) 2007-2019. The SimGrid Team. All rights reserved.          */
4
5 /* This program is free software; you can redistribute it and/or modify it
6  * under the terms of the license (GNU LGPL) which comes with this package. */
7
8 #include "simgrid/msg.h"
9 #include "src/kernel/lmm/maxmin.hpp"
10 #include "src/surf/surf_interface.hpp"
11 #include "xbt/log.h"
12 #include "xbt/module.h"
13 #include "xbt/sysdep.h"
14 #include <algorithm>
15 #include <cmath>
16
17 XBT_LOG_NEW_DEFAULT_CATEGORY(surf_test, "Messages specific for surf example");
18
19 namespace lmm = simgrid::kernel::lmm;
20
21 #define PRINT_VAR(var) XBT_DEBUG(#var " = %g", (var)->get_value())
22 #define SHOW_EXPR(expr) XBT_DEBUG(#expr " = %g",expr)
23
24 /*        ______                 */
25 /*  ==l1==  L2  ==L3==           */
26 /*        ------                 */
27
28 static lmm::System* new_system()
29 {
30   return lmm::make_new_maxmin_system(false);
31 }
32
33 double a_test_1 = 0;
34 double b_test_1 = 0;
35 static double diff_lagrange_test_1(double x)
36 {
37   return -(3 / (1 + 3 * x * x / 2) - 3 / (2 * (3 * (a_test_1 - x) * (a_test_1 - x) / 2 + 1)) +
38            3 / (2 * (3 * (b_test_1 - a_test_1 + x) * (b_test_1 - a_test_1 + x) / 2 + 1)));
39 }
40
41 static double dichotomy(double min, double max, double min_error)
42 {
43   double overall_error = 2 * min_error;
44
45   double min_func = diff_lagrange_test_1(min);
46   double max_func = diff_lagrange_test_1(max);
47
48   if (min_func > 0 && max_func > 0)
49     return min - 1.0;
50   if (min_func < 0 && max_func < 0)
51     return max + 1.0;
52   if (min_func > 0 && max_func < 0)
53     abort();
54
55   SHOW_EXPR(min_error);
56
57   while (overall_error > min_error) {
58     SHOW_EXPR(overall_error);
59     xbt_assert(min_func <= 0 || max_func <= 0);
60     xbt_assert(min_func >= 0 || max_func >= 0);
61     xbt_assert(min_func <= 0 || max_func >= 0);
62
63     SHOW_EXPR(min);
64     SHOW_EXPR(min_func);
65     SHOW_EXPR(max);
66     SHOW_EXPR(max_func);
67
68     double middle = (max + min) / 2.0;
69     if (fabs(min - middle) < 1e-12 || fabs(max - middle) < 1e-12) {
70       break;
71     }
72     double middle_func = diff_lagrange_test_1(middle);
73     SHOW_EXPR(middle);
74     SHOW_EXPR(middle_func);
75
76     if (middle_func < 0) {
77       min = middle;
78       min_func = middle_func;
79       overall_error = max_func - middle_func;
80     } else if (middle_func > 0) {
81       max = middle;
82       max_func = middle_func;
83       overall_error = middle_func - min_func;
84     } else {
85       overall_error = 0;
86     }
87   }
88   return ((min + max) / 2.0);
89 }
90
91 static void test1()
92 {
93   double a = 1.0;
94   double b = 10.0;
95
96   lmm::System* Sys    = new_system();
97   lmm::Constraint* L1 = Sys->constraint_new(nullptr, a);
98   lmm::Constraint* L2 = Sys->constraint_new(nullptr, b);
99   lmm::Constraint* L3 = Sys->constraint_new(nullptr, a);
100
101   lmm::Variable* R_1_2_3 = Sys->variable_new(nullptr, 1.0, -1.0, 3);
102   lmm::Variable* R_1     = Sys->variable_new(nullptr, 1.0, -1.0, 1);
103   lmm::Variable* R_2     = Sys->variable_new(nullptr, 1.0, -1.0, 1);
104   lmm::Variable* R_3     = Sys->variable_new(nullptr, 1.0, -1.0, 1);
105
106   Sys->update_variable_penalty(R_1_2_3, 1.0);
107   Sys->update_variable_penalty(R_1, 1.0);
108   Sys->update_variable_penalty(R_2, 1.0);
109   Sys->update_variable_penalty(R_3, 1.0);
110
111   Sys->expand(L1, R_1_2_3, 1.0);
112   Sys->expand(L2, R_1_2_3, 1.0);
113   Sys->expand(L3, R_1_2_3, 1.0);
114
115   Sys->expand(L1, R_1, 1.0);
116   Sys->expand(L2, R_2, 1.0);
117   Sys->expand(L3, R_3, 1.0);
118
119   Sys->solve();
120
121   PRINT_VAR(R_1_2_3);
122   PRINT_VAR(R_1);
123   PRINT_VAR(R_2);
124   PRINT_VAR(R_3);
125
126   Sys->variable_free(R_1_2_3);
127   Sys->variable_free(R_1);
128   Sys->variable_free(R_2);
129   Sys->variable_free(R_3);
130   delete Sys;
131 }
132
133 static void test2()
134 {
135   lmm::System* Sys = new_system();
136
137   lmm::Constraint* CPU1 = Sys->constraint_new(nullptr, 200.0);
138   lmm::Constraint* CPU2 = Sys->constraint_new(nullptr, 100.0);
139
140   lmm::Variable* T1 = Sys->variable_new(nullptr, 1.0, -1.0, 1);
141   lmm::Variable* T2 = Sys->variable_new(nullptr, 1.0, -1.0, 1);
142
143   Sys->update_variable_penalty(T1, 1.0);
144   Sys->update_variable_penalty(T2, 1.0);
145
146   Sys->expand(CPU1, T1, 1.0);
147   Sys->expand(CPU2, T2, 1.0);
148
149   Sys->solve();
150
151   PRINT_VAR(T1);
152   PRINT_VAR(T2);
153
154   Sys->variable_free(T1);
155   Sys->variable_free(T2);
156   delete Sys;
157 }
158
159 static void test3()
160 {
161   int flows = 11;
162   int links = 10;
163
164   double** A = new double*[links + 5];
165   /* array to add the constraints of fictitious variables */
166   double B[15] = { 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1 };
167
168   for (int i = 0; i < links + 5; i++) {
169     A[i] = new double[flows + 5];
170     for (int j = 0; j < flows + 5; j++) {
171       A[i][j] = 0.0;
172
173       if (i >= links || j >= flows) {
174         A[i][j] = 0.0;
175       }
176     }
177   }
178
179   /*matrix that store the constraints/topology */
180   A[0][1] = A[0][7] =                                1.0;
181   A[1][1] = A[1][7] = A[1][8] =                      1.0;
182   A[2][1] = A[2][8] =                                1.0;
183   A[3][8] =                                          1.0;
184   A[4][0] = A[4][3] = A[4][9] =                      1.0;
185   A[5][0] = A[5][3] = A[5][4] = A[5][9] =            1.0;
186   A[6][0] = A[6][4] = A[6][9] = A[6][10] =           1.0;
187   A[7][2] = A[7][4] = A[7][6] = A[7][9] = A[7][10] = 1.0;
188   A[8][2] = A[8][10] =                               1.0;
189   A[9][5] = A[9][6] = A[9][9] =                      1.0;
190   A[10][11] =                                        1.0;
191   A[11][12] =                                        1.0;
192   A[12][13] =                                        1.0;
193   A[13][14] =                                        1.0;
194   A[14][15] =                                        1.0;
195
196   lmm::System* Sys = new_system();
197
198   /* Creates the constraints */
199   lmm::Constraint** tmp_cnst = new lmm::Constraint*[15];
200   for (int i = 0; i < 15; i++)
201     tmp_cnst[i] = Sys->constraint_new(nullptr, B[i]);
202
203   /* Creates the variables */
204   lmm::Variable** tmp_var = new lmm::Variable*[16];
205   for (int j = 0; j < 16; j++) {
206     tmp_var[j] = Sys->variable_new(nullptr, 1.0, -1.0, 15);
207     Sys->update_variable_penalty(tmp_var[j], 1.0);
208   }
209
210   /* Link constraints and variables */
211   for (int i = 0; i < 15; i++)
212     for (int j = 0; j < 16; j++)
213       if (A[i][j])
214         Sys->expand(tmp_cnst[i], tmp_var[j], 1.0);
215
216   Sys->solve();
217
218   for (int j = 0; j < 16; j++)
219     PRINT_VAR(tmp_var[j]);
220
221   for (int j = 0; j < 16; j++)
222     Sys->variable_free(tmp_var[j]);
223   delete[] tmp_var;
224   delete[] tmp_cnst;
225   delete Sys;
226   for (int i = 0; i < links + 5; i++)
227     delete[] A[i];
228   delete[] A;
229 }
230
231 int main(int argc, char** argv)
232 {
233   MSG_init(&argc, argv);
234   XBT_INFO("***** Test 1");
235   test1();
236
237   XBT_INFO("***** Test 2");
238   test2();
239
240   XBT_INFO("***** Test 3");
241   test3();
242
243   return 0;
244 }