testsuite/surf/lmm_usage.c

   1 /* A few tests for the maxmin library                                       */
   2
   3 /* Copyright (c) 2007, 2008, 2009, 2010. The SimGrid Team.
   4  * All rights reserved.                                                     */
   5
   6 /* This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the license (GNU LGPL) which comes with this package. */
   8
   9 #ifdef __BORLANDC__
  10 #pragma hdrstop
  11 #endif
  12
  13 #include "xbt/sysdep.h"
  14 #include "surf/maxmin.h"
  15 #include "xbt/log.h"
  16 #include "xbt/module.h"
  17 #include <math.h>
  18
  19 XBT_LOG_NEW_DEFAULT_CATEGORY(surf_test, "Messages specific for surf example");
  20
  21 #define PRINT_VAR(var) DEBUG1(#var " = %g",lmm_variable_getvalue(var));
  22 #define SHOW_EXPR(expr) DEBUG1(#expr " = %g",expr);
  23
  24 /*                               */
  25 /*        ______                 */
  26 /*  ==l1==  L2  ==L3==           */
  27 /*        ------                 */
  28 /*                               */
  29
  30 typedef enum {
  31   MAXMIN,
  32   LAGRANGE_RENO,
  33   LAGRANGE_VEGAS,
  34 } method_t;
  35
  36 static double dichotomy(double func(double), double min, double max,
  37                         double min_error)
  38 {
  39   double middle;
  40   double min_func, max_func, middle_func;
  41
  42   double overall_error = 2 * min_error;
  43
  44   min_func = func(min);
  45   max_func = func(max);
  46
  47   if ((min_func > 0 && max_func > 0))
  48     return min - 1.0;
  49   if ((min_func < 0 && max_func < 0))
  50     return max + 1.0;
  51   if ((min_func > 0 && max_func < 0))
  52     abort();
  53
  54   SHOW_EXPR(min_error);
  55
  56   while (overall_error > min_error) {
  57     SHOW_EXPR(overall_error);
  58     if ((min_func > 0 && max_func > 0) ||
  59         (min_func < 0 && max_func < 0) || (min_func > 0 && max_func < 0)) {
  60       abort();
  61     }
  62
  63     SHOW_EXPR(min);
  64     SHOW_EXPR(min_func);
  65     SHOW_EXPR(max);
  66     SHOW_EXPR(max_func);
  67
  68     middle = (max + min) / 2.0;
  69     if ((min == middle) || (max == middle)) {
  70       break;
  71     }
  72     middle_func = func(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 double a_test_1 = 0;
  92 double b_test_1 = 0;
  93 static double diff_lagrange_test_1(double x)
  94 {
  95   return -(3 / (1 + 3 * x * x / 2) -
  96            3 / (2 * (3 * (a_test_1 - x) * (a_test_1 - x) / 2 + 1)) +
  97            3 / (2 *
  98                 (3 * (b_test_1 - a_test_1 + x) *
  99                  (b_test_1 - a_test_1 + x) / 2 + 1)));
 100 }
 101
 102 void test1(method_t method);
 103 void test1(method_t method)
 104 {
 105   lmm_system_t Sys = NULL;
 106   lmm_constraint_t L1 = NULL;
 107   lmm_constraint_t L2 = NULL;
 108   lmm_constraint_t L3 = NULL;
 109
 110   lmm_variable_t R_1_2_3 = NULL;
 111   lmm_variable_t R_1 = NULL;
 112   lmm_variable_t R_2 = NULL;
 113   lmm_variable_t R_3 = NULL;
 114
 115   double a = 1.0, b = 10.0;
 116
 117   if (method == LAGRANGE_VEGAS)
 118     lmm_set_default_protocol_function(func_vegas_f, func_vegas_fp,
 119                                       func_vegas_fpi);
 120   else if (method == LAGRANGE_RENO)
 121     lmm_set_default_protocol_function(func_reno_f, func_reno_fpi,
 122                                       func_reno_fpi);
 123
 124   Sys = lmm_system_new();
 125   L1 = lmm_constraint_new(Sys, (void *) "L1", a);
 126   L2 = lmm_constraint_new(Sys, (void *) "L2", b);
 127   L3 = lmm_constraint_new(Sys, (void *) "L3", a);
 128
 129   R_1_2_3 = lmm_variable_new(Sys, (void *) "R 1->2->3", 1.0, -1.0, 3);
 130   R_1 = lmm_variable_new(Sys, (void *) "R 1", 1.0, -1.0, 1);
 131   R_2 = lmm_variable_new(Sys, (void *) "R 2", 1.0, -1.0, 1);
 132   R_3 = lmm_variable_new(Sys, (void *) "R 3", 1.0, -1.0, 1);
 133
 134   lmm_update_variable_weight(Sys, R_1_2_3, 1.0);
 135   lmm_update_variable_weight(Sys, R_1, 1.0);
 136   lmm_update_variable_weight(Sys, R_2, 1.0);
 137   lmm_update_variable_weight(Sys, R_3, 1.0);
 138
 139   lmm_expand(Sys, L1, R_1_2_3, 1.0);
 140   lmm_expand(Sys, L2, R_1_2_3, 1.0);
 141   lmm_expand(Sys, L3, R_1_2_3, 1.0);
 142
 143   lmm_expand(Sys, L1, R_1, 1.0);
 144
 145   lmm_expand(Sys, L2, R_2, 1.0);
 146
 147   lmm_expand(Sys, L3, R_3, 1.0);
 148
 149
 150   if (method == MAXMIN) {
 151     lmm_solve(Sys);
 152   } else if (method == LAGRANGE_VEGAS) {
 153     double x = 3 * a / 4 - 3 * b / 8 +
 154       sqrt(9 * b * b + 4 * a * a - 4 * a * b) / 8;
 155     /* Computed with mupad and D_f=1.0 */
 156     double max_deviation = 0.0;
 157     if (x > a) {
 158       x = a;
 159     }
 160     if (x < 0) {
 161       x = 0;
 162     }
 163
 164     lagrange_solve(Sys);
 165
 166     max_deviation = MAX(max_deviation, fabs(lmm_variable_getvalue(R_1) - x));
 167     max_deviation = MAX(max_deviation, fabs(lmm_variable_getvalue(R_3) - x));
 168     max_deviation =
 169       MAX(max_deviation, fabs(lmm_variable_getvalue(R_2) - (b - a + x)));
 170     max_deviation =
 171       MAX(max_deviation, fabs(lmm_variable_getvalue(R_1_2_3) - (a - x)));
 172
 173     if (max_deviation > MAXMIN_PRECISION) {
 174       WARN1("Max Deviation from optimal solution : %g", max_deviation);
 175       WARN1("Found x = %1.20f", x);
 176       WARN2("Deviation from optimal solution (R_1 = %g): %1.20f", x,
 177             lmm_variable_getvalue(R_1) - x);
 178       WARN2("Deviation from optimal solution (R_2 = %g): %1.20f",
 179             b - a + x, lmm_variable_getvalue(R_2) - (b - a + x));
 180       WARN2("Deviation from optimal solution (R_3 = %g): %1.20f", x,
 181             lmm_variable_getvalue(R_3) - x);
 182       WARN2("Deviation from optimal solution (R_1_2_3 = %g): %1.20f",
 183             a - x, lmm_variable_getvalue(R_1_2_3) - (a - x));
 184     }
 185   } else if (method == LAGRANGE_RENO) {
 186     double x;
 187     double max_deviation = 0.0;
 188
 189     a_test_1 = a;
 190     b_test_1 = b;
 191     x = dichotomy(diff_lagrange_test_1, 0, a, 1e-13);
 192
 193     if (x < 0)
 194       x = 0;
 195     if (x > a)
 196       x = a;
 197     lagrange_solve(Sys);
 198
 199     max_deviation = MAX(max_deviation, fabs(lmm_variable_getvalue(R_1) - x));
 200     max_deviation = MAX(max_deviation, fabs(lmm_variable_getvalue(R_3) - x));
 201     max_deviation =
 202       MAX(max_deviation, fabs(lmm_variable_getvalue(R_2) - (b - a + x)));
 203     max_deviation =
 204       MAX(max_deviation, fabs(lmm_variable_getvalue(R_1_2_3) - (a - x)));
 205
 206     if (max_deviation > MAXMIN_PRECISION) {
 207       WARN1("Max Deviation from optimal solution : %g", max_deviation);
 208       WARN1("Found x = %1.20f", x);
 209       WARN2("Deviation from optimal solution (R_1 = %g): %1.20f", x,
 210             lmm_variable_getvalue(R_1) - x);
 211       WARN2("Deviation from optimal solution (R_2 = %g): %1.20f",
 212             b - a + x, lmm_variable_getvalue(R_2) - (b - a + x));
 213       WARN2("Deviation from optimal solution (R_3 = %g): %1.20f", x,
 214             lmm_variable_getvalue(R_3) - x);
 215       WARN2("Deviation from optimal solution (R_1_2_3 = %g): %1.20f",
 216             a - x, lmm_variable_getvalue(R_1_2_3) - (a - x));
 217     }
 218   } else {
 219     xbt_assert0(0, "Invalid method");
 220   }
 221
 222   PRINT_VAR(R_1_2_3);
 223   PRINT_VAR(R_1);
 224   PRINT_VAR(R_2);
 225   PRINT_VAR(R_3);
 226
 227   lmm_system_free(Sys);
 228 }
 229
 230 void test2(method_t method);
 231 void test2(method_t method)
 232 {
 233   lmm_system_t Sys = NULL;
 234   lmm_constraint_t CPU1 = NULL;
 235   lmm_constraint_t CPU2 = NULL;
 236
 237   lmm_variable_t T1 = NULL;
 238   lmm_variable_t T2 = NULL;
 239
 240
 241   if (method == LAGRANGE_VEGAS)
 242     lmm_set_default_protocol_function(func_vegas_f, func_vegas_fp,
 243                                       func_vegas_fpi);
 244   else if (method == LAGRANGE_RENO)
 245     lmm_set_default_protocol_function(func_reno_f, func_reno_fp,
 246                                       func_reno_fpi);
 247
 248   Sys = lmm_system_new();
 249   CPU1 = lmm_constraint_new(Sys, (void *) "CPU1", 200.0);
 250   CPU2 = lmm_constraint_new(Sys, (void *) "CPU2", 100.0);
 251
 252   T1 = lmm_variable_new(Sys, (void *) "T1", 1.0, -1.0, 1);
 253   T2 = lmm_variable_new(Sys, (void *) "T2", 1.0, -1.0, 1);
 254
 255   lmm_update_variable_weight(Sys, T1, 1.0);
 256   lmm_update_variable_weight(Sys, T2, 1.0);
 257
 258
 259   lmm_expand(Sys, CPU1, T1, 1.0);
 260   lmm_expand(Sys, CPU2, T2, 1.0);
 261
 262
 263
 264   if (method == MAXMIN) {
 265     lmm_solve(Sys);
 266   } else if (method == LAGRANGE_VEGAS) {
 267     lagrange_solve(Sys);
 268   } else if (method == LAGRANGE_RENO) {
 269     lagrange_solve(Sys);
 270   } else {
 271     xbt_assert0(0, "Invalid method");
 272   }
 273
 274   PRINT_VAR(T1);
 275   PRINT_VAR(T2);
 276
 277   lmm_system_free(Sys);
 278 }
 279
 280
 281
 282 void test3(method_t method);
 283 void test3(method_t method)
 284 {
 285   int flows = 11;
 286   int links = 10;
 287
 288   int i = 0;
 289   int j = 0;
 290
 291   double **A;
 292
 293   lmm_system_t Sys = NULL;
 294   lmm_constraint_t *tmp_cnst = NULL;
 295   lmm_variable_t *tmp_var = NULL;
 296   char **tmp_name;
 297
 298
 299   /*array to add the the constraints of fictiv variables */
 300   double B[15] = { 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
 301
 302     1, 1, 1, 1, 1
 303   };
 304
 305   /*A = xbt_new0(double*, links + 5); */
 306   A = xbt_new0(double *, links + 5);
 307
 308   for (i = 0; i < links + 5; i++) {
 309     A[i] = xbt_new0(double, flows + 5);
 310     for (j = 0; j < flows + 5; j++) {
 311       A[i][j] = 0.0;
 312
 313       if (i >= links || j >= flows) {
 314         A[i][j] = 0.0;
 315       }
 316     }
 317   }
 318
 319   /*matrix that store the constraints/topollogy */
 320   /*double A[15][16]=
 321      {{0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0,    0, 0, 0, 0, 0},
 322      {0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0,    0, 0, 0, 0, 0},
 323      {0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0,    0, 0, 0, 0, 0},
 324      {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,    0, 0, 0, 0, 0},
 325      {1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0,    0, 0, 0, 0, 0},
 326      {1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0,    0, 0, 0, 0, 0},
 327      {1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1,    0, 0, 0, 0, 0},
 328      {0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1,    0, 0, 0, 0, 0},
 329      {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1,    0, 0, 0, 0, 0},
 330      {0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0,    0, 0, 0, 0, 0},
 331
 332      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    1, 0, 0, 0, 0},
 333      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    0, 1, 0, 0, 0},
 334      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 1, 0, 0},
 335      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 1, 0},
 336      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 1}
 337      }; */
 338
 339   A[0][1] = 1.0;
 340   A[0][7] = 1.0;
 341
 342   A[1][1] = 1.0;
 343   A[1][7] = 1.0;
 344   A[1][8] = 1.0;
 345
 346   A[2][1] = 1.0;
 347   A[2][8] = 1.0;
 348
 349   A[2][1] = 1.0;
 350   A[2][8] = 1.0;
 351
 352   A[3][8] = 1.0;
 353
 354   A[4][0] = 1.0;
 355   A[4][3] = 1.0;
 356   A[4][9] = 1.0;
 357
 358   A[5][0] = 1.0;
 359   A[5][3] = 1.0;
 360   A[5][4] = 1.0;
 361   A[5][9] = 1.0;
 362
 363   A[6][0] = 1.0;
 364   A[6][4] = 1.0;
 365   A[6][9] = 1.0;
 366   A[6][10] = 1.0;
 367
 368   A[7][2] = 1.0;
 369   A[7][4] = 1.0;
 370   A[7][6] = 1.0;
 371   A[7][9] = 1.0;
 372   A[7][10] = 1.0;
 373
 374   A[8][2] = 1.0;
 375   A[8][10] = 1.0;
 376
 377   A[9][5] = 1.0;
 378   A[9][6] = 1.0;
 379   A[9][9] = 1.0;
 380
 381
 382   A[10][11] = 1.0;
 383   A[11][12] = 1.0;
 384   A[12][13] = 1.0;
 385   A[13][14] = 1.0;
 386   A[14][15] = 1.0;
 387
 388
 389   if (method == LAGRANGE_VEGAS)
 390     lmm_set_default_protocol_function(func_vegas_f, func_vegas_fp,
 391                                       func_vegas_fpi);
 392   else if (method == LAGRANGE_RENO)
 393     lmm_set_default_protocol_function(func_reno_f, func_reno_fp,
 394                                       func_reno_fpi);
 395
 396   Sys = lmm_system_new();
 397
 398
 399
 400   tmp_name = xbt_new0(char *, 31);
 401
 402   /*
 403    * Creates the constraints
 404    */
 405   tmp_cnst = xbt_new0(lmm_constraint_t, 15);
 406   for (i = 0; i < 15; i++) {
 407     tmp_name[i] = bprintf("C_%03d", i);
 408     tmp_cnst[i] = lmm_constraint_new(Sys, (void *) tmp_name[i], B[i]);
 409   }
 410
 411
 412   /*
 413    * Creates the variables
 414    */
 415   tmp_var = xbt_new0(lmm_variable_t, 16);
 416   for (j = 0; j < 16; j++) {
 417     tmp_name[i + j] = bprintf("X_%03d", j);
 418     tmp_var[j] =
 419       lmm_variable_new(Sys, (void *) tmp_name[i + j], 1.0, -1.0, 15);
 420     lmm_update_variable_weight(Sys, tmp_var[j], 1.0);
 421   }
 422
 423   /*
 424    * Link constraints and variables
 425    */
 426   for (i = 0; i < 15; i++) {
 427     for (j = 0; j < 16; j++) {
 428       if (A[i][j]) {
 429         lmm_expand(Sys, tmp_cnst[i], tmp_var[j], 1.0);
 430       }
 431     }
 432   }
 433
 434
 435
 436   if (method == MAXMIN) {
 437     lmm_solve(Sys);
 438   } else if (method == LAGRANGE_VEGAS) {
 439     lagrange_solve(Sys);
 440   } else if (method == LAGRANGE_RENO) {
 441     lagrange_solve(Sys);
 442   } else {
 443     xbt_assert0(0, "Invalid method");
 444   }
 445
 446   for (j = 0; j < 16; j++) {
 447     PRINT_VAR(tmp_var[j]);
 448   }
 449
 450   free(tmp_var);
 451   free(tmp_cnst);
 452   free(tmp_name);
 453   lmm_system_free(Sys);
 454 }
 455
 456 #ifdef __BORLANDC__
 457 #pragma argsused
 458 #endif
 459
 460 int main(int argc, char **argv)
 461 {
 462   xbt_init(&argc, argv);
 463
 464   INFO0("***** Test 1 (Max-Min)");
 465   test1(MAXMIN);
 466   INFO0("***** Test 1 (Lagrange - Vegas)");
 467   test1(LAGRANGE_VEGAS);
 468   INFO0("***** Test 1 (Lagrange - Reno)");
 469   test1(LAGRANGE_RENO);
 470
 471
 472
 473   INFO0("***** Test 2 (Max-Min)");
 474   test2(MAXMIN);
 475   INFO0("***** Test 2 (Lagrange - Vegas)");
 476   test2(LAGRANGE_VEGAS);
 477   INFO0("***** Test 2 (Lagrange - Reno)");
 478   test2(LAGRANGE_RENO);
 479
 480
 481   INFO0("***** Test 3 (Max-Min)");
 482   test3(MAXMIN);
 483   INFO0("***** Test 3 (Lagrange - Vegas)");
 484   test3(LAGRANGE_VEGAS);
 485   INFO0("***** Test 3 (Lagrange - Reno)");
 486   test3(LAGRANGE_RENO);
 487
 488   return 0;
 489 }