From 780ca0cd82979273de26bd01971bc5547e7aa609 Mon Sep 17 00:00:00 2001 From: Sebastian Hack Date: Thu, 16 Jun 2011 12:58:11 +0200 Subject: [PATCH] added lpp --- ir/lpp/lpp.c | 584 ++++++++++++++++++++++++++++++++++ ir/lpp/lpp.h | 303 ++++++++++++++++++ ir/lpp/lpp_cmd.def | 9 + ir/lpp/lpp_comm.c | 421 +++++++++++++++++++++++++ ir/lpp/lpp_comm.h | 124 ++++++++ ir/lpp/lpp_cplex.c | 268 ++++++++++++++++ ir/lpp/lpp_cplex.h | 15 + ir/lpp/lpp_net.c | 234 ++++++++++++++ ir/lpp/lpp_net.h | 21 ++ ir/lpp/lpp_remote.c | 186 +++++++++++ ir/lpp/lpp_remote.h | 15 + ir/lpp/lpp_server.c | 585 ++++++++++++++++++++++++++++++++++ ir/lpp/lpp_server.h | 179 +++++++++++ ir/lpp/lpp_set_dbg.c | 28 ++ ir/lpp/lpp_show.c | 38 +++ ir/lpp/lpp_t.h | 54 ++++ ir/lpp/lpp_test.c | 37 +++ ir/lpp/mps.c | 162 ++++++++++ ir/lpp/mps.h | 35 +++ ir/lpp/sp_matrix.c | 733 +++++++++++++++++++++++++++++++++++++++++++ ir/lpp/sp_matrix.h | 145 +++++++++ 21 files changed, 4176 insertions(+) create mode 100644 ir/lpp/lpp.c create mode 100644 ir/lpp/lpp.h create mode 100644 ir/lpp/lpp_cmd.def create mode 100644 ir/lpp/lpp_comm.c create mode 100644 ir/lpp/lpp_comm.h create mode 100644 ir/lpp/lpp_cplex.c create mode 100644 ir/lpp/lpp_cplex.h create mode 100644 ir/lpp/lpp_net.c create mode 100644 ir/lpp/lpp_net.h create mode 100644 ir/lpp/lpp_remote.c create mode 100644 ir/lpp/lpp_remote.h create mode 100644 ir/lpp/lpp_server.c create mode 100644 ir/lpp/lpp_server.h create mode 100644 ir/lpp/lpp_set_dbg.c create mode 100644 ir/lpp/lpp_show.c create mode 100644 ir/lpp/lpp_t.h create mode 100644 ir/lpp/lpp_test.c create mode 100644 ir/lpp/mps.c create mode 100644 ir/lpp/mps.h create mode 100644 ir/lpp/sp_matrix.c create mode 100644 ir/lpp/sp_matrix.h diff --git a/ir/lpp/lpp.c b/ir/lpp/lpp.c new file mode 100644 index 000000000..af1bd2d36 --- /dev/null +++ b/ir/lpp/lpp.c @@ -0,0 +1,584 @@ +/** + * Author: Daniel Grund + * Date: Fri 13.05.2005 + * Copyright: (c) Universitaet Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * CVS-Id: $Id: lpp.c 27353 2010-04-07 13:33:16Z matze $ + */ + +#include "config.h" + +#ifdef HAVE_IO_H +#include +#endif + +#include +#include +#include + +#include "assert.h" +#include "obst.h" +#include "hashptr.h" +#include "debug.h" +#include "set.h" + +#include "sp_matrix.h" +#include "mps.h" +#include "lpp_t.h" +#include "lpp_comm.h" + +#define HASH_NAME_T(n) HASH_STR((n)->name, strlen((n)->name)) + +static firm_dbg_module_t *dbg = NULL; + +static inline char *obst_xstrdup(struct obstack *obst, const char *str) { + return obstack_copy0(obst, str, strlen(str)); +} + +static int cmp_name_t(const void *x, const void *y, size_t size) { + const lpp_name_t *n = x; + const lpp_name_t *m = y; + (void)size; /* stop warnings */ + return strcmp(n->name, m->name); +} + +/** + * Update statistic information about matrix usage. + */ +static void update_stats(lpp_t *lpp) { + lpp->n_elems = matrix_get_entries(lpp->m); + lpp->matrix_mem = lpp->n_elems * matrix_get_elem_size(); + lpp->density = (double)lpp->n_elems / (double)(lpp->cst_next * lpp->var_next) * 100.0; +} + +#define INITIAL_SIZE 64 + +lpp_t *new_lpp(const char *name, lpp_opt_t opt_type) { + return new_lpp_userdef(name, opt_type, INITIAL_SIZE, INITIAL_SIZE, 2.0); +} + +lpp_t *new_lpp_userdef(const char *name, lpp_opt_t opt_type, + int estimated_vars, int estimated_csts, double grow_factor) +{ + lpp_t *lpp; + int idx; + + dbg = firm_dbg_register("lpp"); + lpp = XMALLOCZ(lpp_t); + obstack_init(&lpp->obst); + + lpp->name = obst_xstrdup(&lpp->obst, name); + lpp->opt_type = opt_type; + lpp->grow_factor = grow_factor; + lpp->cst2nr = new_set(cmp_name_t, estimated_csts); + lpp->var2nr = new_set(cmp_name_t, estimated_vars); + lpp->cst_size = estimated_csts; + lpp->var_size = estimated_vars; + lpp->csts = XMALLOCNZ(lpp_name_t *, estimated_csts); + lpp->vars = XMALLOCNZ(lpp_name_t *, estimated_vars); + lpp->m = new_matrix(estimated_csts, estimated_vars); + lpp->emphasis = lpp_balanced; + idx = lpp_add_cst(lpp, "obj", lpp_objective, 0); + assert(idx == 0); + idx = lpp_add_var(lpp, "rhs", lpp_rhs, 0); + assert(idx == 0); + + return lpp; +} + +void free_lpp_matrix(lpp_t *lpp) { + del_matrix(lpp->m); + lpp->m = NULL; +} + +void free_lpp(lpp_t *lpp) { + obstack_free(&lpp->obst, NULL); + + del_set(lpp->cst2nr); + del_set(lpp->var2nr); + + /* matrix might have been already deleted */ + if (lpp->m) + del_matrix(lpp->m); + + free(lpp->csts); + free(lpp->vars); + + free(lpp); +} + +double lpp_get_fix_costs(lpp_t *lpp) { + return matrix_get(lpp->m, 0, 0); +} + +void lpp_set_fix_costs(lpp_t *lpp, double value) { + matrix_set(lpp->m, 0, 0, value); +} + +static inline int name2nr(set *where, const char *name) { + lpp_name_t find, *found; + find.name = name; + found = set_find(where, &find, sizeof(find), HASH_NAME_T(&find)); + return (found ? found->nr : -1); +} + +#define cst_nr(lpp, name) name2nr(lpp->cst2nr, name) +#define var_nr(lpp, name) name2nr(lpp->var2nr, name) + +static inline char *get_next_name(lpp_t *lpp) { + char *res = obstack_alloc(&lpp->obst, 12); + snprintf(res, 12, "_%d", lpp->next_name_number++); + return res; +} + +int lpp_add_cst(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs) { + lpp_name_t n, *inner; + + DBG((dbg, LEVEL_2, "%s %d %g\n", cst_name, cst_type, rhs)); + + if (cst_name && cst_name[0] == '_') + return ERR_NAME_NOT_ALLOWED; + + if (cst_name) + n.name = obst_xstrdup(&lpp->obst, cst_name); + else + n.name = get_next_name(lpp); + + n.nr = -1; + inner = set_insert(lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n)); + assert(inner); + + if (inner->nr == -1) { + inner->value_kind = lpp_none; + inner->value = 0.0; + inner->nr = lpp->cst_next; + inner->type.cst_type = cst_type; + + if (lpp->cst_next == lpp->cst_size) { + lpp->cst_size = (int)((double)lpp->cst_size * lpp->grow_factor) + 1; + lpp->csts = XREALLOC(lpp->csts, lpp_name_t *, lpp->cst_size); + } + + lpp->csts[lpp->cst_next] = inner; + lpp->cst_next++; + matrix_set(lpp->m, inner->nr, 0, rhs); + } + + update_stats(lpp); + return inner->nr; +} + +int lpp_add_cst_uniq(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs) { + if (cst_name) { + lpp_name_t n; + + n.name = cst_name; + n.nr = -1; + assert(!set_find(lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n)) && + "constraint already exists"); + } + return lpp_add_cst(lpp, cst_name, cst_type, rhs); +} + +int lpp_get_cst_idx(lpp_t *lpp, const char *cst_name) { + DBG((dbg, LEVEL_2, "%s --> %d\n", cst_name, cst_nr(lpp, cst_name))); + return cst_nr(lpp, cst_name); +} + +void lpp_get_cst_name(lpp_t *lpp, int index, char *buf, size_t buf_size) { + DBG((dbg, LEVEL_2, "%d --> %s\n", index, lpp->csts[index]->name)); + strncpy(buf, lpp->csts[index]->name, buf_size); +} + +int lpp_add_var_default(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj, double startval) { + int val; + + val = lpp_add_var(lpp, var_name, var_type, obj); + lpp_set_start_value(lpp, val, startval); + + return val; +} + +int lpp_add_var(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj) { + lpp_name_t n, *inner; + + DBG((dbg, LEVEL_2, "%s %d %g\n", var_name, var_type, obj)); + + assert(var_type != lpp_invalid && "invalid is for internal use only"); + + if (var_name && var_name[0] == '_') + return ERR_NAME_NOT_ALLOWED; + + if (var_name) + n.name = obst_xstrdup(&lpp->obst, var_name); + else + n.name = get_next_name(lpp); + + n.nr = -1; + inner = set_insert(lpp->var2nr, &n, sizeof(n), HASH_NAME_T(&n)); + assert(inner); + + if (inner->nr == -1) { + inner->nr = lpp->var_next; + inner->value_kind = 0; + inner->value = 0; + inner->type.var_type = var_type; + + if (lpp->var_next == lpp->var_size) { + lpp->var_size = (int)((double)lpp->var_size * lpp->grow_factor) + 1; + lpp->vars = XREALLOC(lpp->vars, lpp_name_t *, lpp->var_size); + } + + lpp->vars[lpp->var_next] = inner; + lpp->var_next++; + matrix_set(lpp->m, 0, inner->nr, obj); + } + + update_stats(lpp); + return inner->nr; +} + +int lpp_get_var_idx(lpp_t *lpp, const char *var_name) { + DBG((dbg, LEVEL_2, "%s --> %d\n", var_name, var_nr(lpp, var_name))); + return var_nr(lpp, var_name); +} + +void lpp_get_var_name(lpp_t *lpp, int index, char *buf, size_t buf_size) { + DBG((dbg, LEVEL_2, "%d --> %s\n", index, lpp->vars[index]->name)); + strncpy(buf, lpp->vars[index]->name, buf_size); +} + +int lpp_set_factor(lpp_t *lpp, const char *cst_name, const char *var_name, double value) { + int cst, var; + + cst = cst_nr(lpp, cst_name); + var = var_nr(lpp, var_name); + assert(cst != -1 && var != -1); + DBG((dbg, LEVEL_2, "%s[%d] %s[%d] %g\n", cst_name, cst, var_name, var, value)); + matrix_set(lpp->m, cst, var, value); + update_stats(lpp); + return 0; +} + +int lpp_set_factor_fast(lpp_t *lpp, int cst_idx, int var_idx, double value) { + assert(cst_idx >= 0 && var_idx >= 0); + assert(cst_idx < lpp->cst_next && var_idx < lpp->var_next); + DBG((dbg, LEVEL_2, "%s[%d] %s[%d] %g\n", lpp->csts[cst_idx]->name, cst_idx, lpp->vars[var_idx]->name, var_idx, value)); + matrix_set(lpp->m, cst_idx, var_idx, value); + update_stats(lpp); + return 0; +} + +int lpp_set_factor_fast_bulk(lpp_t *lpp, int cst_idx, int *var_idx, int num_vars, double value) { + assert(cst_idx >= 0 && cst_idx < lpp->cst_next); + assert(num_vars < lpp->var_next); + DBG((dbg, LEVEL_2, "row %s[%d] %d vars %g\n", lpp->csts[cst_idx]->name, cst_idx, num_vars, value)); + matrix_set_row_bulk(lpp->m, cst_idx, var_idx, num_vars, value); + update_stats(lpp); + return 0; +} + +void lpp_set_start_value(lpp_t *lpp, int var_idx, double value) { + assert(var_idx > 0 && var_idx < lpp->var_next); + DBG((dbg, LEVEL_2, "%d %s %g\n", var_idx, lpp->vars[var_idx]->name, value)); + lpp->vars[var_idx]->value = value; + lpp->vars[var_idx]->value_kind = lpp_value_start; +} + +lpp_sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end) { + int i; + + if (lpp->sol_state < lpp_feasible) + return lpp->sol_state; + + /* here we are feasible or optimal */ + for (i = 0; i < end - begin + 1; ++i) + values[i] = lpp->vars[begin + i]->value; + + return lpp->sol_state; +} + +void lpp_check_startvals(lpp_t *lpp) { + int cst_idx; + + for (cst_idx = 1; cst_idx < lpp->cst_next; ++cst_idx) { + double sum = 0.0; + lpp_name_t *cst = lpp->csts[cst_idx]; + double cst_val = matrix_get(lpp->m, cst_idx, 0); + int var_idx; + + for (var_idx = 1; var_idx < lpp->var_next; ++var_idx) { + if (lpp->vars[var_idx]->value_kind != lpp_value_start) + goto next; + + sum += lpp->vars[var_idx]->value * + matrix_get(lpp->m, cst_idx, var_idx); + } + switch(cst->type.cst_type) { + case lpp_equal: + if(sum != cst_val) { + fprintf(stderr, "constraint %s unsatisfied: %g != %g\n", cst->name, sum, cst_val); + } + break; + case lpp_less: + if(sum > cst_val) { + fprintf(stderr, "constraint %s unsatisfied: %g > %g\n", cst->name, sum, cst_val); + } + break; + case lpp_greater: + if(sum < cst_val) { + fprintf(stderr, "constraint %s unsatisfied: %g < %g\n", cst->name, sum, cst_val); + } + break; + default: + assert(0 && "unknown constraint type"); + } +next: ; + } +} + +void lpp_dump(lpp_t *lpp, const char *filename) { + FILE *out = fopen(filename, "wt"); + mps_write_mps(lpp, s_mps_fixed, out); + fclose(out); +} + +void lpp_set_log(lpp_t *lpp, FILE *log) +{ + lpp->log = log; +} + + +static const char *lpp_cst_op_to_str(lpp_cst_t cst) +{ + switch(cst) { + case lpp_equal: + return "="; + case lpp_less: + return "<="; + case lpp_greater: + return ">="; + default: + return ""; + } +} + +void lpp_dump_plain(lpp_t *lpp, FILE *f) +{ + int i; + + for(i = 0; i < lpp->cst_next; ++i) { + const matrix_elem_t *elm; + lpp_name_t *cst = lpp->csts[i]; + + fprintf(f, "%16s: ", cst->name); + matrix_foreach_in_row(lpp->m, cst->nr, elm) { + lpp_name_t *var = lpp->vars[elm->col]; + /* TODO Perhaps better a define LPP_COL_RHS */ + if(elm->col > 0) + fprintf(f, "%+4.1f*%-16s ", elm->val, var->name); + } + + fprintf(f, "%3s %+4.1f\n", + lpp_cst_op_to_str(cst->type.cst_type), matrix_get(lpp->m, cst->nr, 0)); + } +} + +/** + * Serialize a lpp to a file descriptor. + * @param comm The file descriptor. + * @param lpp The lpp. + */ +void lpp_serialize(lpp_comm_t *comm, const lpp_t *lpp, int with_names) +{ + int n, i; + + lpp_writel(comm, with_names); + lpp_writel(comm, lpp->cst_next); + lpp_writel(comm, lpp->var_next); + lpp_writel(comm, lpp->opt_type); + lpp_writes(comm, lpp->name); + + /* write options */ + lpp_writel(comm, lpp->set_bound); + lpp_writed(comm, lpp->bound); + lpp_writed(comm, lpp->time_limit_secs); + lpp_writed(comm, lpp->emphasis); + + for(i = 0; i < lpp->cst_next; ++i) { + lpp_name_t *name = lpp->csts[i]; + lpp_writel(comm, name->nr); + lpp_writel(comm, name->value_kind); + lpp_writel(comm, name->type.cst_type); + + if(with_names) + lpp_writes(comm, name->name); + } + + for(i = 0; i < lpp->var_next; ++i) { + lpp_name_t *name = lpp->vars[i]; + lpp_writel(comm, name->nr); + lpp_writel(comm, name->value_kind); + lpp_writel(comm, name->type.var_type); + + if(with_names) + lpp_writes(comm, name->name); + } + + { + const matrix_elem_t *elm; + n = 0; + + matrix_foreach(lpp->m, elm) + n++; + + assert(n == matrix_get_entries(lpp->m)); + lpp_writel(comm, n); + matrix_foreach(lpp->m, elm) { + lpp_writel(comm, elm->row); + lpp_writel(comm, elm->col); + lpp_writed(comm, elm->val); + } + } +} + +#define NAMELEN 64 + +/** + * Deserialize an lpp from a file descriptor. + * @param comm The file descriptor. + * @return The Problem. + */ +lpp_t *lpp_deserialize(lpp_comm_t *comm) +{ + int i, n; + int with_names; + + lpp_t *lpp = XMALLOCZ(lpp_t); + + /* read general settings */ + with_names = lpp_readl(comm); + lpp->cst_next = lpp_readl(comm); + lpp->var_next = lpp_readl(comm); + lpp->opt_type = lpp_readl(comm); + lpp->name = lpp_reads(comm); + + /* read options */ + lpp->set_bound = lpp_readl(comm); + lpp->bound = lpp_readd(comm); + lpp->time_limit_secs = lpp_readd(comm); + lpp->emphasis = lpp_readd(comm); + + lpp->cst_size = lpp->cst_next; + lpp->var_size = lpp->var_next; + + lpp->cst2nr = new_set(cmp_name_t, lpp->cst_next); + lpp->var2nr = new_set(cmp_name_t, lpp->var_next); + + lpp->csts = XMALLOCNZ(lpp_name_t*, lpp->cst_next); + lpp->vars = XMALLOCNZ(lpp_name_t*, lpp->var_next); + lpp->m = new_matrix(lpp->cst_next, lpp->var_next); + + for(i = 0; i < lpp->cst_next; ++i) { + lpp_name_t name, *res; + + name.nr = lpp_readl(comm); + name.value_kind = lpp_readl(comm); + name.type.cst_type = lpp_readl(comm); + + if(with_names) + name.name = lpp_reads(comm); + else { + char* buf = XMALLOCN(char, NAMELEN); + snprintf(buf, NAMELEN, "c%d\n", name.nr); + name.name = buf; + } + + res = set_insert(lpp->cst2nr, &name, sizeof(name), HASH_NAME_T(&name)); + lpp->csts[name.nr] = res; + } + + for(i = 0; i < lpp->var_next; ++i) { + lpp_name_t name, *res; + + name.nr = lpp_readl(comm); + name.value_kind = lpp_readl(comm); + name.type.var_type = lpp_readl(comm); + + if(with_names) + name.name = lpp_reads(comm); + else { + char* buf = XMALLOCN(char, NAMELEN); + snprintf(buf, NAMELEN, "v%d\n", name.nr); + name.name = buf; + } + + res = set_insert(lpp->var2nr, &name, sizeof(name), HASH_NAME_T(&name)); + lpp->vars[name.nr] = res; + } + + n = lpp_readl(comm); + for(i = 0; i < n; ++i) { + matrix_elem_t elm; + elm.row = lpp_readl(comm); + elm.col = lpp_readl(comm); + elm.val = lpp_readd(comm); + matrix_set(lpp->m, elm.row, elm.col, elm.val); + } + + return lpp; +} + +void lpp_serialize_values(lpp_comm_t *comm, const lpp_t *lpp, lpp_value_kind_t value_kind) +{ + int i, n; + + for(i = 0, n = 0; i < lpp->var_next; ++i) + n += lpp->vars[i]->value_kind == value_kind; + + /* Write the number of values to expect */ + lpp_writel(comm, n); + + /* send the values */ + for(i = 0, n = lpp->var_next; i < n; ++i) { + const lpp_name_t *name = lpp->vars[i]; + if(name->value_kind == value_kind) { + lpp_writel(comm, name->nr); + lpp_writed(comm, name->value); + } + } +} + +void lpp_deserialize_values(lpp_comm_t *comm, lpp_t *lpp, lpp_value_kind_t value_kind) +{ + int i, n; + + /* Get the number of values to read */ + n = lpp_readl(comm); + + for(i = 0; i < n; ++i) { + int nr = lpp_readl(comm); + lpp_name_t *name = lpp->vars[nr]; + + name->value_kind = value_kind; + name->value = lpp_readd(comm); + } +} + +void lpp_serialize_stats(lpp_comm_t *comm, const lpp_t *lpp) +{ + lpp_writel(comm, lpp->sol_state); + lpp_writel(comm, lpp->iterations); + lpp_writed(comm, lpp->sol_time); + lpp_writed(comm, lpp->objval); + lpp_writed(comm, lpp->best_bound); +} + +void lpp_deserialize_stats(lpp_comm_t *comm, lpp_t *lpp) +{ + lpp->sol_state = lpp_readl(comm); + lpp->iterations = lpp_readl(comm); + lpp->sol_time = lpp_readd(comm); + lpp->objval = lpp_readd(comm); + lpp->best_bound = lpp_readd(comm); +} diff --git a/ir/lpp/lpp.h b/ir/lpp/lpp.h new file mode 100644 index 000000000..1fd6bb43e --- /dev/null +++ b/ir/lpp/lpp.h @@ -0,0 +1,303 @@ +/** + * Author: Daniel Grund + * Date: 16.05.2005 + * Copyright: (c) Universitaet Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * CVS-Id: $Id: lpp.h 16112 2007-10-07 15:50:49Z mallon $ + * + * Interface for specifying an milp. Does not define a solution method. + */ +#ifndef _LPP_H +#define _LPP_H + +#include +#include + +#include "set.h" + +#include "sp_matrix.h" + +typedef enum _lpp_opt_t { + lpp_minimize, + lpp_maximize +} lpp_opt_t; + +typedef enum _lpp_cst_t { + lpp_objective = 0, + lpp_equal = 1, + lpp_less = 2, + lpp_greater = 3 +} lpp_cst_t; + +typedef enum _lpp_var_t { + lpp_invalid = 0, + lpp_rhs = 1, + lpp_continous = 2, + lpp_binary = 3 +} lpp_var_t; + +typedef enum _lpp_sol_state_t { + lpp_unknown = 0, + lpp_infeasible = 1, + lpp_inforunb = 2, + lpp_unbounded = 3, + lpp_feasible = 4, + lpp_optimal = 5 +} lpp_sol_state_t; + +typedef enum _lpp_value_kind_t { + lpp_none = 0, + lpp_value_start = 1, + lpp_value_solution = 2, +} lpp_value_kind_t; + +typedef enum _lpp_emphasis_t { + lpp_balanced = 0, + lpp_feasability = 1, + lpp_optimality = 2, + lpp_bestbound = 3, + lpp_hiddenfeasibility = 4 +} lpp_emphasis_t; + +typedef struct _name_t { + const char *name; /**< the name of the var/constraint supplied by user */ + int nr; /**< the col/row number in the matrix */ + lpp_value_kind_t value_kind; + double value; + union _type { + lpp_var_t var_type; + lpp_cst_t cst_type; + } type; +} lpp_name_t; + +typedef struct _lpp_t { + /* The problem data */ + const char *name; /**< A textual name for this problem */ + FILE *log; /**< The log file. */ + lpp_opt_t opt_type; /**< Optimization direction */ + struct obstack obst; /**< Obstack for variable names */ + sp_matrix_t *m; /**< The matrix holding objective, constraints and rhs */ + + /* Cst/Var to Nr mapping */ + set *cst2nr; /**< Holds name_t's for constraints */ + set *var2nr; /**< Holds name_t's for variables */ + + /* Nr to Cst/Var mapping */ + int cst_size, var_size; /**< Size of the csts/vars-arrays below */ + int cst_next, var_next; /**< Next free position in arrays below */ + lpp_name_t **csts; /**< Pointers to the elements in the cst2nr set */ + lpp_name_t **vars; /**< Pointers to the elements in the var2nr set */ + double objval; /**< OUT: Value of the objective function. */ + double best_bound; /**< OUT: best bound to the integer solution. */ + double grow_factor; /**< The factor by which the vars and constraints are enlarged */ + + /* Solving options */ + int set_bound; /**< IN: Boolean flag to set a bound for the objective function. */ + double bound; /**< IN: The bound. Only valid if set_bound == 1. */ + double time_limit_secs; /**< IN: Time limit to obey while solving (0.0 means no time limit) */ + + /* Solution stuff */ + lpp_sol_state_t sol_state; /**< State of the solution */ + double sol_time; /**< Time in seconds */ + unsigned iterations; /**< Number of iterations CPLEX needed to solve the ILP (whatever this means) */ + + char *error; + unsigned next_name_number; /**< for internal use only */ + lpp_emphasis_t emphasis; /**< On what should CPLEX concentrate (feasibility, bestbound, ...) */ + + /* some statistic stuff */ + unsigned send_time; /**< in case of solve_net: send time in usec */ + unsigned recv_time; /**< in case of solve_net: recv time in usec */ + unsigned n_elems; /**< number of elements stored in the matrix */ + unsigned matrix_mem; /**< memory used by matrix elements (in bytes) */ + double density; /**< density of the matrix (percentage) */ +} lpp_t; + +#define ERR_NAME_NOT_ALLOWED -2 + +/** + * Creates a new problem. Optimization type is minimize or maximize. + * Implicit row with name "obj" is inserted. + * Implicit col with name "rhs" is inserted. + */ +lpp_t *new_lpp(const char *name, lpp_opt_t opt_type); + +/** + * Creates a new problem. Optimization type is minimize or maximize. + * Implicit row with name "obj" is inserted. + * Implicit col with name "rhs" is inserted. + * @param estimated_vars The estimated number of variables for the problem + * @param estimated_csts The estimated number of constraints for the problem + * @param grow_factor By which factor should the problem grow, if there are + * more variables or constraints than estimated. + */ +lpp_t *new_lpp_userdef(const char *name, lpp_opt_t opt_type, + int estimated_vars, int estimated_csts, double grow_factor); + +/** + * Frees the matrix embedded in the LPP. + */ +void free_lpp_matrix(lpp_t *lpp); + +/** + * Frees all memory allocated for LPP data structure. + */ +void free_lpp(lpp_t *lpp); + +/** + * @return The constant term in the objective function + */ +double lpp_get_fix_costs(lpp_t *lpp); + +/** + * Sets the constant term in the objective function to @p value + */ +void lpp_set_fix_costs(lpp_t *lpp, double value); + +/** + * Adds a constraint to a problem. If a constraint with the same name already + * exists nothing is altered, and the index of the existing entry is returned. + * @param cst_name The name of the constraint (1st char only alpha-numeric!). If NULL, a default name will be used. + * @param cst_type The type of constraint: objective, equality, less-or-equal, greater-or-equal + * @param rhs The right hand side value to set for this constraint. + * @return The (new or existing) index of the constraint + */ +int lpp_add_cst(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs); + +/** + * Adds a constraint to a problem. If a constraint with the same name already + * exists it dies a horribly cruel death + * @param cst_name The name of the constraint (1st char only alpha-numeric!). If NULL, a default name will be used. + * @param cst_type The type of constraint: objective, equality, less-or-equal, greater-or-equal + * @param rhs The right hand side value to set for this constraint. + * @return The (new or existing) index of the constraint + */ +int lpp_add_cst_uniq(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs); + +/** + * Returns the internal index of a constraint. + * @param cst_name The name of the constraint + * @return The internal index of constraint @p cst_name or -1 if it does not exist. + */ +int lpp_get_cst_idx(lpp_t *lpp, const char *cst_name); + +/** + * Returns the name of a constraint. + * @param index The internal index of a constraint. + * @param buf A buffer to hold the name of the constraint + * @param buf_size Size of the buffer + */ +void lpp_get_cst_name(lpp_t *lpp, int index, char *buf, size_t buf_size); + +/** + * Adds a variable to a problem. If a variable with the same name already + * exists nothing is altered, and the index of the existing entry is returned. + * @param var_name The name of the constraint (1st char only alpha-numeric!). If NULL, a default name will be used. + * @param var_type The type of variable: real, binary + * @param obj The objective value coefficient for this variable. + * @return The (new or existing) index of the variable + * + * NOTE: common integer or semi-continuous vars are not (yet) implemented + */ +int lpp_add_var(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj); + +/** + * Same as lpp_add_var() but the user can supply a default value. + */ +int lpp_add_var_default(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj, double startval); + +/** + * Returns the internal index of a variable. + * @param cst_name The name of the variable + * @return The internal index of variable @p var_name or -1 if it does not exist. + */ +int lpp_get_var_idx(lpp_t *lpp, const char *var_name); + +/** + * Returns the name of a variable. + * @param index The internal index of a variable. + * @param buf A buffer to hold the name of the variable + * @param buf_size Size of the buffer + */ +void lpp_get_var_name(lpp_t *lpp, int index, char *buf, size_t buf_size); + +/** + * Sets the factor of the variable @p var_name in constraint @p cst_name to @p value. + * @return -1 if constraint or variable name does not exist. + * 0 otherwise + */ +int lpp_set_factor(lpp_t *lpp, const char *cst_name, const char *var_name, double value); + +/** + * Same as lpp_set_factor but uses the internal indices instead of names. + * @return -1 if an index was invalid + * 0 otherwise + */ +int lpp_set_factor_fast(lpp_t *lpp, int cst_idx, int var_idx, double value); + +int lpp_set_factor_fast_bulk(lpp_t *lpp, int cst_idx, int *var_idx, int num_vars, double value); + +/** + * Set a starting value for a var. + * @param var_idx The index of the variable to set the value for. + * @param value The value to set. + */ +void lpp_set_start_value(lpp_t *lpp, int var_idx, double value); + +/** + * @return The solution values of the variables from index begin to index end. + */ +lpp_sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end); + +/** + * Dumps the lpp into a file with name @p filename in MPS-format + */ +void lpp_dump(lpp_t *lpp, const char *filename); + +/** + * Set the log file, where the solver should write to. + * @param lpp The problem. + * @param log The logfile. NULL for no logging. + */ +void lpp_set_log(lpp_t *lpp, FILE *log); + +/** + * Check the start values and list conflicting constraints. + */ +void lpp_check_startvals(lpp_t *lpp); + +/** + * Dump problem into a text file. + * @param lpp The problem. + * @param f The file. + */ +void lpp_dump_plain(lpp_t *lpp, FILE *f); + +#define lpp_get_iter_cnt(lpp) ((lpp)->iterations) +#define lpp_get_sol_time(lpp) ((lpp)->sol_time) +#define lpp_get_sol_state(lpp) ((lpp)->sol_state) +#define lpp_get_var_count(lpp) ((lpp)->var_next-1) +#define lpp_get_cst_count(lpp) ((lpp)->cst_next-1) +#define lpp_get_sol_state(lpp) ((lpp)->sol_state) +#define lpp_get_var_sol(lpp,idx) ((lpp)->vars[idx]->value) +#define lpp_is_sol_valid(lpp) (lpp_get_sol_state(lpp) >= lpp_feasible) + +#define lpp_set_time_limit(lpp,secs) ((lpp)->time_limit_secs = secs) + +/** + * Set a bound for the objective function. + * @param lpp The problem. + * @param bound A bound for the objective function. + * If the problem is a minimization problem, the bound + * is a lower bound. If it is a maximization problem, + * the bound is an upper bound. + */ +#define lpp_set_bound(lpp,bnd) ((lpp)->set_bound = 1, (lpp)->bound = (bnd)) + +/** + * Clear a set bound. + * @param lpp The problem. + */ +#define lpp_unset_bound(lpp) ((lpp)->set_bound = 0) + +#endif /* _LPP_H */ diff --git a/ir/lpp/lpp_cmd.def b/ir/lpp/lpp_cmd.def new file mode 100644 index 000000000..513f54cc7 --- /dev/null +++ b/ir/lpp/lpp_cmd.def @@ -0,0 +1,9 @@ +LPP_CMD(BAD) +LPP_CMD(OK) +LPP_CMD(PROBLEM) +LPP_CMD(SOLUTION) +LPP_CMD(SOLVER) +LPP_CMD(BYE) +LPP_CMD(SOLVERS) +LPP_CMD(SET_DEBUG) +LPP_CMD(INFO) diff --git a/ir/lpp/lpp_comm.c b/ir/lpp/lpp_comm.c new file mode 100644 index 000000000..ea0a0b241 --- /dev/null +++ b/ir/lpp/lpp_comm.c @@ -0,0 +1,421 @@ +/** + * @file lpp_comm.c + * @date 21.07.2005 + * @author Sebastian Hack + * + * Protocol stuff for lpp server + * + * Copyright (C) 2005 Universitaet Karlsruhe + * Released under the GPL + */ + +#include +#include +#include +#include + +#ifdef _WIN32 +#define WIN32_LEAN_AND_MEAN +#include +#include + +#define vsnprintf _vsnprintf + +#else +#include +#include +#include +#endif + +#include "irtools.h" +#include "debug.h" + +#include "lpp_comm.h" + + +/* undef to disable buffering socket i/o */ +#define ENABLE_BUFFERING + +/* undef to disable debugging */ +#undef ENABLE_DEBUGGING + +struct _lpp_comm_t { + int fd; + size_t buf_size; + char *w_pos; + char *r_pos; + char *r_max; + char *w_buf; + char *r_buf; +}; + +static firm_dbg_module_t *dbg = NULL; + +/** + * Try to read some bytes but block until a certain amount is read. + * @param fd The file descriptor. + * @param buf The buffer to read into. + * @param try The amount of bytes to try to read. + * @param at_least block until this many bytes are read. + * @return The number of bytes read or -1 on error. + */ +static ssize_t secure_recv(int fd, void *buf, size_t try, size_t at_least) +{ + ssize_t res; + size_t bytes_read = 0; + char *data = buf; + + do { + res = recv(fd, &data[bytes_read], try - bytes_read, 0); + if(res <= 0) { + if(res == 0 || errno != EAGAIN) + return -1; + continue; + } + + bytes_read += res; + + } while(bytes_read < at_least); + + return bytes_read; +} + +static ssize_t secure_send(int fd, const void *buf, size_t n) +{ + ssize_t res; + size_t bytes_written = 0; + const char *data = buf; + + do { + res = send(fd, &data[bytes_written], n - bytes_written, 0); + if(res < 0) { + if(errno != EAGAIN) + return -1; + continue; + } + + bytes_written += res; + + } while(bytes_written < n); + + return n; +} + +#ifdef ENABLE_BUFFERING +ssize_t lpp_flush(lpp_comm_t *comm) +{ + ssize_t res = 0; + if(comm->w_pos - comm->w_buf > 0) { + DBG((dbg, LEVEL_1, "flushing %d bytes\n", comm->w_pos - comm->w_buf)); + res = secure_send(comm->fd, comm->w_buf, comm->w_pos - comm->w_buf); + if(res < 0) + return res; + + comm->w_pos = comm->w_buf; + } + return res; +} + +static ssize_t lpp_write(lpp_comm_t *comm, const void *buf, size_t len) +{ + assert(comm->w_pos - comm->w_buf >= 0); + + DBG((dbg, LEVEL_1, "write of length %d\n", len)); + if(len > 0) { + size_t free = (comm->w_buf + comm->buf_size) - comm->w_pos; + size_t copy = MIN(free, len); + size_t rest = len - copy; + const char *pos = buf; + + DBG((dbg, LEVEL_1, "\tfree = %d, copy = %d, rest = %d\n", free, copy, rest)); + if(copy > 0) { + memcpy(comm->w_pos, pos, copy); + comm->w_pos += copy; + pos += copy; + } + + /* + * Not everything in buf fits into the buffer, + * so flush the buffer and write the rest. + */ + if(rest > 0) { + size_t i; + size_t n_direct = rest / comm->buf_size; + size_t last_rest; + + if(lpp_flush(comm) < 0) + return -1; + + for(i = 0; i < n_direct; ++i) { + if(secure_send(comm->fd, pos, comm->buf_size) < 0) + return -1; + + pos += comm->buf_size; + } + + last_rest = ((const char *) buf + len) - pos; + + if(last_rest > 0) { + assert(last_rest < comm->buf_size); + assert(comm->w_pos == comm->w_buf); + memcpy(comm->w_pos, pos, last_rest); + comm->w_pos += last_rest; + } + } + } + + return len; +} + +static ssize_t lpp_read(lpp_comm_t *comm, void *buf, size_t len) +{ + DBG((dbg, LEVEL_1, "read of length %d\n", len)); + if(len > 0) { + size_t left = comm->r_max - comm->r_pos; + size_t copy = MIN(left, len); + size_t rest = len - copy; + char *pos = buf; + + DBG((dbg, LEVEL_1, "\tleft = %d, copy = %d, rest = %d\n", left, copy, rest)); + if(copy > 0) { + memcpy(pos, comm->r_pos, copy); + pos += copy; + comm->r_pos += copy; + } + + /* We want to read more than the buffer can provide. */ + if(rest > 0) { + size_t bs = comm->buf_size; + size_t n_direct = rest / comm->buf_size; + size_t i; + size_t last_rest; + + /* + * The buffer is now completely read, so + * reset the pointers. + */ + comm->r_pos = comm->r_buf; + comm->r_max = comm->r_buf; + + for(i = 0; i < n_direct; ++i) { + if(secure_recv(comm->fd, pos, bs, bs) < 0) + return -1; + + pos += comm->buf_size; + } + + last_rest = ((const char *) buf + len) - pos; + + if(last_rest > 0) { + ssize_t bytes_read = 0; + + assert(last_rest < comm->buf_size); + assert(comm->r_pos == comm->r_buf); + + bytes_read = secure_recv(comm->fd, comm->r_buf, bs, last_rest); + if(bytes_read < 0) + return -1; + + memcpy(pos, comm->r_buf, last_rest); + comm->r_pos = comm->r_buf + last_rest; + comm->r_max = comm->r_buf + bytes_read; + } + } + } + + return len; +} + +#else /* ENABLE_BUFFERING */ +ssize_t lpp_flush(lpp_comm_t *comm) +{ + return 0; +} + +static ssize_t lpp_write(lpp_comm_t *comm, const void *buf, size_t len) +{ + return secure_send(comm->fd, buf, len); +} + +static ssize_t lpp_read(lpp_comm_t *comm, void *buf, size_t len) +{ + return secure_recv(comm->fd, buf, len, len); +} +#endif + +lpp_comm_t *lpp_comm_new(int fd, size_t buf_size) +{ + lpp_comm_t *res = malloc(sizeof(res[0])); + + res->fd = fd; + res->w_buf = malloc(buf_size); + res->w_pos = res->w_buf; + res->r_buf = malloc(buf_size); + res->r_pos = res->r_buf; + res->r_max = res->r_buf; + res->buf_size = buf_size; + + return res; +} + +int lpp_comm_fileno(const lpp_comm_t *comm) +{ + return comm->fd; +} + +void lpp_comm_free(lpp_comm_t *comm) +{ + free(comm->w_buf); + free(comm->r_buf); + free(comm); +} + +void lpp_print_err(const char *fmt, ...) +{ + va_list args; + + va_start(args, fmt); + vfprintf(stderr, fmt, args); + va_end(args); +} + +void lpp_writel(lpp_comm_t *comm, uint32_t x) +{ + x = htonl(x); + ERRNO_CHECK(lpp_write(comm, &x, sizeof(x)), !=, sizeof(x)); +} + +void lpp_writed(lpp_comm_t *comm, double dbl) +{ + ERRNO_CHECK(lpp_write(comm, &dbl, sizeof(dbl)), !=, sizeof(dbl)); +} + +void lpp_writes(lpp_comm_t *comm, const char *str) +{ + size_t n = strlen(str); + lpp_writel(comm, n); + ERRNO_CHECK(lpp_write(comm, str, n), !=, (ssize_t) n); +} + +uint32_t lpp_readl(lpp_comm_t *comm) +{ + uint32_t res; + + ERRNO_CHECK(lpp_read(comm, &res, sizeof(res)), !=, sizeof(res)); + return ntohl(res); +} + +int lpp_read_cmd(lpp_comm_t *comm) +{ + uint32_t res = 0; + int retval; + + for(;;) { + retval = recv(comm->fd, (char *)&res, sizeof(res), 0); + if(retval < 0) { + if(errno != EAGAIN) + return -1; + } + + else + break; + } + + return (int) ntohl(res); +} + +double lpp_readd(lpp_comm_t *comm) +{ + double res; + ERRNO_CHECK(lpp_read(comm, &res, sizeof(res)), !=, sizeof(res)); + return res; +} + +char *lpp_reads(lpp_comm_t *comm) +{ + size_t len = lpp_readl(comm); + char *res = malloc(sizeof(char) * (len + 1)); + + ERRNO_CHECK(lpp_read(comm, res, len), !=, (ssize_t) len); + res[len] = '\0'; + return res; +} + +char *lpp_readbuf(lpp_comm_t *comm, char *buf, size_t buflen) +{ + char dummy[1024]; + size_t i; + size_t n = buflen - 1; + size_t len = lpp_readl(comm); + size_t max_read = n < len ? n : len; + size_t rest = len - max_read; + + if(buflen > 0 && buf != NULL) { + ERRNO_CHECK(lpp_read(comm, buf, max_read), !=, (ssize_t) max_read); + buf[max_read] = '\0'; + } + else + rest = len; + + /* eat up data that didnt fit into the string */ + for(i = 0, n = rest / sizeof(dummy); i < n; ++i) + ERRNO_CHECK(lpp_read(comm, dummy, sizeof(dummy)), !=, sizeof(dummy)); + + if(rest % sizeof(dummy) > 0) + ERRNO_CHECK(lpp_read(comm, dummy, rest % sizeof(dummy)), !=, + (ssize_t) (rest % sizeof(dummy)) ); + + return buf; +} + +int lpp_ack(lpp_comm_t *comm, char *buf, size_t buflen) +{ + int res = 0; + int cmd = lpp_readl(comm); + + switch(cmd) { + case LPP_CMD_OK: + res = 1; + break; + case LPP_CMD_BAD: + lpp_readbuf(comm, buf, buflen); + default: + res = 0; + } + + return res; +} + +void lpp_send_res(lpp_comm_t *comm, int ok, const char *fmt, ...) +{ + if(!ok) { + char buf[1024]; + va_list args; + + va_start(args, fmt); + vsnprintf(buf, sizeof(buf), fmt, args); + va_end(args); + + lpp_writel(comm, LPP_CMD_BAD); + lpp_writes(comm, buf); + } + + else + lpp_writel(comm, LPP_CMD_OK); +} + +void lpp_send_ack(lpp_comm_t *comm) +{ + lpp_send_res(comm, 1, ""); +} + +const char *lpp_get_cmd_name(int cmd) +{ + switch(cmd) { +#define LPP_CMD(x) case LPP_CMD_ ## x: return #x; +#include "lpp_cmd.def" +#undef LPP_CMD + } + + return ""; +} diff --git a/ir/lpp/lpp_comm.h b/ir/lpp/lpp_comm.h new file mode 100644 index 000000000..5d03f1aa9 --- /dev/null +++ b/ir/lpp/lpp_comm.h @@ -0,0 +1,124 @@ +/** + * @file lpp_server.h + * @date 19.07.2005 + * @author Sebastian Hack + * + * Copyright (C) 2005 Universitaet Karlsruhe + * Released under the GPL + */ + +#ifndef _LPP_COMM_H +#define _LPP_COMM_H + +#include +#include + +#ifdef _MSC_VER + +typedef size_t ssize_t; +typedef unsigned __int16 uint16_t; +typedef unsigned __int32 uint32_t; + +/* disable warning: 'foo' was declared deprecated, use 'bla' instead */ +/* of course MS had to make 'bla' incompatible to 'foo', so a simple */ +/* define will not work :-((( */ +#pragma warning( disable : 4996 ) + +#else /* _MSC_VER */ + +#include +#include +#include +#include + +#endif /* _MSC_VER */ + + + +#define LPP_PORT 2175 +#define LPP_BUFSIZE (1 << 20) + +enum { +#define LPP_CMD(x) LPP_CMD_ ## x, +#include "lpp_cmd.def" +#undef LPP_CMD + LPP_CMD_LAST +}; + +#define BASIC_ERR_CHECK(expr,op,cond,fmt,last) \ +{ \ + int res; \ + if((res = (expr)) op cond) { \ + fprintf(stderr, "%s(%u): %d = %s(%d): ", \ + __FILE__, (unsigned) __LINE__, res, #expr, cond); \ + lpp_print_err fmt; \ + fprintf(stderr, "\n"); \ + last; \ + } \ +} + +#define BASIC_ERRNO_CHECK(expr,op,cond,last) \ +{ \ + int _basic_errno_check_res = (expr); \ + if(_basic_errno_check_res op cond) { \ + fprintf(stderr, "%s(%u): %d = %s(%d): %s\n", \ + __FILE__, (unsigned) __LINE__, _basic_errno_check_res, #expr, (int) cond, strerror(errno)); \ + last; \ + } \ +} + +#define ERR_CHECK_RETURN(expr, op, cond, fmt, retval) \ + BASIC_ERR_CHECK(expr, op, cond, fmt, return retval) + +#define ERRNO_CHECK_RETURN(expr, op, cond, retval) \ + BASIC_ERRNO_CHECK(expr, op, cond, return retval) + +#define ERR_CHECK_RETURN_VOID(expr, op, cond, fmt) \ + BASIC_ERR_CHECK(expr, op, cond, fmt, return) + +#define ERRNO_CHECK_RETURN_VOID(expr, op, cond) \ + BASIC_ERRNO_CHECK(expr, op, cond, return) + +#define ERR_CHECK(expr, op, cond, fmt) \ + BASIC_ERR_CHECK(expr, op, cond, fmt, (void) 0) + +#define ERRNO_CHECK(expr, op, cond) \ + BASIC_ERRNO_CHECK(expr, op, cond, (void) 0) + +typedef struct _lpp_comm_t lpp_comm_t; + +lpp_comm_t *lpp_comm_new(int fd, size_t buf_size); + +int lpp_comm_fileno(const lpp_comm_t *comm); + +ssize_t lpp_flush(lpp_comm_t *comm); + +void lpp_comm_free(lpp_comm_t *comm); + +void lpp_print_err(const char *fmt, ...); + +void lpp_writel(lpp_comm_t *comm, uint32_t x); + +void lpp_writed(lpp_comm_t *comm, double dbl); + +void lpp_writes(lpp_comm_t *comm, const char *str); + +uint32_t lpp_readl(lpp_comm_t *comm); + +int lpp_read_cmd(lpp_comm_t *comm); + +double lpp_readd(lpp_comm_t *comm); + +char *lpp_reads(lpp_comm_t *comm); + +char *lpp_readbuf(lpp_comm_t *comm, char *buf, size_t buflen); + +int lpp_ack(lpp_comm_t *comm, char *buf, size_t buflen); + +void lpp_send_res(lpp_comm_t *comm, int ok, const char *fmt, ...); + +void lpp_send_ack(lpp_comm_t *comm); + +const char *lpp_get_cmd_name(int cmd); + +#endif /* _LPP_COMM_H */ diff --git a/ir/lpp/lpp_cplex.c b/ir/lpp/lpp_cplex.c new file mode 100644 index 000000000..d6a1f3b42 --- /dev/null +++ b/ir/lpp/lpp_cplex.c @@ -0,0 +1,268 @@ +/** + * Author: Daniel Grund + * Date: 02.06.2005 + * Copyright: (c) Universitaet Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ + +#include "lpp_cplex.h" + +#include +#include + + +#ifdef _WIN32 +#include +#else +#include +#include +#endif + +#include "obst.h" + +#include + +#include "assert.h" +#include "sp_matrix.h" + +static char cpx_cst_encoding[4] = "?ELG"; +static char cpx_var_encoding[4] = "??CB"; + +#define my_timersub(tvp, uvp, vvp) \ + do { \ + (vvp)->tv_sec = (tvp)->tv_sec - (uvp)->tv_sec; \ + (vvp)->tv_usec = (tvp)->tv_usec - (uvp)->tv_usec; \ + if ((vvp)->tv_usec < 0) { \ + (vvp)->tv_sec--; \ + (vvp)->tv_usec += 1000000; \ + } \ + } while (0) + +typedef struct _cpx_t { + lpp_t *lpp; + CPXENVptr env; + CPXLPptr prob; + int status; + char buf[1024]; +} cpx_t; + +static void chk_cpx_err(cpx_t *cpx) { + if (cpx->status) { + if (CPXgeterrorstring(cpx->env, cpx->status, cpx->buf)) + printf("%s", cpx->buf); + else + printf("Unknown CPLEX error\n"); + assert(0); + } +} + +static cpx_t *new_cpx(lpp_t *lpp) { + cpx_t *cpx = XMALLOCZ(cpx_t); + cpx->lpp = lpp; + cpx->env = CPXopenCPLEX(&cpx->status); + chk_cpx_err(cpx); + cpx->prob = CPXcreateprob(cpx->env, &cpx->status, lpp->name); + chk_cpx_err(cpx); + CPXchgobjsen(cpx->env, cpx->prob, (lpp->opt_type == lpp_minimize)?1:-1); + chk_cpx_err(cpx); + if (lpp->log && CPXsetlogfile(cpx->env, lpp->log)) + lpp->log = NULL; + return cpx; +} + +static void free_cpx(cpx_t *cpx) { + CPXfreeprob(cpx->env, &cpx->prob); + CPXcloseCPLEX(&cpx->env); + free(cpx); +} + +/** + * Build CPLEX data structure from LPP matrix. + * @note: The LPP matrix is freed after this step, to save memory. + */ +static void cpx_construct(cpx_t *cpx) { + const matrix_elem_t *elem; + int i, o, sv_cnt; + int numcols, numrows, numentries; + int objsen, *matbeg, *matcnt, *matind, *indices; + double *obj, *rhs, *matval, *lb, *ub, *startv; + char *sense, *vartype; + char **colname, **rowname; + struct obstack obst; + lpp_t *lpp = cpx->lpp; + + numcols = lpp->var_next-1; + numrows = lpp->cst_next-1; + numentries = matrix_get_entries(lpp->m); + objsen = lpp->opt_type == lpp_minimize ? 1 : -1; + obstack_init(&obst); + + obj = obstack_alloc(&obst, numcols * sizeof(*obj)); + lb = obstack_alloc(&obst, numcols * sizeof(*lb)); + ub = obstack_alloc(&obst, numcols * sizeof(*ub)); + colname = obstack_alloc(&obst, numcols * sizeof(*colname)); + rowname = obstack_alloc(&obst, numrows * sizeof(*rowname)); + vartype = obstack_alloc(&obst, numcols * sizeof(*vartype)); + indices = obstack_alloc(&obst, numcols * sizeof(*indices)); + startv = obstack_alloc(&obst, numcols * sizeof(*startv)); + matbeg = obstack_alloc(&obst, numcols * sizeof(*matbeg)); + matcnt = obstack_alloc(&obst, numcols * sizeof(*matcnt)); + matind = obstack_alloc(&obst, numentries * sizeof(*matind)); + matval = obstack_alloc(&obst, numentries * sizeof(*matval)); + rhs = obstack_alloc(&obst, numrows * sizeof(*rhs)); + sense = obstack_alloc(&obst, numrows * sizeof(*sense)); + + o = 0; + sv_cnt = 0; + /* fill the CPLEX matrix*/ + for (i = 0; i < numcols; ++i) { + lpp_name_t *curr_var = lpp->vars[1+i]; + + obj[i] = matrix_get(lpp->m, 0, 1+i); + lb[i] = 0.0; + ub[i] = CPX_INFBOUND; + + colname[i] = (char*) curr_var->name; + vartype[i] = cpx_var_encoding[curr_var->type.var_type]; + + if (curr_var->value_kind == lpp_value_start) { + indices[sv_cnt] = i; + startv[sv_cnt++] = curr_var->value; + } + + matbeg[i] = o; + matcnt[i] = 0; + matrix_foreach_in_col(lpp->m, 1 + i, elem) { + if (elem->row == 0) + continue; + matind[o] = elem->row-1; + matval[o] = elem->val; + matcnt[i]++; + o++; + } + } + + /* get constraint stuff (right hand side, type, name) */ + for (i = 0; i < numrows; ++i) { + lpp_name_t *curr_cst = lpp->csts[1 + i]; + + rhs[i] = matrix_get(lpp->m, 1 + i, 0); + sense[i] = cpx_cst_encoding[curr_cst->type.cst_type]; + rowname[i] = (char*) curr_cst->name; + } + + cpx->status = CPXcopylpwnames(cpx->env, cpx->prob, + numcols, numrows, objsen, + obj, rhs, sense, + matbeg, matcnt, matind, matval, + lb, ub, NULL, + colname, rowname); + chk_cpx_err(cpx); + + cpx->status = CPXcopyctype(cpx->env, cpx->prob, vartype); + chk_cpx_err(cpx); + cpx->status = CPXcopymipstart(cpx->env, cpx->prob, sv_cnt, indices, startv); + chk_cpx_err(cpx); + + obstack_free(&obst, NULL); + free_lpp_matrix(lpp); +} + +static void cpx_solve(cpx_t *cpx) { + int i, CPX_state, numcols; + double *values; + struct timeval tvb, tva, tvdiff; + + lpp_t *lpp = cpx->lpp; + numcols = CPXgetnumcols(cpx->env, cpx->prob); + chk_cpx_err(cpx); + + /* set performance parameters */ + // CPXsetintparam(cpx->env, CPX_PARAM_MIPSTART, CPX_ON); + CPXsetintparam(cpx->env, CPX_PARAM_MIPORDTYPE, CPX_MIPORDER_COST); + /* output every search tree node */ + // CPXsetintparam(cpx->env, CPX_PARAM_MIPINTERVAL, 1); + + /* experimental switches */ + // CPXsetintparam(cpx->env, CPX_PARAM_VARSEL, CPX_VARSEL_STRONG); + // CPXsetdblparam(cpx->env, CPX_PARAM_BTTOL, 1.0); + // CPXsetintparam(cpx->env, CPX_PARAM_BRDIR, CPX_BRDIR_UP); + + + /* Set the time limit appropriately */ + if(lpp->time_limit_secs > 0.0) + CPXsetdblparam(cpx->env, CPX_PARAM_TILIM, lpp->time_limit_secs); + + /* + * If we have enough time, we instruct cplex to imply some + * of its higher order magic to pursue the best solution + */ + if(lpp->emphasis) { + CPXsetintparam(cpx->env, CPX_PARAM_MIPEMPHASIS, lpp->emphasis); + } + + /* + * If a bound of the objective function is supplied, + * set it accordingly, dependign on minimization or maximization. + */ + if(lpp->set_bound) { + CPXsetdblparam(cpx->env, (lpp->opt_type == lpp_minimize + ? CPX_PARAM_OBJLLIM : CPX_PARAM_OBJULIM), lpp->bound); + } + + /* solve */ + gettimeofday(&tvb, NULL); + cpx->status = CPXmipopt(cpx->env, cpx->prob); + gettimeofday(&tva, NULL); + chk_cpx_err(cpx); + + /* get solution status */ + CPX_state = CPXgetstat(cpx->env, cpx->prob); + { + char buf[512]; + CPXgetstatstring(cpx->env, CPX_state, buf); + fprintf(stderr, "%s\n", buf); + } + switch (CPX_state) { + case CPXMIP_INFEASIBLE: + case CPX_STAT_INFEASIBLE: lpp->sol_state = lpp_infeasible; break; + case CPXMIP_INForUNBD: + case CPX_STAT_INForUNBD: lpp->sol_state = lpp_inforunb; break; + case CPXMIP_UNBOUNDED: + case CPX_STAT_UNBOUNDED: lpp->sol_state = lpp_unbounded; break; + case CPXMIP_ABORT_FEAS: + case CPXMIP_FAIL_FEAS: + case CPXMIP_MEM_LIM_FEAS: + case CPXMIP_NODE_LIM_FEAS: + case CPXMIP_TIME_LIM_FEAS: lpp->sol_state = lpp_feasible; break; + case CPXMIP_OPTIMAL: + case CPXMIP_OPTIMAL_TOL: /* TODO: Is this ok? Read the docu more closely */ + case CPX_STAT_OPTIMAL: lpp->sol_state = lpp_optimal; break; + default: lpp->sol_state = lpp_unknown; + } + + /* get variable solution values */ + values = alloca(numcols * sizeof(*values)); + CPXgetmipx(cpx->env, cpx->prob, values, 0, numcols-1); + chk_cpx_err(cpx); + for(i=0; ivars[1+i]->value = values[i]; + lpp->vars[1+i]->value_kind = lpp_value_solution; + } + + /* Get the value of the objective function. */ + CPXgetmipobjval(cpx->env, cpx->prob, &lpp->objval); + CPXgetbestobjval(cpx->env, cpx->prob, &lpp->best_bound); + + /* get some statistics */ + my_timersub(&tva, &tvb, &tvdiff); + lpp->sol_time = tvdiff.tv_sec + tvdiff.tv_usec / 1e6; + lpp->iterations = CPXgetmipitcnt(cpx->env, cpx->prob); +} + +void lpp_solve_cplex(lpp_t *lpp) { + cpx_t *cpx = new_cpx(lpp); + cpx_construct(cpx); + cpx_solve(cpx); + free_cpx(cpx); +} diff --git a/ir/lpp/lpp_cplex.h b/ir/lpp/lpp_cplex.h new file mode 100644 index 000000000..b1566868c --- /dev/null +++ b/ir/lpp/lpp_cplex.h @@ -0,0 +1,15 @@ +/** + * Author: Daniel Grund + * Date: 02.06.2005 + * Copyright: (c) Universitaet Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ + +#ifndef _LPP_CPLEX_H_ +#define _LPP_CPLEX_H_ + +#include "lpp.h" + +void lpp_solve_cplex(lpp_t *lpp); + +#endif /*_LPP_CPLEX_H_*/ diff --git a/ir/lpp/lpp_net.c b/ir/lpp/lpp_net.c new file mode 100644 index 000000000..de91540ec --- /dev/null +++ b/ir/lpp/lpp_net.c @@ -0,0 +1,234 @@ +/** + * @file lpp_net.c + * @date 19.07.2005 + * @author Sebastian Hack + * + * A client for an lpp solving server. + * + * Copyright (C) 2005 Universitaet Karlsruhe + * Released under the GPL + */ + +#ifdef _WIN32 +#include +#include + +#else +#include +#include +#include +#include +#include + +#include +#include +#include + +#include + +/* solaris fix */ +#ifndef INADDR_NONE +#define INADDR_NONE (in_addr_t)(-1) +#endif + +#endif + + +#include +#include +#include +#include +#include + +#include "timing.h" + +#include "lpp_net.h" +#include "lpp_t.h" +#include "lpp_comm.h" + +#ifdef _WIN32 +static int winsock_init(void) { + WORD wVersionRequested; + WSADATA wsaData; + int err; + + wVersionRequested = MAKEWORD( 2, 2 ); + + err = WSAStartup( wVersionRequested, &wsaData ); + if ( err != 0 ) { + /* Tell the user that we could not find a usable */ + /* WinSock DLL. */ + return 0; + } + + /* Confirm that the WinSock DLL supports 2.2.*/ + /* Note that if the DLL supports versions greater */ + /* than 2.2 in addition to 2.2, it will still return */ + /* 2.2 in wVersion since that is the version we */ + /* requested. */ + + if ( LOBYTE( wsaData.wVersion ) != 2 || + HIBYTE( wsaData.wVersion ) != 2 ) { + /* Tell the user that we could not find a usable */ + /* WinSock DLL. */ + WSACleanup( ); + return 0; + } + return 1; +} +#endif + +static int connect_tcp(const char *host, uint16_t port) +{ + struct hostent *phe; + struct protoent *ppe; + struct sockaddr_in sin; + int s; + +#ifdef _WIN32 + winsock_init(); +#endif + + memset(&sin, 0, sizeof(sin)); + sin.sin_family = AF_INET; + sin.sin_port = htons(port); + + if ((phe = gethostbyname(host))) + memcpy(&sin.sin_addr, phe->h_addr, phe->h_length); + else if((sin.sin_addr.s_addr = inet_addr(host)) == INADDR_NONE) { + lpp_print_err("cannot get host entry for %s", host); + return -1; + } + + ppe = getprotobyname("tcp"); + ERRNO_CHECK_RETURN(s = socket(PF_INET, SOCK_STREAM, ppe->p_proto), <, 0, -1); + ERRNO_CHECK_RETURN(connect(s, (struct sockaddr *) &sin, sizeof(sin)), <, 0, -1); + + return s; +} + +char **lpp_get_solvers(const char *host) +{ + int fd, n; + char **res = NULL; + lpp_comm_t *comm; + + ERR_CHECK_RETURN(fd = connect_tcp(host, LPP_PORT), <, 0, + ("could not connect to %s", host), NULL); + + comm = lpp_comm_new(fd, LPP_BUFSIZE); + + lpp_writel(comm, LPP_CMD_SOLVERS); + lpp_flush(comm); + n = lpp_readl(comm); + res = malloc((n + 1) * sizeof(res[0])); + res[n] = NULL; + + if(n > 0) { + int i; + for(i = 0; i < n; ++i) + res[i] = lpp_reads(comm); + } + + lpp_writel(comm, LPP_CMD_BYE); + lpp_flush(comm); + lpp_comm_free(comm); + close(fd); + return res; +} + +void lpp_set_dbg(const char *host, int mask) +{ + int fd; + lpp_comm_t *comm; + + ERR_CHECK_RETURN_VOID(fd = connect_tcp(host, LPP_PORT), <, 0, ("could not connect to %s", host)); + + comm = lpp_comm_new(fd, LPP_BUFSIZE); + + lpp_writel(comm, LPP_CMD_SET_DEBUG); + lpp_writel(comm, mask); + lpp_flush(comm); + lpp_writel(comm, LPP_CMD_BYE); + lpp_flush(comm); + lpp_comm_free(comm); + close(fd); +} + +void lpp_solve_net(lpp_t *lpp, const char *host, const char *solver) +{ + char buf[1024]; + int n, fd, ready; + lpp_comm_t *comm; + ir_timer_t *t_send, *t_recv; + + ERR_CHECK_RETURN_VOID(fd = connect_tcp(host, LPP_PORT), <, 0, + ("could not connect to %s", host)); + + comm = lpp_comm_new(fd, LPP_BUFSIZE); + + /* Set the solver */ + lpp_writel(comm, LPP_CMD_SOLVER); + lpp_writes(comm, solver); + lpp_flush(comm); + +#if 0 + ERR_CHECK_RETURN_VOID(lpp_ack(fd, sizeof(buf), buf), == 0, + ("could not set solver: %s", solver)); +#endif + + t_send = ir_timer_new(); + t_recv = ir_timer_new(); + + ir_timer_push(t_send); + lpp_writel(comm, LPP_CMD_PROBLEM); + lpp_serialize(comm, lpp, 1); + lpp_serialize_values(comm, lpp, lpp_value_start); + lpp_flush(comm); + ir_timer_pop(); + lpp->send_time = ir_timer_elapsed_usec(t_send); + + ready = 0; + while (! ready) { + int cmd = lpp_readl(comm); + switch(cmd) { + case LPP_CMD_SOLUTION: + ir_timer_push(t_recv); + lpp_deserialize_stats(comm, lpp); + lpp_deserialize_values(comm, lpp, lpp_value_solution); + ir_timer_pop(); + lpp->recv_time = ir_timer_elapsed_usec(t_recv); + ready = 1; + break; + case LPP_CMD_INFO: + lpp_readbuf(comm, buf, sizeof(buf)); + buf[sizeof(buf) - 1] = '\0'; + + if(lpp->log != NULL) { + fputs(buf, lpp->log); + n = strlen(buf); + if(buf[n - 1] != '\n') + putc('\n', lpp->log); + fflush(lpp->log); + } + break; + case LPP_CMD_BAD: + fprintf(stderr, "solver process died unexpectedly\n"); + goto end; + default: + fprintf(stderr, "invalid command: %s(%d)\n", lpp_get_cmd_name(cmd), cmd); + return; + } + } + + lpp_writel(comm, LPP_CMD_BYE); + lpp_flush(comm); + +end: + lpp_comm_free(comm); +#ifdef _WIN32 + closesocket(fd); +#else + close(fd); +#endif +} diff --git a/ir/lpp/lpp_net.h b/ir/lpp/lpp_net.h new file mode 100644 index 000000000..b4133819f --- /dev/null +++ b/ir/lpp/lpp_net.h @@ -0,0 +1,21 @@ +/** + * @file lpp_net.h + * @date 20.07.2005 + * @author Sebastian Hack + * + * Copyright (C) 2005 Universitaet Karlsruhe + * Released under the GPL + */ + +#ifndef _LPP_NET_H +#define _LPP_NET_H + +#include "lpp.h" + +char **lpp_get_solvers(const char *host); + +void lpp_set_dbg(const char *host, int mask); + +void lpp_solve_net(lpp_t *lpp, const char *host, const char *solver); + +#endif /* _LPP_NET_H */ diff --git a/ir/lpp/lpp_remote.c b/ir/lpp/lpp_remote.c new file mode 100644 index 000000000..fabd13111 --- /dev/null +++ b/ir/lpp/lpp_remote.c @@ -0,0 +1,186 @@ +/** + * Author: Daniel Grund + * Date: 02.06.2005 + * Copyright: (c) Universitaet Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ +#include "config.h" + +#include +#include +#include +#include +#include + +#include "lpp_remote.h" +#include "assert.h" +#include "mps.h" + +#ifdef _WIN32 +#define WIN32_LEAN_AND_MEAN +#include + +#define snprintf _snprintf +#define chmod(a, b) _chmod(a, b) + +/* disable warning: 'foo' was declared deprecated, use 'bla' instead */ +/* of course MS had to make 'bla' incompatible to 'foo', so a simple */ +/* define will not work :-((( */ +#pragma warning( disable : 4996 ) + +#endif + +/* CPLEX-account related stuff */ +#define DELETE_FILES /**< deletes all dumped files after use. Files on server are always deleted. */ +#define SSH_USER_HOST "kb61@sp-smp.rz.uni-karlsruhe.de" +#define SSH_PASSWD_FILE "/ben/daniel/.smppw" +#define EXPECT_FILENAME "runme" /* name of the expect-script */ + +static FILE *ffopen(const char *base, const char *ext, const char *mode) { + FILE *out; + char buf[1024]; + + snprintf(buf, sizeof(buf), "%s.%s", base, ext); + if (! (out = fopen(buf, mode))) { + fprintf(stderr, "Cannot open file %s in mode %s\n", buf, mode); + return NULL; + } + return out; +} + +static void lpp_write_cmd(lpp_t *lpp) { + FILE *out = ffopen(lpp->name, "cmd", "wt"); + fprintf(out, "set logfile %s.sol\n", lpp->name); + fprintf(out, "set mip strategy mipstart 1\n"); + // fprintf(out, "set mip emphasis 3\n"); /* moving best bound */ + fprintf(out, "set mip emphasis 0\n"); /* balance optimality and feasability */ + fprintf(out, "set mip strategy variableselect 3\n"); /* strong branching */ + fprintf(out, "read %s.mps\n", lpp->name); + fprintf(out, "read %s.mst\n", lpp->name); + fprintf(out, "optimize\n"); + fprintf(out, "display solution variables -\n"); + fprintf(out, "quit\n"); + fclose(out); +} + +static void lpp_write_exp(lpp_t *lpp) { + FILE *pwfile, *out; + char passwd[128]; + + pwfile = fopen(SSH_PASSWD_FILE, "rt"); + fgets(passwd, sizeof(passwd), pwfile); + fclose(pwfile); + + out = ffopen(EXPECT_FILENAME, "exp", "wt"); + fprintf(out, "#! /usr/bin/expect\n"); + fprintf(out, "spawn scp %s.mps %s.mst %s.cmd %s:\n", lpp->name, lpp->name, lpp->name, SSH_USER_HOST); /* copy problem files */ + fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd); + + fprintf(out, "spawn ssh %s \"./cplex90 < %s.cmd\"\n", SSH_USER_HOST, lpp->name); /* solve */ + fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd); + + fprintf(out, "spawn scp %s:%s.sol .\n", SSH_USER_HOST, lpp->name); /*copy back solution */ + fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd); + + fprintf(out, "spawn ssh %s ./dell\n", SSH_USER_HOST); /* clean files on server */ + fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd); + fclose(out); +} + +static void lpp_read_solution(lpp_t *lpp) { + FILE *in; + double sol_time; + unsigned iter; + int vars_section = 0; + char var_name[128]; + double var_value; + + if (!(in = ffopen(lpp->name, "sol", "rt"))) { + lpp->sol_state = lpp_unknown; + return; + } + while (!feof(in)) { + char buf[1024]; + fgets(buf, sizeof(buf), in); + + /* error and solution state */ + if (!strncmp(buf, "CPLEX Error", 11)) + lpp->error = strdup(buf); + else if (!strncmp(buf, "Warning:", 8)) + lpp->error = strdup(buf); + else if (!strncmp(buf, "Integer optimal solution:", 25)) + lpp->sol_state = lpp_optimal; + else if (!strcmp(buf, "No integer feasible solution exists.")) + lpp->sol_state = lpp_infeasible; + else if (!strcmp(buf, "Error termination, integer feasible:")) + lpp->sol_state = lpp_feasible; + /* stats */ + else if (sscanf(buf, "Solution time = %lg sec. Iterations = %u", &sol_time, &iter) == 2) { + lpp->sol_time = sol_time; + lpp->iterations = iter; + } + /* variable values */ + else if(!strcmp(buf, "Variable Name Solution Value")) { + int i; + vars_section = 1; + for(i=0; ivar_next; ++i) { + lpp_name_t *var = lpp->vars[i]; + var->value = 0; + var->value_kind = lpp_value_solution; + } + } + else if(!strncmp(buf, "All other var", 13)) + vars_section = 0; + else if (vars_section) { + if (sscanf(buf, "%s %lg", var_name, &var_value) == 2) + lpp->vars[lpp_get_var_idx(lpp, var_name)]->value = var_value; + else + assert(0 && "There should be variables to read in!"); + } + } + fclose(in); + if (lpp->error) { + printf("\n%s\n", lpp->error); + assert(0); + } +} + +#ifdef DELETE_FILES +static void lpp_delete_files(lpp_t *lpp) { + char buf[1024]; + int end = snprintf(buf, sizeof(buf), "%s", lpp->name); + + snprintf(buf+end, sizeof(buf)-end, ".mps"); + remove(buf); + snprintf(buf+end, sizeof(buf)-end, ".mst"); + remove(buf); + snprintf(buf+end, sizeof(buf)-end, ".cmd"); + remove(buf); + snprintf(buf+end, sizeof(buf)-end, ".sol"); + remove(buf); + remove(EXPECT_FILENAME ".exp"); +} +#endif + +void lpp_solve_remote(lpp_t *lpp) { + FILE *out; + out = ffopen(lpp->name, "mps", "wt"); + mps_write_mps(lpp, s_mps_free, out); + fclose(out); + + out = ffopen(lpp->name, "mst", "wt"); + mps_write_mst(lpp, s_mps_free, out); + fclose(out); + + lpp_write_cmd(lpp); + lpp_write_exp(lpp); + + /* call the expect script */ + chmod(EXPECT_FILENAME ".exp", 0700); + system(EXPECT_FILENAME ".exp"); + + lpp_read_solution(lpp); +#ifdef DELETE_FILES + lpp_delete_files(lpp); +#endif +} diff --git a/ir/lpp/lpp_remote.h b/ir/lpp/lpp_remote.h new file mode 100644 index 000000000..c382a18fc --- /dev/null +++ b/ir/lpp/lpp_remote.h @@ -0,0 +1,15 @@ +/** + * Author: Daniel Grund + * Date: 02.06.2005 + * Copyright: (c) Universitaet Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ + +#ifndef _LPP_REMOTE_H_ +#define _LPP_REMOTE_H_ + +#include "lpp.h" + +void lpp_solve_remote(lpp_t *lpp); + +#endif /*_LPP_REMOTE_H_*/ diff --git a/ir/lpp/lpp_server.c b/ir/lpp/lpp_server.c new file mode 100644 index 000000000..bae79c0fe --- /dev/null +++ b/ir/lpp/lpp_server.c @@ -0,0 +1,585 @@ +/** + * @file lpp_server.c + * @date 19.07.2005 + * @author Sebastian Hack + * + * lpp_solving server. + * + * Copyright (C) 2005 Universitaet Karlsruhe + * Released under the GPL + */ + +#ifdef _WIN32 +#error Sorry, lpp_server is for UNIX only. +#endif + +#include +#include +#include +#include +#include +#include +#include + +#include +#include + +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "debug.h" +#include "list.h" +#include "irtools.h" +#include "util.h" + +#include "lpp_t.h" +#include "lpp_comm.h" +#include "lpp_cplex.h" + +#define MAX_JOBS 128 + +/* stack size of the solver thread. */ +static size_t solver_stack_size = PTHREAD_STACK_MIN; + +/* master listening socket. */ +static int msock; + +/* master semaphore */ +static int sem; + +/* title of the current process */ +static char *title; +static int title_length; + +static int n_children = 0; + +extern char** environ; + +typedef void (solver_func_t)(lpp_t *lpp); + +typedef struct _job_t { + struct list_head list; + int id; + pthread_t solver; + pthread_t session; + lpp_comm_t *comm; + lpp_t *lpp; + solver_func_t *solver_func; + time_t received; + int csock; +} job_t; + +#define set_solver_stack_size(size) solver_stack_size = MAX(PTHREAD_STACK_MIN, (size)) + +#define setproctitle(name, args...) snprintf(title,title_length,(name),##args) + +static void initproctitle(int argc, char **argv) { + int i; + char **envp = environ; + + /* + * Move the environment so we can reuse the memory. + * (Code borrowed from sendmail.) + * WARNING: ugly assumptions on memory layout here; + * if this ever causes problems, #undef DO_PS_FIDDLING + */ + for (i = 0; envp[i] != NULL; i++) + continue; + environ = (char **) malloc(sizeof(char *) * (i + 1)); + if (environ == NULL) + return; + for (i = 0; envp[i] != NULL; i++) + if ((environ[i] = strdup(envp[i])) == NULL) + return; + environ[i] = NULL; + + title = argv[0]; + if (i > 0) + title_length = envp[i-1] + strlen(envp[i-1]) - argv[0]; + else + title_length = argv[argc-1] + strlen(argv[argc-1]) - argv[0]; + + argv[1] = NULL; + memset(title, 0, title_length); + --title_length; +} + +static void job_init(job_t *job, lpp_comm_t *comm, lpp_t *lpp, solver_func_t *solver_func) +{ + /* TODO MAXJOBS */ + memset(job, 0, sizeof(job[0])); + job->lpp = lpp; + job->solver_func = solver_func; + job->comm = comm; + job->csock = lpp_comm_fileno(comm); + job->received = time(NULL); + job->session = pthread_self(); + job->id = getpid(); +} + +static firm_dbg_module_t *dbg = NULL; + +/** + * Set up a socket. + */ +static int passive_tcp(uint16_t port, int queue_len) +{ + int s; + int one = 1; + struct protoent *ppe; + struct sockaddr_in sin; + + memset(&sin, 0, sizeof(sin)); + sin.sin_family = AF_INET; + sin.sin_addr.s_addr = INADDR_ANY; + sin.sin_port = htons(port); + + ppe = getprotobyname("tcp"); + s = socket(PF_INET, SOCK_STREAM, ppe->p_proto); + setsockopt(s, SOL_SOCKET, SO_REUSEADDR, &one, sizeof(one)); + + if(bind(s, (struct sockaddr *) &sin, sizeof(sin)) < 0) { + perror("bind server socket"); + exit(1); + } + + if(listen(s, queue_len) < 0) { + perror("listen server socket"); + exit(1); + } + + return s; +} + +static void dummy_solver(lpp_t *lpp) +{ + int i; + + for(i = 0; i < lpp->var_next; ++i) { + lpp->vars[i]->value = i; + lpp->vars[i]->value_kind = lpp_value_solution; + } + + if(lpp->log) + fprintf(lpp->log, "dummy solver exiting now.\n"); + + sleep(1); + lpp->sol_time = 0.0; + lpp->iterations = 0; + lpp->sol_state = lpp_optimal; +} + +static void segv_solver(lpp_t *lpp) +{ + int i; + + for(i = 0; i < lpp->var_next; ++i) { + lpp->vars[i]->value = i; + lpp->vars[i]->value_kind = lpp_value_solution; + } + + if(lpp->log) + fprintf(lpp->log, "segv dummy solver exiting now.\n"); + + sleep(1); + *((int *) 0) = 1; +} + +#define DEFAULT_SOLVER lpp_solve_cplex + +struct { + solver_func_t *solver; + const char *name; + int n_instances; +} solvers[] = { + { lpp_solve_cplex, "cplex", 1 }, + { dummy_solver, "dummy", 2 }, + { segv_solver, "segv", 2 }, +}; + + +static solver_func_t *find_solver(const char *name) +{ + unsigned i; + + for(i = 0; i < sizeof(solvers) / sizeof(solvers[0]); ++i) + if(strcmp(solvers[i].name, name) == 0) + return solvers[i].solver; + + return NULL; +} + +static void *solver_thread(void * data) +{ + job_t *job = data; + DBG((dbg, LEVEL_1, "starting solver thread pid %d tid %d\n", getpid(), pthread_self())); + setproctitle("lpp_server [problem solving: %s]", job->lpp->name); + + /* I may be cancelled at every time. */ + pthread_setcanceltype(PTHREAD_CANCEL_ASYNCHRONOUS, NULL); + + /* solve */ + job->solver_func(job->lpp); + + /* notify the session thread that we are finished. */ + fclose(job->lpp->log); + + return NULL; +} + +static int solve(lpp_comm_t *comm, job_t *job) +{ + char buf[1024]; + struct timeval tv; + fd_set rfds; + int fds[2]; + FILE *rd, *log; + int res = 0; + int retval, fd_rd, fd_comm; + pthread_attr_t solver_thr_attr; + + struct sembuf semops; + /* try to acquire a lock for the solver resource. */ + semops.sem_num = 0; + semops.sem_op = -1; + semops.sem_flg = SEM_UNDO; + retval = semop(sem, &semops, 1); + if(retval < 0) { + perror("free semaphore"); + } + DBG((dbg, LEVEL_1, "job %d: solving problem %s\n", job->id, job->lpp->name)); + + /* set the log file of the lpp to the pipe. */ + pipe(fds); + DBG((dbg, LEVEL_4, "pipe read %d write %d\n", fds[0], fds[1])); + + fd_comm = lpp_comm_fileno(comm); + fd_rd = fds[0]; + rd = fdopen(fd_rd, "r"); + log = fdopen(fds[1], "w"); + + lpp_set_log(job->lpp, log); + + /* also set the stack size of the solver thread to a considerable amount */ + pthread_attr_init(&solver_thr_attr); + pthread_attr_setstacksize(&solver_thr_attr, solver_stack_size); + pthread_create(&job->solver, &solver_thr_attr, solver_thread, job); + + while(1) { + /* set select timeout to 10 seconds */ + tv.tv_sec = 10; + tv.tv_usec = 0; + + /* set the file descriptors. */ + FD_ZERO(&rfds); + FD_SET(fd_rd, &rfds); + FD_SET(fd_comm, &rfds); + DBG((dbg, LEVEL_4, "select %d %d\n", fd_rd, fd_comm)); + retval = select(MAX(fd_rd, fd_comm) + 1, &rfds, NULL, NULL, &tv); + DBG((dbg, LEVEL_4, "retval %d\n", retval)); + + /* an event on one of the descriptors arrived. */ + if(retval > 0) { + /* A log message arrived. */ + if(FD_ISSET(fd_rd, &rfds)) { + + /* if there is nothing more to read, the child died; we go home now. */ + if(feof(rd)) + break; + + if(fgets(buf, sizeof(buf), rd)) { + DBG((dbg, LEVEL_4, "receiving log message %s\n", buf)); + /* send the message over the net. */ + lpp_writel(comm, LPP_CMD_INFO); + lpp_writes(comm, buf); + lpp_flush(comm); + } + } + + /* A network message arrived. */ + if(FD_ISSET(fd_comm, &rfds)) { + int cmd; + int retval; + + retval = read(fd_comm, &cmd, sizeof(cmd)); + if(retval == 0) { + DBG((dbg, LEVEL_2, "cancelling solver thread tid %d\n", job->solver)); + //pthread_cancel(job->solver); + exit(1); + //res = 1; + //break; + } + + switch(cmd) { + /* eat senseless data. */ + default: + while(read(fd_comm, &cmd, sizeof(cmd)) > 0); + } + res = 1; + } + } + } + + pthread_join(job->solver, NULL); + semops.sem_num = 0; + semops.sem_op = 1; + semops.sem_flg = SEM_UNDO; + retval = semop(sem, &semops, 1); + if(retval < 0) { + perror("free semaphore"); + } + + fclose(rd); + return res; +} + +static void *session(int fd) +{ + solver_func_t *solver = DEFAULT_SOLVER; + lpp_comm_t *comm = lpp_comm_new(fd, LPP_BUFSIZE); + + DBG((dbg, LEVEL_1, "starting session thread pid %d tid %d\n", getpid(), pthread_self())); + setproctitle("lpp_server [child]"); + + /* install the signal handler which gets triggered when the child dies. */ + DBG((dbg, LEVEL_1, "new thread\n")); + for(;;) { + char buf[64]; + int cmd = lpp_readl(comm); + + DBG((dbg, LEVEL_2, "command: %s(%d)\n", lpp_get_cmd_name(cmd), cmd)); + setproctitle("lpp_server [command %s(%d)]", lpp_get_cmd_name(cmd), cmd); + switch(cmd) { + /* we could not read from the socket, so the connection died. bail out. */ + case -1: + case LPP_CMD_BAD: + goto end; + + case LPP_CMD_PROBLEM: + { + job_t job; + lpp_t *lpp; + + lpp = lpp_deserialize(comm); + lpp_deserialize_values(comm, lpp, lpp_value_start); + DBG((dbg, LEVEL_3, "problem %s received\n", lpp->name)); + job_init(&job, comm, lpp, solver); + + DBG((dbg, LEVEL_3, "starting job for problem %s\n", lpp->name)); + setproctitle("lpp_server [problem waiting: %s]", lpp->name); + + solve(comm, &job); + lpp_writel(comm, LPP_CMD_SOLUTION); + lpp_serialize_stats(comm, lpp); + lpp_serialize_values(comm, lpp, lpp_value_solution); + lpp_flush(comm); + DBG((dbg, LEVEL_1, "job %d: finished with problem %s\n", job.id, lpp->name)); + setproctitle("lpp_server [problem finished: %s]", lpp->name); + + free_lpp(lpp); + } + + break; + + case LPP_CMD_SOLVER: + lpp_readbuf(comm, buf, sizeof(buf)); + solver = find_solver(buf); + DBG((dbg, LEVEL_2, "setting solver to: %s\n", buf)); + //lpp_send_res(comm, solver != NULL, "could not find solver: %s", buf); + break; + + case LPP_CMD_SOLVERS: + { + int i, n = ARRAY_SIZE(solvers); + lpp_writel(comm, n); + for(i = 0; i < n; ++i) + lpp_writes(comm, solvers[i].name); + lpp_flush(comm); + } + break; + + case LPP_CMD_SET_DEBUG: + { + int mask = lpp_readl(comm); + firm_dbg_set_mask(dbg, mask); + } + break; + + case LPP_CMD_BYE: + goto end; + + default: + fprintf(stderr, "illegal command %d. exiting\n", cmd); + goto end; + } + } + +end: + /* signal the queue, bail out and we are free now. */ + lpp_comm_free(comm); + close(fd); + + exit(0); +} + +static void child_handler(int sig) +{ + pid_t pid; + int status; + + (void) sig; + + pid = waitpid(-1, &status, WNOHANG); + do { + if(WIFEXITED(status)) { + DBG((dbg, LEVEL_1, "child %d died normally with return value %d\n", pid, WEXITSTATUS(status))); + --n_children; + if(n_children != 0) + setproctitle("lpp_server [main (%d %s)]", n_children, (n_children>1)?"children":"child"); + else + setproctitle("lpp_server [main]"); + } else if(WIFSIGNALED(status)) { + DBG((dbg, LEVEL_1, "child %d died by signal %d\n", pid, WTERMSIG(status))); + --n_children; + if(n_children != 0) + setproctitle("lpp_server [main (%d %s)]", n_children, (n_children>1)?"children":"child"); + else + setproctitle("lpp_server [main]"); + } else + DBG((dbg, LEVEL_1, "child %d did something unexpected\n", pid)); + + pid = waitpid(-1, &status, WNOHANG); + } while(pid > 0); +} + +static void main_loop(void) +{ + int csock; + + DBG((dbg, LEVEL_1, "master pid %d\n", getpid())); + + msock = passive_tcp(LPP_PORT, 10); + + for(;;) { + struct sockaddr_in fsin; + socklen_t len = sizeof(fsin); + pid_t child; + + csock = accept(msock, (struct sockaddr *) &fsin, &len); + if(csock < 0) { + if(errno == EINTR) + continue; + else + fprintf(stderr, "could not accept: %s\n", strerror(errno)); + } + + child = fork(); + switch(child) { + case 0: /* we're in the new child, start the session handler */ + close(msock); + session(csock); + break; + case -1: /* error, die! */ + perror("fork"); + exit(1); + default: /* if we're in the parent just continue */ + ++n_children; + setproctitle("lpp_server [main (%d %s)]", n_children, (n_children>1)?"children":"child"); + close(csock); + break; + } + } +} + +static void toggle_dbg(int num) +{ + static int mask = 0; + (void) num; + mask = ~mask; + firm_dbg_set_mask(dbg, mask); +} + +#define SEMKEYPATH "/tmp/lppkey" +#define SEMKEYID 42 + +static void print_syntax(void) { + fprintf(stderr, "lpp_server [-g ] [-s ]\n"); +} + +int main(int argc, char *argv[]) +{ + key_t semkey; + int ret; + int c; + struct sigaction sigact1, sigact2; + + dbg = firm_dbg_register("lpp.server"); + firm_dbg_set_mask(dbg, 1); + + set_solver_stack_size(128 * 1024 * 1024); + + /* parse options. */ + while((c = getopt(argc, argv, "s:g:")) != -1) { + switch(c) { + case 's': + set_solver_stack_size(atoi(optarg)); + break; + case 'g': + firm_dbg_set_mask(dbg, atoi(optarg)); + break; + default: + print_syntax(); + exit(1); + } + } + + initproctitle(argc, argv); + setproctitle("lpp_server [main]"); + + memset(&sigact1, 0, sizeof(sigact1)); + sigact1.sa_handler = toggle_dbg; + sigaction(SIGUSR1, &sigact1, NULL); + + memset(&sigact2, 0, sizeof(sigact2)); + sigact2.sa_handler = child_handler; + sigact2.sa_flags = SA_NOCLDSTOP; + sigaction(SIGCHLD, &sigact2, NULL); + + /* set up semaphore */ + semkey = ftok(SEMKEYPATH,SEMKEYID); + if ( semkey == (key_t)-1 ) { + perror("ftok() for sem failed"); + return 1; + } + + sem = semget( semkey, 1, 0666 | IPC_CREAT);// | IPC_EXCL ); + if ( sem == -1 ) { + perror("semget() failed"); + return -1; + } + + ret = semctl(sem, 0, SETVAL, 1); + if ( ret < 0 ) { + perror("semctl() failed"); + return -1; + } + + main_loop(); + + ret = semctl( sem, 0, IPC_RMID ); + if (ret < 0) { + printf("semctl() remove id failed\n"); + return -1; + } + return 0; +} diff --git a/ir/lpp/lpp_server.h b/ir/lpp/lpp_server.h new file mode 100644 index 000000000..5eaa21242 --- /dev/null +++ b/ir/lpp/lpp_server.h @@ -0,0 +1,179 @@ +/** + * @file lpp_server.h + * @date 19.07.2005 + * @author Sebastian Hack + * + * Copyright (C) 2005 Universitaet Karlsruhe + * Released under the GPL + */ + +#ifndef _LPP_SERVER_H +#define _LPP_SERVER_H + +#include +#include +#include +#include +#include +#include + +enum { +#define LPP_CMD(x) x, +#include "lpp_cmd.def" +#undef LPP_CMD + LPP_CMD_LAST +}; + +#define BASIC_ERR_CHECK(expr,cond,fmt,last) \ + if((expr) cond) { \ + fprintf(stderr, "%s(%d): %s %s: ", __FILE__, __LINE__, #expr, #cond); \ + print_err fmt; \ + fprintf(stderr, "\n"); \ + last; \ + } + +#define BASIC_ERRNO_CHECK(expr,cond,last) \ + if((expr) cond) { \ + fprintf(stderr, "%s(%d): %s %s: %s\n", \ + __FILE__, __LINE__, #expr, #cond, strerror(errno)); \ + last; \ + } + +#define ERR_CHECK_RETURN(expr, cond, fmt, retval) \ + BASIC_ERR_CHECK(expr, cond, fmt, return retval) + +#define ERRNO_CHECK_RETURN(expr, cond, retval) \ + BASIC_ERRNO_CHECK(expr, cond, return retval) + +#define ERR_CHECK_RETURN_VOID(expr, cond, fmt) \ + BASIC_ERR_CHECK(expr, cond, fmt, return) + +#define ERRNO_CHECK_RETURN_VOID(expr, cond) \ + BASIC_ERRNO_CHECK(expr, cond, return) + +#define ERR_CHECK(expr, cond, fmt) \ + BASIC_ERR_CHECK(expr, cond, fmt, (void) 0) + +#define ERRNO_CHECK(expr, cond) \ + BASIC_ERRNO_CHECK(expr, cond, (void) 0) + +static void print_err(const char *fmt, ...) +{ + va_list args; + + va_start(args, fmt); + vfprintf(stderr, fmt, args); + va_end(args); +} + +static void writel(int fd, uint32_t x) +{ + x = htonl(x); + ERRNO_CHECK(write(fd, &x, sizeof(x)), == -1); +} + +static void writed(int fd, double dbl) +{ + ERRNO_CHECK(write(fd, &dbl, sizeof(dbl)), == -1); +} + +static void writes(int fd, const char *str) +{ + size_t n = strlen(str); + writel(fd, n); + ERRNO_CHECK(write(fd, str, n), == -1); +} + +static uint32_t readl(int fd) +{ + uint32_t res; + + ERRNO_CHECK(read(fd, &res, sizeof(res)), == -1); + return ntohl(res); +} + +static double readd(int fd) +{ + double res; + ERRNO_CHECK(read(fd, &res, sizeof(res)), == -1); + return res; +} + +static char *reads(int fd) +{ + size_t len = readl(fd); + char *res = malloc(sizeof(char) * (len + 1)); + + ERRNO_CHECK(read(fd, res, len), == -1); + res[len] = '\0'; + return res; +} + +static char *readbuf(int fd, size_t buflen, char *buf) +{ + char dummy[1024]; + size_t i; + size_t n = buflen - 1; + size_t len = readl(fd); + size_t max_read = n < len ? n : len; + size_t rest = len - max_read; + + if(buflen > 0 && buf != NULL) { + ERRNO_CHECK(read(fd, buf, max_read), == -1); + buf[max_read] = '\0'; + } + + /* eat up data that didnt fit into the string */ + for(i = 0, n = rest / sizeof(dummy); i < n; ++i) + read(fd, dummy, sizeof(dummy)); + + if(rest % sizeof(dummy) > 0) + read(fd, dummy, rest % sizeof(dummy)); + + return buf; +} + +static int ack(int fd, size_t buflen, char *buf) +{ + int res = 0; + int cmd = readl(fd); + + switch(cmd) { + case LPP_CMD_OK: + res = 1; + break; + case LPP_CMD_BAD: + readbuf(fd, buflen, buf); + default: + res = 0; + } + + return res; +} + +static void send_res(int fd, int ok, const char *fmt, ...) +{ + if(!ok) { + char buf[1024]; + va_list args; + + va_start(args, fmt); + vsnprintf(buf, sizeof(buf), fmt, args); + va_end(args); + + writel(fd, LPP_CMD_BAD); + writes(fd, buf); + } + + else + writel(fd, LPP_CMD_OK); +} + +static void send_ack(int fd) +{ + send_res(fd, 1, ""); +} + + + +#endif /* _LPP_SERVER_H */ diff --git a/ir/lpp/lpp_set_dbg.c b/ir/lpp/lpp_set_dbg.c new file mode 100644 index 000000000..3d601036e --- /dev/null +++ b/ir/lpp/lpp_set_dbg.c @@ -0,0 +1,28 @@ +/** + * @file lpp_set_dbg.c + * @date 04.08.2006 + * @author Sebastian Hack + * + * Copyright (C) 2006 Universitaet Karlsruhe + * Released under the GPL + */ + +#include +#include + +#include "lpp.h" +#include "lpp_net.h" + +int main(int argc, char *argv[]) +{ + if(argc < 3) { + fprintf(stderr, "syntax: lpp_set_dbg \n"); + } + + else { + const char *host = argv[1]; + int mask = atoi(argv[2]); + lpp_set_dbg(host, mask); + } + return 0; +} diff --git a/ir/lpp/lpp_show.c b/ir/lpp/lpp_show.c new file mode 100644 index 000000000..d4619191e --- /dev/null +++ b/ir/lpp/lpp_show.c @@ -0,0 +1,38 @@ +/** + * @file lpp_show.c + * @date 26.07.2005 + * @author Sebastian Hack + * + * Copyright (C) 2005 Universitaet Karlsruhe + * Released under the GPL + */ + +#include "lpp_net.h" +#include "xmalloc.h" + +int main(int argc, char *argv[]) +{ + const char *host; + char **solvers; + + if(argc < 2) + return 1; + + host = argv[1]; + + solvers = lpp_get_solvers(host); + if(solvers) { + int i; + for(i = 0; solvers[i]; ++i) { + printf("%s\n", solvers[i]); + xfree(solvers[i]); + } + + xfree(solvers); + } + + else + fprintf(stderr, "lpp server not found\n"); + + return 0; +} diff --git a/ir/lpp/lpp_t.h b/ir/lpp/lpp_t.h new file mode 100644 index 000000000..974f32354 --- /dev/null +++ b/ir/lpp/lpp_t.h @@ -0,0 +1,54 @@ + +/** + * @file lpp_t.h + * @date 30.07.2005 + * @author Sebastian Hack + * + * Copyright (C) 2005 Universitaet Karlsruhe + * Released under the GPL + */ + +#ifndef _LPP_T_H +#define _LPP_T_H + +#include "lpp.h" +#include "lpp_comm.h" + +/** + * Serialize a lpp to a file descriptor. + * @param comm The file descriptor. + * @param lpp The lpp. + * @param with_names Also send the names of constraints/variables. + */ +void lpp_serialize(lpp_comm_t *comm, const lpp_t *lpp, int with_names); + +/** + * Deserialize an lpp from a file descriptor. + * @param comm The file descriptor. + * @param with_names Also receive names of constraints/variables. + * @return The Problem. + */ +lpp_t *lpp_deserialize(lpp_comm_t *comm); + +/** + * Serialize values of the lpps for a given value kind. + * This function only serializes values of the given kind. + * @param fd The file descriptor to serialize to. + * @param lpp The problem. + * @param kind The value kind. + */ +void lpp_serialize_values(lpp_comm_t *comm, const lpp_t *lpp, lpp_value_kind_t kind); + +/** + * Desrialize values from a stream. + * @param fd The file descriptor to read from. + * @param lpp The problem to set the values. + * @param kind The value kind the values shall be assigned. + */ +void lpp_deserialize_values(lpp_comm_t *comm, lpp_t *lpp, lpp_value_kind_t kind); + +void lpp_serialize_stats(lpp_comm_t *comm, const lpp_t *lpp); +void lpp_deserialize_stats(lpp_comm_t *comm, lpp_t *lpp); + + +#endif /* _LPP_T_H */ diff --git a/ir/lpp/lpp_test.c b/ir/lpp/lpp_test.c new file mode 100644 index 000000000..63f54089c --- /dev/null +++ b/ir/lpp/lpp_test.c @@ -0,0 +1,37 @@ +/** + * @file lpp_test.c + * @date 20.07.2005 + * @author Sebastian Hack + * + * Small test program for lpp solving + * + * Copyright (C) 2005 Universitaet Karlsruhe + * Released under the GPL + */ + +#include "lpp.h" +#include "lpp_net.h" + +int main(int argc, char *argv[]) +{ + int i; + lpp_t *lpp = new_lpp("test", lpp_minimize); + + lpp_add_cst(lpp, "a", lpp_equal, 1.0); + + lpp_add_var(lpp, "x", lpp_binary, 1.0); + lpp_add_var(lpp, "y", lpp_binary, 1.0); + + lpp_set_factor(lpp, "a", "x", 1.0); + lpp_set_factor(lpp, "a", "y", 1.0); + lpp_set_log(lpp, stdout); + + lpp_solve_net(lpp, argc > 1 ? argv[1] : "localhost", argc > 2 ? argv[2] : "dummy"); + + for(i = 0; i < lpp->var_next; ++i) { + lpp_name_t *name = lpp->vars[i]; + printf("%10s %4d %10f\n", name->name, name->nr, name->value); + } + + return 0; +} diff --git a/ir/lpp/mps.c b/ir/lpp/mps.c new file mode 100644 index 000000000..3b9fb216e --- /dev/null +++ b/ir/lpp/mps.c @@ -0,0 +1,162 @@ +/** + * Author: Daniel Grund + * Date: 02.06.2005 + * Copyright: (c) Universitaet Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ + +#include "config.h" +#include +#include +#include "mps.h" + +/** + * These must comply to the enum cst_t in lpp.h + */ +static const char *mps_cst_encoding[4] = {"N", "E", "L", "G"}; + +/** + * Diffferent line styles which can be used in a mps file + */ +typedef enum _mps_line_t {l_raw, + l_ind_name, l_ind_objs, l_ind_rows, l_ind_cols, l_ind_rhs, l_ind_end, + l_data_row, l_data_col1, l_data_col2, l_data_mst, l_marker} mps_line_t; + +static void mps_write_line(FILE *out, style_t style, mps_line_t line_type, ...) { + va_list args; + const char *fmt = ""; + + assert(style == s_mps_fixed || style == s_mps_free); + va_start(args, line_type); + + if (style == s_mps_fixed) { + /* white spaces are important! */ + switch (line_type) { + case l_raw: fmt = "%s\n"; break; + case l_ind_name: fmt = "NAME %s\n"; break; + case l_ind_objs: fmt = "OBJSENSE\n"; break; + case l_ind_rows: fmt = "ROWS\n"; break; + case l_ind_cols: fmt = "COLUMNS\n"; break; + case l_ind_rhs: fmt = "RHS\n"; break; + case l_ind_end: fmt = "ENDATA\n"; break; + case l_data_row: fmt = " %-2s %-8s\n"; break; /* Field 1-2 */ + case l_data_col1: fmt = " %-8s %-8s %12g\n"; break; /* Field 2-4 */ + case l_data_col2: fmt = " %-8s %-8s %12g %-8s %12g\n"; break; /* Field 2-6 */ + case l_data_mst: fmt = " %-8s %12g\n"; break; /* Field 3-4 */ + case l_marker: fmt = " M%-7d 'MARKER' '%s'\n"; break; /* Field 2,3,5 */ + default: assert(0); + } + } else { + switch (line_type) { + case l_raw: fmt = "%s\n"; break; + case l_ind_name: fmt = "NAME %s\n"; break; + case l_ind_objs: fmt = "OBJSENSE\n"; break; + case l_ind_rows: fmt = "ROWS\n"; break; + case l_ind_cols: fmt = "COLUMNS\n"; break; + case l_ind_rhs: fmt = "RHS\n"; break; + case l_ind_end: fmt = "ENDATA\n"; break; + case l_data_row: fmt = " %s\t%s\n"; break; + case l_data_col1: fmt = " %s\t%s\t%g\n"; break; + case l_data_col2: fmt = " %s\t%s\t%g\t%s\t%g\n"; break; + case l_data_mst: fmt = " %s\t%g\n"; break; + case l_marker: fmt = " M%d\t'MARKER'\t'%s'\n"; break; + default: assert(0); + } + } + + vfprintf(out, fmt, args); + va_end(args); +} + +static int mps_insert_markers(FILE *out, style_t style, lpp_var_t curr, lpp_var_t last, int marker_nr) { + assert(style == s_mps_fixed || style == s_mps_free); + if (last != curr) { + /* print end-marker for last */ + if (last == lpp_binary) + mps_write_line(out, style, l_marker, marker_nr++, "INTEND"); + + /* print begin-marker for curr */ + if (curr == lpp_binary) + mps_write_line(out, style, l_marker, marker_nr++, "INTORG"); + } + return marker_nr; +} + +void mps_write_mps(lpp_t *lpp, style_t style, FILE *out) { + int i, count, marker_nr = 0; + const lpp_name_t *curr; + const matrix_elem_t *elem, *before = NULL; + lpp_var_t last_type; + assert(style == s_mps_fixed || style == s_mps_free); + + /* NAME */ + mps_write_line(out, style, l_ind_name, lpp->name); + + /* OBJSENSE */ + if (lpp->opt_type == lpp_maximize) { + mps_write_line(out, style, l_ind_objs); + mps_write_line(out, style, l_raw, " MAX"); + } + + /* ROWS */ + mps_write_line(out, style, l_ind_rows); + for(i=0; icst_next; ++i) { + curr = lpp->csts[i]; + mps_write_line(out, style, l_data_row, mps_cst_encoding[curr->type.cst_type], curr->name); + } + + /* COLUMNS */ + mps_write_line(out, style, l_ind_cols); + last_type = lpp_invalid; + for(i=1; ivar_next; ++i) { /* column 0 is rhs */ + curr = lpp->vars[i]; + + /* markers */ + marker_nr = mps_insert_markers(out, style, curr->type.var_type, last_type, marker_nr); + last_type = curr->type.var_type; + + /* participation in constraints */ + count = 0; + matrix_foreach_in_col(lpp->m, curr->nr, elem) { + if (count == 0) { + before = elem; + count = 1; + } else { + mps_write_line(out, style, l_data_col2, curr->name, lpp->csts[before->row]->name, (double)before->val, lpp->csts[elem->row]->name, (double)elem->val); + count = 0; + } + } + if (count == 1) + mps_write_line(out, style, l_data_col1, curr->name, lpp->csts[before->row]->name, (double)before->val); + } + mps_insert_markers(out, style, lpp_invalid, last_type, marker_nr); /* potential end-marker */ + + /* RHS */ + mps_write_line(out, style, l_ind_rhs); + count = 0; + matrix_foreach_in_col(lpp->m, 0, elem) { + if (count == 0) { + before = elem; + count = 1; + } else { + mps_write_line(out, style, l_data_col2, "rhs", lpp->csts[before->row]->name, (double)before->val, lpp->csts[elem->row]->name, (double)elem->val); + count = 0; + } + } + if (count == 1) + mps_write_line(out, style, l_data_col1, "rhs", lpp->csts[before->row]->name, (double)before->val); + + /* ENDATA */ + mps_write_line(out, style, l_ind_end); +} + +void mps_write_mst(lpp_t *lpp, style_t style, FILE *out) { + int i; + mps_write_line(out, style, l_ind_name, ""); + for (i=0; ivar_next; ++i) { + const lpp_name_t *var = lpp->vars[i]; + if (var->value_kind == lpp_value_start) + mps_write_line(out, style, l_data_mst, var->name, (double)var->value); + } + mps_write_line(out, style, l_ind_end); +} diff --git a/ir/lpp/mps.h b/ir/lpp/mps.h new file mode 100644 index 000000000..d28c4f1e9 --- /dev/null +++ b/ir/lpp/mps.h @@ -0,0 +1,35 @@ +/** + * Author: Daniel Grund + * Date: 02.06.2005 + * Copyright: (c) Universitaet Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ + +#ifndef _MPS_H_ +#define _MPS_H_ + +#include +#include "lpp.h" + +/** + * Two styles of mps files + * + * s_mps_fixed: mps where spaces are allowed in identifiers + * and all things have a fixed column... :-0 + * s_mps_free: mps where whitespace is a seperator :-) + */ +typedef enum _style_t {s_mps_fixed, s_mps_free} style_t; + +/** + * Writes the description of a lp problem object (lpp) + * to the stream out, using the specified style. + */ +void mps_write_mps(lpp_t *lpp, style_t style, FILE *out); + +/** + * Writes the start values of a lp problem object (lpp) + * to the stream out, using the specified style. + */ +void mps_write_mst(lpp_t *lpp, style_t style, FILE *out); + +#endif /*_MPS_H_*/ diff --git a/ir/lpp/sp_matrix.c b/ir/lpp/sp_matrix.c new file mode 100644 index 000000000..289d74572 --- /dev/null +++ b/ir/lpp/sp_matrix.c @@ -0,0 +1,733 @@ +/** + * Author: Daniel Grund, Christian Wuerdig + * Date: 07.04.2005 + * Copyright: (c) Universitaet Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * CVS-Id: $Id: sp_matrix.c 24123 2008-11-28 15:08:27Z mallon $ + * + * Sparse matrix storage with linked lists for rows and cols. + * Matrix is optimized for left-to-right and top-to-bottom access. + * Complexity is O(1) then. + * Random access or right-to-left and bottom-to-top is O(m*n). + */ + +#ifdef _WIN32 +#include +#endif +#ifdef HAVE_ALLOCA_H +#include +#endif + +#include +#include +#include +#include + +#include "sp_matrix.h" + +#include "irtools.h" +#include "bitset.h" +#include "xmalloc.h" + +typedef enum _iter_direction_t { + down, right, all +} iter_direction_t; + +/** + * Embedded list pointer. + */ +typedef struct _sp_matrix_list_head_t { + struct _sp_matrix_list_head_t *next; +} sp_matrix_list_head_t; + +/** + * A matrix entry. + */ +typedef struct _entry_t { + sp_matrix_list_head_t col_chain; /**< points to next element in same column */ + sp_matrix_list_head_t row_chain; /**< points to next element in same row */ + matrix_elem_t e; /**< The actual element */ +} entry_t; + +struct _sp_matrix_t { + /* These specify the dimensions of the matrix. + * They equal the largest values ever used in matrix_set */ + int maxrow, maxcol; + /* These are the dimensions of allocated arrays below. + * rowc >= maxrow and colc >= maxcol hold. */ + int rowc, colc; + /* number of entries */ + int entries; + /* arrays of sp_matrix_list_head* as entry-points to rows and cols */ + sp_matrix_list_head_t **rows, **cols; + /* for iteration: first is to remember start-point; + * last was returned just before + * next is used in case last was removed from list */ + iter_direction_t dir; + sp_matrix_list_head_t *first, *last, *next; + int iter_row; /* used for iteration over all elements */ + /* for each column the last inserted element in col list */ + sp_matrix_list_head_t **last_col_el; + /* for each row the last inserted element in row list */ + sp_matrix_list_head_t **last_row_el; +}; + +#define SP_MATRIX_INIT_LIST_HEAD(ptr) do { (ptr)->next = NULL; } while (0) + +#define _offsetof(type,member) ((char *) &(((type *) 0)->member) - (char *) 0) +#define _container_of(ptr,type,member) ((type *) ((char *) (ptr) - _offsetof(type, member))) + +#define is_empty_row(row) (row > m->maxrow || (m->rows[row])->next == NULL) +#define is_empty_col(col) (col > m->maxcol || (m->cols[col])->next == NULL) + +#define list_entry_by_col(h) (&_container_of(h, entry_t, col_chain)->e) +#define list_entry_by_row(h) (&_container_of(h, entry_t, row_chain)->e) + +/** + * Returns the size of a single matrix element. + */ +unsigned matrix_get_elem_size(void) { + return sizeof(entry_t); +} + +/** + * Returns the new size for an array of size old_size, + * which must at least store an entry at position min. + */ +static inline int _m_new_size(int old_size, int min) { + unsigned bits = 0; + assert(min >= old_size); + while (min > 0) { + min >>= 1; + bits++; + } + assert(bits < sizeof(min) * 8 - 1); + return 1 << bits; +} + +/** + * Allocates space for @p count entries in the rows array and + * initializes all entries from @p start to the end. + */ +static inline void _m_alloc_row(sp_matrix_t *m, int start, int count) { + int p; + + m->rowc = count; + m->rows = XREALLOC(m->rows, sp_matrix_list_head_t *, m->rowc); + m->last_row_el = XREALLOC(m->last_row_el, sp_matrix_list_head_t *, m->rowc); + + for (p = start; p < m->rowc; ++p) { + m->rows[p] = XMALLOC(sp_matrix_list_head_t); + SP_MATRIX_INIT_LIST_HEAD(m->rows[p]); + m->last_row_el[p] = m->rows[p]; + } +} + +/** + * Allocates space for @p count entries in the cols array and + * initializes all entries from @p start to the end. + */ +static inline void _m_alloc_col(sp_matrix_t *m, int start, int count) { + int p; + + m->colc = count; + m->cols = XREALLOC(m->cols, sp_matrix_list_head_t*, m->colc); + m->last_col_el = XREALLOC(m->last_col_el, sp_matrix_list_head_t*, m->colc); + + for (p = start; p < m->colc; ++p) { + m->cols[p] = XMALLOC(sp_matrix_list_head_t); + SP_MATRIX_INIT_LIST_HEAD(m->cols[p]); + m->last_col_el[p] = m->cols[p]; + } +} + +/** + * Searches in row @p row for the matrix element m[row, col], starting at element @p start. + * @return If the element exists: + * Element m[row, col] and @p prev points to the sp_matrix_list_head in the entry_t holding the element. + * Else: NULL and @p prev points to the sp_matrix_list_head after which the element would be inserted. + * @p prev_prev always points to the previous element of @p prev + */ +static inline matrix_elem_t *_m_search_in_row_from(const sp_matrix_t *m, + int row, int col, sp_matrix_list_head_t *start, sp_matrix_list_head_t **prev, sp_matrix_list_head_t **prev_prev) +{ + sp_matrix_list_head_t *row_start; + matrix_elem_t *res = NULL; + + row_start = m->rows[row]; + *prev = start; + + while ((*prev)->next != NULL && list_entry_by_row((*prev)->next)->col <= col) { + (*prev_prev) = (*prev); + *prev = (*prev)->next; + } + + if (*prev != row_start) { + matrix_elem_t *me = list_entry_by_row(*prev); + + if (me->row == row && me->col == col) + res = me; + } + + if (res) { + m->last_row_el[row] = *prev; + } + + return res; +} + +/** + * Searches in row @p row for the matrix element m[row, col]. + * @return If the element exists: + * Element m[row, col] and @p prev points to the sp_matrix_list_head in the entry_t holding the element. + * Else: NULL and @p prev points to the sp_matrix_list_head after which the element would be inserted. + * @p prev_prev always points to the previous element of @p prev + */ +static inline matrix_elem_t *_m_search_in_row(const sp_matrix_t *m, + int row, int col, sp_matrix_list_head_t **prev, sp_matrix_list_head_t **prev_prev) +{ + sp_matrix_list_head_t *start = m->rows[row]; + + *prev_prev = NULL; + + if (m->last_row_el[row] != start) { + matrix_elem_t *el = list_entry_by_row(m->last_row_el[row]); + if (el->col < col) { + *prev_prev = start = m->last_row_el[row]; + } + } + + return _m_search_in_row_from(m, row, col, start, prev, prev_prev); +} + +/** + * Searches in col @p col for the matrix element m[row, col], starting at @p start. + * @return If the element exists: + * Element m[row, col] and @p prev points to the sp_matrix_list_head in the entry_t holding the element. + * Else: NULL and @p prev points to the sp_matrix_list_head after which the element would be inserted. + * @p prev_prev always points to the previous element of @p prev + */ +static inline matrix_elem_t *_m_search_in_col_from(const sp_matrix_t *m, + int row, int col, sp_matrix_list_head_t *start, sp_matrix_list_head_t **prev, sp_matrix_list_head_t **prev_prev) +{ + sp_matrix_list_head_t *col_start; + matrix_elem_t *res = NULL; + + col_start = m->cols[col]; + *prev = start; + + while ((*prev)->next != NULL && list_entry_by_col((*prev)->next)->row <= row) { + *prev_prev = (*prev); + *prev = (*prev)->next; + } + + if (*prev != col_start) { + matrix_elem_t *me = list_entry_by_col(*prev); + + if (me->row == row && me->col == col) + res = me; + } + + if (res) { + m->last_col_el[col] = *prev; + } + + return res; +} + +/** + * Searches in col @p col for the matrix element m[row, col]. + * @return If the element exists: + * Element m[row, col] and @p prev points to the sp_matrix_list_head in the entry_t holding the element. + * Else: NULL and @p prev points to the sp_matrix_list_head after which the element would be inserted. + * @p prev_prev always points to the previous element of @p prev + */ +static inline matrix_elem_t *_m_search_in_col(const sp_matrix_t *m, + int row, int col, sp_matrix_list_head_t **prev, sp_matrix_list_head_t **prev_prev) +{ + sp_matrix_list_head_t *start = m->cols[col]; + + *prev_prev = NULL; + + if (m->last_col_el[col] != start) { + matrix_elem_t *el = list_entry_by_col(m->last_col_el[col]); + if (el->row < row) { + *prev_prev = start = m->last_col_el[col]; + } + } + + return _m_search_in_col_from(m, row, col, start, prev, prev_prev); +} + +sp_matrix_t *new_matrix(int row_init, int col_init) { + sp_matrix_t *res = XMALLOCZ(sp_matrix_t); + res->maxrow = -1; + res->maxcol = -1; + _m_alloc_row(res, 0, MAX(0, row_init)); + _m_alloc_col(res, 0, MAX(0, col_init)); + return res; +} + +void del_matrix(sp_matrix_t *m) { + int i; + + for (i = 0; i < m->rowc; ++i) { + if (! is_empty_row(i)) { + entry_t *e; + sp_matrix_list_head_t *n; + + n = m->rows[i]->next; + do { + /* get current matrix element */ + e = _container_of(n, entry_t, row_chain); + n = n->next; + xfree(e); + } while (n != NULL); + + } + xfree(m->rows[i]); + } + for (i = 0; i < m->colc; ++i) + xfree(m->cols[i]); + xfree(m->last_col_el); + xfree(m->last_row_el); + xfree(m->rows); + xfree(m->cols); + xfree(m); +} + +void matrix_set(sp_matrix_t *m, int row, int col, double val) { + matrix_elem_t *me = NULL; + entry_t *entr; + sp_matrix_list_head_t *leftof, *above; + sp_matrix_list_head_t *prev_leftof, *prev_above; + + /* if necessary enlarge the matrix */ + if (row > m->maxrow) { + m->maxrow = row; + if (row >= m->rowc) + _m_alloc_row(m, m->rowc, _m_new_size(m->rowc, row)); + } + if (col > m->maxcol) { + m->maxcol = col; + if (col >= m->colc) + _m_alloc_col(m, m->colc, _m_new_size(m->colc, col)); + } + + /* search for existing entry */ + if (m->maxrow < m->maxcol) + me = _m_search_in_col(m, row, col, &above, &prev_above); + else + me = _m_search_in_row(m, row, col, &leftof, &prev_leftof); + + /* if it exists, set the value and return */ + if (me) { + if (val != 0) { + me->val = (float)val; + } else { + entr = _container_of(me, entry_t, e); + + /* remove row_chain entry */ + if (prev_leftof) + prev_leftof->next = entr->row_chain.next; + else + m->rows[row]->next = entr->row_chain.next; + + /* remove col_chain entry */ + if (prev_above) + prev_above->next = entr->col_chain.next; + else + m->cols[col]->next = entr->col_chain.next; + + entr->row_chain.next = NULL; + entr->col_chain.next = NULL; + + /* set the last pointer to the "previous" element */ + if (m->last_col_el[col] == &entr->col_chain || + m->last_row_el[row] == &entr->row_chain) + { + m->last_col_el[col] = prev_above ? prev_above : m->cols[col]; + m->last_row_el[row] = prev_leftof ? prev_leftof : m->rows[row]; + } + + free(entr); + m->entries--; + } + return; + } + + /* if it does not exist and 0 should be set just quit */ + if (val == 0) + return; + + /* if it does not exist and val != 0 search the other direction */ + if (m->maxrow >= m->maxcol) + _m_search_in_col(m, row, col, &above, &prev_above); + else + _m_search_in_row(m, row, col, &leftof, &prev_leftof); + /* now leftof and above are the entry_t's prior the new one in each direction */ + + /* insert new entry */ + entr = XMALLOC(entry_t); + entr->e.row = row; + entr->e.col = col; + entr->e.val = (float)val; + + /* add row_chain entry */ + entr->row_chain.next = leftof->next; + leftof->next = &entr->row_chain; + + /* add col_chain entry */ + entr->col_chain.next = above->next; + above->next = &entr->col_chain; + + m->last_col_el[col] = &entr->col_chain; + m->last_row_el[row] = &entr->row_chain; + + m->entries++; +} + +void matrix_set_row_bulk(sp_matrix_t *m, int row, int *cols, int num_cols, double val) { + matrix_elem_t *me = NULL; + entry_t *entr; + int i; + sp_matrix_list_head_t *leftof, *above; + sp_matrix_list_head_t *prev_leftof, *prev_above; + + /* if necessary enlarge the matrix */ + if (row > m->maxrow) { + m->maxrow = row; + if (row >= m->rowc) + _m_alloc_row(m, m->rowc, _m_new_size(m->rowc, row)); + } + if (cols[num_cols - 1] > m->maxcol) { + m->maxcol = cols[num_cols - 1]; + if (cols[num_cols - 1] >= m->colc) + _m_alloc_col(m, m->colc, _m_new_size(m->colc, cols[num_cols - 1])); + } + + /* set start values */ + prev_above = NULL; + prev_leftof = NULL; + + for (i = 0; i < num_cols; ++i) { + /* search for existing entry */ + me = _m_search_in_row(m, row, cols[i], &leftof, &prev_leftof); + + /* if it exists, set the value and return */ + if (me) { + if (val != 0) { + me->val = (float)val; + } else { + entr = _container_of(me, entry_t, e); + + /* remove row_chain entry */ + if (prev_leftof) + prev_leftof->next = entr->row_chain.next; + else + m->rows[row]->next = entr->row_chain.next; + + /* remove col_chain entry */ + if (prev_above) + prev_above->next = entr->col_chain.next; + else + m->cols[cols[i]]->next = entr->col_chain.next; + + entr->row_chain.next = NULL; + entr->col_chain.next = NULL; + + /* set the last pointer to the "previous" element */ + if (m->last_col_el[cols[i]] == &entr->col_chain || + m->last_row_el[row] == &entr->row_chain) + { + m->last_col_el[cols[i]] = prev_above ? prev_above : m->cols[cols[i]]; + m->last_row_el[row] = prev_leftof ? prev_leftof : m->rows[row]; + } + + free(entr); + m->entries--; + } + + continue; + } + + /* if it does not exist and 0 should be set just quit */ + if (val == 0) + continue; + + /* we have to search the col list as well, to get the above pointer */ + _m_search_in_col(m, row, cols[i], &above, &prev_above); + + /* now leftof and above are the entry_t's prior the new one in each direction */ + + /* insert new entry */ + entr = XMALLOC(entry_t); + entr->e.row = row; + entr->e.col = cols[i]; + entr->e.val = (float)val; + + m->last_col_el[cols[i]] = &entr->col_chain; + m->last_row_el[row] = &entr->row_chain; + + /* add row_chain entry */ + entr->row_chain.next = leftof->next; + leftof->next = &entr->row_chain; + + /* add col_chain entry */ + entr->col_chain.next = above->next; + above->next = &entr->col_chain; + + m->entries++; + } +} + +double matrix_get(const sp_matrix_t *m, int row, int col) { + sp_matrix_list_head_t *dummy, *dummy2; + matrix_elem_t *me; + + if (is_empty_row(row) || is_empty_col(col)) + return 0.0; + + if (m->maxrow < m->maxcol) + me = _m_search_in_col(m, row, col, &dummy, &dummy2); + else + me = _m_search_in_row(m, row, col, &dummy, &dummy2); + + if (me) + assert(me->col == col && me->row == row); + + return me ? me->val : 0.0; +} + +int matrix_get_entries(const sp_matrix_t *m) { + return m->entries; +} + +int matrix_get_rowcount(const sp_matrix_t *m) { + return m->maxrow + 1; +} + +int matrix_get_colcount(const sp_matrix_t *m) { + return m->maxcol + 1; +} + +const matrix_elem_t *matrix_row_first(sp_matrix_t *m, int row) { + if (is_empty_row(row)) + return NULL; + + m->dir = right; + m->first = m->rows[row]; + m->last = m->first->next; + m->next = m->last ? m->last->next : NULL; + + assert (list_entry_by_row(m->last)->row == row); + + return list_entry_by_row(m->last); +} + +const matrix_elem_t *matrix_col_first(sp_matrix_t *m, int col) { + if (is_empty_col(col)) + return NULL; + + m->dir = down; + m->first = m->cols[col]; + m->last = m->first->next; + m->next = m->last ? m->last->next : NULL; + + assert (list_entry_by_col(m->last)->col == col); + + return list_entry_by_col(m->last); +} + +static inline const matrix_elem_t *matrix_first_from(sp_matrix_t *m, int startrow) { + const matrix_elem_t *res; + int i; + + for (i = startrow; i <= m->maxrow; ++i) { + res = matrix_row_first(m, i); + if (res) { + m->iter_row = i; + m->dir = all; + return res; + } + } + + return NULL; +} + +const matrix_elem_t *matrix_first(sp_matrix_t *m) { + return matrix_first_from(m, 0); +} + +const matrix_elem_t *matrix_next(sp_matrix_t *m) { + assert(m->first && "Start iteration with matrix_???_first, before calling me!"); + + if (m->next == NULL) { + if (m->dir == all) + return matrix_first_from(m, ++m->iter_row); + else + return NULL; + } + + m->last = m->next; + m->next = m->next->next; + + if (m->dir == down) + return list_entry_by_col(m->last); + else /* right or all */ + return list_entry_by_row(m->last); +} + +static int cmp_count(const void *e1, const void *e2) { + return (int *)e2 - (int *)e1; +} + +static inline void matrix_fill_row(sp_matrix_t *m, int row, bitset_t *fullrow) { + const matrix_elem_t *e; + bitset_set(fullrow, row); + matrix_foreach_in_col(m, row, e) { + if (! bitset_is_set(fullrow, e->row)) { + assert(0.0 == matrix_get(m, e->col, e->row)); + matrix_set(m, e->col, e->row, e->val); + matrix_set(m, e->row, e->col, 0.0); + } + } +} + +void matrix_optimize(sp_matrix_t *m) { + int i, size, redo; + int *c; + const matrix_elem_t *e; + bitset_t *fullrow; + + size = MAX(m->maxcol, m->maxrow)+1; + + /* kill all double-entries (Mij and Mji are set) */ + matrix_foreach(m, e) { + double t_val; + + assert(e->row != e->col && "Root has itself as arg. Ok. But the arg (=root) will always have the same color as root"); + t_val = matrix_get(m, e->col, e->row); + if (fabs(t_val) > 1e-10) { + matrix_set(m, e->col, e->row, 0); + matrix_set(m, e->row, e->col, e->val + t_val); + } + } + + c = alloca(size * sizeof(*c)); + redo = 1; + fullrow = bitset_alloca(size); + + /* kill 'all' rows containing only 1 entry */ + while (redo) { + redo = 0; + /* count elements in rows */ + memset(c, 0, size * sizeof(*c)); + + matrix_foreach(m, e) + c[e->row]++; + + for (i = 0; icol] > 0) + matrix_fill_row(m, e->col, fullrow); + else + matrix_fill_row(m, e->row, fullrow); + } + } + } + + + memset(c, 0, size * sizeof(*c)); + matrix_foreach(m, e) + c[e->row]++; + + qsort(c, size, sizeof(*c), cmp_count); + + for (i = 0; i < size; ++i) { + if (! bitset_is_set(fullrow, i)) + matrix_fill_row(m, i, fullrow); + } +} + +void matrix_dump(sp_matrix_t *m, FILE *out, int factor) { + int i, o, last_idx; + const matrix_elem_t *e; + + for (i = 0; i <= m->maxrow; ++i) { + last_idx = -1; + matrix_foreach_in_row(m, i, e) { + for (o = last_idx + 1; o < e->col; ++o) + fprintf(out, " %4.1f" , 0.0); + + fprintf(out, " %4.1f", factor * e->val); + last_idx = e->col; + } + + for (o = last_idx + 1; o <= m->maxcol; ++o) + fprintf(out, " %4.1f" , 0.0); + + fprintf(out, "\n"); + } +} + +void matrix_self_test(int d) { + int i, o; + const matrix_elem_t *e; + sp_matrix_t *m = new_matrix(10, 10); + + for (i = 0; i < d; ++i) + for (o = 0; o < d; ++o) + matrix_set(m, i, o, i*o); + + for (i = 0; i < d; ++i) + for (o = 0; oval == i); + i++; + } + assert(!matrix_next(m)); /*iter must finish */ + + i = d-1; + matrix_foreach_in_col(m,d-1,e) { + assert(e->val == i); + i += d-1; + } + assert(!matrix_next(m)); + del_matrix(m); + m = new_matrix(16,16); + matrix_set(m, 1,1,9); + matrix_set(m, 1,2,8); + matrix_set(m, 1,3,7); + + matrix_set(m, 1,3,6); + matrix_set(m, 1,2,5); + matrix_set(m, 1,1,4); + i = 1; + matrix_foreach_in_row(m, 1, e) { + assert(e->row == 1 && e->col == i && e->val == i+3); + i++; + } + assert(i == 4); + del_matrix(m); + + m = new_matrix(5,5); + matrix_set(m, 1,1,1); + matrix_set(m, 2,2,2); + matrix_set(m, 3,3,3); + matrix_set(m, 3,5,4); + matrix_set(m, 4,4,5); + matrix_set(m, 5,5,6); + for (i=1, e = matrix_first(m); e; ++i, e=matrix_next(m)) + assert(e->val == i); + assert(i == 7); + matrix_set(m, 1,1,0); + assert(5 == matrix_get_entries(m)); + del_matrix(m); +} diff --git a/ir/lpp/sp_matrix.h b/ir/lpp/sp_matrix.h new file mode 100644 index 000000000..c94a255cd --- /dev/null +++ b/ir/lpp/sp_matrix.h @@ -0,0 +1,145 @@ +/** + * Author: Daniel Grund + * Date: 07.04.2005 + * Copyright: (c) Universitaet Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * CVS-Id: $Id: sp_matrix.h 16112 2007-10-07 15:50:49Z mallon $ + * + * Sparse matrix storage with linked lists for rows and cols. + */ + +#ifndef _SP_MATRIX_H +#define _SP_MATRIX_H + +#include + +/** + * A matrix element. + */ +typedef struct _matrix_elem_t { + int row; /* row index */ + int col; /* column index */ + float val; /* the actual value of the entry */ +} matrix_elem_t; + +typedef struct _sp_matrix_t sp_matrix_t; + +/** + * Allocate a new matrix and init internal data for a matrix of size + * row_init X col_init. Matrix cannot grow beyond these init values. + * All elements are initially (implicit) set to 0. + */ +sp_matrix_t *new_matrix(int rows, int cols); + +/** + * Free space used by matrix m + */ +void del_matrix(sp_matrix_t *m); + +/** + * Sets m[row, col] to val + */ +void matrix_set(sp_matrix_t *m, int row, int col, double val); + +/** + * Sets m[row, cols[0,...,i]] to val for i in (0, ..., num_cols - 1) + * Following assumptions are done here: + * - the current row inserted is the last inserted row so far + * - cols[] is sorted ascending by col number + */ +void matrix_set_row_bulk(sp_matrix_t *m, int row, int *cols, int num_cols, double val); + +/** + * Returns the value stored in m[row, col]. + */ +double matrix_get(const sp_matrix_t *m, int row, int col); + +/** + * Returns the number of (not-0-)entries. + */ +int matrix_get_entries(const sp_matrix_t *m); + +/** + * Returns the number of rows in this matrix; the height; the first dimension + */ +int matrix_get_rowcount(const sp_matrix_t *m); + +/** + * Returns the number of cols in this matrix; the width; the second dimension + */ +int matrix_get_colcount(const sp_matrix_t *m); + +/** + * Start iteration over all matrix elements. Row by row, from top to bottom. + * @return NULL if the matrix is empty, else the first element. + */ +const matrix_elem_t *matrix_first(sp_matrix_t *m); + +/** + * Start iteration over a row. Elements are returned from left to right. + * @return NULL if row is empty, else the first element. + */ +const matrix_elem_t *matrix_row_first(sp_matrix_t *m, int row); + +/** + * Start iteration over a column. Elements are returned from top to bottom. + * @return NULL if column is empty, else the first element. + */ +const matrix_elem_t *matrix_col_first(sp_matrix_t *m, int col); + +/** + * @return the next element in iteration order or NULL if iteration is done. + */ +const matrix_elem_t *matrix_next(sp_matrix_t *m); + +/** + * @return the size for a single matrix element + */ +unsigned matrix_get_elem_size(void); + +/** + * m The matrix + * curr The variable to assign all elements to during iteration + * Save against removal of curr + */ +#define matrix_foreach(m,curr) \ + for (curr = matrix_first(m); curr; curr = matrix_next(m)) + +/** + * m The matrix + * r The row + * curr The variable to assign all elements to during iteration + * Save against removal of curr + */ +#define matrix_foreach_in_row(m,r,curr) \ + for (curr = matrix_row_first(m, r); curr; curr = matrix_next(m)) + +/** + * m The matrix + * c The col + * curr The variable to assign all elements to during iteration + * Save against removal of curr + */ +#define matrix_foreach_in_col(m,c,curr) \ + for (curr = matrix_col_first(m, c); curr; curr = matrix_next(m)) + +/** + * Changes the matrix into an equivalent one with maximal number zero-rows. + * The only equivalence transformation is: + * Adding a constant to Qij and subtracting it from Qji + */ +void matrix_optimize(sp_matrix_t *m); + +/** + * Dumps the matrix factor*m to the stream @p out. + * Remark: I dont need spaces between the elements. So feel free to add + * char *seperator to the arguments. + */ +void matrix_dump(sp_matrix_t *m, FILE *out, int factor); + +/** + * Perform a self test with a square matrix of dimensions d. + */ +void matrix_self_test(int d); + +#endif -- 2.20.1