implementation of mip gap tolerance interval

5 files changed, 163 insertions, 57 deletions

diff --git a/src/ats/ats.conf.in b/src/ats/ats.conf.in
index db70f143a..e1ad75c8f 100644
--- a/src/ats/ats.conf.in
+++ b/src/ats/ats.conf.in
@@ -44,8 +44,12 @@ PROP_STABILITY_FACTOR = 125
 # MLP specific settings
 # MLP defaults
 
-# Maximum duration for a solution process
+# Maximum duration for a solution process (both LP and MILP)
 # MLP_MAX_DURATION = 3 s
+# Maximum numbero of iterations for a solution process (only LP)
+# MLP_MAX_ITERATIONS = 
+# Tolerated MIP Gap in percent [0 .. 100]
+# MLP_MAX_MIP_GAP = 0.0
 
 # Maximum number of iterations for a solution process
 # MLP_MAX_ITERATIONS = 1024
diff --git a/src/ats/perf_ats_solver.c b/src/ats/perf_ats_solver.c
index 2017b794b..01906c87d 100644
--- a/src/ats/perf_ats_solver.c
+++ b/src/ats/perf_ats_solver.c
@@ -27,7 +27,7 @@
 #include "gnunet_util_lib.h"
 #include "gnunet_statistics_service.h"
 #include "gnunet-service-ats_addresses.h"
-#include "gnunet-service-ats_normalization.h"
+
 #include "gnunet_ats_service.h"
 #include "gnunet_ats_plugin.h"
 #include "test_ats_api_common.h"
diff --git a/src/ats/perf_ats_solver.conf b/src/ats/perf_ats_solver.conf
index 7de6d5d00..0557203f4 100644
--- a/src/ats/perf_ats_solver.conf
+++ b/src/ats/perf_ats_solver.conf
@@ -35,6 +35,9 @@ PROP_STABILITY_FACTOR = 125
 
 # Maximum number of iterations for a solution process
 # MLP_MAX_ITERATIONS = 1024
+# Tolerated MIP Gap [0.0 .. 1.0]
+MLP_MAX_MIP_GAP = 0,025
+
 # MLP_COEFFICIENT_D = 1.0
 # MLP_COEFFICIENT_U = 1.0
 # MLP_COEFFICIENT_R = 1.0
@@ -43,7 +46,8 @@ MLP_MIN_BANDWIDTH = 10
 # MLP_DBG_FEASIBILITY_ONLY = YES
 MLP_DBG_AUTOSCALE_PROBLEM = YES
 # MLP_DBG_INTOPT_PRESOLVE = YES
-
+# Print GLPK output
+#MLP_DBG_GLPK_VERBOSE = YES
 
 #MLP_DBG_OPTIMIZE_UTILITY = NO
 #MLP_DBG_OPTIMIZE_QUALITY = NO
@@ -54,8 +58,7 @@ MLP_LOG_FORMAT = CPLEX
 
 # MLP Log settings
 # Dump all problems to disk
-MLP_DUMP_PROBLEM_ALL = YES
+# MLP_DUMP_PROBLEM_ALL = YES
 # Dump all solution to disk
-MLP_DUMP_SOLUTION_ALL = YES
-# Print GLPK output
-MLP_DBG_GLPK_VERBOSE = NO
+# MLP_DUMP_SOLUTION_ALL = YES
+
diff --git a/src/ats/plugin_ats_mlp.c b/src/ats/plugin_ats_mlp.c
index 385b14a16..c4c97b796 100644
--- a/src/ats/plugin_ats_mlp.c
+++ b/src/ats/plugin_ats_mlp.c
@@ -147,8 +147,9 @@
 static int
 mlp_term_hook (void *info, const char *s)
 {
-  /* Not needed atm struct MLP_information *mlp = info; */
-  LOG (GNUNET_ERROR_TYPE_ERROR, "%s", s);
+  struct GAS_MLP_Handle *mlp = info;
+  if (mlp->opt_dbg_glpk_verbose)
+    LOG (GNUNET_ERROR_TYPE_ERROR, "%s", s);
   return 1;
 }
 
@@ -1010,42 +1011,6 @@ mlp_solve_lp_problem (struct GAS_MLP_Handle *mlp)
 
 
 /**
- * Solves the MLP problem
- *
- * @param mlp the MLP Handle
- * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
- */
-int
-mlp_solve_mlp_problem (struct GAS_MLP_Handle *mlp)
-{
-  int res = 0;
-  int res_status = 0;
-  res = glp_intopt(mlp->p.prob, &mlp->control_param_mlp);
-  if (0 == res)
-    LOG(GNUNET_ERROR_TYPE_DEBUG, "Solving MLP problem: 0x%02X %s\n", res,
-        mlp_solve_to_string (res));
-  else
-    LOG(GNUNET_ERROR_TYPE_DEBUG, "Solving MLP problem failed: 0x%02X %s\n", res,
-        mlp_solve_to_string (res));
-  /* Analyze problem status  */
-  res_status = glp_mip_status(mlp->p.prob);
-  switch (res_status) {
-    case GLP_OPT: /* solution is optimal */
-      LOG (GNUNET_ERROR_TYPE_INFO,
-          "Solving MLP problem: 0x%02X %s, 0x%02X %s\n",
-          res, mlp_solve_to_string(res),
-          res_status, mlp_status_to_string(res_status));
-      return GNUNET_OK;
-    default:
-      LOG (GNUNET_ERROR_TYPE_WARNING,
-          "Solving MLP problem failed: 0x%02X %s 0x%02X %s\n",
-          res, mlp_solve_to_string(res),
-          res_status, mlp_status_to_string(res_status));
-      return GNUNET_SYSERR;
-  }
-}
-
-/**
  * Propagates the results when MLP problem was solved
  *
  * @param cls the MLP handle
@@ -1176,6 +1141,45 @@ static void notify (struct GAS_MLP_Handle *mlp,
   if (NULL != mlp->env->info_cb)
     mlp->env->info_cb (mlp->env->info_cb_cls, op, stat, add);
 }
+
+static void mlp_branch_and_cut_cb (glp_tree *tree, void *info)
+{
+  struct GAS_MLP_Handle *mlp = info;
+
+  switch (glp_ios_reason (tree))
+  {
+    case GLP_ISELECT:
+        /* Do nothing here */
+      break;
+    case GLP_IPREPRO:
+        /* Do nothing here */
+      break;
+    case GLP_IROWGEN:
+        /* Do nothing here */
+      break;
+    case GLP_IHEUR:
+        /* Do nothing here */
+      break;
+    case GLP_ICUTGEN:
+        /* Do nothing here */
+      break;
+    case GLP_IBRANCH:
+        /* Do nothing here */
+      break;
+    case GLP_IBINGO:
+        /* A better solution was found  */
+      mlp->ps.mlp_gap = glp_ios_mip_gap (tree);
+      LOG (GNUNET_ERROR_TYPE_ERROR,
+          "Found better integer solution, current MIP GAP: %f\n", mlp->ps.mlp_gap);
+
+      break;
+    default:
+      break;
+  }
+  //GNUNET_break (0);
+}
+
+
 /**
  * Solves the MLP problem
  *
@@ -1188,7 +1192,8 @@ GAS_mlp_solve_problem (void *solver)
   struct GAS_MLP_Handle *mlp = solver;
   char *filename;
   int res_lp = 0;
-  int res_mip = 0;
+  int mip_res = 0;
+  int mip_status = 0;
 
   struct GNUNET_TIME_Absolute start_total;
   struct GNUNET_TIME_Absolute start_cur_op;
@@ -1254,6 +1259,12 @@ GAS_mlp_solve_problem (void *solver)
     LOG(GNUNET_ERROR_TYPE_DEBUG, "Problem was updated, resolving\n");
   }
 
+  /* Reset solution info */
+  mlp->ps.lp_objective_value = 0.0;
+  mlp->ps.mlp_gap = 1.0;
+  mlp->ps.mlp_objective_value = 0.0;
+
+
   dur_setup = GNUNET_TIME_absolute_get_duration (start_total);
 
   /* Run LP solver */
@@ -1289,16 +1300,76 @@ GAS_mlp_solve_problem (void *solver)
     start_cur_op = GNUNET_TIME_absolute_get();
 
     /* Solve MIP */
+
     /* Only for debugging, always use MLP presolver */
     if (GNUNET_YES == mlp->opt_dbg_intopt_presolver)
       mlp->control_param_mlp.presolve = GNUNET_YES;
-    res_mip = mlp_solve_mlp_problem(mlp);
+
+
+    mip_res = glp_intopt (mlp->p.prob, &mlp->control_param_mlp);
+    switch (mip_res)
+    {
+        case 0:
+          /* Successful */
+          LOG (GNUNET_ERROR_TYPE_WARNING,
+               "Solving MLP problem: 0x%02X %s\n",
+               mip_res, mlp_solve_to_string (mip_res));
+          break;
+        case GLP_ETMLIM: /* Time limit reached */
+        case GLP_EMIPGAP: /* MIP gap tolerance limit reached */
+        case GLP_ESTOP: /* Solver was instructed to stop*/
+          /* Semi-successful */
+          LOG (GNUNET_ERROR_TYPE_WARNING,
+               "Solving MLP problem solution was interupted: 0x%02X %s\n",
+               mip_res, mlp_solve_to_string (mip_res));
+          break;
+        case GLP_EBOUND:
+        case GLP_EROOT:
+        case GLP_ENOPFS:
+        case GLP_ENODFS:
+        case GLP_EFAIL:
+        default:
+         /* Fail */
+          LOG (GNUNET_ERROR_TYPE_ERROR,
+              "Solving MLP problem failed: 0x%02X %s\n",
+              mip_res, mlp_solve_to_string (mip_res));
+        break;
+    }
+
+    /* Analyze problem status  */
+    mip_status = glp_mip_status(mlp->p.prob);
+    switch (mip_status)
+    {
+      case GLP_OPT: /* solution is optimal */
+        LOG (GNUNET_ERROR_TYPE_WARNING,
+            "Solution of MLP problem is optimal: 0x%02X %s, 0x%02X %s\n",
+            mip_res, mlp_solve_to_string (mip_res),
+            mip_status, mlp_status_to_string (mip_status));
+        mip_res = GNUNET_OK;
+        break;
+      case GLP_FEAS: /* solution is feasible but not proven optimal */
+        LOG (GNUNET_ERROR_TYPE_WARNING,
+               "Solution of MLP problem is feasible: 0x%02X %s, 0x%02X %s\n",
+               mip_res, mlp_solve_to_string (mip_res),
+               mip_status, mlp_status_to_string (mip_status));
+        mip_res = GNUNET_OK;
+        break;
+      case GLP_UNDEF: /* Solution undefined */
+      case GLP_NOFEAS: /* No feasible solution */
+      default:
+        LOG (GNUNET_ERROR_TYPE_ERROR,
+            "Solving MLP problem failed: 0x%02X %s 0x%02X %s\n",
+            mip_res, mlp_solve_to_string (mip_res),
+            mip_status, mlp_status_to_string (mip_status));
+        mip_res = GNUNET_SYSERR;
+        break;
+    }
 
     dur_mlp = GNUNET_TIME_absolute_get_duration (start_cur_op);
     dur_total = GNUNET_TIME_absolute_get_duration (start_total);
 
     notify(mlp, GAS_OP_SOLVE_MLP_MLP_STOP,
-        (GNUNET_OK == res_mip) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
+        (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
         (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
   }
   else
@@ -1309,12 +1380,12 @@ GAS_mlp_solve_problem (void *solver)
 
     notify(mlp, GAS_OP_SOLVE_MLP_MLP_STOP, GAS_STAT_FAIL,
         (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
-    res_mip = GNUNET_SYSERR;
+    mip_res = GNUNET_SYSERR;
   }
 
   /* Notify about end */
   notify(mlp, GAS_OP_SOLVE_STOP,
-      ((GNUNET_OK == res_mip) && (GNUNET_OK == res_mip)) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
+      ((GNUNET_OK == mip_res) && (GNUNET_OK == mip_res)) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
       (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
 
   LOG (GNUNET_ERROR_TYPE_DEBUG,
@@ -1327,7 +1398,7 @@ GAS_mlp_solve_problem (void *solver)
 
   /* Save stats */
   mlp->ps.lp_res = res_lp;
-  mlp->ps.mip_res = res_mip;
+  mlp->ps.mip_res = mip_res;
   mlp->ps.lp_presolv = mlp->control_param_lp.presolve;
   mlp->ps.mip_presolv = mlp->control_param_mlp.presolve;
   mlp->ps.p_cols = glp_get_num_cols(mlp->p.prob);
@@ -1336,20 +1407,20 @@ GAS_mlp_solve_problem (void *solver)
 
   /* Propagate result*/
   notify (mlp, GAS_OP_SOLVE_UPDATE_NOTIFICATION_START,
-      (GNUNET_OK == res_lp) && (GNUNET_OK == res_mip) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
+      (GNUNET_OK == res_lp) && (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
       GAS_INFO_NONE);
-  if ((GNUNET_OK == res_lp) && (GNUNET_OK == res_mip))
+  if ((GNUNET_OK == res_lp) && (GNUNET_OK == mip_res))
     {
       GNUNET_CONTAINER_multipeermap_iterate(mlp->addresses,
           &mlp_propagate_results, mlp);
     }
   notify (mlp, GAS_OP_SOLVE_UPDATE_NOTIFICATION_STOP,
-      (GNUNET_OK == res_lp) && (GNUNET_OK == res_mip) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
+      (GNUNET_OK == res_lp) && (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
       GAS_INFO_NONE);
 
   struct GNUNET_TIME_Absolute time = GNUNET_TIME_absolute_get();
   if ( (GNUNET_YES == mlp->opt_dump_problem_all) ||
-      (mlp->opt_dump_problem_on_fail && ((GNUNET_OK != res_lp) || (GNUNET_OK != res_mip))) )
+      (mlp->opt_dump_problem_on_fail && ((GNUNET_OK != res_lp) || (GNUNET_OK != mip_res))) )
     {
       /* Write problem to disk */
       switch (mlp->opt_log_format) {
@@ -1375,7 +1446,7 @@ GAS_mlp_solve_problem (void *solver)
       GNUNET_free(filename);
     }
   if ( (mlp->opt_dump_solution_all) ||
-      (mlp->opt_dump_solution_on_fail && ((GNUNET_OK != res_lp) || (GNUNET_OK != res_mip))) )
+      (mlp->opt_dump_solution_on_fail && ((GNUNET_OK != res_lp) || (GNUNET_OK != mip_res))) )
   {
     /* Write solution to disk */
     GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.sol", mlp->p.num_peers,
@@ -1390,7 +1461,7 @@ GAS_mlp_solve_problem (void *solver)
   mlp->stat_mlp_prob_updated = GNUNET_NO;
   mlp->stat_mlp_prob_changed = GNUNET_NO;
 
-  if ((GNUNET_OK == res_lp) && (GNUNET_OK == res_mip))
+  if ((GNUNET_OK == res_lp) && (GNUNET_OK == mip_res))
     return GNUNET_OK;
   else
     return GNUNET_SYSERR;
@@ -2059,6 +2130,7 @@ libgnunet_plugin_ats_mlp_init (void *cls)
   int c;
   int c2;
   int found;
+  char *tmp_str;
   char *outputformat;
 
   struct GNUNET_TIME_Relative max_duration;
@@ -2218,6 +2290,22 @@ libgnunet_plugin_ats_mlp_init (void *cls)
   }
 
   mlp->pv.BIG_M = (double) BIG_M_VALUE;
+  mlp->pv.mip_gap = (double) 0.0;
+
+  if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_string (env->cfg, "ats",
+      "MLP_MAX_MIP_GAP", &tmp_str))
+  {
+    /* Dangerous due to localized separator , or . */
+    mlp->pv.mip_gap = strtod (tmp_str, NULL);
+    if ( (mlp->pv.mip_gap < 0.0) && (mlp->pv.mip_gap > 1.0) )
+    {
+        LOG (GNUNET_ERROR_TYPE_INFO, "Invalid MIP gap configuration %u \n",
+            tmp);
+    }
+    else
+        LOG (GNUNET_ERROR_TYPE_WARNING, "Using MIP gap of %.3f\n",
+            mlp->pv.mip_gap);
+  }
 
   /* Get timeout for iterations */
   if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time(env->cfg, "ats",
@@ -2429,7 +2517,11 @@ libgnunet_plugin_ats_mlp_init (void *cls)
 
   /* Init MLP solving parameters */
   glp_init_iocp(&mlp->control_param_mlp);
+  /* Setting callback function */
+  mlp->control_param_mlp.cb_func = &mlp_branch_and_cut_cb;
+  mlp->control_param_mlp.cb_info = mlp;
   mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
+  mlp->control_param_mlp.mip_gap = mlp->pv.mip_gap;
   if (GNUNET_YES == mlp->opt_dbg_glpk_verbose)
     mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
   mlp->control_param_mlp.tm_lim = max_duration.rel_value_us / 1000LL;
diff --git a/src/ats/plugin_ats_mlp.h b/src/ats/plugin_ats_mlp.h
index b53c0d674..3b5c8f2a0 100644
--- a/src/ats/plugin_ats_mlp.h
+++ b/src/ats/plugin_ats_mlp.h
@@ -71,6 +71,10 @@ struct MLP_Solution
   int mip_res;
   int mip_presolv;
 
+  double lp_objective_value;
+  double mlp_objective_value;
+  double mlp_gap;
+
   int p_elements;
   int p_cols;
   int p_rows;
@@ -156,6 +160,9 @@ struct MLP_Variables
   /* Big M value for bandwidth capping */
   double BIG_M;
 
+  /* MIP Gap */
+  double mip_gap;
+
   /* ATS Quality metrics
    *
    * Array with GNUNET_ATS_QualityPropertiesCount elements