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 /*
  37  * The MLP handle
  38  */
  39 static struct GAS_MLP_Handle *GAS_mlp;
  40
  41
  42 /**
  43  * Solves the LP problem
  44  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
  45  */
  46 int
  47 mlp_solve_lp_problem (struct GAS_MLP_Handle *mlp)
  48 {
  49   int res;
  50   struct GNUNET_TIME_Relative duration;
  51   struct GNUNET_TIME_Absolute end;
  52   struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
  53
  54   /* LP presolver?
  55    * Presolver is required if the problem was modified and an existing
  56    * valid basis is now invalid */
  57   if (mlp->presolver_required == GNUNET_YES)
  58     mlp->control_param_lp.presolve = GLP_ON;
  59   else
  60     mlp->control_param_lp.presolve = GLP_OFF;
  61
  62   /* Solve LP problem to have initial valid solution */
  63 lp_solv:
  64   res = glp_simplex(mlp->prob, &mlp->control_param_lp);
  65   if (res == 0)
  66   {
  67     /* The LP problem instance has been successfully solved. */
  68   }
  69   else if (res == GLP_EITLIM)
  70   {
  71     /* simplex iteration limit has been exceeded. */
  72     // TODO Increase iteration limit?
  73   }
  74   else if (res == GLP_ETMLIM)
  75   {
  76     /* Time limit has been exceeded.  */
  77     // TODO Increase time limit?
  78   }
  79   else
  80   {
  81     /* Problem was ill-defined, retry with presolver */
  82     if (mlp->presolver_required == GNUNET_NO)
  83     {
  84       mlp->presolver_required = GNUNET_YES;
  85       goto lp_solv;
  86     }
  87     else
  88     {
  89       /* Problem was ill-defined, no way to handle that */
  90       GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
  91           "ats-mlp",
  92           "Solving LP problem failed: glp_simplex error 0x%X", res);
  93       return GNUNET_SYSERR;
  94     }
  95   }
  96
  97   end = GNUNET_TIME_absolute_get ();
  98   duration = GNUNET_TIME_absolute_get_difference (start, end);
  99   mlp->lp_solved++;
 100   mlp->lp_total_duration =+ duration.rel_value;
 101
 102   GNUNET_STATISTICS_update (mlp->stats,"# LP problem solved", 1, GNUNET_NO);
 103   GNUNET_STATISTICS_set (mlp->stats,"# LP execution time", duration.rel_value, GNUNET_NO);
 104   GNUNET_STATISTICS_set (mlp->stats,"# LP execution time average",
 105                          mlp->lp_total_duration / mlp->lp_solved,  GNUNET_NO);
 106
 107
 108   /* Analyze problem status  */
 109   res = glp_get_status (mlp->prob);
 110   switch (res) {
 111     /* solution is optimal */
 112     case GLP_OPT:
 113     /* solution is feasible */
 114     case GLP_FEAS:
 115       break;
 116
 117     /* Problem was ill-defined, no way to handle that */
 118     default:
 119       GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
 120           "ats-mlp",
 121           "Solving LP problem failed, no solution: glp_get_status 0x%X", res);
 122       return GNUNET_SYSERR;
 123       break;
 124   }
 125
 126   /* solved sucessfully, no presolver required next time */
 127   mlp->presolver_required = GNUNET_NO;
 128
 129   return GNUNET_OK;
 130 }
 131
 132
 133 /**
 134  * Solves the MLP problem
 135  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 136  */
 137 int
 138 mlp_solve_mlp_problem (struct GAS_MLP_Handle *mlp)
 139 {
 140   int res;
 141   struct GNUNET_TIME_Relative duration;
 142   struct GNUNET_TIME_Absolute end;
 143   struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
 144
 145   /* solve MLP problem */
 146   res = glp_intopt(mlp->prob, &mlp->control_param_mlp);
 147
 148   if (res == 0)
 149   {
 150     /* The MLP problem instance has been successfully solved. */
 151   }
 152   else if (res == GLP_EITLIM)
 153   {
 154     /* simplex iteration limit has been exceeded. */
 155     // TODO Increase iteration limit?
 156   }
 157   else if (res == GLP_ETMLIM)
 158   {
 159     /* Time limit has been exceeded.  */
 160     // TODO Increase time limit?
 161   }
 162   else
 163   {
 164     /* Problem was ill-defined, no way to handle that */
 165     GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
 166         "ats-mlp",
 167         "Solving MLP problem failed: glp_intopt error 0x%X", res);
 168     return GNUNET_SYSERR;
 169   }
 170
 171   end = GNUNET_TIME_absolute_get ();
 172   duration = GNUNET_TIME_absolute_get_difference (start, end);
 173   mlp->mlp_solved++;
 174   mlp->mlp_total_duration =+ duration.rel_value;
 175
 176   GNUNET_STATISTICS_update (mlp->stats,"# MLP problem solved", 1, GNUNET_NO);
 177   GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time", duration.rel_value, GNUNET_NO);
 178   GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time average",
 179                          mlp->mlp_total_duration / mlp->mlp_solved,  GNUNET_NO);
 180
 181   /* Analyze problem status  */
 182   res = glp_mip_status(mlp->prob);
 183   switch (res) {
 184     /* solution is optimal */
 185     case GLP_OPT:
 186     /* solution is feasible */
 187     case GLP_FEAS:
 188       break;
 189
 190     /* Problem was ill-defined, no way to handle that */
 191     default:
 192       GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
 193           "ats-mlp",
 194           "Solving MLP problem failed, no solution: glp_mip_status 0x%X", res);
 195       return GNUNET_SYSERR;
 196       break;
 197   }
 198
 199   return GNUNET_OK;
 200 }
 201
 202 /**
 203  * Solves the MLP problem
 204  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 205  */
 206 int
 207 mlp_solve_problem (struct GAS_MLP_Handle *mlp)
 208 {
 209   int res;
 210   mlp->last_execution = GNUNET_TIME_absolute_get ();
 211   res = mlp_solve_lp_problem (mlp);
 212   if (res == GNUNET_OK)
 213     res = mlp_solve_mlp_problem (mlp);
 214   return res;
 215 }
 216
 217 /**
 218  * Init the MLP problem solving component
 219  *
 220  * @param stats the GNUNET_STATISTICS handle
 221  * @param max_duration maximum numbers of iterations for the LP/MLP Solver
 222  * @param max_iterations maximum time limit for the LP/MLP Solver
 223  * @return GNUNET_OK on success, GNUNET_SYSERR on fail
 224  */
 225 int
 226 GAS_mlp_init (const struct GNUNET_STATISTICS_Handle *stats,
 227               struct GNUNET_TIME_Relative max_duration,
 228               unsigned int max_iterations)
 229 {
 230   GAS_mlp = GNUNET_malloc (sizeof (struct GAS_MLP_Handle));
 231
 232   /* Init GLPK environment */
 233   GNUNET_assert (glp_init_env() == 0);
 234
 235   /* Create initial MLP problem */
 236   GAS_mlp->prob = glp_create_prob();
 237   GNUNET_assert (GAS_mlp->prob != NULL);
 238
 239   GAS_mlp->stats = (struct GNUNET_STATISTICS_Handle *) stats;
 240   GAS_mlp->max_iterations = max_iterations;
 241   GAS_mlp->max_exec_duration = max_duration;
 242
 243   /* Init LP solving parameters */
 244   glp_init_smcp(&GAS_mlp->control_param_lp);
 245 #if DEBUG_MLP
 246   GAS_mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
 247 #else
 248   GAS_mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
 249 #endif
 250   GAS_mlp->control_param_lp.it_lim = max_iterations;
 251   GAS_mlp->control_param_lp.tm_lim = max_duration.rel_value;
 252
 253   /* Init MLP solving parameters */
 254   glp_init_iocp(&GAS_mlp->control_param_mlp);
 255 #if DEBUG_MLP
 256   GAS_mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
 257 #else
 258   GAS_mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
 259 #endif
 260   GAS_mlp->control_param_mlp.tm_lim = max_duration.rel_value;
 261
 262   GAS_mlp->last_execution = GNUNET_TIME_absolute_get_forever();
 263   return GNUNET_OK;
 264 }
 265
 266 /**
 267  * Updates a single address in the MLP problem
 268  *
 269  * If the address did not exist before in the problem:
 270  * The MLP problem has to be recreated and the problem has to be resolved
 271  *
 272  * Otherwise the addresses' values can be updated and the existing base can
 273  * be reused
 274  */
 275 void
 276 GAS_mlp_address_update (struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
 277 {
 278   int new;
 279
 280   GNUNET_STATISTICS_update (GAS_mlp->stats,"# LP address updates", 1, GNUNET_NO);
 281
 282   /* We update a new address */
 283   if (address->mlp_information == NULL)
 284   {
 285     new = GNUNET_YES;
 286     address->mlp_information = GNUNET_malloc (sizeof (struct MLP_information));
 287   }
 288   else
 289     new = GNUNET_NO;
 290
 291   /* Do the update */
 292
 293   /* Recalculate */
 294   if (new == GNUNET_YES)
 295     GAS_mlp->presolver_required = GNUNET_YES;
 296   mlp_solve_problem (GAS_mlp);
 297 }
 298
 299 /**
 300  * Deletes a single address in the MLP problem
 301  *
 302  * The MLP problem has to be recreated and the problem has to be resolved
 303  */
 304 void
 305 GAS_mlp_address_delete (struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
 306 {
 307   GNUNET_STATISTICS_update (GAS_mlp->stats,"# LP address deletions", 1, GNUNET_NO);
 308
 309   /* Free resources */
 310   if (address->mlp_information != NULL)
 311   {
 312     GNUNET_free (address->mlp_information);
 313     address->mlp_information = NULL;
 314   }
 315
 316   /* Update problem */
 317
 318   /* Recalculate */
 319   GAS_mlp->presolver_required = GNUNET_YES;
 320   mlp_solve_problem (GAS_mlp);
 321 }
 322
 323 /**
 324  * Deletes a single address in the MLP problem
 325  */
 326 void
 327 GAS_mlp_address_change_preference (struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
 328 {
 329   GNUNET_STATISTICS_update (GAS_mlp->stats,"# LP address preference changes", 1, GNUNET_NO);
 330
 331
 332 }
 333
 334 /**
 335  * Shutdown the MLP problem solving component
 336  */
 337 void
 338 GAS_mlp_done ()
 339 {
 340   if (GAS_mlp != NULL)
 341     glp_delete_prob(GAS_mlp->prob);
 342
 343   /* Clean up GLPK environment */
 344   glp_free_env();
 345
 346   GNUNET_free (GAS_mlp);
 347 }
 348
 349
 350 /* end of gnunet-service-ats_addresses_mlp.c */