testsuite/surf/lmm_usage.c

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