* Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
*/
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#ifdef HAVE_IO_H
+#include <io.h>
+#endif
+
#include <stdlib.h>
#include <stdio.h>
-#include <stdarg.h>
#include <string.h>
-#include "lpp.h"
+
#include "xmalloc.h"
+#include "debug.h"
#include "assert.h"
#include "hashptr.h"
-#include "set.h"
-#include "sp_matrix.h"
-
-typedef struct _name_t name_t;
-
-struct _name_t {
- const char *name; /**< the name of the var/constraint supplied by user */
- int nr; /**< the col/row number in the matrix */
- union _type {
- var_t var_type;
- cst_t cst_type;
- } type;
-};
-
-struct _lpp_t {
- /* The problem data */
- char *name; /**< A textual name for this problem */
- opt_t opt_type; /**< Optimization direction */
- sp_matrix_t *m; /**< The matrix holding objective and constraints */
- int rhs_size; /**< Size of the rhs-array below */
- int *rhs; /**< The right hand side vector */
-
- /* Cst/Var to Nr mapping */
- set *cst2nr; /**< Holds name_t's for constraints */
- set *var2nr; /**< Holds name_t's for variables */
+#include "mps.h"
+#include "lpp.h"
- /* 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 */
- name_t **csts; /**< Pointers to the elements in the cst2nr set */
- name_t **vars; /**< Pointers to the elements in the var2nr set */
-};
+#define DEBUG_LVL SET_LEVEL_1
+static firm_dbg_module_t *dbg = NULL;
#define HASH_NAME_T(n) HASH_STR((n)->name, strlen((n)->name))
#define INITIAL_SIZE 64
-lpp_t *new_lp(char *name, opt_t opt_type) {
- lpp_t *lpp = xcalloc(1, sizeof(*lpp));
- lpp->name = name;
+lpp_t *new_lpp(const char *name, opt_t opt_type) {
+ lpp_t *lpp;
+
+ dbg = firm_dbg_register("ir.be.lpp");
+ firm_dbg_set_mask(dbg, DEBUG_LVL);
+
+ lpp = xcalloc(1, sizeof(*lpp));
+ lpp->name = xstrdup(name);
lpp->opt_type = opt_type;
lpp->cst2nr = new_set(cmp_name_t, INITIAL_SIZE);
lpp->var2nr = new_set(cmp_name_t, INITIAL_SIZE);
lpp->cst_size = INITIAL_SIZE;
- lpp->csts = xcalloc(INITIAL_SIZE, sizeof(*lpp->csts));
lpp->var_size = INITIAL_SIZE;
+ lpp->csts = xcalloc(INITIAL_SIZE, sizeof(*lpp->csts));
lpp->vars = xcalloc(INITIAL_SIZE, sizeof(*lpp->vars));
lpp->m = new_matrix(INITIAL_SIZE, INITIAL_SIZE);
- lpp->rhs_size = INITIAL_SIZE;
- lpp->rhs = xcalloc(INITIAL_SIZE, sizeof(*lpp->rhs));
+ lpp_add_cst(lpp, "obj", objective, 0);
+ lpp_add_var(lpp, "rhs", rhs, 0);
return lpp;
}
-void free_lp(lpp_t *lpp) {
+void free_lpp(lpp_t *lpp) {
+ int i;
+ for(i=0;i<lpp->cst_next;++i)
+ free(lpp->csts[i]->name);
+ for(i=0;i<lpp->var_next;++i)
+ free(lpp->vars[i]->name);
del_set(lpp->cst2nr);
del_set(lpp->var2nr);
del_matrix(lpp->m);
+ free(lpp->name);
free(lpp->csts);
free(lpp->vars);
- free(lpp->rhs);
+ if (lpp->error)
+ free(lpp->error);
free(lpp);
}
-void lpp_add_constr(lpp_t *lpp, const char *cst_name, cst_t cst_type) {
- name_t n, *inner;
- n.name = xstrdup(cst_name);
- n.nr = lpp->cst_next++;
- n.type.cst_type = cst_type;
- inner = set_insert(lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n));
- assert(inner);
- if (lpp->cst_next == lpp->cst_size)
- lpp->csts = xrealloc(lpp->csts, 2 * lpp->cst_size * sizeof(*lpp->csts));
- lpp->csts[lpp->cst_next++] = inner;
-}
-
-void lpp_add_var(lpp_t *lpp, const char *var_name, var_t var_type) {
- name_t n, *inner;
- assert(var_type != invalid && "invalid is for internal use only");
- n.name = xstrdup(var_name);
- n.nr = lpp->var_next++;
- n.type.var_type = var_type;
- inner = set_insert(lpp->var2nr, &n, sizeof(n), HASH_NAME_T(&n));
- assert(inner);
- if (lpp->var_next == lpp->var_size)
- lpp->vars = xrealloc(lpp->vars, 2 * lpp->var_size * sizeof(*lpp->vars));
- lpp->vars[lpp->var_next++] = inner;
-}
-
-static INLINE int name2nr(set *where, const char *name) {
+static INLINE int name2nr(set *where, char *name) {
name_t find, *found;
find.name = name;
found = set_find(where, &find, sizeof(find), HASH_NAME_T(&find));
- if (found)
- return found->nr;
- else
- return -1;
+ return (found ? found->nr : -1);
}
-#define cst_nr(lp, name) name2nr(lpp->cst2nr, name)
-#define var_nr(lp, name) name2nr(lpp->var2nr, name)
+#define cst_nr(lpp, name) name2nr(lpp->cst2nr, name)
+#define var_nr(lpp, name) name2nr(lpp->var2nr, name)
-void lpp_set_factor(lpp_t *lpp, const char *cst_name, const char *var_name, int value) {
- int cst, var;
- cst = cst_nr(lp, cst_name);
- var = var_nr(lp, var_name);
- assert(cst != -1);
- assert(var != -1);
- matrix_set(lpp->m, cst, var, value);
+static INLINE char *get_next_name(lpp_t *lpp) {
+ char *res = xmalloc(12);
+ snprintf(res, 12, "_%d", lpp->next_name_number++);
+ return res;
}
-static INLINE void adjust_rhs_size(lpp_t *lpp) {
- if (lpp->cst_size > lpp->rhs_size) {
- lpp->rhs_size = lpp->cst_size;
- lpp->rhs = xrealloc(lpp->rhs, lpp->rhs_size);
+int lpp_add_cst(lpp_t *lpp, char *cst_name, cst_t cst_type, double rhs) {
+ 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 = xstrdup(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->nr = lpp->cst_next;
+ inner->type.cst_type = cst_type;
+ if (lpp->cst_next == lpp->cst_size) {
+ lpp->cst_size *= 2;
+ lpp->csts = xrealloc(lpp->csts, lpp->cst_size * sizeof(*lpp->csts));
+ }
+ lpp->csts[lpp->cst_next] = inner;
+ lpp->cst_next++;
+ matrix_set(lpp->m, inner->nr, 0, rhs);
}
-}
-void lpp_set_rhs(lpp_t *lpp, char *cst_name, int value) {
- int cst = cst_nr(lp, cst_name);
- assert(cst != -1);
- adjust_rhs_size(lpp);
- lpp->rhs[cst] = value;
+ return inner->nr;
}
-void lpp_set_all_constr(lpp_t *lpp, char *cst_name, char **var_names, int *values) {
- assert(0 && "NYI");
+int lpp_get_cst_idx(lpp_t *lpp, char *cst_name) {
+ DBG((dbg, LEVEL_2, "%s --> %d\n", cst_name, cst_nr(lpp, cst_name)));
+ return cst_nr(lpp, cst_name);
}
-/******************************************************************************
- MPS-STUFF
-******************************************************************************/
-
-static char *mps_cst_encoding[4] = {"N", "E", "L", "G"};
-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_marker} mps_line_t;
-
-static INLINE void mps_write_line(FILE *out, style_t style, mps_line_t line_type, ...) {
- va_list args;
- char *fmt = "";
+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);
+}
- assert(style == s_mps_fixed || style == s_mps_free);
- va_start(args, line_type);
+int lpp_add_var(lpp_t *lpp, char *var_name, var_t var_type, double obj) {
+ name_t n, *inner;
+ DBG((dbg, LEVEL_2, "%s %d %g\n", var_name, var_type, obj));
+ assert(var_type != invalid && "invalid is for internal use only");
+ if (var_name && var_name[0] == '_')
+ return ERR_NAME_NOT_ALLOWED;
+ if (var_name)
+ n.name = xstrdup(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 (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 %12d\n"; break; /* Field 2-4 */
- case l_data_col2: fmt = " %-8s %-8s %12d %-8s %12d\n"; break; /* Field 2-6 */
- 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%d\n"; break;
- case l_data_col2: fmt = " %s\t%s\t%d\t%s\t%d\n"; break;
- case l_marker: fmt = " M%d\t'MARKER'\t'%s'\n"; break;
- default: assert(0);
+ 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 *= 2;
+ lpp->vars = xrealloc(lpp->vars, lpp->var_size * sizeof(*lpp->vars));
}
+ lpp->vars[lpp->var_next] = inner;
+ lpp->var_next++;
+ matrix_set(lpp->m, 0, inner->nr, obj);
}
- vfprintf(out, fmt, args);
- va_end(args);
+ return inner->nr;
}
-static INLINE int mps_insert_markers(FILE *out, style_t style, var_t curr, 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 == binary)
- mps_write_line(out, style, l_marker, marker_nr++, "INTEND");
-
- /* print begin-marker for curr */
- if (curr == binary)
- mps_write_line(out, style, l_marker, marker_nr++, "INTORG");
- }
- return marker_nr;
+int lpp_get_var_idx(lpp_t *lpp, char *var_name) {
+ DBG((dbg, LEVEL_2, "%s --> %d\n", var_name, var_nr(lpp, var_name)));
+ return var_nr(lpp, var_name);
}
-static void lpp_dump_mps(lpp_t *lpp, FILE *out, style_t style) {
- int i, count, marker_nr = 0;
- const name_t *curr;
- 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 */
- mps_write_line(out, style, l_ind_objs);
- if (lpp->opt_type == maximize)
- mps_write_line(out, style, l_raw, " MAX");
-
- /* ROWS */
- mps_write_line(out, style, l_ind_rows);
- for(i=0; i<lpp->cst_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 = invalid;
- for(i=0; i<lpp->var_next; ++i) {
- const matrix_elem_t *elem, *before = NULL;
- curr = lpp->vars[i];
-
- /* markers */
- marker_nr = mps_insert_markers(out, style, last_type, curr->type.var_type, marker_nr);
- last_type = curr->type.var_type;
+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);
+}
- /* 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, before->val, lpp->csts[elem->row]->name, elem->val);
- count = 0;
- }
- }
- if (count == 1)
- mps_write_line(out, style, l_data_col1, curr->name, lpp->csts[before->row]->name, before->val);
- }
- mps_insert_markers(out, style, last_type, invalid, marker_nr); /* potential end-marker */
+int lpp_set_factor(lpp_t *lpp, char *cst_name, char *var_name, double value) {
+ int cst, var;
- /* RHS */
- mps_write_line(out, style, l_ind_rhs);
- for(i=0; i<lpp->rhs_size/2; ++i)
- mps_write_line(out, style, l_data_col2, "rhs", lpp->csts[2*i]->name, lpp->rhs[2*i], lpp->csts[2*i+1]->name, lpp->rhs[2*i+1]);
- if ((lpp->rhs_size & 1) == 1)
- mps_write_line(out, style, l_data_col1, "rhs", lpp->csts[lpp->rhs_size-1]->name, lpp->rhs[lpp->rhs_size-1]);
+ 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);
+ return 0;
+}
- /* ENDATA */
- mps_write_line(out, style, l_ind_end);
+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);
+ return 0;
}
-/******************************************************************************
- LP-STUFF
-******************************************************************************/
+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 = value_start;
+}
-static void lpp_dump_lp(lpp_t *lpp, FILE *out) {
- assert(0 && "NYI");
+sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end) {
+ int i;
+ if (lpp->sol_state < 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_dump(lpp_t *lpp, FILE *out, style_t style) {
- adjust_rhs_size(lpp);
- switch (style) {
- case s_mps_fixed:
- case s_mps_free: lpp_dump_mps(lpp, out, style); break;
- case s_lp: lpp_dump_lp(lpp, out); break;
- default: assert(0);
- }
+void lpp_dump(lpp_t *lpp, const char *filename) {
+ FILE *out = fopen(filename, "wt");
+ mps_write_mps(lpp, s_mps_fixed, out);
+ fclose(out);
}
projects / libfirm / blobdiff