src/ats/plugin_ats_mlp.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2011-2014 GNUnet e.V.
   4
   5      GNUnet is free software: you can redistribute it and/or modify it
   6      under the terms of the GNU Affero General Public License as published
   7      by the Free Software Foundation, either version 3 of the License,
   8      or (at your 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      Affero General Public License for more details.
  14 */
  15
  16 /**
  17  * @file ats/plugin_ats_mlp.c
  18  * @brief ats mlp problem solver
  19  * @author Matthias Wachs
  20  * @author Christian Grothoff
  21  */
  22 #include "platform.h"
  23 #include "gnunet_util_lib.h"
  24 #include "gnunet_ats_service.h"
  25 #include "gnunet_ats_plugin.h"
  26 #include "gnunet-service-ats_addresses.h"
  27 #include "gnunet_statistics_service.h"
  28 #include <float.h>
  29 #include <glpk.h>
  30
  31
  32 #define BIG_M_VALUE (UINT32_MAX) /10
  33 #define BIG_M_STRING "unlimited"
  34
  35 #define MLP_AVERAGING_QUEUE_LENGTH 3
  36
  37 #define MLP_MAX_EXEC_DURATION   GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 10)
  38 #define MLP_MAX_ITERATIONS      4096
  39
  40 #define MLP_DEFAULT_D 1.0
  41 #define MLP_DEFAULT_R 1.0
  42 #define MLP_DEFAULT_U 1.0
  43 #define MLP_DEFAULT_QUALITY 1.0
  44 #define MLP_DEFAULT_MIN_CONNECTIONS 4
  45 #define MLP_DEFAULT_PEER_PREFERENCE 1.0
  46
  47 #define MLP_NaN -1
  48 #define MLP_UNDEFINED 0
  49 #define GLP_YES 1.0
  50 #define GLP_NO  0.0
  51
  52 enum MLP_Output_Format
  53 {
  54   MLP_MPS,
  55   MLP_CPLEX,
  56   MLP_GLPK
  57 };
  58
  59
  60 enum QualityMetrics
  61 {
  62   RQ_QUALITY_METRIC_DELAY = 0,
  63   RQ_QUALITY_METRIC_DISTANCE = 1,
  64   RQ_QUALITY_METRIC_COUNT = 2
  65 };
  66
  67
  68 static const char *
  69 print_quality_type (enum QualityMetrics qm)
  70 {
  71   switch (qm){
  72   case RQ_QUALITY_METRIC_DELAY:
  73     return "delay";
  74   case RQ_QUALITY_METRIC_DISTANCE:
  75     return "distance";
  76   default:
  77     GNUNET_break (0);
  78     return NULL;
  79   }
  80 }
  81
  82
  83 struct MLP_Solution
  84 {
  85   int lp_res;
  86   int lp_presolv;
  87   int mip_res;
  88   int mip_presolv;
  89
  90   double lp_objective_value;
  91   double mlp_objective_value;
  92   double mlp_gap;
  93   double lp_mlp_gap;
  94
  95   int p_elements;
  96   int p_cols;
  97   int p_rows;
  98
  99   int n_peers;
 100   int n_addresses;
 101
 102 };
 103
 104 struct ATS_Peer
 105 {
 106   struct GNUNET_PeerIdentity id;
 107
 108   /* Was this peer already added to the current problem? */
 109   int processed;
 110
 111   /* constraint 2: 1 address per peer*/
 112   unsigned int r_c2;
 113
 114   /* constraint 9: relativity */
 115   unsigned int r_c9;
 116
 117   /* Legacy preference value */
 118   double f;
 119 };
 120
 121 struct MLP_Problem
 122 {
 123   /**
 124    * GLPK (MLP) problem object
 125    */
 126   glp_prob *prob;
 127
 128   /* Number of addresses in problem */
 129   unsigned int num_addresses;
 130   /* Number of peers in problem */
 131   unsigned int num_peers;
 132   /* Number of elements in problem matrix */
 133   unsigned int num_elements;
 134
 135   /* Row index constraint 2: */
 136   unsigned int r_c2;
 137   /* Row index constraint 4: minimum connections */
 138   unsigned int r_c4;
 139   /* Row index constraint 6: maximize diversity */
 140   unsigned int r_c6;
 141   /* Row index constraint 8: utilization*/
 142   unsigned int r_c8;
 143   /* Row index constraint 9: relativity*/
 144   unsigned int r_c9;
 145   /* Row indices quality metrics  */
 146   int r_q[RQ_QUALITY_METRIC_COUNT];
 147   /* Row indices ATS network quotas */
 148   int r_quota[GNUNET_ATS_NetworkTypeCount];
 149
 150   /* Column index Diversity (D) column */
 151   int c_d;
 152   /* Column index Utilization (U) column */
 153   int c_u;
 154   /* Column index Proportionality (R) column */
 155   int c_r;
 156   /* Column index quality metrics  */
 157   int c_q[RQ_QUALITY_METRIC_COUNT];
 158
 159   /* Problem matrix */
 160   /* Current index */
 161   unsigned int ci;
 162   /* Row index array */
 163   int *ia;
 164   /* Column index array */
 165   int *ja;
 166   /* Column index value */
 167   double *ar;
 168
 169 };
 170
 171 struct MLP_Variables
 172 {
 173   /* Big M value for bandwidth capping */
 174   double BIG_M;
 175
 176   /* MIP Gap */
 177   double mip_gap;
 178
 179   /* LP MIP Gap */
 180   double lp_mip_gap;
 181
 182   /* Number of quality metrics @deprecated, use RQ_QUALITY_METRIC_COUNT */
 183   int m_q;
 184
 185   /* Number of quality metrics */
 186   int m_rc;
 187
 188   /* Quality metric coefficients*/
 189   double co_Q[RQ_QUALITY_METRIC_COUNT];
 190
 191   /* Ressource costs coefficients*/
 192   double co_RC[RQ_QUALITY_METRIC_COUNT];
 193
 194   /* Diversity coefficient */
 195   double co_D;
 196
 197   /* Utility coefficient */
 198   double co_U;
 199
 200   /* Relativity coefficient */
 201   double co_R;
 202
 203   /* Minimum bandwidth assigned to an address */
 204   unsigned int b_min;
 205
 206   /* Minimum number of addresses with bandwidth assigned */
 207   unsigned int n_min;
 208
 209   /* Quotas */
 210   /* Array mapping array index to ATS network */
 211   int quota_index[GNUNET_ATS_NetworkTypeCount];
 212   /* Outbound quotas */
 213   unsigned long long quota_out[GNUNET_ATS_NetworkTypeCount];
 214   /* Inbound quotas */
 215
 216   unsigned long long quota_in[GNUNET_ATS_NetworkTypeCount];
 217
 218   /* ATS ressource costs
 219    * array with GNUNET_ATS_QualityPropertiesCount elements
 220    * contains mapping to GNUNET_ATS_Property
 221    * */
 222   int rc[RQ_QUALITY_METRIC_COUNT];
 223
 224 };
 225
 226 /**
 227  * MLP Handle
 228  */
 229 struct GAS_MLP_Handle
 230 {
 231   struct GNUNET_ATS_PluginEnvironment *env;
 232
 233   /**
 234    * Exclude peer from next result propagation
 235    */
 236   const struct GNUNET_PeerIdentity *exclude_peer;
 237
 238   /**
 239    * Encapsulation for the MLP problem
 240    */
 241   struct MLP_Problem p;
 242
 243   /**
 244    * Encapsulation for the MLP problem variables
 245    */
 246   struct MLP_Variables pv;
 247
 248   /**
 249    * Encapsulation for the MLP solution
 250    */
 251   struct MLP_Solution ps;
 252
 253   /**
 254    * Bulk lock
 255    */
 256   int stat_bulk_lock;
 257
 258   /**
 259    * Number of changes while solver was locked
 260    */
 261   int stat_bulk_requests;
 262
 263   /**
 264    * GLPK LP control parameter
 265    */
 266   glp_smcp control_param_lp;
 267
 268   /**
 269    * GLPK LP control parameter
 270    */
 271   glp_iocp control_param_mlp;
 272
 273   /**
 274    * Peers with pending address requests
 275    */
 276   struct GNUNET_CONTAINER_MultiPeerMap *requested_peers;
 277
 278   /**
 279    * Was the problem updated since last solution
 280    */
 281   int stat_mlp_prob_updated;
 282
 283   /**
 284    * Has the problem size changed since last solution
 285    */
 286   int stat_mlp_prob_changed;
 287
 288   /**
 289    * Solve the problem automatically when updates occur?
 290    * Default: GNUNET_YES
 291    * Can be disabled for test and measurements
 292    */
 293   int opt_mlp_auto_solve;
 294
 295   /**
 296    * Write all MILP problems to a MPS file
 297    */
 298   int opt_dump_problem_all;
 299
 300   /**
 301    * Write all MILP problem solutions to a file
 302    */
 303   int opt_dump_solution_all;
 304
 305   /**
 306    * Write MILP problems to a MPS file when solver fails
 307    */
 308   int opt_dump_problem_on_fail;
 309
 310   /**
 311    * Write MILP problem solutions to a file when solver fails
 312    */
 313   int opt_dump_solution_on_fail;
 314
 315   /**
 316    * solve feasibility only
 317    */
 318   int opt_dbg_feasibility_only;
 319
 320   /**
 321    * solve autoscale the problem
 322    */
 323   int opt_dbg_autoscale_problem;
 324
 325   /**
 326    * use the intopt presolver instead of simplex
 327    */
 328   int opt_dbg_intopt_presolver;
 329
 330   /**
 331    * Print GLPK output
 332    */
 333   int opt_dbg_glpk_verbose;
 334
 335   /**
 336    * solve autoscale the problem
 337    */
 338   int opt_dbg_optimize_relativity;
 339
 340   /**
 341    * solve autoscale the problem
 342    */
 343   int opt_dbg_optimize_diversity;
 344
 345   /**
 346    * solve autoscale the problem
 347    */
 348   int opt_dbg_optimize_quality;
 349
 350   /**
 351    * solve autoscale the problem
 352    */
 353   int opt_dbg_optimize_utility;
 354
 355
 356   /**
 357    * Output format
 358    */
 359   enum MLP_Output_Format opt_log_format;
 360 };
 361
 362 /**
 363  * Address specific MLP information
 364  */
 365 struct MLP_information
 366 {
 367
 368   /**
 369    * Bandwidth assigned outbound
 370    */
 371   uint32_t b_out;
 372
 373   /**
 374    * Bandwidth assigned inbound
 375    */
 376   uint32_t b_in;
 377
 378   /**
 379    * Address selected
 380    */
 381   int n;
 382
 383   /**
 384    * bandwidth column index
 385    */
 386   signed int c_b;
 387
 388   /**
 389    * address usage column
 390    */
 391   signed int c_n;
 392
 393   /* row indexes */
 394
 395   /**
 396    * constraint 1: bandwidth capping
 397    */
 398   unsigned int r_c1;
 399
 400   /**
 401    * constraint 3: minimum bandwidth
 402    */
 403   unsigned int r_c3;
 404 };
 405
 406
 407
 408 /**
 409  *
 410  * NOTE: Do not modify this documentation. This documentation is based on
 411  * gnunet.org:/vcs/fsnsg/ats-paper.git/tech-doku/ats-tech-guide.tex
 412  * use build_txt.sh to generate plaintext output
 413  *
 414  *    The MLP solver (mlp) tries to finds an optimal bandwidth assignmentby
 415  *    optimizing an mixed integer programming problem. The MLP solver uses a
 416  *    number of constraints to find the best adddress for a peer and an optimal
 417  *    bandwidth assignment. mlp uses the GNU Linear Programming Kit to solve the
 418  *    MLP problem.
 419  *
 420  *    We defined a constraint system to find an optimal bandwidth assignment.
 421  *    This constraint system uses as an input data addresses, bandwidth quotas,
 422  *    preferences and quality values. This constraint system is stored in an
 423  *    matrix based equotation system.
 424  *
 425  *   5 Using GLPK
 426  *
 427  *    A (M)LP problem consists of a target function to optimizes, constraints
 428  *    and rows and columns. FIXME GLP uses three arrays to index the matrix: two
 429  *    integer arrays storing the row and column indices in the matrix and an
 430  *    float array to store the coeeficient.
 431  *
 432  *    To solve the problem we first find an initial solution for the LP problem
 433  *    using the LP solver and then find an MLP solution based on this solution
 434  *    using the MLP solver.
 435  *
 436  *    Solving (M)LP problems has the property that finding an initial solution
 437  *    for the LP problem is computationally expensive and finding the MLP
 438  *    solution is cheaper. This is especially interesting an existing LP
 439  *    solution can be reused if only coefficients in the matrix have changed
 440  *    (addresses updated). Only when the problem size changes (addresses added
 441  *    or deleted) a new LP solution has to be found.
 442  *
 443  *    Intended usage
 444  *    The mlp solver solves the bandwidth assignment problem only on demand when
 445  *    an address suggestion is requested. When an address is requested mlp the
 446  *    solves the mlp problem and if the active address or the bandwidth assigned
 447  *    changes it calls the callback to addresses. The mlp solver gets notified
 448  *    about new addresses (adding sessions), removed addresses (address
 449  *    deletions) and address updates. To benefit from the mlp properties
 450  *    mentioned in section 5 the solver rembers if since the last solution
 451  *    addresses were added or deleted (problem size changed, problem has to be
 452  *    rebuild and solved from sratch) or if addresses were updated and the
 453  *    existing solution can be reused.
 454  *
 455  *     5.1 Input data
 456  *
 457  *    The quotas for each network segment are passed by addresses. MLP can be
 458  *    adapted using configuration settings and uses the following parameters:
 459  *      * MLP_MAX_DURATION:
 460  *        Maximum duration for a MLP solution procees (default: 3 sec.)
 461  *      * MLP_MAX_ITERATIONS:
 462  *        Maximum number of iterations for a MLP solution process (default:
 463  *        1024)
 464  *      * MLP_MIN_CONNECTIONS:
 465  *        Minimum number of desired connections (default: 4)
 466  *      * MLP_MIN_BANDWIDTH:
 467  *        Minimum amount of bandwidth assigned to an address (default: 1024)
 468  *      * MLP_COEFFICIENT_D:
 469  *        Diversity coefficient (default: 1.0)
 470  *      * MLP_COEFFICIENT_R:
 471  *        Relativity coefficient (default: 1.0)
 472  *      * MLP_COEFFICIENT_U:
 473  *        Utilization coefficient (default: 1.0)
 474  *      * MLP_COEFFICIENT_D:
 475  *        Diversity coefficient (default: 1.0)
 476  *      * MLP_COEFFICIENT_QUALITY_DELAY:
 477  *        Quality delay coefficient (default: 1.0)
 478  *      * MLP_COEFFICIENT_QUALITY_DISTANCE:
 479  *        Quality distance coefficient (default: 1.0)
 480  *      * MLP_COEFFICIENT_QUALITY_DISTANCE:
 481  *        Quality distance coefficient (default: 1.0)
 482  *      * MLP_COEFFICIENT_QUALITY_DISTANCE:
 483  *        Quality distance coefficient (default: 1.0)
 484  *      * MLP_COEFFICIENT_QUALITY_DISTANCE:
 485  *        Quality distance coefficient (default: 1.0)
 486  *
 487  *     5.2 Data structures used
 488  *
 489  *    mlp has for each known peer a struct ATS_Peer containing information about
 490  *    a specific peer. The address field solver_information contains information
 491  *    about the mlp properties of this address.
 492  *
 493  *     5.3 Initializing
 494  *
 495  *    During initialization mlp initializes the GLPK libray used to solve the
 496  *    MLP problem: it initializes the glpk environment and creates an initial LP
 497  *    problem. Next it loads the configuration values from the configuration or
 498  *    uses the default values configured in -addresses_mlp.h. The quotas used
 499  *    are given by addresses but may have to be adjusted. mlp uses a upper limit
 500  *    for the bandwidth assigned called BIG M and a minimum amount of bandwidth
 501  *    an address gets assigned as well as a minium desired number of
 502  *    connections. If the configured quota is bigger than BIG M, it is reduced
 503  *    to BIG M. If the configured quota is smaller than MLP_MIN_CONNECTIONS
 504  *    *MLP_MIN_BANDWIDTH it is increased to this value.
 505  *
 506  *     5.4 Shutdown
 507
 508  */
 509
 510 #define LOG(kind,...) GNUNET_log_from (kind, "ats-mlp",__VA_ARGS__)
 511
 512 /**
 513  * Print debug output for mlp problem creation
 514  */
 515 #define DEBUG_MLP_PROBLEM_CREATION GNUNET_NO
 516
 517
 518 /**
 519  * Intercept GLPK terminal output
 520  * @param info the mlp handle
 521  * @param s the string to print
 522  * @return 0: glpk prints output on terminal, 0 != surpress output
 523  */
 524 static int
 525 mlp_term_hook (void *info, const char *s)
 526 {
 527   struct GAS_MLP_Handle *mlp = info;
 528
 529   if (mlp->opt_dbg_glpk_verbose)
 530     LOG (GNUNET_ERROR_TYPE_ERROR, "%s", s);
 531   return 1;
 532 }
 533
 534
 535 /**
 536  * Reset peers for next problem creation
 537  *
 538  * @param cls not used
 539  * @param key the key
 540  * @param value ATS_Peer
 541  * @return #GNUNET_OK
 542  */
 543 static int
 544 reset_peers (void *cls,
 545              const struct GNUNET_PeerIdentity *key,
 546              void *value)
 547  {
 548    struct ATS_Peer *peer = value;
 549    peer->processed = GNUNET_NO;
 550    return GNUNET_OK;
 551  }
 552
 553 /**
 554  * Delete the MLP problem and free the constrain matrix
 555  *
 556  * @param mlp the MLP handle
 557  */
 558 static void
 559 mlp_delete_problem (struct GAS_MLP_Handle *mlp)
 560 {
 561   int c;
 562   if (mlp == NULL)
 563     return;
 564   if (mlp->p.prob != NULL)
 565   {
 566     glp_delete_prob(mlp->p.prob);
 567     mlp->p.prob = NULL;
 568   }
 569
 570   /* delete row index */
 571   if (mlp->p.ia != NULL)
 572   {
 573     GNUNET_free (mlp->p.ia);
 574     mlp->p.ia = NULL;
 575   }
 576
 577   /* delete column index */
 578   if (mlp->p.ja != NULL)
 579   {
 580     GNUNET_free (mlp->p.ja);
 581     mlp->p.ja = NULL;
 582   }
 583
 584   /* delete coefficients */
 585   if (mlp->p.ar != NULL)
 586   {
 587     GNUNET_free (mlp->p.ar);
 588     mlp->p.ar = NULL;
 589   }
 590   mlp->p.ci = 0;
 591   mlp->p.prob = NULL;
 592
 593   mlp->p.c_d = MLP_UNDEFINED;
 594   mlp->p.c_r = MLP_UNDEFINED;
 595   mlp->p.r_c2 = MLP_UNDEFINED;
 596   mlp->p.r_c4 = MLP_UNDEFINED;
 597   mlp->p.r_c6 = MLP_UNDEFINED;
 598   mlp->p.r_c9 = MLP_UNDEFINED;
 599   for (c = 0; c < RQ_QUALITY_METRIC_COUNT ; c ++)
 600     mlp->p.r_q[c] = MLP_UNDEFINED;
 601   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c ++)
 602     mlp->p.r_quota[c] = MLP_UNDEFINED;
 603   mlp->p.ci = MLP_UNDEFINED;
 604
 605
 606   GNUNET_CONTAINER_multipeermap_iterate (mlp->requested_peers,
 607                                          &reset_peers, NULL);
 608 }
 609
 610
 611 /**
 612  * Translate glpk status error codes to text
 613  * @param retcode return code
 614  * @return string with result
 615  */
 616 static const char *
 617 mlp_status_to_string (int retcode)
 618 {
 619   switch (retcode) {
 620     case GLP_UNDEF:
 621       return "solution is undefined";
 622     case GLP_FEAS:
 623       return "solution is feasible";
 624     case GLP_INFEAS:
 625       return "solution is infeasible";
 626     case GLP_NOFEAS:
 627       return "no feasible solution exists";
 628     case GLP_OPT:
 629       return "solution is optimal";
 630     case GLP_UNBND:
 631       return "solution is unbounded";
 632     default:
 633       GNUNET_break (0);
 634       return "unknown error";
 635   }
 636 }
 637
 638
 639 /**
 640  * Translate glpk solver error codes to text
 641  * @param retcode return code
 642  * @return string with result
 643  */
 644 static const char *
 645 mlp_solve_to_string (int retcode)
 646 {
 647   switch (retcode) {
 648     case 0:
 649       return "ok";
 650     case GLP_EBADB:
 651       return "invalid basis";
 652     case GLP_ESING:
 653       return "singular matrix";
 654     case GLP_ECOND:
 655       return "ill-conditioned matrix";
 656     case GLP_EBOUND:
 657       return "invalid bounds";
 658     case GLP_EFAIL:
 659       return "solver failed";
 660     case GLP_EOBJLL:
 661       return "objective lower limit reached";
 662     case GLP_EOBJUL:
 663       return "objective upper limit reached";
 664     case GLP_EITLIM:
 665       return "iteration limit exceeded";
 666     case GLP_ETMLIM:
 667       return "time limit exceeded";
 668     case GLP_ENOPFS:
 669       return "no primal feasible solution";
 670     case GLP_ENODFS:
 671       return "no dual feasible solution";
 672     case GLP_EROOT:
 673       return "root LP optimum not provided";
 674     case GLP_ESTOP:
 675       return "search terminated by application";
 676     case GLP_EMIPGAP:
 677       return "relative mip gap tolerance reached";
 678     case GLP_ENOFEAS:
 679       return "no dual feasible solution";
 680     case GLP_ENOCVG:
 681       return "no convergence";
 682     case GLP_EINSTAB:
 683       return "numerical instability";
 684     case GLP_EDATA:
 685       return "invalid data";
 686     case GLP_ERANGE:
 687       return "result out of range";
 688     default:
 689       GNUNET_break (0);
 690       return "unknown error";
 691   }
 692 }
 693
 694
 695 struct CountContext
 696 {
 697   const struct GNUNET_CONTAINER_MultiPeerMap *map;
 698   int result;
 699 };
 700
 701 static int
 702 mlp_create_problem_count_addresses_it (void *cls,
 703                                        const struct GNUNET_PeerIdentity *key,
 704                                        void *value)
 705 {
 706   struct CountContext *cctx = cls;
 707
 708   /* Check if we have to add this peer due to a pending request */
 709   if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (cctx->map, key))
 710     cctx->result++;
 711   return GNUNET_OK;
 712 }
 713
 714
 715 static int
 716 mlp_create_problem_count_addresses (const struct GNUNET_CONTAINER_MultiPeerMap *requested_peers,
 717                                     const struct GNUNET_CONTAINER_MultiPeerMap *addresses)
 718 {
 719   struct CountContext cctx;
 720
 721   cctx.map = requested_peers;
 722   cctx.result = 0;
 723   GNUNET_CONTAINER_multipeermap_iterate (addresses,
 724            &mlp_create_problem_count_addresses_it, &cctx);
 725   return cctx.result;
 726 }
 727
 728
 729 static int
 730 mlp_create_problem_count_peers_it (void *cls,
 731                                    const struct GNUNET_PeerIdentity *key,
 732                                    void *value)
 733 {
 734   struct CountContext *cctx = cls;
 735
 736   /* Check if we have to addresses for the requested peer */
 737   if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (cctx->map, key))
 738     cctx->result++;
 739   return GNUNET_OK;
 740 }
 741
 742
 743 static int
 744 mlp_create_problem_count_peers (const struct GNUNET_CONTAINER_MultiPeerMap *requested_peers,
 745     const struct GNUNET_CONTAINER_MultiPeerMap *addresses)
 746 {
 747   struct CountContext cctx;
 748
 749   cctx.map = addresses;
 750   cctx.result = 0;
 751   GNUNET_CONTAINER_multipeermap_iterate (requested_peers,
 752            &mlp_create_problem_count_peers_it, &cctx);
 753   return cctx.result;
 754 }
 755
 756
 757 /**
 758  * Updates an existing value in the matrix
 759  *
 760  * Extract the row, updates the value and updates the row in the problem
 761  *
 762  * @param p the mlp problem
 763  * @param row the row to create the value in
 764  * @param col the column to create the value in
 765  * @param val the value to set
 766  * @param line calling line for debbuging
 767  * @return GNUNET_YES value changed, GNUNET_NO value did not change, GNUNET_SYSERR
 768  * on error
 769  */
 770 static int
 771 mlp_create_problem_update_value (struct MLP_Problem *p,
 772                               int row, int col, double val,
 773                               int line)
 774 {
 775   int c_cols;
 776   int c_elems;
 777   int c1;
 778   int res;
 779   int found;
 780   double *val_array;
 781   int *ind_array;
 782
 783   GNUNET_assert (NULL != p->prob);
 784
 785   /* Get number of columns and prepare data structure */
 786   c_cols = glp_get_num_cols(p->prob);
 787   if (0 >= c_cols)
 788     return GNUNET_SYSERR;
 789
 790   val_array = GNUNET_malloc ((c_cols +1)* sizeof (double));
 791   GNUNET_assert (NULL != val_array);
 792   ind_array = GNUNET_malloc ((c_cols+1) * sizeof (int));
 793   GNUNET_assert (NULL != ind_array);
 794   /* Extract the row */
 795
 796   /* Update the value */
 797   c_elems = glp_get_mat_row (p->prob, row, ind_array, val_array);
 798   found = GNUNET_NO;
 799   for (c1 = 1; c1 < (c_elems+1); c1++)
 800   {
 801     if (ind_array[c1] == col)
 802     {
 803       found = GNUNET_YES;
 804       break;
 805     }
 806   }
 807   if (GNUNET_NO == found)
 808   {
 809     ind_array[c_elems+1] = col;
 810     val_array[c_elems+1] = val;
 811     LOG (GNUNET_ERROR_TYPE_DEBUG, "[P] Setting value in [%s : %s] to `%.2f'\n",
 812         glp_get_row_name (p->prob, row), glp_get_col_name (p->prob, col),
 813         val);
 814     glp_set_mat_row (p->prob, row, c_elems+1, ind_array, val_array);
 815     GNUNET_free (ind_array);
 816     GNUNET_free (val_array);
 817     return GNUNET_YES;
 818   }
 819   else
 820   {
 821     /* Update value */
 822     LOG (GNUNET_ERROR_TYPE_DEBUG, "[P] Updating value in [%s : %s] from `%.2f' to `%.2f'\n",
 823         glp_get_row_name (p->prob, row), glp_get_col_name (p->prob, col),
 824         val_array[c1], val);
 825     if (val != val_array[c1])
 826       res = GNUNET_YES;
 827     else
 828       res = GNUNET_NO;
 829     val_array[c1] = val;
 830     /* Update the row in the matrix */
 831     glp_set_mat_row (p->prob, row, c_elems, ind_array, val_array);
 832   }
 833
 834   GNUNET_free (ind_array);
 835   GNUNET_free (val_array);
 836   return res;
 837 }
 838
 839 /**
 840  * Creates a new value in the matrix
 841  *
 842  * Sets the row and column index in the problem array and increments the
 843  * position field
 844  *
 845  * @param p the mlp problem
 846  * @param row the row to create the value in
 847  * @param col the column to create the value in
 848  * @param val the value to set
 849  * @param line calling line for debbuging
 850  */
 851 static void
 852 mlp_create_problem_set_value (struct MLP_Problem *p,
 853                               int row, int col, double val,
 854                               int line)
 855 {
 856   if ((p->ci) >= p->num_elements)
 857   {
 858     LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: line %u: Request for index %u bigger than array size of %u\n",
 859         line, p->ci + 1, p->num_elements);
 860     GNUNET_break (0);
 861     return;
 862   }
 863   if ((0 == row) || (0 == col))
 864   {
 865     GNUNET_break (0);
 866     LOG (GNUNET_ERROR_TYPE_ERROR, "[P]: Invalid call from line %u: row = %u, col = %u\n",
 867         line, row, col);
 868   }
 869   p->ia[p->ci] = row ;
 870   p->ja[p->ci] = col;
 871   p->ar[p->ci] = val;
 872 #if  DEBUG_MLP_PROBLEM_CREATION
 873   LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: line %u: Set value [%u,%u] in index %u ==  %.2f\n",
 874       line, p->ia[p->ci], p->ja[p->ci], p->ci, p->ar[p->ci]);
 875 #endif
 876   p->ci++;
 877 }
 878
 879 static int
 880 mlp_create_problem_create_column (struct MLP_Problem *p, char *name,
 881     unsigned int type, unsigned int bound, double lb, double ub,
 882     double coef)
 883 {
 884   int col = glp_add_cols (p->prob, 1);
 885   glp_set_col_name (p->prob, col, name);
 886   glp_set_col_bnds (p->prob, col, bound, lb, ub);
 887   glp_set_col_kind (p->prob, col, type);
 888   glp_set_obj_coef (p->prob, col, coef);
 889 #if  DEBUG_MLP_PROBLEM_CREATION
 890   LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%u] `%s': %.2f\n",
 891       col, name, coef);
 892 #endif
 893   return col;
 894 }
 895
 896 static int
 897 mlp_create_problem_create_constraint (struct MLP_Problem *p, char *name,
 898     unsigned int bound, double lb, double ub)
 899 {
 900   char * op;
 901   int row = glp_add_rows (p->prob, 1);
 902   /* set row name */
 903   glp_set_row_name (p->prob, row, name);
 904   /* set row bounds: <= 0 */
 905   glp_set_row_bnds (p->prob, row, bound, lb, ub);
 906   switch (bound)
 907   {
 908     case GLP_UP:
 909             GNUNET_asprintf(&op, "-inf <= x <= %.2f", ub);
 910             break;
 911     case GLP_DB:
 912             GNUNET_asprintf(&op, "%.2f <= x <= %.2f", lb, ub);
 913             break;
 914     case GLP_FX:
 915             GNUNET_asprintf(&op, "%.2f == x == %.2f", lb, ub);
 916             break;
 917     case GLP_LO:
 918             GNUNET_asprintf(&op, "%.2f <= x <= inf", lb);
 919             break;
 920     default:
 921             GNUNET_asprintf(&op, "ERROR");
 922             break;
 923   }
 924 #if  DEBUG_MLP_PROBLEM_CREATION
 925     LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s\n",
 926         row, name, op);
 927 #endif
 928   GNUNET_free (op);
 929   return row;
 930 }
 931
 932 /**
 933  * Create the
 934  * - address columns b and n
 935  * - address dependent constraint rows c1, c3
 936  * - peer dependent rows c2 and c9
 937  * - Set address dependent entries in problem matrix as well
 938  */
 939 static int
 940 mlp_create_problem_add_address_information (void *cls,
 941                                             const struct GNUNET_PeerIdentity *key,
 942                                             void *value)
 943 {
 944   struct GAS_MLP_Handle *mlp = cls;
 945   struct MLP_Problem *p = &mlp->p;
 946   struct ATS_Address *address = value;
 947   struct ATS_Peer *peer;
 948   struct MLP_information *mlpi;
 949   char *name;
 950   double cur_bigm;
 951   uint32_t addr_net;
 952   uint32_t addr_net_index;
 953   unsigned long long max_quota;
 954   int c;
 955
 956   /* Check if we have to add this peer due to a pending request */
 957   if (GNUNET_NO == GNUNET_CONTAINER_multipeermap_contains(mlp->requested_peers, key))
 958     return GNUNET_OK;
 959
 960   mlpi = address->solver_information;
 961   if (NULL == mlpi)
 962   {
 963       fprintf (stderr, "%s %p\n",GNUNET_i2s (&address->peer), address);
 964       GNUNET_break (0);
 965       return GNUNET_OK;
 966   }
 967
 968   addr_net = address->properties.scope;
 969   for (addr_net_index = 0; addr_net_index < GNUNET_ATS_NetworkTypeCount; addr_net_index++)
 970   {
 971     if (mlp->pv.quota_index[addr_net_index] == addr_net)
 972       break;
 973   }
 974
 975   if (addr_net_index >= GNUNET_ATS_NetworkTypeCount)
 976   {
 977     GNUNET_break (0);
 978     return GNUNET_OK;
 979   }
 980
 981   max_quota = 0;
 982   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
 983   {
 984     if (mlp->pv.quota_out[c] > max_quota)
 985       max_quota = mlp->pv.quota_out[c];
 986     if (mlp->pv.quota_in[c] > max_quota)
 987       max_quota = mlp->pv.quota_in[c];
 988   }
 989   if (max_quota > mlp->pv.BIG_M)
 990     cur_bigm = (double) mlp->pv.BIG_M;
 991   else
 992     cur_bigm = max_quota;
 993
 994
 995   /* Get peer */
 996   peer = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers, key);
 997   GNUNET_assert (NULL != peer);
 998   if (peer->processed == GNUNET_NO)
 999   {
1000       /* Add peer dependent constraints */
1001       /* Add c2) One address active per peer */
1002       GNUNET_asprintf(&name, "c2_%s", GNUNET_i2s(&address->peer));
1003       peer->r_c2 = mlp_create_problem_create_constraint (p, name, GLP_FX, 1.0, 1.0);
1004       GNUNET_free (name);
1005       if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1006       {
1007         if (GNUNET_YES == mlp->opt_dbg_optimize_relativity)
1008         {
1009           /* Add c9) Relativity */
1010           GNUNET_asprintf(&name, "c9_%s", GNUNET_i2s(&address->peer));
1011           peer->r_c9 = mlp_create_problem_create_constraint (p, name, GLP_LO, 0.0, 0.0);
1012           GNUNET_free (name);
1013           /* c9) set coefficient */
1014           mlp_create_problem_set_value (p, peer->r_c9, p->c_r, -peer->f , __LINE__);
1015         }
1016       }
1017       peer->processed = GNUNET_YES;
1018   }
1019
1020   /* Reset addresses' solver information */
1021   mlpi->c_b = 0;
1022   mlpi->c_n = 0;
1023   mlpi->n = 0;
1024   mlpi->r_c1 = 0;
1025   mlpi->r_c3 = 0;
1026
1027   /* Add bandwidth column */
1028   GNUNET_asprintf (&name, "b_%s_%s_%p", GNUNET_i2s (&address->peer), address->plugin, address);
1029   if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1030   {
1031     mlpi->c_b = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, 0.0);
1032   }
1033   else
1034   {
1035     /* Maximize for bandwidth assignment in feasibility testing */
1036     mlpi->c_b = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, 1.0);
1037   }
1038   GNUNET_free (name);
1039
1040   /* Add address active column */
1041   GNUNET_asprintf (&name, "n_%s_%s_%p", GNUNET_i2s (&address->peer), address->plugin, address);
1042   mlpi->c_n = mlp_create_problem_create_column (p, name, GLP_IV, GLP_DB, 0.0, 1.0, 0.0);
1043   GNUNET_free (name);
1044
1045   /* Add address dependent constraints */
1046   /* Add c1) bandwidth capping: b_t  + (-M) * n_t <= 0 */
1047   GNUNET_asprintf(&name, "c1_%s_%s_%p", GNUNET_i2s(&address->peer), address->plugin, address);
1048   mlpi->r_c1 = mlp_create_problem_create_constraint (p, name, GLP_UP, 0.0, 0.0);
1049   GNUNET_free (name);
1050   /*  c1) set b = 1 coefficient */
1051   mlp_create_problem_set_value (p, mlpi->r_c1, mlpi->c_b, 1, __LINE__);
1052   /*  c1) set n = - min (M, quota) coefficient */
1053   cur_bigm = (double) mlp->pv.quota_out[addr_net_index];
1054   if (cur_bigm > mlp->pv.BIG_M)
1055     cur_bigm = (double) mlp->pv.BIG_M;
1056   mlp_create_problem_set_value (p, mlpi->r_c1, mlpi->c_n, -cur_bigm, __LINE__);
1057
1058   /* Add constraint c 3) minimum bandwidth
1059    * b_t + (-n_t * b_min) >= 0
1060    * */
1061   GNUNET_asprintf(&name, "c3_%s_%s_%p", GNUNET_i2s(&address->peer), address->plugin, address);
1062   mlpi->r_c3 = mlp_create_problem_create_constraint (p, name, GLP_LO, 0.0, 0.0);
1063   GNUNET_free (name);
1064
1065   /*  c3) set b = 1 coefficient */
1066   mlp_create_problem_set_value (p, mlpi->r_c3, mlpi->c_b, 1, __LINE__);
1067   /*  c3) set n = -b_min coefficient */
1068   mlp_create_problem_set_value (p, mlpi->r_c3, mlpi->c_n, - ((double )mlp->pv.b_min), __LINE__);
1069
1070
1071   /* Set coefficient entries in invariant rows */
1072
1073   /* Feasbility */
1074
1075   /* c 4) minimum connections */
1076   mlp_create_problem_set_value (p, p->r_c4, mlpi->c_n, 1, __LINE__);
1077   /* c 2) 1 address peer peer */
1078   mlp_create_problem_set_value (p, peer->r_c2, mlpi->c_n, 1, __LINE__);
1079   /* c 10) obey network specific quotas
1080    * (1)*b_1 + ... + (1)*b_m <= quota_n
1081    */
1082   mlp_create_problem_set_value (p, p->r_quota[addr_net_index], mlpi->c_b, 1, __LINE__);
1083
1084   /* Optimality */
1085   if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1086   {
1087     /* c 6) maximize diversity */
1088     mlp_create_problem_set_value (p, p->r_c6, mlpi->c_n, 1, __LINE__);
1089     /* c 9) relativity */
1090     if (GNUNET_YES == mlp->opt_dbg_optimize_relativity)
1091       mlp_create_problem_set_value (p, peer->r_c9, mlpi->c_b, 1, __LINE__);
1092     /* c 8) utility */
1093     if (GNUNET_YES == mlp->opt_dbg_optimize_utility)
1094       mlp_create_problem_set_value (p, p->r_c8, mlpi->c_b, 1, __LINE__);
1095     /* c 7) Optimize quality */
1096     /* For all quality metrics, set quality of this address */
1097     if (GNUNET_YES == mlp->opt_dbg_optimize_quality)
1098     {
1099       mlp_create_problem_set_value (p,
1100                                     p->r_q[RQ_QUALITY_METRIC_DELAY],
1101                                     mlpi->c_b,
1102                                     address->norm_delay.norm,
1103                                     __LINE__);
1104       mlp_create_problem_set_value (p,
1105                                     p->r_q[RQ_QUALITY_METRIC_DISTANCE],
1106                                     mlpi->c_b,
1107                                     address->norm_distance.norm,
1108                                     __LINE__);
1109     }
1110   }
1111
1112   return GNUNET_OK;
1113 }
1114
1115
1116 /**
1117  * Create the invariant columns c4, c6, c10, c8, c7
1118  */
1119 static void
1120 mlp_create_problem_add_invariant_rows (struct GAS_MLP_Handle *mlp, struct MLP_Problem *p)
1121 {
1122   int c;
1123
1124   /* Feasibility */
1125
1126   /* Row for c4) minimum connection */
1127   /* Number of minimum connections is min(|Peers|, n_min) */
1128   p->r_c4 = mlp_create_problem_create_constraint (p, "c4", GLP_LO, (mlp->pv.n_min > p->num_peers) ? p->num_peers : mlp->pv.n_min, 0.0);
1129
1130   /* Rows for c 10) Enforce network quotas */
1131   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
1132   {
1133     char * text;
1134     GNUNET_asprintf(&text, "c10_quota_ats_%s",
1135         GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]));
1136     p->r_quota[c] = mlp_create_problem_create_constraint (p, text, GLP_DB, 0.0, mlp->pv.quota_out[c]);
1137     GNUNET_free (text);
1138   }
1139
1140   /* Optimality */
1141   if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1142   {
1143     char *name;
1144     /* Add row for c6) Maximize for diversity */
1145     if (GNUNET_YES == mlp->opt_dbg_optimize_diversity)
1146     {
1147       p->r_c6 = mlp_create_problem_create_constraint (p, "c6", GLP_FX, 0.0, 0.0);
1148       /* Set c6 ) Setting -D */
1149       mlp_create_problem_set_value (p, p->r_c6, p->c_d, -1, __LINE__);
1150     }
1151
1152     /* Adding rows for c 8) Maximize utility */
1153     if (GNUNET_YES == mlp->opt_dbg_optimize_utility)
1154     {
1155       p->r_c8 = mlp_create_problem_create_constraint (p, "c8", GLP_FX, 0.0, 0.0);
1156       /* -u */
1157       mlp_create_problem_set_value (p, p->r_c8, p->c_u, -1, __LINE__);
1158     }
1159
1160     /* For all quality metrics:
1161      * c 7) Maximize quality, austerity */
1162     if (GNUNET_YES == mlp->opt_dbg_optimize_quality)
1163     {
1164       for (c = 0; c < mlp->pv.m_q; c++)
1165       {
1166         GNUNET_asprintf (&name,
1167                          "c7_q%i_%s", c,
1168                          print_quality_type (c));
1169         p->r_q[c] = mlp_create_problem_create_constraint (p, name, GLP_FX, 0.0, 0.0);
1170         GNUNET_free (name);
1171         mlp_create_problem_set_value (p,
1172                                       p->r_q[c],
1173                                       p->c_q[c], -1, __LINE__);
1174       }
1175     }
1176   }
1177 }
1178
1179
1180 /**
1181  * Create the invariant columns d, u, r, q0 ... qm
1182  */
1183 static void
1184 mlp_create_problem_add_invariant_columns (struct GAS_MLP_Handle *mlp, struct MLP_Problem *p)
1185 {
1186   if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1187   {
1188     char *name;
1189     int c;
1190
1191     /* Diversity d column  */
1192     if (GNUNET_YES == mlp->opt_dbg_optimize_diversity)
1193       p->c_d = mlp_create_problem_create_column (p, "d", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_D);
1194
1195     /* Utilization u column  */
1196     if (GNUNET_YES == mlp->opt_dbg_optimize_utility)
1197       p->c_u = mlp_create_problem_create_column (p, "u", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_U);
1198
1199     /* Relativity r column  */
1200     if (GNUNET_YES == mlp->opt_dbg_optimize_relativity)
1201       p->c_r = mlp_create_problem_create_column (p, "r", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_R);
1202
1203     /* Quality metric columns */
1204     if (GNUNET_YES == mlp->opt_dbg_optimize_quality)
1205     {
1206       for (c = 0; c < mlp->pv.m_q; c++)
1207       {
1208         GNUNET_asprintf (&name, "q_%u", c);
1209         p->c_q[c] = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_Q[c]);
1210         GNUNET_free (name);
1211       }
1212     }
1213   }
1214 }
1215
1216
1217 /**
1218  * Create the MLP problem
1219  *
1220  * @param mlp the MLP handle
1221  * @return #GNUNET_OK or #GNUNET_SYSERR
1222  */
1223 static int
1224 mlp_create_problem (struct GAS_MLP_Handle *mlp)
1225 {
1226   struct MLP_Problem *p = &mlp->p;
1227   int res = GNUNET_OK;
1228
1229   GNUNET_assert (p->prob == NULL);
1230   GNUNET_assert (p->ia == NULL);
1231   GNUNET_assert (p->ja == NULL);
1232   GNUNET_assert (p->ar == NULL);
1233   /* Reset MLP problem struct */
1234
1235   /* create the glpk problem */
1236   p->prob = glp_create_prob ();
1237   GNUNET_assert (NULL != p->prob);
1238   p->num_peers = mlp_create_problem_count_peers (mlp->requested_peers, mlp->env->addresses);
1239   p->num_addresses = mlp_create_problem_count_addresses (mlp->requested_peers,
1240                                                          mlp->env->addresses);
1241
1242   /* Create problem matrix: 10 * #addresses + #q * #addresses + #q, + #peer + 2 + 1 */
1243   p->num_elements = (10 * p->num_addresses + mlp->pv.m_q * p->num_addresses +
1244       mlp->pv.m_q + p->num_peers + 2 + 1);
1245   LOG (GNUNET_ERROR_TYPE_DEBUG,
1246        "Rebuilding problem for %u peer(s) and %u addresse(s) and %u quality metrics == %u elements\n",
1247        p->num_peers,
1248        p->num_addresses,
1249        mlp->pv.m_q,
1250        p->num_elements);
1251
1252   /* Set a problem name */
1253   glp_set_prob_name (p->prob, "GNUnet ATS bandwidth distribution");
1254   /* Set optimization direction to maximize */
1255   glp_set_obj_dir (p->prob, GLP_MAX);
1256
1257   /* Create problem matrix */
1258   /* last +1 caused by glpk index starting with one: [1..elements]*/
1259   p->ci = 1;
1260   /* row index */
1261   p->ia = GNUNET_malloc (p->num_elements * sizeof (int));
1262   /* column index */
1263   p->ja = GNUNET_malloc (p->num_elements * sizeof (int));
1264   /* coefficient */
1265   p->ar = GNUNET_malloc (p->num_elements * sizeof (double));
1266
1267   if ((NULL == p->ia) || (NULL == p->ja) || (NULL == p->ar))
1268   {
1269       LOG (GNUNET_ERROR_TYPE_ERROR, _("Problem size too large, cannot allocate memory!\n"));
1270       return GNUNET_SYSERR;
1271   }
1272
1273   /* Adding invariant columns */
1274   mlp_create_problem_add_invariant_columns (mlp, p);
1275
1276   /* Adding address independent constraint rows */
1277   mlp_create_problem_add_invariant_rows (mlp, p);
1278
1279   /* Adding address dependent columns constraint rows */
1280   GNUNET_CONTAINER_multipeermap_iterate (mlp->env->addresses,
1281                                          &mlp_create_problem_add_address_information,
1282                                          mlp);
1283
1284   /* Load the matrix */
1285   LOG (GNUNET_ERROR_TYPE_DEBUG, "Loading matrix\n");
1286   glp_load_matrix(p->prob, (p->ci)-1, p->ia, p->ja, p->ar);
1287   if (GNUNET_YES == mlp->opt_dbg_autoscale_problem)
1288   {
1289     glp_scale_prob (p->prob, GLP_SF_AUTO);
1290   }
1291
1292   return res;
1293 }
1294
1295
1296 /**
1297  * Solves the LP problem
1298  *
1299  * @param mlp the MLP Handle
1300  * @return #GNUNET_OK if could be solved, #GNUNET_SYSERR on failure
1301  */
1302 static int
1303 mlp_solve_lp_problem (struct GAS_MLP_Handle *mlp)
1304 {
1305   int res = 0;
1306   int res_status = 0;
1307   res = glp_simplex(mlp->p.prob, &mlp->control_param_lp);
1308   if (0 == res)
1309     LOG(GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem: %s\n",
1310         mlp_solve_to_string (res));
1311   else
1312     LOG(GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem failed: %s\n",
1313         mlp_solve_to_string (res));
1314
1315   /* Analyze problem status  */
1316   res_status = glp_get_status (mlp->p.prob);
1317   switch (res_status) {
1318     case GLP_OPT: /* solution is optimal */
1319       LOG (GNUNET_ERROR_TYPE_INFO,
1320           "Solving LP problem: %s, %s\n",
1321           mlp_solve_to_string(res),
1322           mlp_status_to_string(res_status));
1323       return GNUNET_OK;
1324     default:
1325       LOG (GNUNET_ERROR_TYPE_ERROR,
1326           "Solving LP problem failed: %s %s\n",
1327           mlp_solve_to_string(res),
1328           mlp_status_to_string(res_status));
1329       return GNUNET_SYSERR;
1330   }
1331 }
1332
1333
1334 /**
1335  * Propagates the results when MLP problem was solved
1336  *
1337  * @param cls the MLP handle
1338  * @param key the peer identity
1339  * @param value the address
1340  * @return #GNUNET_OK to continue
1341  */
1342 static int
1343 mlp_propagate_results (void *cls,
1344                        const struct GNUNET_PeerIdentity *key,
1345                        void *value)
1346 {
1347   struct GAS_MLP_Handle *mlp = cls;
1348   struct ATS_Address *address;
1349   struct MLP_information *mlpi;
1350   double mlp_bw_in = MLP_NaN;
1351   double mlp_bw_out = MLP_NaN;
1352   double mlp_use = MLP_NaN;
1353
1354   /* Check if we have to add this peer due to a pending request */
1355   if (GNUNET_NO == GNUNET_CONTAINER_multipeermap_contains (mlp->requested_peers,
1356                                                            key))
1357   {
1358     return GNUNET_OK;
1359   }
1360   address = value;
1361   GNUNET_assert (address->solver_information != NULL);
1362   mlpi = address->solver_information;
1363
1364   mlp_bw_in = glp_mip_col_val(mlp->p.prob, mlpi->c_b);/* FIXME */
1365   if (mlp_bw_in > (double) UINT32_MAX)
1366   {
1367       LOG (GNUNET_ERROR_TYPE_DEBUG, "Overflow in assigned bandwidth, reducing ...\n" );
1368       mlp_bw_in = (double) UINT32_MAX;
1369   }
1370   mlp_bw_out = glp_mip_col_val(mlp->p.prob, mlpi->c_b);
1371   if (mlp_bw_out > (double) UINT32_MAX)
1372   {
1373       LOG (GNUNET_ERROR_TYPE_DEBUG, "Overflow in assigned bandwidth, reducing ...\n" );
1374       mlp_bw_out = (double) UINT32_MAX;
1375   }
1376   mlp_use = glp_mip_col_val(mlp->p.prob, mlpi->c_n);
1377
1378   /*
1379    * Debug: solution
1380    * LOG (GNUNET_ERROR_TYPE_INFO, "MLP result address: `%s' `%s' length %u session %u, mlp use %.3f\n",
1381    *    GNUNET_i2s(&address->peer), address->plugin,
1382    *    address->addr_len, address->session_id);
1383    */
1384
1385   if (GLP_YES == mlp_use)
1386   {
1387     /* This address was selected by the solver to be used */
1388     mlpi->n = GNUNET_YES;
1389     if (GNUNET_NO == address->active)
1390     {
1391             /* Address was not used before, enabling address */
1392       LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : enabling address\n",
1393           (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out);
1394       address->active = GNUNET_YES;
1395       address->assigned_bw_in = mlp_bw_in;
1396       mlpi->b_in = mlp_bw_in;
1397       address->assigned_bw_out = mlp_bw_out;
1398       mlpi->b_out = mlp_bw_out;
1399       if ((NULL == mlp->exclude_peer) || (0 != memcmp (&address->peer, mlp->exclude_peer, sizeof (address->peer))))
1400         mlp->env->bandwidth_changed_cb (mlp->env->cls, address);
1401       return GNUNET_OK;
1402     }
1403     else if (GNUNET_YES == address->active)
1404     {
1405       /* Address was used before, check for bandwidth change */
1406       if ((mlp_bw_out != address->assigned_bw_out) ||
1407               (mlp_bw_in != address->assigned_bw_in))
1408       {
1409           LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : bandwidth changed\n",
1410               (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out);
1411           address->assigned_bw_in = mlp_bw_in;
1412           mlpi->b_in = mlp_bw_in;
1413           address->assigned_bw_out = mlp_bw_out;
1414           mlpi->b_out = mlp_bw_out;
1415           if ((NULL == mlp->exclude_peer) || (0 != memcmp (&address->peer, mlp->exclude_peer, sizeof (address->peer))))
1416             mlp->env->bandwidth_changed_cb (mlp->env->cls, address);
1417           return GNUNET_OK;
1418       }
1419     }
1420     else
1421       GNUNET_break (0);
1422   }
1423   else if (GLP_NO == mlp_use)
1424   {
1425     /* This address was selected by the solver to be not used */
1426     mlpi->n = GNUNET_NO;
1427     if (GNUNET_NO == address->active)
1428     {
1429       /* Address was not used before, nothing to do */
1430       LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : no change\n",
1431           (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out);
1432       return GNUNET_OK;
1433     }
1434     else if (GNUNET_YES == address->active)
1435     {
1436     /* Address was used before, disabling address */
1437     LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : disabling address\n",
1438         (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out);
1439       address->active = GNUNET_NO;
1440       /* Set bandwidth to 0 */
1441       address->assigned_bw_in = 0;
1442       mlpi->b_in = 0;
1443       address->assigned_bw_out = 0;
1444       mlpi->b_out = 0;
1445       return GNUNET_OK;
1446     }
1447     else
1448       GNUNET_break (0);
1449   }
1450   else
1451     GNUNET_break (0);
1452
1453   return GNUNET_OK;
1454 }
1455
1456
1457 static void
1458 notify (struct GAS_MLP_Handle *mlp,
1459         enum GAS_Solver_Operation op,
1460         enum GAS_Solver_Status stat,
1461         enum GAS_Solver_Additional_Information add)
1462 {
1463   mlp->env->info_cb (mlp->env->cls,
1464                      op,
1465                      stat,
1466                      add);
1467 }
1468
1469
1470 static void
1471 mlp_branch_and_cut_cb (glp_tree *tree, void *info)
1472 {
1473   struct GAS_MLP_Handle *mlp = info;
1474   double mlp_obj = 0;
1475
1476   switch (glp_ios_reason (tree))
1477   {
1478     case GLP_ISELECT:
1479         /* Do nothing here */
1480       break;
1481     case GLP_IPREPRO:
1482         /* Do nothing here */
1483       break;
1484     case GLP_IROWGEN:
1485         /* Do nothing here */
1486       break;
1487     case GLP_IHEUR:
1488         /* Do nothing here */
1489       break;
1490     case GLP_ICUTGEN:
1491         /* Do nothing here */
1492       break;
1493     case GLP_IBRANCH:
1494         /* Do nothing here */
1495       break;
1496     case GLP_IBINGO:
1497         /* A better solution was found  */
1498       mlp->ps.mlp_gap = glp_ios_mip_gap (tree);
1499       mlp_obj = glp_mip_obj_val (mlp->p.prob);
1500       mlp->ps.lp_mlp_gap = (abs(mlp_obj - mlp->ps.lp_objective_value)) / (abs(mlp_obj) + DBL_EPSILON);
1501
1502       LOG (GNUNET_ERROR_TYPE_INFO,
1503           "Found better integer solution, current gaps: %.3f <= %.3f, %.3f <= %.3f\n",
1504           mlp->ps.mlp_gap, mlp->pv.mip_gap,
1505           mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
1506
1507       if (mlp->ps.mlp_gap <= mlp->pv.mip_gap)
1508       {
1509         LOG (GNUNET_ERROR_TYPE_INFO,
1510           "Current LP/MLP gap of %.3f smaller than tolerated gap of %.3f, terminating search\n",
1511           mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
1512         glp_ios_terminate (tree);
1513       }
1514
1515       if (mlp->ps.lp_mlp_gap <= mlp->pv.lp_mip_gap)
1516       {
1517         LOG (GNUNET_ERROR_TYPE_INFO,
1518           "Current LP/MLP gap of %.3f smaller than tolerated gap of %.3f, terminating search\n",
1519           mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
1520         glp_ios_terminate (tree);
1521       }
1522
1523       break;
1524     default:
1525       break;
1526   }
1527   //GNUNET_break (0);
1528 }
1529
1530
1531 /**
1532  * Solves the MLP problem
1533  *
1534  * @param solver the MLP Handle
1535  * @return #GNUNET_OK if could be solved, #GNUNET_SYSERR on failure
1536  */
1537 static int
1538 GAS_mlp_solve_problem (void *solver)
1539 {
1540   struct GAS_MLP_Handle *mlp = solver;
1541   char *filename;
1542   int res_lp = 0;
1543   int mip_res = 0;
1544   int mip_status = 0;
1545
1546   struct GNUNET_TIME_Absolute start_total;
1547   struct GNUNET_TIME_Absolute start_cur_op;
1548   struct GNUNET_TIME_Relative dur_total;
1549   struct GNUNET_TIME_Relative dur_setup;
1550   struct GNUNET_TIME_Relative dur_lp;
1551   struct GNUNET_TIME_Relative dur_mlp;
1552
1553   GNUNET_assert(NULL != solver);
1554
1555   if (GNUNET_YES == mlp->stat_bulk_lock)
1556     {
1557       mlp->stat_bulk_requests++;
1558       return GNUNET_NO;
1559     }
1560   notify(mlp, GAS_OP_SOLVE_START, GAS_STAT_SUCCESS,
1561       (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1562   start_total = GNUNET_TIME_absolute_get();
1563
1564   if (0 == GNUNET_CONTAINER_multipeermap_size(mlp->requested_peers))
1565     {
1566       notify(mlp, GAS_OP_SOLVE_STOP, GAS_STAT_SUCCESS, GAS_INFO_NONE);
1567       return GNUNET_OK; /* No pending requests */
1568     }
1569   if (0 == GNUNET_CONTAINER_multipeermap_size(mlp->env->addresses))
1570     {
1571       notify(mlp, GAS_OP_SOLVE_STOP, GAS_STAT_SUCCESS, GAS_INFO_NONE);
1572       return GNUNET_OK; /* No addresses available */
1573     }
1574
1575   if ((GNUNET_NO == mlp->stat_mlp_prob_changed)
1576       && (GNUNET_NO == mlp->stat_mlp_prob_updated))
1577     {
1578       LOG(GNUNET_ERROR_TYPE_DEBUG, "No changes to problem\n");
1579       notify(mlp, GAS_OP_SOLVE_STOP, GAS_STAT_SUCCESS, GAS_INFO_NONE);
1580       return GNUNET_OK;
1581     }
1582   if (GNUNET_YES == mlp->stat_mlp_prob_changed)
1583   {
1584     LOG(GNUNET_ERROR_TYPE_DEBUG, "Problem size changed, rebuilding\n");
1585     notify(mlp, GAS_OP_SOLVE_SETUP_START, GAS_STAT_SUCCESS, GAS_INFO_FULL);
1586     mlp_delete_problem (mlp);
1587     if (GNUNET_SYSERR == mlp_create_problem (mlp))
1588       {
1589         notify(mlp, GAS_OP_SOLVE_SETUP_STOP, GAS_STAT_FAIL, GAS_INFO_FULL);
1590         return GNUNET_SYSERR;
1591       }
1592     notify(mlp, GAS_OP_SOLVE_SETUP_STOP, GAS_STAT_SUCCESS, GAS_INFO_FULL);
1593     if (GNUNET_NO == mlp->opt_dbg_intopt_presolver)
1594     {
1595     mlp->control_param_lp.presolve = GLP_YES; /* LP presolver, we need lp solution */
1596     mlp->control_param_mlp.presolve = GNUNET_NO; /* No presolver, we have LP solution */
1597     }
1598     else
1599     {
1600       mlp->control_param_lp.presolve = GNUNET_NO; /* LP presolver, we need lp solution */
1601       mlp->control_param_mlp.presolve = GLP_YES; /* No presolver, we have LP solution */
1602       dur_lp = GNUNET_TIME_UNIT_ZERO;
1603     }
1604   }
1605   else
1606   {
1607     LOG(GNUNET_ERROR_TYPE_DEBUG, "Problem was updated, resolving\n");
1608   }
1609
1610   /* Reset solution info */
1611   mlp->ps.lp_objective_value = 0.0;
1612   mlp->ps.mlp_gap = 1.0;
1613   mlp->ps.mlp_objective_value = 0.0;
1614   mlp->ps.lp_mlp_gap = 0.0;
1615
1616   dur_setup = GNUNET_TIME_absolute_get_duration (start_total);
1617
1618   /* Run LP solver */
1619   if (GNUNET_NO == mlp->opt_dbg_intopt_presolver)
1620   {
1621     notify(mlp, GAS_OP_SOLVE_MLP_LP_START, GAS_STAT_SUCCESS,
1622         (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1623     LOG(GNUNET_ERROR_TYPE_DEBUG,
1624         "Running LP solver %s\n",
1625         (GLP_YES == mlp->control_param_lp.presolve)? "with presolver": "without presolver");
1626     start_cur_op = GNUNET_TIME_absolute_get();
1627
1628     /* Solve LP */
1629     /* Only for debugging:
1630      * Always use LP presolver:
1631      * mlp->control_param_lp.presolve = GLP_YES; */
1632     res_lp = mlp_solve_lp_problem(mlp);
1633     if (GNUNET_OK == res_lp)
1634     {
1635         mlp->ps.lp_objective_value = glp_get_obj_val (mlp->p.prob);
1636         LOG (GNUNET_ERROR_TYPE_DEBUG,
1637              "LP solution was: %.3f\n",
1638              mlp->ps.lp_objective_value);
1639     }
1640
1641     dur_lp = GNUNET_TIME_absolute_get_duration (start_cur_op);
1642     notify(mlp, GAS_OP_SOLVE_MLP_LP_STOP,
1643         (GNUNET_OK == res_lp) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1644         (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1645   }
1646
1647   if (GNUNET_YES == mlp->opt_dbg_intopt_presolver)
1648     res_lp = GNUNET_OK;
1649
1650   /* Run MLP solver */
1651   if ((GNUNET_OK == res_lp) || (GNUNET_YES == mlp->opt_dbg_intopt_presolver))
1652   {
1653     LOG(GNUNET_ERROR_TYPE_DEBUG, "Running MLP solver \n");
1654     notify(mlp, GAS_OP_SOLVE_MLP_MLP_START, GAS_STAT_SUCCESS,
1655         (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1656     start_cur_op = GNUNET_TIME_absolute_get();
1657
1658     /* Solve MIP */
1659
1660     /* Only for debugging, always use LP presolver */
1661     if (GNUNET_YES == mlp->opt_dbg_intopt_presolver)
1662       mlp->control_param_mlp.presolve = GNUNET_YES;
1663
1664     mip_res = glp_intopt (mlp->p.prob, &mlp->control_param_mlp);
1665     switch (mip_res)
1666     {
1667         case 0:
1668           /* Successful */
1669           LOG (GNUNET_ERROR_TYPE_INFO,
1670                "Solving MLP problem: %s\n",
1671                mlp_solve_to_string (mip_res));
1672           break;
1673         case GLP_ETMLIM: /* Time limit reached */
1674         case GLP_EMIPGAP: /* MIP gap tolerance limit reached */
1675         case GLP_ESTOP: /* Solver was instructed to stop*/
1676           /* Semi-successful */
1677           LOG (GNUNET_ERROR_TYPE_INFO,
1678                "Solving MLP problem solution was interupted: %s\n",
1679                mlp_solve_to_string (mip_res));
1680           break;
1681         case GLP_EBOUND:
1682         case GLP_EROOT:
1683         case GLP_ENOPFS:
1684         case GLP_ENODFS:
1685         case GLP_EFAIL:
1686         default:
1687          /* Fail */
1688           LOG (GNUNET_ERROR_TYPE_INFO,
1689               "Solving MLP problem failed: %s\n",
1690               mlp_solve_to_string (mip_res));
1691         break;
1692     }
1693
1694     /* Analyze problem status  */
1695     mip_status = glp_mip_status(mlp->p.prob);
1696     switch (mip_status)
1697     {
1698       case GLP_OPT: /* solution is optimal */
1699         LOG (GNUNET_ERROR_TYPE_WARNING,
1700             "Solution of MLP problem is optimal: %s, %s\n",
1701             mlp_solve_to_string (mip_res),
1702             mlp_status_to_string (mip_status));
1703         mip_res = GNUNET_OK;
1704         break;
1705       case GLP_FEAS: /* solution is feasible but not proven optimal */
1706
1707         if ( (mlp->ps.mlp_gap <= mlp->pv.mip_gap) ||
1708              (mlp->ps.lp_mlp_gap <= mlp->pv.lp_mip_gap) )
1709         {
1710           LOG (GNUNET_ERROR_TYPE_INFO,
1711                  "Solution of MLP problem is feasible and solution within gap constraints: %s, %s\n",
1712                  mlp_solve_to_string (mip_res),
1713                  mlp_status_to_string (mip_status));
1714           mip_res = GNUNET_OK;
1715         }
1716         else
1717         {
1718           LOG (GNUNET_ERROR_TYPE_WARNING,
1719                "Solution of MLP problem is feasible but solution not within gap constraints: %s, %s\n",
1720                mlp_solve_to_string (mip_res),
1721                mlp_status_to_string (mip_status));
1722           mip_res = GNUNET_SYSERR;
1723         }
1724         break;
1725       case GLP_UNDEF: /* Solution undefined */
1726       case GLP_NOFEAS: /* No feasible solution */
1727       default:
1728         LOG (GNUNET_ERROR_TYPE_ERROR,
1729             "Solving MLP problem failed: %s %s\n",
1730             mlp_solve_to_string (mip_res),
1731             mlp_status_to_string (mip_status));
1732         mip_res = GNUNET_SYSERR;
1733         break;
1734     }
1735
1736     dur_mlp = GNUNET_TIME_absolute_get_duration (start_cur_op);
1737     dur_total = GNUNET_TIME_absolute_get_duration (start_total);
1738
1739     notify(mlp, GAS_OP_SOLVE_MLP_MLP_STOP,
1740         (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1741         (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1742   }
1743   else
1744   {
1745     /* Do not execute mip solver since lp solution is invalid */
1746     dur_mlp = GNUNET_TIME_UNIT_ZERO;
1747     dur_total = GNUNET_TIME_absolute_get_duration (start_total);
1748
1749     notify(mlp, GAS_OP_SOLVE_MLP_MLP_STOP, GAS_STAT_FAIL,
1750         (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1751     mip_res = GNUNET_SYSERR;
1752   }
1753
1754   /* Notify about end */
1755   notify(mlp, GAS_OP_SOLVE_STOP,
1756       ((GNUNET_OK == mip_res) && (GNUNET_OK == mip_res)) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1757       (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1758
1759   LOG (GNUNET_ERROR_TYPE_DEBUG,
1760       "Execution time for %s solve: (total/setup/lp/mlp) : %llu %llu %llu %llu\n",
1761       (GNUNET_YES == mlp->stat_mlp_prob_changed) ? "full" : "updated",
1762       (unsigned long long) dur_total.rel_value_us,
1763       (unsigned long long) dur_setup.rel_value_us,
1764       (unsigned long long) dur_lp.rel_value_us,
1765       (unsigned long long) dur_mlp.rel_value_us);
1766
1767   /* Save stats */
1768   mlp->ps.lp_res = res_lp;
1769   mlp->ps.mip_res = mip_res;
1770   mlp->ps.lp_presolv = mlp->control_param_lp.presolve;
1771   mlp->ps.mip_presolv = mlp->control_param_mlp.presolve;
1772   mlp->ps.p_cols = glp_get_num_cols(mlp->p.prob);
1773   mlp->ps.p_rows = glp_get_num_rows(mlp->p.prob);
1774   mlp->ps.p_elements = mlp->p.num_elements;
1775
1776   /* Propagate result*/
1777   notify (mlp, GAS_OP_SOLVE_UPDATE_NOTIFICATION_START,
1778       (GNUNET_OK == res_lp) && (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1779       GAS_INFO_NONE);
1780   if ((GNUNET_OK == res_lp) && (GNUNET_OK == mip_res))
1781     {
1782       GNUNET_CONTAINER_multipeermap_iterate(mlp->env->addresses,
1783           &mlp_propagate_results, mlp);
1784     }
1785   notify (mlp, GAS_OP_SOLVE_UPDATE_NOTIFICATION_STOP,
1786       (GNUNET_OK == res_lp) && (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1787       GAS_INFO_NONE);
1788
1789   struct GNUNET_TIME_Absolute time = GNUNET_TIME_absolute_get();
1790   if ( (GNUNET_YES == mlp->opt_dump_problem_all) ||
1791       (mlp->opt_dump_problem_on_fail && ((GNUNET_OK != res_lp) || (GNUNET_OK != mip_res))) )
1792     {
1793       /* Write problem to disk */
1794       switch (mlp->opt_log_format) {
1795         case MLP_CPLEX:
1796           GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.cplex", mlp->p.num_peers,
1797               mlp->p.num_addresses, time.abs_value_us);
1798           glp_write_lp (mlp->p.prob, NULL, filename);
1799           break;
1800         case MLP_GLPK:
1801           GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.glpk", mlp->p.num_peers,
1802               mlp->p.num_addresses, time.abs_value_us);
1803           glp_write_prob (mlp->p.prob, 0, filename);
1804           break;
1805         case MLP_MPS:
1806           GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.mps", mlp->p.num_peers,
1807               mlp->p.num_addresses, time.abs_value_us);
1808           glp_write_mps (mlp->p.prob, GLP_MPS_FILE, NULL, filename);
1809           break;
1810         default:
1811           break;
1812       }
1813       LOG(GNUNET_ERROR_TYPE_ERROR, "Dumped problem to file: `%s' \n", filename);
1814       GNUNET_free(filename);
1815     }
1816   if ( (mlp->opt_dump_solution_all) ||
1817       (mlp->opt_dump_solution_on_fail && ((GNUNET_OK != res_lp) || (GNUNET_OK != mip_res))) )
1818   {
1819     /* Write solution to disk */
1820     GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.sol", mlp->p.num_peers,
1821         mlp->p.num_addresses, time.abs_value_us);
1822     glp_print_mip(mlp->p.prob, filename);
1823     LOG(GNUNET_ERROR_TYPE_ERROR, "Dumped solution to file: `%s' \n", filename);
1824     GNUNET_free(filename);
1825   }
1826
1827   /* Reset change and update marker */
1828   mlp->control_param_lp.presolve = GLP_NO;
1829   mlp->stat_mlp_prob_updated = GNUNET_NO;
1830   mlp->stat_mlp_prob_changed = GNUNET_NO;
1831
1832   if ((GNUNET_OK == res_lp) && (GNUNET_OK == mip_res))
1833     return GNUNET_OK;
1834   else
1835     return GNUNET_SYSERR;
1836 }
1837
1838 /**
1839  * Add a single address to the solve
1840  *
1841  * @param solver the solver Handle
1842  * @param address the address to add
1843  * @param network network type of this address
1844  */
1845 static void
1846 GAS_mlp_address_add (void *solver,
1847                     struct ATS_Address *address,
1848                     uint32_t network)
1849 {
1850   struct GAS_MLP_Handle *mlp = solver;
1851
1852   if (GNUNET_ATS_NetworkTypeCount <= network)
1853   {
1854     GNUNET_break (0);
1855     return;
1856   }
1857
1858   if (NULL == address->solver_information)
1859   {
1860       address->solver_information = GNUNET_new (struct MLP_information);
1861   }
1862   else
1863       LOG (GNUNET_ERROR_TYPE_ERROR,
1864            _("Adding address for peer `%s' multiple times\n"),
1865            GNUNET_i2s(&address->peer));
1866
1867   /* Is this peer included in the problem? */
1868   if (NULL ==
1869       GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers,
1870                                          &address->peer))
1871   {
1872     /* FIXME: should this be an error? */
1873     LOG (GNUNET_ERROR_TYPE_DEBUG,
1874          "Adding address for peer `%s' without address request\n",
1875          GNUNET_i2s(&address->peer));
1876     return;
1877   }
1878
1879   LOG (GNUNET_ERROR_TYPE_DEBUG,
1880        "Adding address for peer `%s' with address request \n",
1881        GNUNET_i2s(&address->peer));
1882   /* Problem size changed: new address for peer with pending request */
1883   mlp->stat_mlp_prob_changed = GNUNET_YES;
1884   if (GNUNET_YES == mlp->opt_mlp_auto_solve)
1885     GAS_mlp_solve_problem (solver);
1886 }
1887
1888
1889 /**
1890  * Transport properties for this address have changed
1891  *
1892  * @param solver solver handle
1893  * @param address the address
1894  */
1895 static void
1896 GAS_mlp_address_property_changed (void *solver,
1897                                   struct ATS_Address *address)
1898 {
1899   struct MLP_information *mlpi = address->solver_information;
1900   struct GAS_MLP_Handle *mlp = solver;
1901
1902   if (NULL == mlp->p.prob)
1903     return; /* There is no MLP problem to update yet */
1904
1905   if (NULL == mlpi)
1906   {
1907     LOG (GNUNET_ERROR_TYPE_INFO,
1908          _("Updating address property for peer `%s' %p not added before\n"),
1909          GNUNET_i2s (&address->peer),
1910          address);
1911     GNUNET_break (0);
1912     return;
1913   }
1914   if (NULL ==
1915       GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers,
1916                                          &address->peer))
1917   {
1918     /* Peer is not requested, so no need to update problem */
1919     return;
1920   }
1921   LOG (GNUNET_ERROR_TYPE_DEBUG,
1922        "Updating properties for peer `%s'\n",
1923        GNUNET_i2s(&address->peer));
1924
1925   if (GNUNET_YES == mlp->opt_dbg_feasibility_only)
1926     return;
1927
1928   /* Update c7) [r_q[index]][c_b] = f_q * q_averaged[type_index] */
1929   if ( (GNUNET_YES ==
1930         mlp_create_problem_update_value (&mlp->p,
1931                                          mlp->p.r_q[RQ_QUALITY_METRIC_DELAY],
1932                                          mlpi->c_b,
1933                                          address->norm_delay.norm,
1934                                          __LINE__)) ||
1935        (GNUNET_YES ==
1936         mlp_create_problem_update_value (&mlp->p,
1937                                          mlp->p.r_q[RQ_QUALITY_METRIC_DISTANCE],
1938                                          mlpi->c_b,
1939                                          address->norm_distance.norm,
1940                                          __LINE__)) )
1941   {
1942     mlp->stat_mlp_prob_updated = GNUNET_YES;
1943     if (GNUNET_YES == mlp->opt_mlp_auto_solve)
1944       GAS_mlp_solve_problem (solver);
1945   }
1946
1947 }
1948
1949
1950 /**
1951  * Find the active address in the set of addresses of a peer
1952  * @param cls destination
1953  * @param key peer id
1954  * @param value address
1955  * @return #GNUNET_OK
1956  */
1957 static int
1958 mlp_get_preferred_address_it (void *cls,
1959                               const struct GNUNET_PeerIdentity *key,
1960                               void *value)
1961 {
1962   static int counter = 0;
1963   struct ATS_Address **aa = cls;
1964   struct ATS_Address *addr = value;
1965   struct MLP_information *mlpi = addr->solver_information;
1966
1967   if (mlpi == NULL)
1968     return GNUNET_YES;
1969
1970   /*
1971    * Debug output
1972    * GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1973    *           "MLP [%u] Peer `%s' %s length %u session %u active %s mlp active %s\n",
1974    *           counter, GNUNET_i2s (&addr->peer), addr->plugin, addr->addr_len, addr->session_id,
1975    *           (GNUNET_YES == addr->active) ? "active" : "inactive",
1976    *           (GNUNET_YES == mlpi->n) ? "active" : "inactive");
1977    */
1978
1979   if (GNUNET_YES == mlpi->n)
1980   {
1981
1982     (*aa) = addr;
1983     (*aa)->assigned_bw_in = mlpi->b_in;
1984     (*aa)->assigned_bw_out = mlpi->b_out;
1985     return GNUNET_NO;
1986   }
1987   counter++;
1988   return GNUNET_YES;
1989 }
1990
1991
1992 static double
1993 get_peer_pref_value (struct GAS_MLP_Handle *mlp,
1994                      const struct GNUNET_PeerIdentity *peer)
1995 {
1996   double res;
1997   const double *preferences;
1998   int c;
1999
2000   preferences = mlp->env->get_preferences (mlp->env->cls, peer);
2001   res = 0.0;
2002   for (c = 0; c < GNUNET_ATS_PREFERENCE_END; c++)
2003   {
2004     /* fprintf (stderr, "VALUE[%u] %s %.3f \n",
2005      *        c, GNUNET_i2s (&cur->addr->peer), t[c]); */
2006     res += preferences[c];
2007   }
2008
2009   res /= GNUNET_ATS_PREFERENCE_END;
2010   res += 1.0;
2011
2012   LOG (GNUNET_ERROR_TYPE_DEBUG,
2013        "Peer preference for peer  `%s' == %.2f\n",
2014        GNUNET_i2s(peer), res);
2015
2016   return res;
2017 }
2018
2019
2020 /**
2021  * Get the preferred address for a specific peer
2022  *
2023  * @param solver the MLP Handle
2024  * @param peer the peer
2025  */
2026 static void
2027 GAS_mlp_get_preferred_address (void *solver,
2028                                const struct GNUNET_PeerIdentity *peer)
2029 {
2030   struct GAS_MLP_Handle *mlp = solver;
2031   struct ATS_Peer *p;
2032   struct ATS_Address *res;
2033
2034   LOG (GNUNET_ERROR_TYPE_DEBUG,
2035        "Getting preferred address for `%s'\n",
2036        GNUNET_i2s (peer));
2037
2038   /* Is this peer included in the problem? */
2039   if (NULL ==
2040       GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers,
2041                                          peer))
2042     {
2043       LOG (GNUNET_ERROR_TYPE_INFO, "Adding peer `%s' to list of requested_peers with requests\n",
2044           GNUNET_i2s (peer));
2045
2046       p = GNUNET_new (struct ATS_Peer);
2047       p->id = (*peer);
2048       p->f = get_peer_pref_value (mlp, peer);
2049       GNUNET_CONTAINER_multipeermap_put (mlp->requested_peers,
2050                                          peer, p,
2051                                          GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
2052
2053       /* Added new peer, we have to rebuild problem before solving */
2054       mlp->stat_mlp_prob_changed = GNUNET_YES;
2055
2056       if ((GNUNET_YES == mlp->opt_mlp_auto_solve)&&
2057           (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains(mlp->env->addresses,
2058                                                                 peer)))
2059       {
2060         mlp->exclude_peer = peer;
2061         GAS_mlp_solve_problem (mlp);
2062         mlp->exclude_peer = NULL;
2063       }
2064   }
2065   /* Get prefered address */
2066   res = NULL;
2067   GNUNET_CONTAINER_multipeermap_get_multiple (mlp->env->addresses, peer,
2068                                               &mlp_get_preferred_address_it, &res);
2069   if (NULL != res)
2070     mlp->env->bandwidth_changed_cb (mlp->env->cls,
2071                                     res);
2072 }
2073
2074
2075 /**
2076  * Deletes a single address in the MLP problem
2077  *
2078  * The MLP problem has to be recreated and the problem has to be resolved
2079  *
2080  * @param solver the MLP Handle
2081  * @param address the address to delete
2082  */
2083 static void
2084 GAS_mlp_address_delete (void *solver,
2085                         struct ATS_Address *address)
2086 {
2087   struct GAS_MLP_Handle *mlp = solver;
2088   struct MLP_information *mlpi;
2089   struct ATS_Address *res;
2090   int was_active;
2091
2092   mlpi = address->solver_information;
2093   if (NULL != mlpi)
2094   {
2095     /* Remove full address */
2096     GNUNET_free (mlpi);
2097     address->solver_information = NULL;
2098   }
2099   was_active = address->active;
2100   address->active = GNUNET_NO;
2101   address->assigned_bw_in = 0;
2102   address->assigned_bw_out = 0;
2103
2104   /* Is this peer included in the problem? */
2105   if (NULL ==
2106       GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers,
2107                                          &address->peer))
2108   {
2109     LOG (GNUNET_ERROR_TYPE_INFO,
2110          "Deleting address for peer `%s' without address request \n",
2111          GNUNET_i2s(&address->peer));
2112     return;
2113   }
2114   LOG (GNUNET_ERROR_TYPE_INFO,
2115        "Deleting address for peer `%s' with address request \n",
2116       GNUNET_i2s (&address->peer));
2117
2118   /* Problem size changed: new address for peer with pending request */
2119   mlp->stat_mlp_prob_changed = GNUNET_YES;
2120   if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2121   {
2122     GAS_mlp_solve_problem (solver);
2123   }
2124   if (GNUNET_YES == was_active)
2125   {
2126     GAS_mlp_get_preferred_address (solver, &address->peer);
2127     res = NULL;
2128     GNUNET_CONTAINER_multipeermap_get_multiple (mlp->env->addresses,
2129                                                 &address->peer,
2130                                                 &mlp_get_preferred_address_it,
2131                                                 &res);
2132     if (NULL == res)
2133     {
2134       /* No alternative address, disconnecting peer */
2135       mlp->env->bandwidth_changed_cb (mlp->env->cls, address);
2136     }
2137   }
2138 }
2139
2140
2141 /**
2142  * Start a bulk operation
2143  *
2144  * @param solver the solver
2145  */
2146 static void
2147 GAS_mlp_bulk_start (void *solver)
2148 {
2149   struct GAS_MLP_Handle *s = solver;
2150
2151   LOG (GNUNET_ERROR_TYPE_DEBUG,
2152        "Locking solver for bulk operation ...\n");
2153   GNUNET_assert (NULL != solver);
2154   s->stat_bulk_lock ++;
2155 }
2156
2157
2158 static void
2159 GAS_mlp_bulk_stop (void *solver)
2160 {
2161   struct GAS_MLP_Handle *s = solver;
2162
2163   LOG (GNUNET_ERROR_TYPE_DEBUG,
2164        "Unlocking solver from bulk operation ...\n");
2165   GNUNET_assert (NULL != solver);
2166
2167   if (s->stat_bulk_lock < 1)
2168   {
2169     GNUNET_break (0);
2170     return;
2171   }
2172   s->stat_bulk_lock --;
2173
2174   if (0 < s->stat_bulk_requests)
2175   {
2176     GAS_mlp_solve_problem (solver);
2177     s->stat_bulk_requests= 0;
2178   }
2179 }
2180
2181
2182
2183 /**
2184  * Stop notifying about address and bandwidth changes for this peer
2185  *
2186  * @param solver the MLP handle
2187  * @param peer the peer
2188  */
2189 static void
2190 GAS_mlp_stop_get_preferred_address (void *solver,
2191                                      const struct GNUNET_PeerIdentity *peer)
2192 {
2193   struct GAS_MLP_Handle *mlp = solver;
2194   struct ATS_Peer *p = NULL;
2195
2196   GNUNET_assert (NULL != solver);
2197   GNUNET_assert (NULL != peer);
2198   if (NULL != (p = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers, peer)))
2199   {
2200     GNUNET_assert (GNUNET_YES ==
2201                    GNUNET_CONTAINER_multipeermap_remove (mlp->requested_peers, peer, p));
2202     GNUNET_free (p);
2203
2204     mlp->stat_mlp_prob_changed = GNUNET_YES;
2205     if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2206     {
2207       GAS_mlp_solve_problem (solver);
2208     }
2209   }
2210 }
2211
2212
2213 /**
2214  * Changes the preferences for a peer in the MLP problem
2215  *
2216  * @param solver the MLP Handle
2217  * @param peer the peer
2218  * @param kind the kind to change the preference
2219  * @param pref_rel the relative score
2220  */
2221 static void
2222 GAS_mlp_address_change_preference (void *solver,
2223                    const struct GNUNET_PeerIdentity *peer,
2224                    enum GNUNET_ATS_PreferenceKind kind,
2225                    double pref_rel)
2226 {
2227   struct GAS_MLP_Handle *mlp = solver;
2228   struct ATS_Peer *p;
2229
2230   LOG (GNUNET_ERROR_TYPE_DEBUG,
2231        "Changing preference for address for peer `%s' to %.2f\n",
2232        GNUNET_i2s(peer),
2233        pref_rel);
2234
2235   GNUNET_STATISTICS_update (mlp->env->stats,
2236                             "# LP address preference changes", 1, GNUNET_NO);
2237   /* Update the constraints with changed preferences */
2238
2239
2240
2241   /* Update relativity constraint c9 */
2242   if (NULL == (p = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers, peer)))
2243   {
2244     LOG (GNUNET_ERROR_TYPE_INFO,
2245          "Updating preference for unknown peer `%s'\n",
2246          GNUNET_i2s(peer));
2247     return;
2248   }
2249
2250   if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
2251   {
2252     p->f = get_peer_pref_value (mlp, peer);
2253     mlp_create_problem_update_value (&mlp->p,
2254                                      p->r_c9,
2255                                      mlp->p.c_r,
2256                                      - p->f,
2257                                      __LINE__);
2258
2259     /* Problem size changed: new address for peer with pending request */
2260     mlp->stat_mlp_prob_updated = GNUNET_YES;
2261     if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2262       GAS_mlp_solve_problem (solver);
2263   }
2264 }
2265
2266
2267 /**
2268  * Get application feedback for a peer
2269  *
2270  * @param solver the solver handle
2271  * @param application the application
2272  * @param peer the peer to change the preference for
2273  * @param scope the time interval for this feedback: [now - scope .. now]
2274  * @param kind the kind to change the preference
2275  * @param score the score
2276  */
2277 static void
2278 GAS_mlp_address_preference_feedback (void *solver,
2279                                      struct GNUNET_SERVICE_Client *application,
2280                                      const struct GNUNET_PeerIdentity *peer,
2281                                      const struct GNUNET_TIME_Relative scope,
2282                                      enum GNUNET_ATS_PreferenceKind kind,
2283                                      double score)
2284 {
2285   struct GAS_PROPORTIONAL_Handle *s = solver;
2286
2287   GNUNET_assert (NULL != solver);
2288   GNUNET_assert (NULL != peer);
2289   GNUNET_assert (NULL != s);
2290 }
2291
2292
2293 static int
2294 mlp_free_peers (void *cls,
2295                 const struct GNUNET_PeerIdentity *key, void *value)
2296 {
2297   struct GNUNET_CONTAINER_MultiPeerMap *map = cls;
2298   struct ATS_Peer *p = value;
2299
2300   GNUNET_assert (GNUNET_YES ==
2301                  GNUNET_CONTAINER_multipeermap_remove (map, key, value));
2302   GNUNET_free (p);
2303
2304   return GNUNET_OK;
2305 }
2306
2307
2308 /**
2309  * Shutdown the MLP problem solving component
2310  *
2311  * @param cls the solver handle
2312  * @return NULL
2313  */
2314 void *
2315 libgnunet_plugin_ats_mlp_done (void *cls)
2316 {
2317   struct GNUNET_ATS_SolverFunctions *sf = cls;
2318   struct GAS_MLP_Handle *mlp = sf->cls;
2319
2320   LOG (GNUNET_ERROR_TYPE_DEBUG,
2321        "Shutting down mlp solver\n");
2322   mlp_delete_problem (mlp);
2323   GNUNET_CONTAINER_multipeermap_iterate (mlp->requested_peers,
2324                                          &mlp_free_peers,
2325                                          mlp->requested_peers);
2326   GNUNET_CONTAINER_multipeermap_destroy (mlp->requested_peers);
2327   mlp->requested_peers = NULL;
2328
2329   /* Clean up GLPK environment */
2330   glp_free_env();
2331   GNUNET_free (mlp);
2332
2333   LOG (GNUNET_ERROR_TYPE_DEBUG,
2334        "Shutdown down of mlp solver complete\n");
2335   return NULL;
2336 }
2337
2338
2339 void *
2340 libgnunet_plugin_ats_mlp_init (void *cls)
2341 {
2342   static struct GNUNET_ATS_SolverFunctions sf;
2343   struct GNUNET_ATS_PluginEnvironment *env = cls;
2344   struct GAS_MLP_Handle * mlp = GNUNET_new (struct GAS_MLP_Handle);
2345   float f_tmp;
2346   unsigned long long tmp;
2347   unsigned int b_min;
2348   unsigned int n_min;
2349   int c;
2350   char *outputformat;
2351
2352   struct GNUNET_TIME_Relative max_duration;
2353   long long unsigned int max_iterations;
2354
2355   /* Init GLPK environment */
2356   int res = glp_init_env();
2357   switch (res) {
2358     case 0:
2359       LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
2360           "initialization successful");
2361       break;
2362     case 1:
2363       LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
2364           "environment is already initialized");
2365       break;
2366     case 2:
2367       LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
2368           "initialization failed (insufficient memory)");
2369       GNUNET_free(mlp);
2370       return NULL;
2371       break;
2372     case 3:
2373       LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
2374           "initialization failed (unsupported programming model)");
2375       GNUNET_free(mlp);
2376       return NULL;
2377       break;
2378     default:
2379       break;
2380   }
2381
2382   mlp->opt_dump_problem_all = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2383      "ats", "MLP_DUMP_PROBLEM_ALL");
2384   if (GNUNET_SYSERR == mlp->opt_dump_problem_all)
2385    mlp->opt_dump_problem_all = GNUNET_NO;
2386
2387   mlp->opt_dump_solution_all = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2388      "ats", "MLP_DUMP_SOLUTION_ALL");
2389   if (GNUNET_SYSERR == mlp->opt_dump_solution_all)
2390    mlp->opt_dump_solution_all = GNUNET_NO;
2391
2392   mlp->opt_dump_problem_on_fail = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2393      "ats", "MLP_DUMP_PROBLEM_ON_FAIL");
2394   if (GNUNET_SYSERR == mlp->opt_dump_problem_on_fail)
2395    mlp->opt_dump_problem_on_fail = GNUNET_NO;
2396
2397   mlp->opt_dump_solution_on_fail = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2398      "ats", "MLP_DUMP_SOLUTION_ON_FAIL");
2399   if (GNUNET_SYSERR == mlp->opt_dump_solution_on_fail)
2400    mlp->opt_dump_solution_on_fail = GNUNET_NO;
2401
2402   mlp->opt_dbg_glpk_verbose = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2403      "ats", "MLP_DBG_GLPK_VERBOSE");
2404   if (GNUNET_SYSERR == mlp->opt_dbg_glpk_verbose)
2405    mlp->opt_dbg_glpk_verbose = GNUNET_NO;
2406
2407   mlp->opt_dbg_feasibility_only = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2408      "ats", "MLP_DBG_FEASIBILITY_ONLY");
2409   if (GNUNET_SYSERR == mlp->opt_dbg_feasibility_only)
2410    mlp->opt_dbg_feasibility_only = GNUNET_NO;
2411   if (GNUNET_YES == mlp->opt_dbg_feasibility_only)
2412     LOG (GNUNET_ERROR_TYPE_WARNING,
2413         "MLP solver is configured to check feasibility only!\n");
2414
2415   mlp->opt_dbg_autoscale_problem = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2416      "ats", "MLP_DBG_AUTOSCALE_PROBLEM");
2417   if (GNUNET_SYSERR == mlp->opt_dbg_autoscale_problem)
2418    mlp->opt_dbg_autoscale_problem = GNUNET_NO;
2419   if (GNUNET_YES == mlp->opt_dbg_autoscale_problem)
2420     LOG (GNUNET_ERROR_TYPE_WARNING,
2421         "MLP solver is configured automatically scale the problem!\n");
2422
2423   mlp->opt_dbg_intopt_presolver = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2424      "ats", "MLP_DBG_INTOPT_PRESOLVE");
2425   if (GNUNET_SYSERR == mlp->opt_dbg_intopt_presolver)
2426    mlp->opt_dbg_intopt_presolver = GNUNET_NO;
2427   if (GNUNET_YES == mlp->opt_dbg_intopt_presolver)
2428     LOG (GNUNET_ERROR_TYPE_WARNING,
2429         "MLP solver is configured use the mlp presolver\n");
2430
2431   mlp->opt_dbg_optimize_diversity = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2432      "ats", "MLP_DBG_OPTIMIZE_DIVERSITY");
2433   if (GNUNET_SYSERR == mlp->opt_dbg_optimize_diversity)
2434    mlp->opt_dbg_optimize_diversity = GNUNET_YES;
2435   if (GNUNET_NO == mlp->opt_dbg_optimize_diversity)
2436     LOG (GNUNET_ERROR_TYPE_WARNING,
2437         "MLP solver is not optimizing for diversity\n");
2438
2439   mlp->opt_dbg_optimize_relativity= GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2440      "ats", "MLP_DBG_OPTIMIZE_RELATIVITY");
2441   if (GNUNET_SYSERR == mlp->opt_dbg_optimize_relativity)
2442    mlp->opt_dbg_optimize_relativity = GNUNET_YES;
2443   if (GNUNET_NO == mlp->opt_dbg_optimize_relativity)
2444     LOG (GNUNET_ERROR_TYPE_WARNING,
2445         "MLP solver is not optimizing for relativity\n");
2446
2447   mlp->opt_dbg_optimize_quality = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2448      "ats", "MLP_DBG_OPTIMIZE_QUALITY");
2449   if (GNUNET_SYSERR == mlp->opt_dbg_optimize_quality)
2450    mlp->opt_dbg_optimize_quality = GNUNET_YES;
2451   if (GNUNET_NO == mlp->opt_dbg_optimize_quality)
2452     LOG (GNUNET_ERROR_TYPE_WARNING,
2453         "MLP solver is not optimizing for quality\n");
2454
2455   mlp->opt_dbg_optimize_utility = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2456      "ats", "MLP_DBG_OPTIMIZE_UTILITY");
2457   if (GNUNET_SYSERR == mlp->opt_dbg_optimize_utility)
2458    mlp->opt_dbg_optimize_utility = GNUNET_YES;
2459   if (GNUNET_NO == mlp->opt_dbg_optimize_utility)
2460     LOG (GNUNET_ERROR_TYPE_WARNING,
2461         "MLP solver is not optimizing for utility\n");
2462
2463   if ( (GNUNET_NO == mlp->opt_dbg_optimize_utility) &&
2464        (GNUNET_NO == mlp->opt_dbg_optimize_quality) &&
2465        (GNUNET_NO == mlp->opt_dbg_optimize_relativity) &&
2466        (GNUNET_NO == mlp->opt_dbg_optimize_utility) &&
2467        (GNUNET_NO == mlp->opt_dbg_feasibility_only))
2468   {
2469     LOG (GNUNET_ERROR_TYPE_ERROR,
2470         _("MLP solver is not optimizing for anything, changing to feasibility check\n"));
2471     mlp->opt_dbg_feasibility_only = GNUNET_YES;
2472   }
2473
2474   if (GNUNET_SYSERR == GNUNET_CONFIGURATION_get_value_string (env->cfg,
2475      "ats", "MLP_LOG_FORMAT", &outputformat))
2476    mlp->opt_log_format = MLP_CPLEX;
2477   else
2478   {
2479     GNUNET_STRINGS_utf8_toupper(outputformat, outputformat);
2480     if (0 == strcmp (outputformat, "MPS"))
2481     {
2482       mlp->opt_log_format = MLP_MPS;
2483     }
2484     else if (0 == strcmp (outputformat, "CPLEX"))
2485     {
2486       mlp->opt_log_format = MLP_CPLEX;
2487     }
2488     else if (0 == strcmp (outputformat, "GLPK"))
2489     {
2490       mlp->opt_log_format = MLP_GLPK;
2491     }
2492     else
2493     {
2494       LOG (GNUNET_ERROR_TYPE_WARNING,
2495           "Invalid log format `%s' in configuration, using CPLEX!\n",
2496           outputformat);
2497       mlp->opt_log_format = MLP_CPLEX;
2498     }
2499     GNUNET_free (outputformat);
2500   }
2501
2502   mlp->pv.BIG_M = (double) BIG_M_VALUE;
2503
2504   mlp->pv.mip_gap = (double) 0.0;
2505   if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_float (env->cfg, "ats",
2506       "MLP_MAX_MIP_GAP", &f_tmp))
2507   {
2508     if ((f_tmp < 0.0) || (f_tmp > 1.0))
2509     {
2510       LOG (GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
2511           "MIP gap", f_tmp);
2512     }
2513     else
2514     {
2515       mlp->pv.mip_gap = f_tmp;
2516       LOG (GNUNET_ERROR_TYPE_INFO, "Using %s of %.3f\n",
2517           "MIP gap", f_tmp);
2518     }
2519   }
2520
2521   mlp->pv.lp_mip_gap = (double) 0.0;
2522   if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_float (env->cfg, "ats",
2523       "MLP_MAX_LP_MIP_GAP", &f_tmp))
2524   {
2525     if ((f_tmp < 0.0) || (f_tmp > 1.0))
2526     {
2527       LOG (GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
2528           "LP/MIP", f_tmp);
2529     }
2530     else
2531     {
2532       mlp->pv.lp_mip_gap = f_tmp;
2533       LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2534           "LP/MIP", f_tmp);
2535     }
2536   }
2537
2538   /* Get timeout for iterations */
2539   if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time(env->cfg, "ats",
2540       "MLP_MAX_DURATION", &max_duration))
2541   {
2542     max_duration = MLP_MAX_EXEC_DURATION;
2543   }
2544
2545   /* Get maximum number of iterations */
2546   if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_size(env->cfg, "ats",
2547       "MLP_MAX_ITERATIONS", &max_iterations))
2548   {
2549     max_iterations = MLP_MAX_ITERATIONS;
2550   }
2551
2552   /* Get diversity coefficient from configuration */
2553   mlp->pv.co_D = MLP_DEFAULT_D;
2554   if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_float (env->cfg, "ats",
2555       "MLP_COEFFICIENT_D", &f_tmp))
2556   {
2557     if ((f_tmp < 0.0))
2558     {
2559       LOG (GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
2560           "MLP_COEFFICIENT_D", f_tmp);
2561     }
2562     else
2563     {
2564       mlp->pv.co_D = f_tmp;
2565       LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2566           "MLP_COEFFICIENT_D", f_tmp);
2567     }
2568   }
2569
2570   /* Get relativity coefficient from configuration */
2571   mlp->pv.co_R = MLP_DEFAULT_R;
2572   if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_float (env->cfg, "ats",
2573       "MLP_COEFFICIENT_R", &f_tmp))
2574   {
2575     if ((f_tmp < 0.0))
2576     {
2577       LOG (GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
2578           "MLP_COEFFICIENT_R", f_tmp);
2579     }
2580     else
2581     {
2582       mlp->pv.co_R = f_tmp;
2583       LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2584           "MLP_COEFFICIENT_R", f_tmp);
2585     }
2586   }
2587
2588
2589   /* Get utilization coefficient from configuration */
2590   mlp->pv.co_U = MLP_DEFAULT_U;
2591   if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_float (env->cfg, "ats",
2592       "MLP_COEFFICIENT_U", &f_tmp))
2593   {
2594     if ((f_tmp < 0.0))
2595     {
2596       LOG (GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
2597           "MLP_COEFFICIENT_U", f_tmp);
2598     }
2599     else
2600     {
2601       mlp->pv.co_U = f_tmp;
2602       LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2603           "MLP_COEFFICIENT_U", f_tmp);
2604     }
2605   }
2606
2607   /* Get quality metric coefficients from configuration */
2608   for (c = 0; c < RQ_QUALITY_METRIC_COUNT; c++)
2609   {
2610     /* initialize quality coefficients with default value 1.0 */
2611     mlp->pv.co_Q[c] = MLP_DEFAULT_QUALITY;
2612   }
2613
2614
2615   if (GNUNET_OK ==
2616       GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats",
2617                                            "MLP_COEFFICIENT_QUALITY_DELAY",
2618                                            &tmp))
2619     mlp->pv.co_Q[RQ_QUALITY_METRIC_DELAY] = (double) tmp / 100;
2620   else
2621     mlp->pv.co_Q[RQ_QUALITY_METRIC_DELAY] = MLP_DEFAULT_QUALITY;
2622
2623   if (GNUNET_OK ==
2624       GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats",
2625                                            "MLP_COEFFICIENT_QUALITY_DISTANCE",
2626                                            &tmp))
2627     mlp->pv.co_Q[RQ_QUALITY_METRIC_DISTANCE] = (double) tmp / 100;
2628   else
2629     mlp->pv.co_Q[RQ_QUALITY_METRIC_DISTANCE] = MLP_DEFAULT_QUALITY;
2630
2631   /* Get minimum bandwidth per used address from configuration */
2632   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats",
2633                                                       "MLP_MIN_BANDWIDTH",
2634                                                       &tmp))
2635     b_min = tmp;
2636   else
2637   {
2638     b_min = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
2639   }
2640
2641   /* Get minimum number of connections from configuration */
2642   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats",
2643                                                       "MLP_MIN_CONNECTIONS",
2644                                                       &tmp))
2645     n_min = tmp;
2646   else
2647     n_min = MLP_DEFAULT_MIN_CONNECTIONS;
2648
2649   /* Init network quotas */
2650   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
2651   {
2652     mlp->pv.quota_index[c] = c;
2653     mlp->pv.quota_out[c] = env->out_quota[c];
2654     mlp->pv.quota_in[c] = env->in_quota[c];
2655
2656     LOG (GNUNET_ERROR_TYPE_INFO,
2657          "Quota for network `%s' (in/out) %llu/%llu\n",
2658          GNUNET_ATS_print_network_type (c),
2659          mlp->pv.quota_out[c],
2660          mlp->pv.quota_in[c]);
2661     /* Check if defined quota could make problem unsolvable */
2662     if ((n_min * b_min) > mlp->pv.quota_out[c])
2663     {
2664       LOG (GNUNET_ERROR_TYPE_INFO,
2665            _("Adjusting inconsistent outbound quota configuration for network `%s', is %llu must be at least %llu\n"),
2666            GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2667            mlp->pv.quota_out[c],
2668            (n_min * b_min));
2669       mlp->pv.quota_out[c] = (n_min * b_min);
2670     }
2671     if ((n_min * b_min) > mlp->pv.quota_in[c])
2672     {
2673       LOG (GNUNET_ERROR_TYPE_INFO,
2674            _("Adjusting inconsistent inbound quota configuration for network `%s', is %llu must be at least %llu\n"),
2675            GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2676            mlp->pv.quota_in[c],
2677            (n_min * b_min));
2678       mlp->pv.quota_in[c] = (n_min * b_min);
2679     }
2680     /* Check if bandwidth is too big to make problem solvable */
2681     if (mlp->pv.BIG_M < mlp->pv.quota_out[c])
2682     {
2683       LOG (GNUNET_ERROR_TYPE_INFO,
2684            _("Adjusting outbound quota configuration for network `%s'from %llu to %.0f\n"),
2685            GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2686            mlp->pv.quota_out[c],
2687            mlp->pv.BIG_M);
2688       mlp->pv.quota_out[c] = mlp->pv.BIG_M ;
2689     }
2690     if (mlp->pv.BIG_M < mlp->pv.quota_in[c])
2691     {
2692       LOG (GNUNET_ERROR_TYPE_INFO,
2693            _("Adjusting inbound quota configuration for network `%s' from %llu to %.0f\n"),
2694            GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2695            mlp->pv.quota_in[c],
2696            mlp->pv.BIG_M);
2697       mlp->pv.quota_in[c] = mlp->pv.BIG_M ;
2698     }
2699   }
2700   mlp->env = env;
2701   sf.cls = mlp;
2702   sf.s_add = &GAS_mlp_address_add;
2703   sf.s_address_update_property = &GAS_mlp_address_property_changed;
2704   sf.s_get = &GAS_mlp_get_preferred_address;
2705   sf.s_get_stop = &GAS_mlp_stop_get_preferred_address;
2706   sf.s_pref = &GAS_mlp_address_change_preference;
2707   sf.s_feedback = &GAS_mlp_address_preference_feedback;
2708   sf.s_del = &GAS_mlp_address_delete;
2709   sf.s_bulk_start = &GAS_mlp_bulk_start;
2710   sf.s_bulk_stop = &GAS_mlp_bulk_stop;
2711
2712   /* Setting MLP Input variables */
2713   mlp->pv.b_min = b_min;
2714   mlp->pv.n_min = n_min;
2715   mlp->pv.m_q = RQ_QUALITY_METRIC_COUNT;
2716   mlp->stat_mlp_prob_changed = GNUNET_NO;
2717   mlp->stat_mlp_prob_updated = GNUNET_NO;
2718   mlp->opt_mlp_auto_solve = GNUNET_YES;
2719   mlp->requested_peers = GNUNET_CONTAINER_multipeermap_create (10, GNUNET_NO);
2720   mlp->stat_bulk_requests = 0;
2721   mlp->stat_bulk_lock = 0;
2722
2723   /* Setup GLPK */
2724   /* Redirect GLPK output to GNUnet logging */
2725   glp_term_hook (&mlp_term_hook, (void *) mlp);
2726
2727   /* Init LP solving parameters */
2728   glp_init_smcp(&mlp->control_param_lp);
2729   mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
2730   if (GNUNET_YES == mlp->opt_dbg_glpk_verbose)
2731     mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
2732
2733   mlp->control_param_lp.it_lim = max_iterations;
2734   mlp->control_param_lp.tm_lim = max_duration.rel_value_us / 1000LL;
2735
2736   /* Init MLP solving parameters */
2737   glp_init_iocp(&mlp->control_param_mlp);
2738   /* Setting callback function */
2739   mlp->control_param_mlp.cb_func = &mlp_branch_and_cut_cb;
2740   mlp->control_param_mlp.cb_info = mlp;
2741   mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
2742   mlp->control_param_mlp.mip_gap = mlp->pv.mip_gap;
2743   if (GNUNET_YES == mlp->opt_dbg_glpk_verbose)
2744     mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
2745   mlp->control_param_mlp.tm_lim = max_duration.rel_value_us / 1000LL;
2746
2747   LOG (GNUNET_ERROR_TYPE_DEBUG, "solver ready\n");
2748
2749   return &sf;
2750 }
2751
2752 /* end of plugin_ats_mlp.c */