src/ats/gnunet-service-ats_addresses_mlp.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2011 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 3, or (at your
   8      option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19 */
  20
  21 /**
  22  * @file ats/gnunet-service-ats_addresses_mlp.c
  23  * @brief ats mlp problem solver
  24  * @author Matthias Wachs
  25  * @author Christian Grothoff
  26  */
  27 #include "platform.h"
  28 #include "gnunet_util_lib.h"
  29 #include "gnunet-service-ats_addresses.h"
  30 #include "gnunet-service-ats_addresses_mlp.h"
  31 #include "gnunet_statistics_service.h"
  32 #if HAVE_LIBGLPK
  33 #include "glpk.h"
  34 #endif
  35
  36 #define DEBUG_ATS GNUNET_YES
  37 #define VERY_BIG_DOUBLE_VALUE DBL_MAX
  38
  39 /**
  40  * Translate glpk solver error codes to text
  41  * @param retcode return code
  42  * @return string with result
  43  */
  44 const char *
  45 mlp_solve_to_string (int retcode)
  46 {
  47   switch (retcode) {
  48     case 0:
  49       return "ok";
  50       break;
  51     case GLP_EBADB:
  52       return "invalid basis";
  53       break;
  54     case GLP_ESING:
  55       return "singular matrix";
  56       break;
  57     case GLP_ECOND:
  58       return "ill-conditioned matrix";
  59       break;
  60     case GLP_EBOUND:
  61       return "invalid bounds";
  62       break;
  63     case GLP_EFAIL:
  64       return "solver failed";
  65       break;
  66     case GLP_EOBJLL:
  67       return "objective lower limit reached";
  68       break;
  69     case GLP_EOBJUL:
  70       return "objective upper limit reached";
  71       break;
  72     case GLP_EITLIM:
  73       return "iteration limit exceeded";
  74       break;
  75     case GLP_ETMLIM:
  76       return "time limit exceeded";
  77       break;
  78     case GLP_ENOPFS:
  79       return "no primal feasible solution";
  80       break;
  81     case GLP_EROOT:
  82       return "root LP optimum not provided";
  83       break;
  84     case GLP_ESTOP:
  85       return "search terminated by application";
  86       break;
  87     case GLP_EMIPGAP:
  88       return "relative mip gap tolerance reached";
  89       break;
  90     case GLP_ENOFEAS:
  91       return "no dual feasible solution";
  92       break;
  93     case GLP_ENOCVG:
  94       return "no convergence";
  95       break;
  96     case GLP_EINSTAB:
  97       return "numerical instability";
  98       break;
  99     case GLP_EDATA:
 100       return "invalid data";
 101       break;
 102     case GLP_ERANGE:
 103       return "result out of range";
 104       break;
 105     default:
 106       GNUNET_break (0);
 107       return "unknown error";
 108       break;
 109   }
 110   GNUNET_break (0);
 111   return "unknown error";
 112 }
 113
 114
 115 /**
 116  * Translate glpk status error codes to text
 117  * @param retcode return code
 118  * @return string with result
 119  */
 120 const char *
 121 mlp_status_to_string (int retcode)
 122 {
 123   switch (retcode) {
 124     case GLP_UNDEF:
 125       return "solution is undefined";
 126       break;
 127     case GLP_FEAS:
 128       return "solution is feasible";
 129       break;
 130     case GLP_INFEAS:
 131       return "solution is infeasible";
 132       break;
 133     case GLP_NOFEAS:
 134       return "no feasible solution exists";
 135       break;
 136     case GLP_OPT:
 137       return "solution is optimal";
 138       break;
 139     case GLP_UNBND:
 140       return "solution is unbounded";
 141       break;
 142     default:
 143       GNUNET_break (0);
 144       return "unknown error";
 145       break;
 146   }
 147   GNUNET_break (0);
 148   return "unknown error";
 149 }
 150
 151 /**
 152  * Intercept GLPK terminal output
 153  * @param info the mlp handle
 154  * @param s the string to print
 155  * @return 0: glpk prints output on terminal, 0 != surpress output
 156  */
 157 static int
 158 mlp_term_hook (void *info, const char *s)
 159 {
 160   /* Not needed atm struct MLP_information *mlp = info; */
 161   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s", s);
 162   return 1;
 163 }
 164
 165 /**
 166  * Delete the MLP problem and free the constrain matrix
 167  *
 168  * @param mlp the MLP handle
 169  */
 170 static void
 171 mlp_delete_problem (struct GAS_MLP_Handle *mlp)
 172 {
 173   if (mlp != NULL)
 174   {
 175     glp_delete_prob(mlp->prob);
 176
 177     /* delete row index */
 178     if (mlp->ia != NULL)
 179       GNUNET_free (mlp->ia);
 180
 181     /* delete column index */
 182     if (mlp->ja != NULL)
 183       GNUNET_free (mlp->ja);
 184
 185     /* delete coefficients */
 186     if (mlp->ar != NULL)
 187       GNUNET_free (mlp->ar);
 188   }
 189 }
 190
 191 /**
 192  * Adds the problem constraints for all addresses
 193  * Required for problem recreation after address deletion
 194  *
 195  * @param addresses all addresses
 196  */
 197
 198 static void
 199 mlp_add_constraints_all_addresses (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
 200 {
 201   //double M = VERY_BIG_DOUBLE_VALUE;
 202   unsigned int n_addresses;
 203
 204   /* Problem matrix*/
 205   n_addresses = GNUNET_CONTAINER_multihashmap_size(addresses);
 206
 207   /* Required indices in the constrain matrix
 208    *
 209    * feasibility constraints:
 210    *
 211    * c 1) bandwidth capping
 212    * #rows: |n_addresses|
 213    * #indices: 2 * |n_addresses|
 214    *
 215    * c 2) one active address per peer
 216    * #rows: |peers|
 217    * #indices: |n_addresses|
 218    *
 219    * c 3) minium bandwidth assigned
 220    * #rows: |n_addresses|
 221    * #indices: 2 * |n_addresses|
 222    *
 223    * c 4) minimum number of active connections
 224    * #rows: 1
 225    * #indices: |n_addresses|
 226    *
 227    * c 5) maximum ressource consumption
 228    * #rows: |ressources|
 229    * #indices: |n_addresses|
 230    *
 231    * Sum for feasibility constraints:
 232    * #rows: 3 * |n_addresses| +  |ressources| + |peers| + 1
 233    * #indices: 7 * |n_addresses|
 234    *
 235    * optimality constraints:
 236    * tbc
 237    * */
 238
 239   int pi = (7 * n_addresses);
 240   mlp->cm_size = pi;
 241
 242   /* row index */
 243   int *ia = GNUNET_malloc (pi * sizeof (int));
 244   mlp->ia = ia;
 245
 246   /* column index */
 247   int *ja = GNUNET_malloc (pi * sizeof (int));
 248   mlp->ja = ja;
 249
 250   /* coefficient */
 251   double *ar= GNUNET_malloc (pi * sizeof (double));
 252   mlp->ar = ar;
 253
 254
 255   /* Adding constraint rows */
 256   /* Feasibility constraints */
 257
 258   /* c 1) bandwidth capping */
 259
 260 }
 261
 262 /**
 263  * Create the MLP problem
 264  *
 265  * @param mlp the MLP handle
 266  * @return GNUNET_OK or GNUNET_SYSERR
 267  */
 268 static int
 269 mlp_create_problem (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
 270 {
 271   int res = GNUNET_OK;
 272   int col;
 273   int c;
 274   char *name;
 275
 276
 277   /* Set a problem name */
 278   glp_set_prob_name (mlp->prob, "gnunet ats bandwidth distribution");
 279
 280   /* Set optimization direction to maximize */
 281   glp_set_obj_dir (mlp->prob, GLP_MAX);
 282
 283   /* Adding invariant columns */
 284
 285   /* Diversity d column  */
 286
 287   col = glp_add_cols (mlp->prob, 1);
 288   mlp->c_d = col;
 289   /* Column name */
 290   glp_set_col_name (mlp->prob, col, "d");
 291   /* Column objective function coefficient */
 292   glp_set_obj_coef (mlp->prob, col, mlp->co_D);
 293   /* Column lower bound = 0.0 */
 294   glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
 295
 296   /* Utilization u column  */
 297
 298   col = glp_add_cols (mlp->prob, 1);
 299   mlp->c_u = col;
 300   /* Column name */
 301   glp_set_col_name (mlp->prob, col, "u");
 302   /* Column objective function coefficient */
 303   glp_set_obj_coef (mlp->prob, col, mlp->co_U);
 304   /* Column lower bound = 0.0 */
 305   glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
 306
 307   /* Relativity r column  */
 308   col = glp_add_cols (mlp->prob, 1);
 309   mlp->c_r = col;
 310   /* Column name */
 311   glp_set_col_name (mlp->prob, col, "r");
 312   /* Column objective function coefficient */
 313   glp_set_obj_coef (mlp->prob, col, mlp->co_R);
 314   /* Column lower bound = 0.0 */
 315   glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
 316
 317   /* Quality metric columns */
 318   col = glp_add_cols(mlp->prob, mlp->m);
 319   for (c = 0; c < mlp->m; c++)
 320   {
 321     mlp->c_q[c] = col + c;
 322     GNUNET_asprintf (&name, "q_%u", mlp->q[c]);
 323     glp_set_col_name (mlp->prob, col + c, name);
 324     /* Column lower bound = 0.0 */
 325     glp_set_col_bnds (mlp->prob, col + c, GLP_LO, 0.0, 0.0);
 326     GNUNET_free (name);
 327     /* Coefficient == Qm */
 328     glp_set_obj_coef (mlp->prob, col + c, mlp->co_Q[c]);
 329   }
 330
 331   /* Add columns for existing addresses */
 332
 333   return res;
 334 }
 335
 336 /**
 337  * Solves the LP problem
 338  *
 339  * @param mlp the MLP Handle
 340  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 341  */
 342 static int
 343 mlp_solve_lp_problem (struct GAS_MLP_Handle *mlp)
 344 {
 345   int res;
 346   struct GNUNET_TIME_Relative duration;
 347   struct GNUNET_TIME_Absolute end;
 348   struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
 349
 350   /* LP presolver?
 351    * Presolver is required if the problem was modified and an existing
 352    * valid basis is now invalid */
 353   if (mlp->presolver_required == GNUNET_YES)
 354     mlp->control_param_lp.presolve = GLP_ON;
 355   else
 356     mlp->control_param_lp.presolve = GLP_OFF;
 357
 358   /* Solve LP problem to have initial valid solution */
 359 lp_solv:
 360   res = glp_simplex(mlp->prob, &mlp->control_param_lp);
 361   if (res == 0)
 362   {
 363     /* The LP problem instance has been successfully solved. */
 364   }
 365   else if (res == GLP_EITLIM)
 366   {
 367     /* simplex iteration limit has been exceeded. */
 368     // TODO Increase iteration limit?
 369   }
 370   else if (res == GLP_ETMLIM)
 371   {
 372     /* Time limit has been exceeded.  */
 373     // TODO Increase time limit?
 374   }
 375   else
 376   {
 377     /* Problem was ill-defined, retry with presolver */
 378     if (mlp->presolver_required == GNUNET_NO)
 379     {
 380       mlp->presolver_required = GNUNET_YES;
 381       goto lp_solv;
 382     }
 383     else
 384     {
 385       /* Problem was ill-defined, no way to handle that */
 386       GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
 387           "ats-mlp",
 388           "Solving LP problem failed:  %s\n", mlp_solve_to_string(res));
 389       return GNUNET_SYSERR;
 390     }
 391   }
 392
 393   end = GNUNET_TIME_absolute_get ();
 394   duration = GNUNET_TIME_absolute_get_difference (start, end);
 395   mlp->lp_solved++;
 396   mlp->lp_total_duration =+ duration.rel_value;
 397
 398   GNUNET_STATISTICS_update (mlp->stats,"# LP problem solved", 1, GNUNET_NO);
 399   GNUNET_STATISTICS_set (mlp->stats,"# LP execution time", duration.rel_value, GNUNET_NO);
 400   GNUNET_STATISTICS_set (mlp->stats,"# LP execution time average",
 401                          mlp->lp_total_duration / mlp->lp_solved,  GNUNET_NO);
 402
 403
 404   /* Analyze problem status  */
 405   res = glp_get_status (mlp->prob);
 406   switch (res) {
 407     /* solution is optimal */
 408     case GLP_OPT:
 409     /* solution is feasible */
 410     case GLP_FEAS:
 411       break;
 412
 413     /* Problem was ill-defined, no way to handle that */
 414     default:
 415       GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
 416           "ats-mlp",
 417           "Solving LP problem failed, no solution: %s\n", mlp_status_to_string(res));
 418       return GNUNET_SYSERR;
 419       break;
 420   }
 421
 422   /* solved sucessfully, no presolver required next time */
 423   mlp->presolver_required = GNUNET_NO;
 424
 425   return GNUNET_OK;
 426 }
 427
 428
 429 /**
 430  * Solves the MLP problem
 431  *
 432  * @param mlp the MLP Handle
 433  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 434  */
 435 int
 436 mlp_solve_mlp_problem (struct GAS_MLP_Handle *mlp)
 437 {
 438   int res;
 439   struct GNUNET_TIME_Relative duration;
 440   struct GNUNET_TIME_Absolute end;
 441   struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
 442
 443   /* solve MLP problem */
 444   res = glp_intopt(mlp->prob, &mlp->control_param_mlp);
 445
 446   if (res == 0)
 447   {
 448     /* The MLP problem instance has been successfully solved. */
 449   }
 450   else if (res == GLP_EITLIM)
 451   {
 452     /* simplex iteration limit has been exceeded. */
 453     // TODO Increase iteration limit?
 454   }
 455   else if (res == GLP_ETMLIM)
 456   {
 457     /* Time limit has been exceeded.  */
 458     // TODO Increase time limit?
 459   }
 460   else
 461   {
 462     /* Problem was ill-defined, no way to handle that */
 463     GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
 464         "ats-mlp",
 465         "Solving MLP problem failed:  %s\n", mlp_solve_to_string(res));
 466     return GNUNET_SYSERR;
 467   }
 468
 469   end = GNUNET_TIME_absolute_get ();
 470   duration = GNUNET_TIME_absolute_get_difference (start, end);
 471   mlp->mlp_solved++;
 472   mlp->mlp_total_duration =+ duration.rel_value;
 473
 474   GNUNET_STATISTICS_update (mlp->stats,"# MLP problem solved", 1, GNUNET_NO);
 475   GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time", duration.rel_value, GNUNET_NO);
 476   GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time average",
 477                          mlp->mlp_total_duration / mlp->mlp_solved,  GNUNET_NO);
 478
 479   /* Analyze problem status  */
 480   res = glp_mip_status(mlp->prob);
 481   switch (res) {
 482     /* solution is optimal */
 483     case GLP_OPT:
 484     /* solution is feasible */
 485     case GLP_FEAS:
 486       break;
 487
 488     /* Problem was ill-defined, no way to handle that */
 489     default:
 490       GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
 491           "ats-mlp",
 492           "Solving MLP problem failed, %s\n\n", mlp_status_to_string(res));
 493       return GNUNET_SYSERR;
 494       break;
 495   }
 496
 497   return GNUNET_OK;
 498 }
 499
 500 int mlp_solve_problem (struct GAS_MLP_Handle *mlp);
 501
 502 static void
 503 mlp_scheduler (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
 504 {
 505   struct GAS_MLP_Handle *mlp = cls;
 506
 507   mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
 508
 509   if (0 != (tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN))
 510     return;
 511
 512 #if DEBUG_ATS
 513   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Scheduled problem solving\n");
 514 #endif
 515   if (mlp->addr_in_problem != 0)
 516     mlp_solve_problem(mlp);
 517 }
 518
 519
 520 /**
 521  * Solves the MLP problem
 522  *
 523  * @param mlp the MLP Handle
 524  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 525  */
 526 int
 527 mlp_solve_problem (struct GAS_MLP_Handle *mlp)
 528 {
 529   int res;
 530   mlp->last_execution = GNUNET_TIME_absolute_get ();
 531   res = mlp_solve_lp_problem (mlp);
 532   if (res == GNUNET_OK)
 533     res = mlp_solve_mlp_problem (mlp);
 534   if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
 535   {
 536     GNUNET_SCHEDULER_cancel(mlp->mlp_task);
 537     mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
 538   }
 539   mlp->mlp_task = GNUNET_SCHEDULER_add_delayed (mlp->exec_interval, &mlp_scheduler, mlp);
 540   return res;
 541 }
 542
 543 /**
 544  * Init the MLP problem solving component
 545  *
 546  * @param stats the GNUNET_STATISTICS handle
 547  * @param max_duration maximum numbers of iterations for the LP/MLP Solver
 548  * @param max_iterations maximum time limit for the LP/MLP Solver
 549  * @return struct GAS_MLP_Handle * on success, NULL on fail
 550  */
 551 struct GAS_MLP_Handle *
 552 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
 553               const struct GNUNET_STATISTICS_Handle *stats,
 554               struct GNUNET_TIME_Relative max_duration,
 555               unsigned int max_iterations)
 556 {
 557   struct GAS_MLP_Handle * mlp = GNUNET_malloc (sizeof (struct GAS_MLP_Handle));
 558
 559   double D;
 560   double R;
 561   double U;
 562   long long unsigned int tmp;
 563   unsigned int b_min;
 564   unsigned int n_min;
 565   struct GNUNET_TIME_Relative i_exec;
 566
 567   /* Init GLPK environment */
 568   GNUNET_assert (glp_init_env() == 0);
 569
 570   /* Create initial MLP problem */
 571   mlp->prob = glp_create_prob();
 572   GNUNET_assert (mlp->prob != NULL);
 573
 574   /* Get diversity coefficient from configuration */
 575   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 576                                                       "COEFFICIENT_D",
 577                                                       &tmp))
 578     D = (double) tmp / 100;
 579   else
 580     D = 1.0;
 581
 582   /* Get proportionality coefficient from configuration */
 583   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 584                                                       "COEFFICIENT_R",
 585                                                       &tmp))
 586     R = (double) tmp / 100;
 587   else
 588     R = 1.0;
 589
 590   /* Get utilization coefficient from configuration */
 591   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 592                                                       "COEFFICIENT_U",
 593                                                       &tmp))
 594     U = (double) tmp / 100;
 595   else
 596     U = 1.0;
 597
 598   /* Get quality metric coefficients from configuration */
 599   int i_delay = -1;
 600   int i_distance = -1;
 601   int q[GNUNET_ATS_QualityPropertiesCount] = GNUNET_ATS_QualityProperties;
 602   int c;
 603   for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
 604   {
 605     /* initialize quality coefficients with default value 1.0 */
 606     mlp->co_Q[c] = 1.0;
 607
 608     mlp->q[c] = q[c];
 609     if (q[c] == GNUNET_ATS_QUALITY_NET_DELAY)
 610       i_delay = c;
 611     if (q[c] == GNUNET_ATS_QUALITY_NET_DISTANCE)
 612       i_distance = c;
 613   }
 614
 615   if ((i_delay != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 616                                                       "COEFFICIENT_QUALITY_DELAY",
 617                                                       &tmp)))
 618
 619     mlp->co_Q[i_delay] = (double) tmp / 100;
 620   else
 621     mlp->co_Q[i_delay] = 1.0;
 622
 623   if ((i_distance != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 624                                                       "COEFFICIENT_QUALITY_DISTANCE",
 625                                                       &tmp)))
 626     mlp->co_Q[i_distance] = (double) tmp / 100;
 627   else
 628     mlp->co_Q[i_distance] = 1.0;
 629
 630   /* Get minimum bandwidth per used address from configuration */
 631   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 632                                                       "MIN_BANDWIDTH",
 633                                                       &tmp))
 634     b_min = tmp;
 635   else
 636     b_min = 64000;
 637
 638   /* Get minimum number of connections from configuration */
 639   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 640                                                       "MIN_CONNECTIONS",
 641                                                       &tmp))
 642     n_min = tmp;
 643   else
 644     n_min = 4;
 645
 646   /* Get minimum number of connections from configuration */
 647   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_time (cfg, "ats",
 648                                                         "ATS_EXEC_INTERVAL",
 649                                                         &i_exec))
 650     mlp->exec_interval = i_exec;
 651   else
 652     mlp->exec_interval = GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30);
 653
 654   mlp->stats = (struct GNUNET_STATISTICS_Handle *) stats;
 655   mlp->max_iterations = max_iterations;
 656   mlp->max_exec_duration = max_duration;
 657
 658   /* Redirect GLPK output to GNUnet logging */
 659   glp_error_hook((void *) mlp, &mlp_term_hook);
 660
 661   /* Init LP solving parameters */
 662   glp_init_smcp(&mlp->control_param_lp);
 663 #if DEBUG_MLP
 664   mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
 665 #else
 666   mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
 667 #endif
 668   mlp->control_param_lp.it_lim = max_iterations;
 669   mlp->control_param_lp.tm_lim = max_duration.rel_value;
 670
 671   /* Init MLP solving parameters */
 672   glp_init_iocp(&mlp->control_param_mlp);
 673 #if DEBUG_MLP
 674   mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
 675 #else
 676   mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
 677 #endif
 678   mlp->control_param_mlp.tm_lim = max_duration.rel_value;
 679
 680   mlp->last_execution = GNUNET_TIME_absolute_get_forever();
 681
 682   mlp->co_D = D;
 683   mlp->co_R = R;
 684   mlp->co_U = U;
 685   mlp->b_min = b_min;
 686   mlp->n_min = n_min;
 687   mlp->m = GNUNET_ATS_QualityPropertiesCount;
 688
 689   return mlp;
 690 }
 691
 692 /**
 693  * Updates a single address in the MLP problem
 694  *
 695  * If the address did not exist before in the problem:
 696  * The MLP problem has to be recreated and the problem has to be resolved
 697  *
 698  * Otherwise the addresses' values can be updated and the existing base can
 699  * be reused
 700  *
 701  * @param mlp the MLP Handle
 702  * @param addresses the address hashmap
 703  * @param address the address to update
 704  */
 705 void
 706 GAS_mlp_address_update (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
 707 {
 708   int new;
 709   int col;
 710   struct MLP_information *mlpi;
 711   char * name;
 712
 713   GNUNET_STATISTICS_update (mlp->stats,"# LP address updates", 1, GNUNET_NO);
 714
 715   /* We add a new address */
 716   if (address->mlp_information == NULL)
 717     new = GNUNET_YES;
 718   else
 719     new = GNUNET_NO;
 720
 721   if (mlp->prob == NULL)
 722   {
 723     mlp_create_problem(mlp, addresses);
 724     mlp_add_constraints_all_addresses (mlp, addresses);
 725   }
 726
 727   /* Do the update */
 728   if (new == GNUNET_YES)
 729   {
 730     mlpi = GNUNET_malloc (sizeof (struct MLP_information));
 731     address->mlp_information = mlpi;
 732     mlp->addr_in_problem ++;
 733
 734     /* Add bandwidth column */
 735     col = glp_add_cols (mlp->prob, 2);
 736     mlpi->c_b = col;
 737     mlpi->c_n = col + 1;
 738
 739     GNUNET_asprintf (&name, "b_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
 740     glp_set_col_name (mlp->prob, mlpi->c_b , name);
 741     GNUNET_free (name);
 742     /* Lower bound == 0 */
 743     glp_set_col_bnds (mlp->prob, mlpi->c_b , GLP_LO, 0.0, 0.0);
 744     /* Continuous value*/
 745     glp_set_col_kind (mlp->prob, mlpi->c_b , GLP_CV);
 746     /* Objective function coefficient == 0 */
 747     glp_set_obj_coef (mlp->prob, mlpi->c_b , 0);
 748
 749     /* Add usage column */
 750     GNUNET_asprintf (&name, "n_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
 751     glp_set_col_name (mlp->prob, mlpi->c_n, name);
 752     GNUNET_free (name);
 753     /* Limit value : 0 <= value <= 1 */
 754     glp_set_col_bnds (mlp->prob, mlpi->c_n, GLP_DB, 0.0, 1.0);
 755     /* Integer value*/
 756     glp_set_col_kind (mlp->prob, mlpi->c_n, GLP_IV);
 757     /* Objective function coefficient == 0 */
 758     glp_set_obj_coef (mlp->prob, mlpi->c_n, 0);
 759
 760     /* Add */
 761   }
 762
 763   /* Recalculate */
 764   if (new == GNUNET_YES)
 765     mlp->presolver_required = GNUNET_YES;
 766   mlp_solve_problem (mlp);
 767 }
 768
 769 /**
 770  * Deletes a single address in the MLP problem
 771  *
 772  * The MLP problem has to be recreated and the problem has to be resolved
 773  *
 774  * @param mlp the MLP Handle
 775  * @param addresses the address hashmap
 776  * @param address the address to delete
 777  */
 778 void
 779 GAS_mlp_address_delete (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
 780 {
 781   GNUNET_STATISTICS_update (mlp->stats,"# LP address deletions", 1, GNUNET_NO);
 782
 783   /* Free resources */
 784   if (address->mlp_information != NULL)
 785   {
 786     GNUNET_free (address->mlp_information);
 787     address->mlp_information = NULL;
 788
 789     mlp->addr_in_problem --;
 790   }
 791
 792   /* Update problem */
 793
 794   /* Recalculate */
 795   mlp->presolver_required = GNUNET_YES;
 796   mlp_solve_problem (mlp);
 797 }
 798
 799 /**
 800  * Deletes a single address in the MLP problem
 801  *
 802  * @param mlp the MLP Handle
 803  * @param addresses the address hashmap
 804  * @param address the address to change the preference
 805  */
 806 void
 807 GAS_mlp_address_change_preference (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
 808 {
 809   GNUNET_STATISTICS_update (mlp->stats,"# LP address preference changes", 1, GNUNET_NO);
 810 }
 811
 812 /**
 813  * Shutdown the MLP problem solving component
 814  * @param mlp the MLP handle
 815  */
 816 void
 817 GAS_mlp_done (struct GAS_MLP_Handle *mlp)
 818 {
 819   if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
 820   {
 821     GNUNET_SCHEDULER_cancel(mlp->mlp_task);
 822     mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
 823   }
 824
 825   mlp_delete_problem (mlp);
 826
 827   /* Clean up GLPK environment */
 828   glp_free_env();
 829
 830   GNUNET_free (mlp);
 831 }
 832
 833
 834 /* end of gnunet-service-ats_addresses_mlp.c */