From 77f1eeaeb90f2d231b0ccc2fcbe071a9b457e6c3 Mon Sep 17 00:00:00 2001 From: Daniel Grund Date: Tue, 7 Jun 2005 09:07:17 +0000 Subject: [PATCH] Made lpp stuff modular. --- ir/be/lpp.c | 213 +++++++++++++++++++++++++++++++++++++++++++++ ir/be/lpp.h | 78 +++++++++++++---- ir/be/lpp_local.c | 192 ++++++++++++++++++++++++++++++++++++++++ ir/be/lpp_local.h | 15 ++++ ir/be/lpp_remote.c | 174 ++++++++++++++++++++++++++++++++++++ ir/be/lpp_remote.h | 15 ++++ ir/be/mps.c | 164 ++++++++++++++++++++++++++++++++++ ir/be/mps.h | 35 ++++++++ 8 files changed, 871 insertions(+), 15 deletions(-) create mode 100644 ir/be/lpp.c create mode 100644 ir/be/lpp_local.c create mode 100644 ir/be/lpp_local.h create mode 100644 ir/be/lpp_remote.c create mode 100644 ir/be/lpp_remote.h create mode 100644 ir/be/mps.c create mode 100644 ir/be/mps.h diff --git a/ir/be/lpp.c b/ir/be/lpp.c new file mode 100644 index 000000000..da1857c8e --- /dev/null +++ b/ir/be/lpp.c @@ -0,0 +1,213 @@ +/** + * Author: Daniel Grund + * Date: Fri 13.05.2005 + * Copyright: (c) Universitaet Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#ifdef HAVE_IO_H +#include +#endif + +#include +#include +#include + +#include "xmalloc.h" +#include "debug.h" +#include "assert.h" +#include "hashptr.h" +#include "mps.h" +#include "lpp.h" + +#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)) + +static int cmp_name_t(const void *x, const void *y, size_t size) { + const name_t *n = x; + const name_t *m = y; + return strcmp(n->name, m->name); +} + +#define INITIAL_SIZE 64 + +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->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_add_cst(lpp, "obj", objective, 0); + lpp_add_var(lpp, "rhs", rhs, 0); + return lpp; +} + +void free_lpp(lpp_t *lpp) { + int i; + for(i=0;icst_next;++i) + free(lpp->csts[i]->name); + for(i=0;ivar_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); + if (lpp->error) + free(lpp->error); + free(lpp); +} + +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)); + 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 = xmalloc(12); + snprintf(res, 12, "_%d", lpp->next_name_number++); + return res; +} + +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); + } + + return inner->nr; +} + +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); +} + +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(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 (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); + } + + return inner->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); +} + +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, char *cst_name, 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); + 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); + 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 = value_start; +} + +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; ivars[begin+i]->value; + return lpp->sol_state; +} + +void lpp_dump(lpp_t *lpp, const char *filename) { + FILE *out = fopen(filename, "wt"); + mps_write_mps(lpp, s_mps_fixed, out); + fclose(out); +} diff --git a/ir/be/lpp.h b/ir/be/lpp.h index 13b45fe83..465bee36e 100644 --- a/ir/be/lpp.h +++ b/ir/be/lpp.h @@ -3,15 +3,58 @@ * Date: 16.05.2005 * Copyright: (c) Universitaet Karlsruhe * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * + * Interface for specifying an milp. Does not define a solution method. */ +#ifndef _LPP_H +#define _LPP_H #include +#include "set.h" +#include "sp_matrix.h" typedef enum _opt_t {minimize, maximize} opt_t; typedef enum _cst_t {objective=0, equal=1, less=2, greater=3} cst_t; -typedef enum _var_t {invalid=0, rhs=1, real=2, binary=3} var_t; -typedef enum _sol_state_t {unknown=0, no_solution_file=1, infeasible=2, unbounded=3, feasible=4, optimal=5} sol_state_t; -typedef struct _lpp_t lpp_t; +typedef enum _var_t {invalid=0, rhs=1, continous=2, binary=3} var_t; +typedef enum _sol_state_t {unknown=0, infeasible=1, inforunb=2, unbounded=3, feasible=4, optimal=5} sol_state_t; +typedef enum _value_kind_t {none=0, value_start, value_solution} value_kind_t; + +typedef struct _name_t name_t; +struct _name_t { + char *name; /**< the name of the var/constraint supplied by user */ + int nr; /**< the col/row number in the matrix */ + value_kind_t value_kind; + double value; + union _type { + var_t var_type; + cst_t cst_type; + } type; +}; + +typedef 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, 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 */ + name_t **csts; /**< Pointers to the elements in the cst2nr set */ + name_t **vars; /**< Pointers to the elements in the var2nr set */ + + /* Solution stuff */ + sol_state_t sol_state; + double sol_time; /**< Time in seconds */ + unsigned iterations; + + char *error; + unsigned next_name_number; +} lpp_t; #define ERR_NAME_NOT_ALLOWED -2 @@ -32,7 +75,7 @@ void free_lpp(lpp_t *lpp); * @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, cst_t cst_type, double rhs); +int lpp_add_cst(lpp_t *lpp, char *cst_name, cst_t cst_type, double rhs); /** * Returns the internal index of a constraint. @@ -44,8 +87,10 @@ int lpp_get_cst_idx(lpp_t *lpp, 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 */ -const char *lpp_get_cst_name(lpp_t *lpp, int index); +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 @@ -57,7 +102,7 @@ const char *lpp_get_cst_name(lpp_t *lpp, int index); * * NOTE: common integer or semi-continous vars are not (yet) implemented */ -int lpp_add_var(lpp_t *lpp, const char *var_name, var_t var_type, double obj); +int lpp_add_var(lpp_t *lpp, char *var_name, var_t var_type, double obj); /** * Returns the internal index of a variable. @@ -69,13 +114,13 @@ int lpp_get_var_idx(lpp_t *lpp, 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 */ -const char *lpp_get_var_name(lpp_t *lpp, int index); +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. - * Use "obj" as constraint name to set factors in the objective function. - * Use "rhs" as variable name to set the right hand side values. * @return -1 if constraint or variable name does not exist. * 0 otherwise */ @@ -83,7 +128,6 @@ int lpp_set_factor(lpp_t *lpp, char *cst_name, char *var_name, double value); /** * Same as lpp_set_factor but uses the internal indices instead of names. - * "obj" and "rhs" both have index 0. * @return -1 if an index was invalid * 0 otherwise */ @@ -97,12 +141,16 @@ int lpp_set_factor_fast(lpp_t *lpp, int cst_idx, int var_idx, double value); void lpp_set_start_value(lpp_t *lpp, int var_idx, double value); /** - * Solve the problem. - * @return -1 if an error ocurred, 0 otherwise + * @return The solution values of the variables from index begin to index end. */ -int lpp_solve(lpp_t *lpp, int use_start_values); +sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end); /** - * @return The solution values of the variables from index begin to index end. + * Dumps the lpp into a file with name @p filename in MPS-format */ -sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end); +void lpp_dump(lpp_t *lpp, const char *filename); + +#define lpp_get_iter_cnt(lpp) lpp->iterations +#define lpp_get_sol_time(lpp) lpp->sol_time + +#endif diff --git a/ir/be/lpp_local.c b/ir/be/lpp_local.c new file mode 100644 index 000000000..93ae09187 --- /dev/null +++ b/ir/be/lpp_local.c @@ -0,0 +1,192 @@ +/** + * Author: Daniel Grund + * Date: 02.06.2005 + * Copyright: (c) Universitaet Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif +#include +#include + +#include "lpp_local.h" +#include "xmalloc.h" +#include "assert.h" +#include "sp_matrix.h" +#include "ilcplex/cplex.h" + + +#define LOGFILE stdout + +static char cpx_cst_encoding[4] = {'?', 'E', 'L', 'G'}; +static char cpx_var_encoding[4] = {'?', '?', 'C', 'B'}; + +typedef struct _cpx_t { + lpp_t *lpp; + CPXENVptr env; + CPXLPptr prob; + int status; + char buf[1024]; +} cpx_t; + +static INLINE void chk_cpx_err(cpx_t *cpx) { + if (cpx->status) { + if (CPXgeterrorstring(cpx->env, cpx->status, cpx->buf)) + printf(cpx->buf); + else + printf("Unknown CPLEX error\n"); + assert(0); + } +} + +static cpx_t *new_cpx(lpp_t *lpp) { + cpx_t *cpx = xcalloc(1, sizeof(*cpx)); + 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 == minimize)?1:-1); + chk_cpx_err(cpx); + if (CPXsetlogfile(cpx->env, LOGFILE)) + assert(0 && "Could not set logfile"); + return cpx; +} + +static void free_cpx(cpx_t *cpx) { + CPXfreeprob(cpx->env, &cpx->prob); + CPXcloseCPLEX(&cpx->env); + free(cpx); +} + +void cpx_construct(cpx_t *cpx) { + const matrix_elem_t *elem; + int i, o, sv_cnt, numcols, numrows, numentries, objsen, *matbeg, *matcnt, *matind, *indices; + double *obj, *rhs, *matval, *lb, *ub, *startv; + char *sense, *vartype, **colname; + 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 == minimize ? 1 : -1; + + obj = alloca(numcols * sizeof(*obj)); + lb = alloca(numcols * sizeof(*lb)); + ub = alloca(numcols * sizeof(*ub)); + colname = alloca(numcols * sizeof(*colname)); + vartype = alloca(numcols * sizeof(*vartype)); + indices = alloca(numcols * sizeof(*indices)); + startv = alloca(numcols * sizeof(*startv)); + matbeg = alloca(numcols * sizeof(*matbeg)); + matcnt = alloca(numcols * sizeof(*matcnt)); + matind = alloca(numentries * sizeof(*matind)); + matval = alloca(numentries * sizeof(*matval)); + rhs = alloca(numrows * sizeof(*rhs)); + sense = alloca(numrows * sizeof(*sense)); + + o = 0; + sv_cnt = 0; + for(i=0; ivars[1+i]; + obj[i] = matrix_get(lpp->m, 0, 1+i); + lb[i] = 0.0; + ub[i] = CPX_INFBOUND; + colname[i] = curr_var->name; + vartype[i] = cpx_var_encoding[curr_var->type.var_type]; + if(curr_var->value_kind == 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++; + } + } + + for(i=0; im, 1+i, 0); + sense[i] = cpx_cst_encoding[lpp->csts[1+i]->type.cst_type]; + } + + cpx->status = CPXcopylpwnames(cpx->env, cpx->prob, + numcols, numrows, objsen, + obj, rhs, sense, + matbeg, matcnt, matind, matval, + lb, ub, NULL, + colname, NULL); + 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); +} + +void cpx_solve(cpx_t *cpx) { + int i, CPX_state, numcols; + double *values; + struct timeval tvb, tva; + + 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_MIPEMPHASIS, CPX_MIPEMPHASIS_BESTBOUND); + CPXsetintparam(cpx->env, CPX_PARAM_VARSEL, CPX_VARSEL_STRONG); + + /* 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); + switch (CPX_state) { + case CPXMIP_INFEASIBLE: + case CPX_STAT_INFEASIBLE: lpp->sol_state = infeasible; break; + case CPXMIP_INForUNBD: + case CPX_STAT_INForUNBD: lpp->sol_state = inforunb; break; + case CPXMIP_UNBOUNDED: + case CPX_STAT_UNBOUNDED: lpp->sol_state = 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 = feasible; break; + case CPXMIP_OPTIMAL: + case CPX_STAT_OPTIMAL: lpp->sol_state = optimal; break; + default: lpp->sol_state = unknown; + } + assert(lpp->sol_state == optimal); + + /* 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 = value_solution; + } + + /* get some statistics */ + lpp->sol_time = tva.tv_sec - tvb.tv_sec; + lpp->iterations = CPXgetmipitcnt(cpx->env, cpx->prob); +} + +void lpp_solve_local(lpp_t *lpp) { + cpx_t *cpx = new_cpx(lpp); + cpx_construct(cpx); + cpx_solve(cpx); + free_cpx(cpx); +} diff --git a/ir/be/lpp_local.h b/ir/be/lpp_local.h new file mode 100644 index 000000000..0bdc5107d --- /dev/null +++ b/ir/be/lpp_local.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_LOCAL_H_ +#define _LPP_LOCAL_H_ + +#include "lpp.h" + +void lpp_solve_local(lpp_t *lpp); + +#endif /*_LPP_LOCAL_H_*/ diff --git a/ir/be/lpp_remote.c b/ir/be/lpp_remote.c new file mode 100644 index 000000000..63583b8c7 --- /dev/null +++ b/ir/be/lpp_remote.c @@ -0,0 +1,174 @@ +/** + * Author: Daniel Grund + * Date: 02.06.2005 + * Copyright: (c) Universitaet Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include +#include +#include +#include +#include + +#include "lpp_remote.h" +#include "xmalloc.h" +#include "assert.h" +#include "mps.h" + +/* 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 INLINE 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 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 = 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 = xstrdup(buf); + else if (!strncmp(buf, "Warning:", 8)) + lpp->error = xstrdup(buf); + else if (!strncmp(buf, "Integer optimal solution:", 25)) + lpp->sol_state = optimal; + else if (!strcmp(buf, "No integer feasible solution exists.")) + lpp->sol_state = infeasible; + else if (!strcmp(buf, "Error termination, integer feasible:")) + lpp->sol_state = 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) { + name_t *var = lpp->vars[i]; + var->value = 0; + var->value_kind = 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/be/lpp_remote.h b/ir/be/lpp_remote.h new file mode 100644 index 000000000..4bde4045c --- /dev/null +++ b/ir/be/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/be/mps.c b/ir/be/mps.c new file mode 100644 index 000000000..ddc2ee974 --- /dev/null +++ b/ir/be/mps.c @@ -0,0 +1,164 @@ +/** + * Author: Daniel Grund + * Date: 02.06.2005 + * Copyright: (c) Universitaet Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif +#include +#include +#include "mps.h" + +/** + * These must comply to the enum cst_t in lpp.h + */ +static 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; + 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 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; +} + +void mps_write_mps(lpp_t *lpp, style_t style, FILE *out) { + int i, count, marker_nr = 0; + const name_t *curr; + const matrix_elem_t *elem, *before = NULL; + 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 == 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 = 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, 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 name_t *var = lpp->vars[i]; + if (var->value_kind == 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/be/mps.h b/ir/be/mps.h new file mode 100644 index 000000000..ffeae3a45 --- /dev/null +++ b/ir/be/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_*/ -- 2.20.1