-/**
- * 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 $
+/*
+ * Copyright (C) 2005-2011 University of Karlsruhe. All right reserved.
+ *
+ * This file is part of libFirm.
+ *
+ * This file may be distributed and/or modified under the terms of the
+ * GNU General Public License version 2 as published by the Free Software
+ * Foundation and appearing in the file LICENSE.GPL included in the
+ * packaging of this file.
+ *
+ * Licensees holding valid libFirm Professional Edition licenses may use
+ * this file in accordance with the libFirm Commercial License.
+ * Agreement provided with the Software.
+ *
+ * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+ * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE.
*/
+/**
+ * @file
+ * @author Daniel Grund
+ */
#include "config.h"
-#ifdef HAVE_IO_H
-#include <io.h>
-#endif
-
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "hashptr.h"
#include "debug.h"
#include "set.h"
+#include "debug.h"
#include "sp_matrix.h"
#include "mps.h"
#include "lpp_t.h"
#include "lpp_comm.h"
#include "lpp_solvers.h"
+#include "lpp_net.h"
-#define HASH_NAME_T(n) HASH_STR((n)->name, strlen((n)->name))
+#define HASH_NAME_T(n) hash_str((n)->name)
-static firm_dbg_module_t *dbg = NULL;
+DEBUG_ONLY(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 inline char *obst_xstrdup(struct obstack *obst, const char *str)
+{
+ return (char*)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 */
+static int cmp_name_t(const void *x, const void *y, size_t size)
+{
+ const lpp_name_t *n = (const lpp_name_t*)x;
+ const lpp_name_t *m = (const lpp_name_t*)y;
+ (void)size;
return strcmp(n->name, m->name);
}
/**
* Update statistic information about matrix usage.
*/
-static void update_stats(lpp_t *lpp) {
+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 *lpp_new(const char *name, lpp_opt_t opt_type)
+{
+ return lpp_new_userdef(name, opt_type, 64, 64, 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_new_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");
+ DEBUG_ONLY(dbg = firm_dbg_register("lpp");)
lpp = XMALLOCZ(lpp_t);
obstack_init(&lpp->obst);
return lpp;
}
-void free_lpp_matrix(lpp_t *lpp) {
+void lpp_free_matrix(lpp_t *lpp)
+{
del_matrix(lpp->m);
lpp->m = NULL;
}
-void free_lpp(lpp_t *lpp) {
+void lpp_free(lpp_t *lpp)
+{
obstack_free(&lpp->obst, NULL);
del_set(lpp->cst2nr);
free(lpp);
}
-double lpp_get_fix_costs(lpp_t *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) {
+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) {
+static 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));
+ found = set_find(lpp_name_t, 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 int cst_nr(const lpp_t *lpp, const char *name)
+{
+ return name2nr(lpp->cst2nr, name);
+}
+
+static int var_nr(const lpp_t *lpp, const char *name)
+{
+ return 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++);
+static inline char *get_next_name(lpp_t *lpp)
+{
+ char *res = OALLOCN(&lpp->obst, char, 12);
+ snprintf(res, 12, "_%u", lpp->next_name_number++);
return res;
}
-int lpp_add_cst(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs) {
+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));
n.name = get_next_name(lpp);
n.nr = -1;
- inner = set_insert(lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n));
+ inner = set_insert(lpp_name_t, lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n));
assert(inner);
if (inner->nr == -1) {
return inner->nr;
}
-int lpp_add_cst_uniq(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs) {
+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)) &&
+ assert(!set_find(lpp_name_t, 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) {
+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) {
+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 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);
return val;
}
-int lpp_add_var(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj) {
+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));
n.name = get_next_name(lpp);
n.nr = -1;
- inner = set_insert(lpp->var2nr, &n, sizeof(n), HASH_NAME_T(&n));
+ inner = set_insert(lpp_name_t, 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_kind = lpp_none;
inner->value = 0;
inner->type.var_type = var_type;
return inner->nr;
}
-int lpp_get_var_idx(lpp_t *lpp, const char *var_name) {
+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) {
+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 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);
return 0;
}
-int lpp_set_factor_fast(lpp_t *lpp, int cst_idx, int var_idx, double value) {
+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));
return 0;
}
-int lpp_set_factor_fast_bulk(lpp_t *lpp, int cst_idx, int *var_idx, int num_vars, double value) {
+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));
return 0;
}
-void lpp_set_start_value(lpp_t *lpp, int var_idx, double value) {
+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) {
+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;
}
-void lpp_check_startvals(lpp_t *lpp) {
+void lpp_check_startvals(lpp_t *lpp)
+{
int cst_idx;
for (cst_idx = 1; cst_idx < lpp->cst_next; ++cst_idx) {
fprintf(stderr, "constraint %s unsatisfied: %g != %g\n", cst->name, sum, cst_val);
}
break;
- case lpp_less:
+ case lpp_less_equal:
if(sum > cst_val) {
- fprintf(stderr, "constraint %s unsatisfied: %g > %g\n", cst->name, sum, cst_val);
+ fprintf(stderr, "constraint %s unsatisfied: %g >= %g\n", cst->name, sum, cst_val);
}
break;
- case lpp_greater:
+ case lpp_greater_equal:
if(sum < cst_val) {
- fprintf(stderr, "constraint %s unsatisfied: %g < %g\n", cst->name, sum, cst_val);
+ fprintf(stderr, "constraint %s unsatisfied: %g <= %g\n", cst->name, sum, cst_val);
}
break;
default:
}
}
-void lpp_dump(lpp_t *lpp, const char *filename) {
+void lpp_dump(lpp_t *lpp, const char *filename)
+{
FILE *out = fopen(filename, "wt");
mps_write_mps(lpp, s_mps_fixed, out);
fclose(out);
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 ">=";
+ switch(cst) {
+ case lpp_equal:
+ return "=";
+ case lpp_less_equal:
+ return "<=";
+ case lpp_greater_equal:
+ return ">=";
default:
- return "";
- }
+ return "";
+ }
}
void lpp_dump_plain(lpp_t *lpp, FILE *f)
{
- int i;
+ int i;
+
+ fprintf(f, lpp->opt_type == lpp_minimize ? "Minimize\n" : "Maximize\n");
+ for(i = 0; i < lpp->cst_next; ++i) {
+ 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);
+ }
- for(i = 0; i < lpp->cst_next; ++i) {
- const matrix_elem_t *elm;
- lpp_name_t *cst = lpp->csts[i];
+ if (i == 0) {
+ fprintf(f, "\nSubject To\n");
+ continue;
+ }
- 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));
+ }
- fprintf(f, "%3s %+4.1f\n",
- lpp_cst_op_to_str(cst->type.cst_type), matrix_get(lpp->m, cst->nr, 0));
- }
+ fprintf(f, "Binary\n");
+ for(i = 0; i < lpp->var_next; ++i) {
+ lpp_name_t *var = lpp->vars[i];
+ if (var->type.var_type == lpp_binary)
+ fprintf(f, "%16s\n", var->name);
+ }
+ fprintf(f, "End\n");
}
/**
lpp_writel(comm, lpp->set_bound);
lpp_writed(comm, lpp->bound);
lpp_writed(comm, lpp->time_limit_secs);
- lpp_writed(comm, lpp->emphasis);
+ lpp_writel(comm, lpp->emphasis);
for(i = 0; i < lpp->cst_next; ++i) {
lpp_name_t *name = lpp->csts[i];
lpp_writes(comm, name->name);
}
- {
- const matrix_elem_t *elm;
- n = 0;
+ n = 0;
+ matrix_foreach(lpp->m, elm)
+ n++;
- 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);
- }
+ 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.
with_names = lpp_readl(comm);
lpp->cst_next = lpp_readl(comm);
lpp->var_next = lpp_readl(comm);
- lpp->opt_type = lpp_readl(comm);
+ lpp->opt_type = (lpp_opt_t)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->emphasis = (lpp_emphasis_t)lpp_readl(comm);
lpp->cst_size = lpp->cst_next;
lpp->var_size = lpp->var_next;
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.value_kind = (lpp_value_kind_t)lpp_readl(comm);
+ name.type.cst_type = (lpp_cst_t)lpp_readl(comm);
+
+ if(with_names) {
+ name.name = lpp_reads(comm);
+ } else {
+ char* buf = XMALLOCN(char, 32);
+ snprintf(buf, 32, "c%d\n", name.nr);
name.name = buf;
}
- res = set_insert(lpp->cst2nr, &name, sizeof(name), HASH_NAME_T(&name));
+ res = set_insert(lpp_name_t, lpp->cst2nr, &name, sizeof(name), HASH_NAME_T(&name));
lpp->csts[name.nr] = res;
}
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.value_kind = (lpp_value_kind_t)lpp_readl(comm);
+ name.type.var_type = (lpp_var_t)lpp_readl(comm);
+
+ if(with_names) {
+ name.name = lpp_reads(comm);
+ } else {
+ char* buf = XMALLOCN(char, 32);
+ snprintf(buf, 32, "v%d\n", name.nr);
name.name = buf;
}
- res = set_insert(lpp->var2nr, &name, sizeof(name), HASH_NAME_T(&name));
+ res = set_insert(lpp_name_t, lpp->var2nr, &name, sizeof(name), HASH_NAME_T(&name));
lpp->vars[name.nr] = res;
}
void lpp_serialize_values(lpp_comm_t *comm, const lpp_t *lpp, lpp_value_kind_t value_kind)
{
- int i, n;
+ int i, n;
- for(i = 0, n = 0; i < lpp->var_next; ++i)
- n += lpp->vars[i]->value_kind == value_kind;
+ 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);
+ /* 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);
- }
- }
+ /* 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;
+ int i, n;
- /* Get the number of values to read */
- n = lpp_readl(comm);
+ /* 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];
+ 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);
- }
+ name->value_kind = value_kind;
+ name->value = lpp_readd(comm);
+ }
}
void lpp_serialize_stats(lpp_comm_t *comm, const lpp_t *lpp)
void lpp_deserialize_stats(lpp_comm_t *comm, lpp_t *lpp)
{
- lpp->sol_state = lpp_readl(comm);
+ lpp->sol_state = (lpp_sol_state_t)lpp_readl(comm);
lpp->iterations = lpp_readl(comm);
lpp->sol_time = lpp_readd(comm);
lpp->objval = lpp_readd(comm);
lpp_solver_func_t* f = lpp_find_solver(solver);
if (f != NULL)
f(lpp);
- }
-
- else {
+ } else {
lpp_solve_net(lpp, host, solver);
}
}
projects / libfirm / blobdiff