Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
acac3e1e0d39f07dbc746d80771c2dbc088c8535
[simgrid.git] / teshsuite / surf / lmm_usage / lmm_usage.cpp
1 /* A few tests for the maxmin library                                       */
2
3 /* Copyright (c) 2007-2018. 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 using namespace simgrid::surf;
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 enum method_t { MAXMIN, LAGRANGE_RENO, LAGRANGE_VEGAS };
29
30 static double dichotomy(double func(double), double min, double max, double min_error)
31 {
32   double overall_error = 2 * min_error;
33
34   double min_func = func(min);
35   double max_func = func(max);
36
37   if ((min_func > 0 && max_func > 0))
38     return min - 1.0;
39   if ((min_func < 0 && max_func < 0))
40     return max + 1.0;
41   if ((min_func > 0 && max_func < 0))
42     abort();
43
44   SHOW_EXPR(min_error);
45
46   while (overall_error > min_error) {
47     SHOW_EXPR(overall_error);
48     xbt_assert(min_func <= 0 || max_func <= 0);
49     xbt_assert(min_func >= 0 || max_func >= 0);
50     xbt_assert(min_func <= 0 || max_func >= 0);
51
52     SHOW_EXPR(min);
53     SHOW_EXPR(min_func);
54     SHOW_EXPR(max);
55     SHOW_EXPR(max_func);
56
57     double middle = (max + min) / 2.0;
58     if (fabs(min - middle) < 1e-12 || fabs(max - middle) < 1e-12) {
59       break;
60     }
61     double middle_func = func(middle);
62     SHOW_EXPR(middle);
63     SHOW_EXPR(middle_func);
64
65     if (middle_func < 0) {
66       min = middle;
67       min_func = middle_func;
68       overall_error = max_func - middle_func;
69     } else if (middle_func > 0) {
70       max = middle;
71       max_func = middle_func;
72       overall_error = middle_func - min_func;
73     } else {
74       overall_error = 0;
75     }
76   }
77   return ((min + max) / 2.0);
78 }
79
80 double a_test_1 = 0;
81 double b_test_1 = 0;
82 static double diff_lagrange_test_1(double x)
83 {
84   return -(3 / (1 + 3 * x * x / 2) - 3 / (2 * (3 * (a_test_1 - x) * (a_test_1 - x) / 2 + 1)) +
85            3 / (2 * (3 * (b_test_1 - a_test_1 + x) * (b_test_1 - a_test_1 + x) / 2 + 1)));
86 }
87
88 static void test1(method_t method)
89 {
90   double a = 1.0;
91   double b = 10.0;
92
93   if (method == LAGRANGE_VEGAS)
94     set_default_protocol_function(simgrid::kernel::lmm::func_vegas_f, simgrid::kernel::lmm::func_vegas_fp,
95                                   simgrid::kernel::lmm::func_vegas_fpi);
96   else if (method == LAGRANGE_RENO)
97     set_default_protocol_function(simgrid::kernel::lmm::func_reno_f, simgrid::kernel::lmm::func_reno_fpi,
98                                   simgrid::kernel::lmm::func_reno_fpi);
99
100   simgrid::kernel::lmm::System* Sys    = new simgrid::kernel::lmm::System(true);
101   simgrid::kernel::lmm::Constraint* L1 = Sys->constraint_new(nullptr, a);
102   simgrid::kernel::lmm::Constraint* L2 = Sys->constraint_new(nullptr, b);
103   simgrid::kernel::lmm::Constraint* L3 = Sys->constraint_new(nullptr, a);
104
105   simgrid::kernel::lmm::Variable* R_1_2_3 = Sys->variable_new(nullptr, 1.0, -1.0, 3);
106   simgrid::kernel::lmm::Variable* R_1     = Sys->variable_new(nullptr, 1.0, -1.0, 1);
107   simgrid::kernel::lmm::Variable* R_2     = Sys->variable_new(nullptr, 1.0, -1.0, 1);
108   simgrid::kernel::lmm::Variable* R_3     = Sys->variable_new(nullptr, 1.0, -1.0, 1);
109
110   Sys->update_variable_weight(R_1_2_3, 1.0);
111   Sys->update_variable_weight(R_1, 1.0);
112   Sys->update_variable_weight(R_2, 1.0);
113   Sys->update_variable_weight(R_3, 1.0);
114
115   Sys->expand(L1, R_1_2_3, 1.0);
116   Sys->expand(L2, R_1_2_3, 1.0);
117   Sys->expand(L3, R_1_2_3, 1.0);
118
119   Sys->expand(L1, R_1, 1.0);
120   Sys->expand(L2, R_2, 1.0);
121   Sys->expand(L3, R_3, 1.0);
122
123   if (method == MAXMIN) {
124     lmm_solve(Sys);
125   } else {
126     double x;
127     if (method == LAGRANGE_VEGAS) {
128       x = 3 * a / 4 - 3 * b / 8 + sqrt(9 * b * b + 4 * a * a - 4 * a * b) / 8;
129       /* Computed with mupad and D_f=1.0 */
130       if (x > a) {
131         x = a;
132       }
133       if (x < 0) {
134         x = 0;
135       }
136     } else if (method == LAGRANGE_RENO) {
137       a_test_1 = a;
138       b_test_1 = b;
139       x = dichotomy(diff_lagrange_test_1, 0, a, 1e-13);
140
141       if (x < 0)
142         x = 0;
143       if (x > a)
144         x = a;
145     } else {
146       xbt_die( "Invalid method");
147     }
148
149     lagrange_solve(Sys);
150
151     double max_deviation = 0.0;
152     max_deviation        = std::max(max_deviation, fabs(R_1->get_value() - x));
153     max_deviation        = std::max(max_deviation, fabs(R_3->get_value() - x));
154     max_deviation        = std::max(max_deviation, fabs(R_2->get_value() - (b - a + x)));
155     max_deviation        = std::max(max_deviation, fabs(R_1_2_3->get_value() - (a - x)));
156
157     if (max_deviation > 0.00001) { // Legacy value used in lagrange.c
158       XBT_WARN("Max Deviation from optimal solution : %g", max_deviation);
159       XBT_WARN("Found x = %1.20f", x);
160       XBT_WARN("Deviation from optimal solution (R_1 = %g): %1.20f", x, R_1->get_value() - x);
161       XBT_WARN("Deviation from optimal solution (R_2 = %g): %1.20f", b - a + x, R_2->get_value() - (b - a + x));
162       XBT_WARN("Deviation from optimal solution (R_3 = %g): %1.20f", x, R_3->get_value() - x);
163       XBT_WARN("Deviation from optimal solution (R_1_2_3 = %g): %1.20f", a - x, R_1_2_3->get_value() - (a - x));
164     }
165   }
166
167   PRINT_VAR(R_1_2_3);
168   PRINT_VAR(R_1);
169   PRINT_VAR(R_2);
170   PRINT_VAR(R_3);
171
172   Sys->variable_free(R_1_2_3);
173   Sys->variable_free(R_1);
174   Sys->variable_free(R_2);
175   Sys->variable_free(R_3);
176   delete Sys;
177 }
178
179 static void test2(method_t method)
180 {
181   if (method == LAGRANGE_VEGAS)
182     set_default_protocol_function(simgrid::kernel::lmm::func_vegas_f, simgrid::kernel::lmm::func_vegas_fp,
183                                   simgrid::kernel::lmm::func_vegas_fpi);
184   if (method == LAGRANGE_RENO)
185     set_default_protocol_function(simgrid::kernel::lmm::func_reno_f, simgrid::kernel::lmm::func_reno_fp,
186                                   simgrid::kernel::lmm::func_reno_fpi);
187
188   simgrid::kernel::lmm::System* Sys      = new simgrid::kernel::lmm::System(true);
189   simgrid::kernel::lmm::Constraint* CPU1 = Sys->constraint_new(nullptr, 200.0);
190   simgrid::kernel::lmm::Constraint* CPU2 = Sys->constraint_new(nullptr, 100.0);
191
192   simgrid::kernel::lmm::Variable* T1 = Sys->variable_new(nullptr, 1.0, -1.0, 1);
193   simgrid::kernel::lmm::Variable* T2 = Sys->variable_new(nullptr, 1.0, -1.0, 1);
194
195   Sys->update_variable_weight(T1, 1.0);
196   Sys->update_variable_weight(T2, 1.0);
197
198   Sys->expand(CPU1, T1, 1.0);
199   Sys->expand(CPU2, T2, 1.0);
200
201   if (method == MAXMIN) {
202     lmm_solve(Sys);
203   } else if (method == LAGRANGE_VEGAS || method == LAGRANGE_RENO) {
204     lagrange_solve(Sys);
205   } else {
206     xbt_die("Invalid method");
207   }
208
209   PRINT_VAR(T1);
210   PRINT_VAR(T2);
211
212   Sys->variable_free(T1);
213   Sys->variable_free(T2);
214   delete Sys;
215 }
216
217 static void test3(method_t method)
218 {
219   int flows = 11;
220   int links = 10;
221
222   double** A = new double*[links + 5];
223   /* array to add the constraints of fictitious variables */
224   double B[15] = { 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1 };
225
226   for (int i = 0; i < links + 5; i++) {
227     A[i] = new double[flows + 5];
228     for (int j = 0; j < flows + 5; j++) {
229       A[i][j] = 0.0;
230
231       if (i >= links || j >= flows) {
232         A[i][j] = 0.0;
233       }
234     }
235   }
236
237   /*matrix that store the constraints/topology */
238   A[0][1] = A[0][7] =                                1.0;
239   A[1][1] = A[1][7] = A[1][8] =                      1.0;
240   A[2][1] = A[2][8] =                                1.0;
241   A[3][8] =                                          1.0;
242   A[4][0] = A[4][3] = A[4][9] =                      1.0;
243   A[5][0] = A[5][3] = A[5][4] = A[5][9] =            1.0;
244   A[6][0] = A[6][4] = A[6][9] = A[6][10] =           1.0;
245   A[7][2] = A[7][4] = A[7][6] = A[7][9] = A[7][10] = 1.0;
246   A[8][2] = A[8][10] =                               1.0;
247   A[9][5] = A[9][6] = A[9][9] =                      1.0;
248   A[10][11] =                                        1.0;
249   A[11][12] =                                        1.0;
250   A[12][13] =                                        1.0;
251   A[13][14] =                                        1.0;
252   A[14][15] =                                        1.0;
253
254   if (method == LAGRANGE_VEGAS)
255     set_default_protocol_function(simgrid::kernel::lmm::func_vegas_f, simgrid::kernel::lmm::func_vegas_fp,
256                                   simgrid::kernel::lmm::func_vegas_fpi);
257   if (method == LAGRANGE_RENO)
258     set_default_protocol_function(simgrid::kernel::lmm::func_reno_f, simgrid::kernel::lmm::func_reno_fp,
259                                   simgrid::kernel::lmm::func_reno_fpi);
260
261   simgrid::kernel::lmm::System* Sys = new simgrid::kernel::lmm::System(true);
262
263   /* Creates the constraints */
264   simgrid::kernel::lmm::Constraint** tmp_cnst = new simgrid::kernel::lmm::Constraint*[15];
265   for (int i = 0; i < 15; i++)
266     tmp_cnst[i] = Sys->constraint_new(nullptr, B[i]);
267
268   /* Creates the variables */
269   simgrid::kernel::lmm::Variable** tmp_var = new simgrid::kernel::lmm::Variable*[16];
270   for (int j = 0; j < 16; j++) {
271     tmp_var[j] = Sys->variable_new(nullptr, 1.0, -1.0, 15);
272     Sys->update_variable_weight(tmp_var[j], 1.0);
273   }
274
275   /* Link constraints and variables */
276   for (int i = 0; i < 15; i++)
277     for (int j = 0; j < 16; j++)
278       if (A[i][j])
279         Sys->expand(tmp_cnst[i], tmp_var[j], 1.0);
280
281   if (method == MAXMIN) {
282     lmm_solve(Sys);
283   } else if (method == LAGRANGE_VEGAS) {
284     lagrange_solve(Sys);
285   } else if (method == LAGRANGE_RENO) {
286     lagrange_solve(Sys);
287   } else {
288     xbt_die("Invalid method");
289   }
290
291   for (int j = 0; j < 16; j++)
292     PRINT_VAR(tmp_var[j]);
293
294   for (int j = 0; j < 16; j++)
295     Sys->variable_free(tmp_var[j]);
296   delete[] tmp_var;
297   delete[] tmp_cnst;
298   delete Sys;
299   for (int i = 0; i < links + 5; i++)
300     delete[] A[i];
301   delete[] A;
302 }
303
304 int main(int argc, char** argv)
305 {
306   MSG_init(&argc, argv);
307   XBT_INFO("***** Test 1 (Max-Min)");
308   test1(MAXMIN);
309   XBT_INFO("***** Test 1 (Lagrange - Vegas)");
310   test1(LAGRANGE_VEGAS);
311   XBT_INFO("***** Test 1 (Lagrange - Reno)");
312   test1(LAGRANGE_RENO);
313
314   XBT_INFO("***** Test 2 (Max-Min)");
315   test2(MAXMIN);
316   XBT_INFO("***** Test 2 (Lagrange - Vegas)");
317   test2(LAGRANGE_VEGAS);
318   XBT_INFO("***** Test 2 (Lagrange - Reno)");
319   test2(LAGRANGE_RENO);
320
321   XBT_INFO("***** Test 3 (Max-Min)");
322   test3(MAXMIN);
323   XBT_INFO("***** Test 3 (Lagrange - Vegas)");
324   test3(LAGRANGE_VEGAS);
325   XBT_INFO("***** Test 3 (Lagrange - Reno)");
326   test3(LAGRANGE_RENO);
327
328   return 0;
329 }