[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r33272 - gnunet/src/ats
|
From: |
gnunet |
|
Subject: |
[GNUnet-SVN] r33272 - gnunet/src/ats |
|
Date: |
Wed, 14 May 2014 00:50:28 +0200 |
Author: wachs
Date: 2014-05-14 00:50:28 +0200 (Wed, 14 May 2014)
New Revision: 33272
Modified:
gnunet/src/ats/ats.conf.in
gnunet/src/ats/perf_ats_solver.conf
gnunet/src/ats/plugin_ats_mlp.c
gnunet/src/ats/plugin_ats_mlp.h
Log:
implemented mip gap
Modified: gnunet/src/ats/ats.conf.in
===================================================================
--- gnunet/src/ats/ats.conf.in 2014-05-13 22:20:01 UTC (rev 33271)
+++ gnunet/src/ats/ats.conf.in 2014-05-13 22:50:28 UTC (rev 33272)
@@ -50,6 +50,7 @@
# MLP_MAX_ITERATIONS =
# Tolerated MIP Gap in percent [0 .. 100]
# MLP_MAX_MIP_GAP = 0.0
+# MLP_MAX_LP_MIP_GAP = 0,0
# Maximum number of iterations for a solution process
# MLP_MAX_ITERATIONS = 1024
Modified: gnunet/src/ats/perf_ats_solver.conf
===================================================================
--- gnunet/src/ats/perf_ats_solver.conf 2014-05-13 22:20:01 UTC (rev 33271)
+++ gnunet/src/ats/perf_ats_solver.conf 2014-05-13 22:50:28 UTC (rev 33272)
@@ -36,7 +36,9 @@
# 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_MAX_MIP_GAP = 0,0025
+# Tolerated LP/MIP Gap [0.0 .. 1.0]
+MLP_MAX_LP_MIP_GAP = 0,025
# MLP_COEFFICIENT_D = 1.0
# MLP_COEFFICIENT_U = 1.0
Modified: gnunet/src/ats/plugin_ats_mlp.c
===================================================================
--- gnunet/src/ats/plugin_ats_mlp.c 2014-05-13 22:20:01 UTC (rev 33271)
+++ gnunet/src/ats/plugin_ats_mlp.c 2014-05-13 22:50:28 UTC (rev 33272)
@@ -985,26 +985,26 @@
int res_status = 0;
res = glp_simplex(mlp->p.prob, &mlp->control_param_lp);
if (0 == res)
- LOG(GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem: 0x%02X %s\n", res,
+ LOG(GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem: %s\n",
mlp_solve_to_string (res));
else
- LOG(GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem failed: 0x%02X %s\n",
- res, mlp_solve_to_string (res));
+ LOG(GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem failed: %s\n",
+ mlp_solve_to_string (res));
/* Analyze problem status */
res_status = glp_get_status (mlp->p.prob);
switch (res_status) {
case GLP_OPT: /* solution is optimal */
LOG (GNUNET_ERROR_TYPE_INFO,
- "Solving LP problem: 0x%02X %s, 0x%02X %s\n",
- res, mlp_solve_to_string(res),
- res_status, mlp_status_to_string(res_status));
+ "Solving LP problem: %s, %s\n",
+ mlp_solve_to_string(res),
+ mlp_status_to_string(res_status));
return GNUNET_OK;
default:
- LOG (GNUNET_ERROR_TYPE_WARNING,
- "Solving LP problem failed: 0x%02X %s 0x%02X %s\n",
- res, mlp_solve_to_string(res),
- res_status, mlp_status_to_string(res_status));
+ LOG (GNUNET_ERROR_TYPE_ERROR,
+ "Solving LP problem failed: %s %s\n",
+ mlp_solve_to_string(res),
+ mlp_status_to_string(res_status));
return GNUNET_SYSERR;
}
}
@@ -1056,7 +1056,7 @@
/*
* Debug: solution
- * LOG (GNUNET_ERROR_TYPE_INFO, "MLP result address: `%s' `%s' length %u
session %u, mlp use %f\n",
+ * LOG (GNUNET_ERROR_TYPE_INFO, "MLP result address: `%s' `%s' length %u
session %u, mlp use %.3f\n",
* GNUNET_i2s(&address->peer), address->plugin,
* address->addr_len, address->session_id);
*/
@@ -1145,6 +1145,7 @@
static void mlp_branch_and_cut_cb (glp_tree *tree, void *info)
{
struct GAS_MLP_Handle *mlp = info;
+ double mlp_obj = 0;
switch (glp_ios_reason (tree))
{
@@ -1169,9 +1170,30 @@
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);
+ mlp_obj = glp_mip_obj_val (mlp->p.prob);
+ mlp->ps.lp_mlp_gap = (abs(mlp_obj - mlp->ps.lp_objective_value)) /
(abs(mlp_obj) + DBL_EPSILON);
+ LOG (GNUNET_ERROR_TYPE_INFO,
+ "Found better integer solution, current gaps: %.3f <= %.3f, %.3f <=
%.3f\n",
+ mlp->ps.mlp_gap, mlp->pv.mip_gap,
+ mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
+
+ if (mlp->ps.mlp_gap <= mlp->pv.mip_gap)
+ {
+ LOG (GNUNET_ERROR_TYPE_INFO,
+ "Current LP/MLP gap of %.3f smaller than tolerated gap of %.3f,
terminating search\n",
+ mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
+ glp_ios_terminate (tree);
+ }
+
+ if (mlp->ps.lp_mlp_gap <= mlp->pv.lp_mip_gap)
+ {
+ LOG (GNUNET_ERROR_TYPE_INFO,
+ "Current LP/MLP gap of %.3f smaller than tolerated gap of %.3f,
terminating search\n",
+ mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
+ glp_ios_terminate (tree);
+ }
+
break;
default:
break;
@@ -1263,8 +1285,8 @@
mlp->ps.lp_objective_value = 0.0;
mlp->ps.mlp_gap = 1.0;
mlp->ps.mlp_objective_value = 0.0;
+ mlp->ps.lp_mlp_gap = 0.0;
-
dur_setup = GNUNET_TIME_absolute_get_duration (start_total);
/* Run LP solver */
@@ -1281,6 +1303,13 @@
/* Only for debugging, always use LP presolver:
* mlp->control_param_lp.presolve = GLP_YES; */
res_lp = mlp_solve_lp_problem(mlp);
+ if (GNUNET_OK == res_lp)
+ {
+ mlp->ps.lp_objective_value = glp_get_obj_val (mlp->p.prob);
+ LOG (GNUNET_ERROR_TYPE_DEBUG,
+ "LP solution was: %.3f\n",
+ mlp->ps.lp_objective_value);
+ }
dur_lp = GNUNET_TIME_absolute_get_duration (start_cur_op);
notify(mlp, GAS_OP_SOLVE_MLP_LP_STOP,
@@ -1311,17 +1340,17 @@
{
case 0:
/* Successful */
- LOG (GNUNET_ERROR_TYPE_WARNING,
- "Solving MLP problem: 0x%02X %s\n",
- mip_res, mlp_solve_to_string (mip_res));
+ LOG (GNUNET_ERROR_TYPE_INFO,
+ "Solving MLP problem: %s\n",
+ 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));
+ LOG (GNUNET_ERROR_TYPE_INFO,
+ "Solving MLP problem solution was interupted: %s\n",
+ mlp_solve_to_string (mip_res));
break;
case GLP_EBOUND:
case GLP_EROOT:
@@ -1330,9 +1359,9 @@
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));
+ LOG (GNUNET_ERROR_TYPE_INFO,
+ "Solving MLP problem failed: %s\n",
+ mlp_solve_to_string (mip_res));
break;
}
@@ -1342,25 +1371,38 @@
{
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));
+ "Solution of MLP problem is optimal: %s, %s\n",
+ mlp_solve_to_string (mip_res),
+ 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;
+
+ if ( (mlp->ps.mlp_gap <= mlp->pv.mip_gap) ||
+ (mlp->ps.lp_mlp_gap <= mlp->pv.lp_mip_gap) )
+ {
+ LOG (GNUNET_ERROR_TYPE_WARNING,
+ "Solution of MLP problem is feasible and solution within gap
constraints: %s, %s\n",
+ mlp_solve_to_string (mip_res),
+ mlp_status_to_string (mip_status));
+ mip_res = GNUNET_OK;
+ }
+ else
+ {
+ LOG (GNUNET_ERROR_TYPE_WARNING,
+ "Solution of MLP problem is feasible but solution not within
gap constraints: %s, %s\n",
+ mlp_solve_to_string (mip_res),
+ mlp_status_to_string (mip_status));
+ mip_res = GNUNET_SYSERR;
+ }
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));
+ "Solving MLP problem failed: %s %s\n",
+ mlp_solve_to_string (mip_res),
+ mlp_status_to_string (mip_status));
mip_res = GNUNET_SYSERR;
break;
}
@@ -2290,8 +2332,8 @@
}
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))
{
@@ -2307,6 +2349,22 @@
mlp->pv.mip_gap);
}
+ mlp->pv.lp_mip_gap = (double) 0.0;
+ if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_string (env->cfg, "ats",
+ "MLP_MAX_LP_MIP_GAP", &tmp_str))
+ {
+ /* Dangerous due to localized separator , or . */
+ mlp->pv.lp_mip_gap = strtod (tmp_str, NULL);
+ if ( (mlp->pv.lp_mip_gap < 0.0) && (mlp->pv.lp_mip_gap > 1.0) )
+ {
+ LOG (GNUNET_ERROR_TYPE_INFO, "Invalid LP/MIP gap configuration %u \n",
+ tmp);
+ }
+ else
+ LOG (GNUNET_ERROR_TYPE_WARNING, "Using LP/MIP gap of %.3f\n",
+ mlp->pv.lp_mip_gap);
+ }
+
/* Get timeout for iterations */
if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time(env->cfg, "ats",
"MLP_MAX_DURATION", &max_duration))
Modified: gnunet/src/ats/plugin_ats_mlp.h
===================================================================
--- gnunet/src/ats/plugin_ats_mlp.h 2014-05-13 22:20:01 UTC (rev 33271)
+++ gnunet/src/ats/plugin_ats_mlp.h 2014-05-13 22:50:28 UTC (rev 33272)
@@ -29,6 +29,7 @@
#include "gnunet_ats_plugin.h"
#include "gnunet-service-ats_addresses.h"
#include "gnunet_statistics_service.h"
+#include <float.h>
#if HAVE_LIBGLPK
#include "glpk.h"
#endif
@@ -74,6 +75,7 @@
double lp_objective_value;
double mlp_objective_value;
double mlp_gap;
+ double lp_mlp_gap;
int p_elements;
int p_cols;
@@ -163,6 +165,9 @@
/* MIP Gap */
double mip_gap;
+ /* LP MIP Gap */
+ double lp_mip_gap;
+
/* ATS Quality metrics
*
* Array with GNUNET_ATS_QualityPropertiesCount elements
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r33272 - gnunet/src/ats,
gnunet <=