src/ats/plugin_ats_mlp.c

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