[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r33269 - gnunet/src/ats
From: |
gnunet |
Subject: |
[GNUnet-SVN] r33269 - gnunet/src/ats |
Date: |
Tue, 13 May 2014 23:54:23 +0200 |
Author: wachs
Date: 2014-05-13 23:54:23 +0200 (Tue, 13 May 2014)
New Revision: 33269
Modified:
gnunet/src/ats/ats.conf.in
gnunet/src/ats/perf_ats_solver.c
gnunet/src/ats/perf_ats_solver.conf
gnunet/src/ats/plugin_ats_mlp.c
gnunet/src/ats/plugin_ats_mlp.h
Log:
implementation of mip gap tolerance interval
Modified: gnunet/src/ats/ats.conf.in
===================================================================
--- gnunet/src/ats/ats.conf.in 2014-05-13 20:37:20 UTC (rev 33268)
+++ gnunet/src/ats/ats.conf.in 2014-05-13 21:54:23 UTC (rev 33269)
@@ -44,8 +44,12 @@
# 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
Modified: gnunet/src/ats/perf_ats_solver.c
===================================================================
--- gnunet/src/ats/perf_ats_solver.c 2014-05-13 20:37:20 UTC (rev 33268)
+++ gnunet/src/ats/perf_ats_solver.c 2014-05-13 21:54:23 UTC (rev 33269)
@@ -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"
Modified: gnunet/src/ats/perf_ats_solver.conf
===================================================================
--- gnunet/src/ats/perf_ats_solver.conf 2014-05-13 20:37:20 UTC (rev 33268)
+++ gnunet/src/ats/perf_ats_solver.conf 2014-05-13 21:54:23 UTC (rev 33269)
@@ -35,6 +35,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_COEFFICIENT_D = 1.0
# MLP_COEFFICIENT_U = 1.0
# MLP_COEFFICIENT_R = 1.0
@@ -43,8 +46,9 @@
# 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
#MLP_DBG_OPTIMIZE_RELATIVITY = NO
@@ -54,8 +58,7 @@
# 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
+
Modified: gnunet/src/ats/plugin_ats_mlp.c
===================================================================
--- gnunet/src/ats/plugin_ats_mlp.c 2014-05-13 20:37:20 UTC (rev 33268)
+++ gnunet/src/ats/plugin_ats_mlp.c 2014-05-13 21:54:23 UTC (rev 33269)
@@ -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 @@
/**
- * 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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
/* 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 @@
/* 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 @@
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 @@
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 @@
int c;
int c2;
int found;
+ char *tmp_str;
char *outputformat;
struct GNUNET_TIME_Relative max_duration;
@@ -2218,7 +2290,23 @@
}
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",
"MLP_MAX_DURATION", &max_duration))
@@ -2429,7 +2517,11 @@
/* 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;
Modified: gnunet/src/ats/plugin_ats_mlp.h
===================================================================
--- gnunet/src/ats/plugin_ats_mlp.h 2014-05-13 20:37:20 UTC (rev 33268)
+++ gnunet/src/ats/plugin_ats_mlp.h 2014-05-13 21:54:23 UTC (rev 33269)
@@ -71,6 +71,10 @@
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 @@
/* Big M value for bandwidth capping */
double BIG_M;
+ /* MIP Gap */
+ double mip_gap;
+
/* ATS Quality metrics
*
* Array with GNUNET_ATS_QualityPropertiesCount elements
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r33269 - gnunet/src/ats,
gnunet <=