From 09e0c5fe3add6833586e4fa463265581391c1cc3 Mon Sep 17 00:00:00 2001 From: Daniel Grund Date: Tue, 24 May 2005 13:18:29 +0000 Subject: [PATCH] Introduced ilp solver interface. becopyilp.c uses it now. --- ir/be/.cvsignore | 3 + ir/be/Makefile.in | 4 +- ir/be/becopyilp.c | 829 +++++++++++----------------------------------- ir/be/becopyopt.h | 2 +- ir/be/lpp.c | 292 ---------------- ir/be/lpp.h | 94 ++++-- ir/be/lpp_rzcpx.c | 559 +++++++++++++++++++++++++++++++ 7 files changed, 832 insertions(+), 951 deletions(-) create mode 100644 ir/be/.cvsignore delete mode 100644 ir/be/lpp.c create mode 100644 ir/be/lpp_rzcpx.c diff --git a/ir/be/.cvsignore b/ir/be/.cvsignore new file mode 100644 index 000000000..6402453a2 --- /dev/null +++ b/ir/be/.cvsignore @@ -0,0 +1,3 @@ +Makefile +.depend +.cvsignore diff --git a/ir/be/Makefile.in b/ir/be/Makefile.in index 41d2bef0f..217c0076d 100644 --- a/ir/be/Makefile.in +++ b/ir/be/Makefile.in @@ -6,7 +6,7 @@ # Modified by: # Created: # CVS-ID: $Id$ -# Copyright: (c) 1999-2003 Universität Karlsruhe +# Copyright: (c) 1999-2003 Universit�t Karlsruhe # Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. # @@ -25,7 +25,7 @@ SOURCES += Makefile.in besched.h belistsched.h belistsched.c \ bera.h bechordalspill.c beasm_dump_globals.c beasm_asm_gnu.c \ sp_matrix.c becopyoptmain.c becopyopt.c becopyheur.c \ becopyilp.c becopystat.c bearch_firm.c bearch.c bechordal_draw.c \ - bechordal_draw.h + bechordal_draw.h lpp_rzcpx.c include $(topdir)/MakeRules diff --git a/ir/be/becopyilp.c b/ir/be/becopyilp.c index 79f564bb3..d022a35cc 100644 --- a/ir/be/becopyilp.c +++ b/ir/be/becopyilp.c @@ -1,26 +1,8 @@ /** * Author: Daniel Grund - * Date: 12.04.2005 + * Date: 17.05.2005 * Copyright: (c) Universitaet Karlsruhe * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. - - * Minimizing copies with an exact algorithm using mixed integer programming (MIP). - * Problem statement as a 'quadratic 0-1 program with linear constraints' with - * n binary variables. Constraints are knapsack (enforce color for each node) and - * cliques of ifg (interference constraints). - * Transformation into a 'mixed integer program' with n binary variables and - * additional 2n real variables. Constraints are the above the transformed - * objective function and 'complementary conditions' for two var classes. - * @author Daniel Grund - * - * NOTE: - * MPS means NOT the old-style, fixed-column format. Some white spaces are - * important. In general spaces are separators, MARKER-lines are used in COLUMN - * section to define binaries. BETTER use last 2 fields in COLUMNS section. - * See MPS docu for details - * - * Unfortunately no good solver is available locally (or even for linking) - * We use CPLEX 9.0 which runs on a machine residing at the Rechenzentrum. */ #ifdef HAVE_CONFIG_H #include "config.h" @@ -33,145 +15,112 @@ #include #endif -#include -#include - +#include "lpp.h" #include "xmalloc.h" #include "becopyopt.h" #include "becopystat.h" -#undef DUMP_MATRICES /**< dumps all matrices completely. only recommended for small problems */ -#undef DUMP_Q2ILP /**< see function pi_dump_q2ilp */ -#define DUMP_DILP /**< see function pi_dump_dilp */ -#define DUMP_MST /**< see function pi_dump_start_sol */ -#define DO_SOLVE /**< solve the MPS output with CPLEX */ -#undef DELETE_FILES /**< deletes all dumped files after use. Files on server are always deleted. */ - -/* CPLEX-account related stuff */ -#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 */ - #define DEBUG_LVL SET_LEVEL_1 static firm_dbg_module_t *dbg = NULL; -#define SLOTS_NUM2POS 256 #define SLOTS_LIVING 32 -/* get_weight represents the _gain_ if node n and m have the same color. */ -#define get_weight(n,m) 1 - /** - * A type storing names of the x variables in the form x[NUMBER]_[COLOR] - */ -typedef struct _x_name_t { - int n, c; -} x_name_t; - -/** - * For each node taking part in the opt-problem its position in the - * x-variable-vector is stored in a set. This set maps the node-nr (given by - * benumb) to the position in the vector. - */ -typedef struct _num2pos_t { - int num, pos; -} num2pos_t; + * Represents the _costs_ if node n and m have different colors. + * Must be >=0. + **/ +#define get_weight(n,m) 1 typedef struct _simpl_t { struct list_head chain; if_node_t *ifn; } simpl_t; -/** - * A type storing the unmodified '0-1 quadratic program' of the form - * min f = xQx - * udN: Ax = e - * Bx <= e - * x \in {0, 1} - * - * This problem is called the original problem - */ typedef struct _problem_instance_t { const copy_opt_t *co; /** the original copy_opt problem */ - int x_dim, A_dim, B_dim, E_dim, c_dim; /**< number of: x variables (equals Q_dim), rows in A, rows in B */ - sp_matrix_t *Q, *A, *B, *E, *c; /**< the (sparse) matrices of this problem */ - x_name_t *x; /**< stores the names of the x variables. all possible colors for a node are ordered and occupy consecutive entries. lives in obstack ob. */ - set *num2pos; /**< maps node numbers to positions in x. */ - /* problem size reduction removing simple nodes */ struct list_head simplicials; /**< holds all simpl_t's in right order to color*/ pset *removed; /**< holds all removed simplicial irns */ - - /* needed for linearization */ - int bigM, maxQij, minQij; - - /* overhead needed to build this */ - struct obstack ob; - int curr_color; - int curr_row; + /* lp problem */ + lpp_t *dilp; /**< problem formulation directly as milp */ + /* overhead stuff */ + lpp_t *curr_lp; /**< points to the problem currently used */ + int curr_color, cst_counter, last_x_var; + char buf[32]; } problem_instance_t; #define is_removed(irn) pset_find_ptr(pi->removed, irn) +/* + * Some stuff for variable name handling. + */ +#define mangle_cst(buf, prefix, nr) \ + snprintf((buf), sizeof(buf), "%c%d", (prefix), (nr)) -/* Nodes have consecutive numbers so this hash shoud be fine */ -#define HASH_NUM(num) num +#define mangle_var(buf, prefix, node_nr, color) \ + snprintf((buf), sizeof(buf), "%c%d_%d", (prefix), (node_nr), (color)) -static int set_cmp_num2pos(const void *x, const void *y, size_t size) { - return ((num2pos_t *)x)->num != ((num2pos_t *)y)->num; -} +#define mangle_var_irn(buf, prefix, irn, color) \ + mangle_var((buf), (prefix), get_irn_graph_nr(irn), (color)) + +#define split_var(var, nnr, col) \ + sscanf(var, "x%d_%d", (nnr), (col)) -/** - * Sets the first position of node with number num to pos. - * See x_name_t *x in _problem_instance_t. - */ -static INLINE void pi_set_first_pos(problem_instance_t *pi, int num, int pos) { - num2pos_t find; - find.num = num; - find.pos = pos; - set_insert(pi->num2pos, &find, sizeof(find), HASH_NUM(num)); -} /** - * Get position by number. (First possible color) - * returns -1 if not found. + * Checks if a node is simplicial in the graph + * heeding the already removed nodes. */ -static INLINE int pi_get_first_pos(problem_instance_t *pi, int num) { - num2pos_t find, *found; - find.num = num; - found = set_find(pi->num2pos, &find, sizeof(find), HASH_NUM(num)); - if (found) { - assert(pi->x[found->pos].n == num && (found->pos == 0 || pi->x[found->pos-1].n != num) && "pi->num2pos is broken!"); - return found->pos; - } else - return -1; +static INLINE int pi_is_simplicial(problem_instance_t *pi, const if_node_t *ifn) { + int i, o, size = 0; + if_node_t **all, *curr; + all = alloca(ifn_get_degree(ifn) * sizeof(*all)); + + /* get all non-removed neighbors */ + foreach_neighb(ifn, curr) + if (!is_removed(curr)) + all[size++] = curr; + + /* check if these form a clique */ + for (i=0; ico->chordal_env, all[i], all[o])) + return 0; + + /* all edges exist so this is a clique */ + return 1; } /** - * Get position by number and color. - * returns -1 if not found. + * Iterative finds and 'removes' from the graph all nodes which are + * simplicial AND not member of a equal-color-wish */ -static INLINE int pi_get_pos(problem_instance_t *pi, int num, int col) { - num2pos_t find, *found; - int pos; - - find.num = num; - found = set_find(pi->num2pos, &find, sizeof(find), HASH_NUM(num)); - if (!found) - return -1; - pos = found->pos; - while (pos < pi->x_dim && pi->x[pos].n == num && pi->x[pos].c < col) - pos++; - - if (pi->x[pos].n == num && pi->x[pos].c == col) - return pos; - else - return -1; +static void pi_find_simplicials(problem_instance_t *pi) { + set *if_nodes; + if_node_t *ifn; + int redo = 1; + + if_nodes = be_ra_get_ifg_nodes(pi->co->chordal_env); + while (redo) { + redo = 0; + for (ifn = set_first(if_nodes); ifn; ifn = set_next(if_nodes)) { + ir_node *irn = get_irn_for_graph_nr(pi->co->irg, ifn->nnr); + if (!is_removed(irn) && !is_optimizable(irn) && + !is_optimizable_arg(pi->co, irn) && pi_is_simplicial(pi, ifn)) { + simpl_t *s = xmalloc(sizeof(*s)); + s->ifn = ifn; + list_add(&s->chain, &pi->simplicials); + pset_insert_ptr(pi->removed, irn); + redo = 1; + DBG((dbg, LEVEL_2, " Removed %n\n", irn)); + } + } + } } /** - * Collects all irns in currently processed register class + * Add coloring-force conditions */ -static void pi_collect_x_names(ir_node *block, void *env) { +static void pi_add_constr_A(ir_node *block, void *env) { problem_instance_t *pi = env; struct list_head *head = get_block_border_head(pi->co->chordal_env, block); border_t *curr; @@ -179,25 +128,29 @@ static void pi_collect_x_names(ir_node *block, void *env) { list_for_each_entry_reverse(border_t, curr, head, list) if (curr->is_def && curr->is_real && !is_removed(curr->irn)) { - x_name_t xx; - pi->A_dim++; /* one knapsack constraint for each node */ + int cst_idx, nnr, col; - xx.n = get_irn_graph_nr(curr->irn); - pi_set_first_pos(pi, xx.n, pi->x_dim); + nnr = get_irn_graph_nr(curr->irn); + mangle_cst(pi->buf, 'A', nnr); + cst_idx = lpp_add_cst(pi->curr_lp, pi->buf, equal, 1); // iterate over all possible colors in order bitset_clear_all(pos_regs); arch_get_allocatable_regs(pi->co->env, curr->irn, arch_pos_make_out(0), pi->co->cls, pos_regs); - bitset_foreach(pos_regs, xx.c) { - DBG((dbg, LEVEL_2, "Adding %n %d\n", curr->irn, xx.c)); - obstack_grow(&pi->ob, &xx, sizeof(xx)); - pi->x_dim++; /* one x variable for each node and color */ + bitset_foreach(pos_regs, col) { + int var_idx; + mangle_var(pi->buf, 'x', nnr, col); + var_idx = lpp_add_var(pi->curr_lp, pi->buf, binary, 0); + pi->last_x_var = var_idx; + lpp_set_factor_fast(pi->curr_lp, cst_idx, var_idx, 1); } } } /** - * Checks if all nodes in living are live_out in block block. + * Checks if all nodes in @p living are live in in block @p block. + * @return 1 if all are live in + * 0 else */ static INLINE int all_live_in(ir_node *block, pset *living) { ir_node *n; @@ -214,8 +167,9 @@ static INLINE int all_live_in(ir_node *block, pset *living) { * for which the color pi->curr_color is possible. Finds only 'maximal-cliques', * viz cliques which are not conatained in another one. * This is used for the matrix B. + * TODO check color */ -static void pi_clique_finder(ir_node *block, void *env) { +static void pi_add_constr_B(ir_node *block, void *env) { problem_instance_t *pi = env; enum phase_t {growing, shrinking} phase = growing; struct list_head *head = get_block_border_head(pi->co->chordal_env, block); @@ -238,13 +192,18 @@ static void pi_clique_finder(ir_node *block, void *env) { * do NOT if clique is a single node * do NOT if all values are live_in (in this case they were contained in a live-out clique elsewhere) */ if (phase == growing && pset_count(living) >= 2 && !all_live_in(block, living)) { + int cst_idx; ir_node *n; + mangle_cst(pi->buf, 'B', pi->cst_counter); + cst_idx = lpp_add_cst(pi->curr_lp, pi->buf, less, 1); for (n = pset_first(living); n; n = pset_next(living)) { - int pos = pi_get_pos(pi, get_irn_graph_nr(n), pi->curr_color); - matrix_set(pi->B, pi->curr_row, pos, 1); - DBG((dbg, LEVEL_2, "B[%d, %d] := %d\n", pi->curr_row, pos, 1)); + int var_idx; + mangle_var_irn(pi->buf, 'x', n, pi->curr_color); + var_idx = lpp_get_var_idx(pi->curr_lp, pi->buf); + assert(var_idx>=1); + lpp_set_factor_fast(pi->curr_lp, cst_idx, var_idx, 1); } - pi->curr_row++; + pi->cst_counter++; } pset_remove_ptr(living, irn); phase = shrinking; @@ -254,44 +213,56 @@ static void pi_clique_finder(ir_node *block, void *env) { del_pset(living); } -static INLINE int pi_is_simplicial(problem_instance_t *pi, const if_node_t *ifn) { - int i, o, size = 0; - if_node_t **all, *curr; - all = alloca(ifn_get_degree(ifn) * sizeof(*all)); - - /* get all non-removed neighbors */ - foreach_neighb(ifn, curr) - if (!is_removed(curr)) - all[size++] = curr; - - /* check if these form a clique */ - for (i=0; ico->chordal_env, all[i], all[o])) - return 0; - - /* all edges exist so this is a clique */ - return 1; -} - -static void pi_find_simplicials(problem_instance_t *pi) { - set *if_nodes; - if_node_t *ifn; - int redo = 1; - - if_nodes = be_ra_get_ifg_nodes(pi->co->chordal_env); - while (redo) { - redo = 0; - for (ifn = set_first(if_nodes); ifn; ifn = set_next(if_nodes)) { - ir_node *irn = get_irn_for_graph_nr(pi->co->irg, ifn->nnr); - if (!is_removed(irn) && !is_optimizable(irn) && - !is_optimizable_arg(pi->co, irn) && pi_is_simplicial(pi, ifn)) { - simpl_t *s = xmalloc(sizeof(*s)); - s->ifn = ifn; - list_add(&s->chain, &pi->simplicials); - pset_insert_ptr(pi->removed, irn); - redo = 1; - DBG((dbg, LEVEL_1, " Removed %n\n", irn)); +static void pi_add_constr_E(problem_instance_t *pi) { + unit_t *curr; + bitset_t *root_regs, *arg_regs; + root_regs = bitset_alloca(pi->co->cls->n_regs); + arg_regs = bitset_alloca(pi->co->cls->n_regs); + + /* for all roots of optimization units */ + list_for_each_entry(unit_t, curr, &pi->co->units, units) { + const ir_node *root, *arg; + int rootnr, argnr, color; + int y_idx, i, cst_counter = 0; + char buf[32]; + + root = curr->nodes[0]; + rootnr = get_irn_graph_nr(root); + bitset_clear_all(root_regs); + arch_get_allocatable_regs(pi->co->env, root, arch_pos_make_out(0), pi->co->cls, root_regs); + + /* for all arguments of root */ + for (i = 1; i < curr->node_count; ++i) { + arg = curr->nodes[i]; + argnr = get_irn_graph_nr(arg); + bitset_clear_all(arg_regs); + arch_get_allocatable_regs(pi->co->env, arg, arch_pos_make_out(0), pi->co->cls, arg_regs); + + /* Introduce new variable and set factor in objective function */ + y_idx = lpp_add_var(pi->curr_lp, NULL, real, get_weight(root, arg)); + + /* For all colors root and arg have in common, add 2 constraints to E */ + bitset_and(arg_regs, root_regs); + bitset_foreach(arg_regs, color) { + int root_idx, arg_idx, cst_idx; + mangle_var(buf, 'x', rootnr, color); + root_idx = lpp_get_var_idx(pi->curr_lp, buf); + mangle_var(buf, 'x', argnr, color); + arg_idx = lpp_get_var_idx(pi->curr_lp, buf); + + /* add root-arg+y <= 1 */ + mangle_cst(buf, 'E', cst_counter++); + cst_idx = lpp_add_cst(pi->curr_lp, buf, less, 0); + lpp_set_factor_fast(pi->curr_lp, cst_idx, root_idx, 1); + lpp_set_factor_fast(pi->curr_lp, cst_idx, arg_idx, -1); + lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, -1); + + /* add arg-root+y <= 1 */ + mangle_cst(buf, 'E', cst_counter++); + cst_idx = lpp_add_cst(pi->curr_lp, buf, less, 0); + lpp_set_factor_fast(pi->curr_lp, cst_idx, root_idx, -1); + lpp_set_factor_fast(pi->curr_lp, cst_idx, arg_idx, 1); + lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, -1); } } } @@ -301,408 +272,74 @@ static void pi_find_simplicials(problem_instance_t *pi) { * Generate the initial problem matrices and vectors. */ static problem_instance_t *new_pi(const copy_opt_t *co) { + DBG((dbg, LEVEL_1, "Generating new instance...\n")); problem_instance_t *pi = xcalloc(1, sizeof(*pi)); pi->co = co; - pi->num2pos = new_set(set_cmp_num2pos, SLOTS_NUM2POS); - pi->bigM = 1; pi->removed = pset_new_ptr_default(); INIT_LIST_HEAD(&pi->simplicials); + pi->dilp = new_lpp(co->name, minimize); /* problem size reduction */ pi_find_simplicials(pi); - //TODO dump_ifg_wo_removed - - /* Vector x - * one entry per node and possible color */ - obstack_init(&pi->ob); - dom_tree_walk_irg(co->irg, pi_collect_x_names, NULL, pi); - pi->x = obstack_finish(&pi->ob); - - /* Matrix Q and E - * weights for the 'same-color-optimization' target */ - { - unit_t *curr; - pi->Q = new_matrix(pi->x_dim, pi->x_dim); - pi->E = new_matrix(pi->x_dim, pi->x_dim); - pi->c = new_matrix(1, pi->x_dim); - - list_for_each_entry(unit_t, curr, &co->units, units) { - const ir_node *root, *arg; - int rootnr, argnr; - unsigned save_rootpos, rootpos, argpos; - int i; - - root = curr->nodes[0]; - rootnr = get_irn_graph_nr(root); - save_rootpos = pi_get_first_pos(pi, rootnr); - for (i = 1; i < curr->node_count; ++i) { - int weight; - rootpos = save_rootpos; - arg = curr->nodes[i]; - argnr = get_irn_graph_nr(arg); - argpos = pi_get_first_pos(pi, argnr); - weight = -get_weight(root, arg); - - DBG((dbg, LEVEL_2, "Q[%n, %n] := %d\n", root, arg, weight)); - /* for all colors root and arg have in common, set the weight for - * this pair in the objective function matrix Q */ - while (rootpos < pi->x_dim && argpos < pi->x_dim && - pi->x[rootpos].n == rootnr && pi->x[argpos].n == argnr) { - if (pi->x[rootpos].c < pi->x[argpos].c) - ++rootpos; - else if (pi->x[rootpos].c > pi->x[argpos].c) - ++argpos; - else { - /* E */ - matrix_set(pi->E, pi->E_dim, rootpos, +1); - matrix_set(pi->E, pi->E_dim, argpos, -1); - matrix_set(pi->E, pi->E_dim, pi->x_dim + pi->c_dim, 1); - pi->E_dim++; - matrix_set(pi->E, pi->E_dim, rootpos, -1); - matrix_set(pi->E, pi->E_dim, argpos, +1); - matrix_set(pi->E, pi->E_dim, pi->x_dim + pi->c_dim, 1); - pi->E_dim++; - - /* Q */ - matrix_set(pi->Q, rootpos, argpos, weight + matrix_get(pi->Q, rootpos, argpos)); - rootpos++; - argpos++; - if (weight < pi->minQij) { - DBG((dbg, LEVEL_2, "minQij = %d\n", weight)); - pi->minQij = weight; - } - if (weight > pi->maxQij) { - DBG((dbg, LEVEL_2, "maxQij = %d\n", weight)); - pi->maxQij = weight; - } - } - } + //TODO dump_ifg_w/o_removed - /* E */ - matrix_set(pi->c, 1, pi->c_dim++, -weight); - } - } - } - - /* Matrix A - * knapsack constraint for each node */ - { - int row = 0, col = 0; - pi->A = new_matrix(pi->A_dim, pi->x_dim); - while (col < pi->x_dim) { - int curr_n = pi->x[col].n; - while (col < pi->x_dim && pi->x[col].n == curr_n) { - DBG((dbg, LEVEL_2, "A[%d, %d] := %d\n", row, col, 1)); - matrix_set(pi->A, row, col++, 1); - } - ++row; - } - assert(row == pi->A_dim); - } - - /* Matrix B - * interference constraints using exactly those cliques not contained in others. */ - { - int color, expected_clipques = pi->A_dim/4 * pi->co->cls->n_regs; - pi->B = new_matrix(expected_clipques, pi->x_dim); - for (color = 0; color < pi->co->cls->n_regs; ++color) { - pi->curr_color = color; - dom_tree_walk_irg(pi->co->irg, pi_clique_finder, NULL, pi); - } - pi->B_dim = matrix_get_rowcount(pi->B); - } + pi->curr_lp = pi->dilp; + /* Matrix A: knapsack constraint for each node */ + dom_tree_walk_irg(co->irg, pi_add_constr_A, NULL, pi); + /* Matrix B: interference constraints using cliques */ + for (pi->curr_color = 0; pi->curr_color < pi->co->cls->n_regs; ++pi->curr_color) + dom_tree_walk_irg(co->irg, pi_add_constr_B, NULL, pi); + /* Matrix E weights for the 'same-color-optimization' target */ + pi_add_constr_E(pi); return pi; } /** - * clean the problem instance + * Clean the problem instance */ static void free_pi(problem_instance_t *pi) { DBG((dbg, LEVEL_1, "Free instance...\n")); - del_matrix(pi->Q); - del_matrix(pi->A); - del_matrix(pi->B); - del_matrix(pi->E); - del_matrix(pi->c); - del_set(pi->num2pos); + /* pi->simplicials get freed during apply_solution */ + free_lpp(pi->dilp); del_pset(pi->removed); - obstack_free(&pi->ob, NULL); free(pi); } -#ifdef DUMP_MATRICES /** - * Dump the raw matrices of the problem to a file for debugging. + * Set starting values for the mip problem according + * to the current coloring of the graph. */ -static void pi_dump_matrices(problem_instance_t *pi) { +static void pi_set_start_sol(problem_instance_t *pi) { int i; - FILE *out = ffopen(pi->co->name, "matrix", "wt"); - - DBG((dbg, LEVEL_1, "Dumping raw...\n")); - fprintf(out, "\n\nx-names =\n"); - for (i=0; ix_dim; ++i) - fprintf(out, "%5d %2d\n", pi->x[i].n, pi->x[i].c); - - fprintf(out, "\n\n-Q =\n"); - matrix_dump(pi->Q, out, -1); - - fprintf(out, "\n\nA =\n"); - matrix_dump(pi->A, out, 1); - - fprintf(out, "\n\nB =\n"); - matrix_dump(pi->B, out, 1); - - fprintf(out, "\n\nE =\n"); - matrix_dump(pi->E, out, 1); - - fprintf(out, "\n\nc =\n"); - matrix_dump(pi->c, out, 1); - - fclose(out); -} -#endif - -#ifdef DUMP_Q2ILP -/** - * Dumps an mps file representing the problem using a linearization of the - * quadratic programming problem. - */ -static void pi_dump_q2ilp(problem_instance_t *pi) { - int i, max_abs_Qij; - const matrix_elem_t *e; - FILE *out; - bitset_t *good_row; - DBG((dbg, LEVEL_1, "Dumping q2ilp...\n")); - - max_abs_Qij = pi->maxQij; - if (-pi->minQij > max_abs_Qij) - max_abs_Qij = -pi->minQij; - pi->bigM = pi->A_dim * max_abs_Qij; - DBG((dbg, LEVEL_2, "BigM = %d\n", pi->bigM)); - - matrix_optimize(pi->Q); - good_row = bitset_alloca(pi->x_dim); - for (i=0; ix_dim; ++i) - if (matrix_row_first(pi->Q, i)) - bitset_set(good_row, i); - - out = ffopen(pi->co->name, "q2ilp", "wt"); - fprintf(out, "NAME %s\n", pi->co->name); - - fprintf(out, "ROWS\n"); - fprintf(out, " N obj\n"); - for (i=0; ix_dim; ++i) - if (bitset_is_set(good_row, i)) - fprintf(out, " E cQ%d\n", i); - for (i=0; iA_dim; ++i) - fprintf(out, " E cA%d\n", i); - for (i=0; iB_dim; ++i) - fprintf(out, " L cB%d\n", i); - for (i=0; ix_dim; ++i) - if (bitset_is_set(good_row, i)) - fprintf(out, " L cy%d\n", i); - - fprintf(out, "COLUMNS\n"); - /* the x vars come first */ - /* mark them as binaries */ - fprintf(out, " MARKI0\t'MARKER'\t'INTORG'\n"); - for (i=0; ix_dim; ++i) { - /* participation in objective */ - if (bitset_is_set(good_row, i)) - fprintf(out, " x%d_%d\tobj\t%d\n", pi->x[i].n, pi->x[i].c, -pi->bigM); - /* in Q */ - matrix_foreach_in_col(pi->Q, i, e) - fprintf(out, " x%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val); - /* in A */ - matrix_foreach_in_col(pi->A, i, e) - fprintf(out, " x%d_%d\tcA%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val); - /* in B */ - matrix_foreach_in_col(pi->B, i, e) - fprintf(out, " x%d_%d\tcB%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val); - /* in y */ - if (bitset_is_set(good_row, i)) - fprintf(out, " x%d_%d\tcy%d\t%d\n", pi->x[i].n, pi->x[i].c, i, 2*pi->bigM); + for (i=1; i<=pi->last_x_var; ++i) { + int nnr, col; + double val; + /* get varibale name */ + const char *var_name = lpp_get_var_name(pi->curr_lp, i); + /* split into components */ + if (split_var(var_name, &nnr, &col) == 2) { + assert(get_irn_col(pi->co, get_irn_for_graph_nr(pi->co->irg, nnr)) != -1); + val = (get_irn_col(pi->co, get_irn_for_graph_nr(pi->co->irg, nnr)) == col) ? 1 : 0; + lpp_set_start_value(pi->curr_lp, i, val); + } else + assert(0 && "x vars always look like this \"x123_45\""); } - - fprintf(out, " MARKI1\t'MARKER'\t'INTEND'\n"); /* end of marking */ - - /* next the s vars */ - for (i=0; ix_dim; ++i) - if (bitset_is_set(good_row, i)) { - /* participation in objective */ - fprintf(out, " s%d_%d\tobj\t%d\n", pi->x[i].n, pi->x[i].c, 1); - /* in Q */ - fprintf(out, " s%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, i, -1); - } - - /* next the y vars */ - for (i=0; ix_dim; ++i) - if (bitset_is_set(good_row, i)) { - /* in Q */ - fprintf(out, " y%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, i, -1); - /* in y */ - fprintf(out, " y%d_%d\tcy%d\t%d\n", pi->x[i].n, pi->x[i].c, i, 1); - } - - fprintf(out, "RHS\n"); - for (i=0; ix_dim; ++i) - if (bitset_is_set(good_row, i)) - fprintf(out, " rhs\tcQ%d\t%d\n", i, -pi->bigM); - for (i=0; iA_dim; ++i) - fprintf(out, " rhs\tcA%d\t%d\n", i, 1); - for (i=0; iB_dim; ++i) - fprintf(out, " rhs\tcB%d\t%d\n", i, 1); - for (i=0; ix_dim; ++i) - if (bitset_is_set(good_row, i)) - fprintf(out, " rhs\tcy%d\t%d\n", i, 2*pi->bigM); - - fprintf(out, "ENDATA\n"); - fclose(out); } -#endif -#ifdef DUMP_DILP /** - * Dumps an mps file representing the problem using directly a formalization as ILP. + * Invoke a solver */ -static void pi_dump_dilp(problem_instance_t *pi) { - int i; - const matrix_elem_t *e; - FILE *out; - DBG((dbg, LEVEL_1, "Dumping dilp...\n")); - - out = ffopen(pi->co->name, "dilp", "wt"); - fprintf(out, "NAME %s\n", pi->co->name); - fprintf(out, "OBJSENSE\n MAX\n"); - - fprintf(out, "ROWS\n"); - fprintf(out, " N obj\n"); - for (i=0; iA_dim; ++i) - fprintf(out, " E cA%d\n", i); - for (i=0; iB_dim; ++i) - fprintf(out, " L cB%d\n", i); - for (i=0; iE_dim; ++i) - fprintf(out, " L cE%d\n", i); - - fprintf(out, "COLUMNS\n"); - /* the x vars come first */ - /* mark them as binaries */ - fprintf(out, " MARKI0\t'MARKER'\t'INTORG'\n"); - for (i=0; ix_dim; ++i) { - /* in A */ - matrix_foreach_in_col(pi->A, i, e) - fprintf(out, " x%d_%d\tcA%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val); - /* in B */ - matrix_foreach_in_col(pi->B, i, e) - fprintf(out, " x%d_%d\tcB%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val); - /* in E */ - matrix_foreach_in_col(pi->E, i, e) - fprintf(out, " x%d_%d\tcE%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val); - } - fprintf(out, " MARKI1\t'MARKER'\t'INTEND'\n"); /* end of marking */ - - /* next the y vars */ - for (i=0; ic_dim; ++i) { - /* in Objective */ - fprintf(out, " y%d\tobj\t%d\n", i, matrix_get(pi->c, 1, i)); - /* in E */ - matrix_foreach_in_col(pi->E, pi->x_dim+i, e) - fprintf(out, " y%d\tcE%d\t%d\n", i, e->row, e->val); - } - - fprintf(out, "RHS\n"); - for (i=0; iA_dim; ++i) - fprintf(out, " rhs\tcA%d\t%d\n", i, 1); - for (i=0; iB_dim; ++i) - fprintf(out, " rhs\tcB%d\t%d\n", i, 1); - for (i=0; iE_dim; ++i) - fprintf(out, " rhs\tcE%d\t%d\n", i, 1); - - fprintf(out, "ENDATA\n"); - fclose(out); -} -#endif - -#ifdef DUMP_MST -/** - * Dumps the known solution to a file to make use of it - * as a starting solution respectively as a bound - */ -static void pi_dump_start_sol(problem_instance_t *pi) { - int i; - FILE *out = ffopen(pi->co->name, "mst", "wt"); - fprintf(out, "NAME\n"); - for (i=0; ix_dim; ++i) { - int val, n, c; - n = pi->x[i].n; - c = pi->x[i].c; - if (get_irn_col(pi->co, get_irn_for_graph_nr(pi->co->irg, n)) == c) - val = 1; - else - val = 0; - fprintf(out, " x%d_%d\t%d\n", n, c, val); - } - fprintf(out, "ENDATA\n"); - fclose(out); +static void pi_solve_ilp(problem_instance_t *pi) { + pi_set_start_sol(pi); + lpp_solve(pi->curr_lp, 1); } -#endif -#ifdef DO_SOLVE /** - * Invoke an external solver + * Set the color of all simplicial nodes removed form + * the graph before transforming it to an ilp. */ -static void pi_solve_ilp(problem_instance_t *pi) { - FILE *out, *pwfile; - char passwd[128]; - - DBG((dbg, LEVEL_1, "Solving with CPLEX@RZ...\n")); - /* write command file for CPLEX */ - out = ffopen(pi->co->name, "cmd", "wt"); - fprintf(out, "set logfile %s.sol\n", pi->co->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, "set mip strategy branch 1\n"); /* branch up first */ -#ifdef DUMP_Q2ILP - fprintf(out, "read %s.q2ilp mps\n", pi->co->name); -#endif -#ifdef DUMP_DILP - fprintf(out, "read %s.dilp mps\n", pi->co->name); -#endif - fprintf(out, "read %s.mst\n", pi->co->name); - fprintf(out, "optimize\n"); - fprintf(out, "display solution variables 1-%d\n", pi->x_dim); - fprintf(out, "quit\n"); - fclose(out); - - /* write expect-file for copying problem to RZ */ - 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.dilp %s.q2ilp %s.mst %s.cmd %s:\n", pi->co->name, pi->co->name, pi->co->name, pi->co->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, pi->co->name); /* solve */ - fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd); - - fprintf(out, "spawn scp %s:%s.sol .\n", SSH_USER_HOST, pi->co->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); - - /* call the expect script */ - chmod(EXPECT_FILENAME ".exp", 0700); - system(EXPECT_FILENAME ".exp"); -} - static void pi_set_simplicials(problem_instance_t *pi) { simpl_t *simpl, *tmp; bitset_t *used_cols = bitset_alloca(arch_register_class_n_regs(pi->co->cls)); @@ -733,115 +370,45 @@ static void pi_set_simplicials(problem_instance_t *pi) { } /** - * Sets the colors of irns according to the values of variables found in the - * output file of the solver. + * Sets the colors of irns according to the values of variables + * provided by the solution of the solver. */ static void pi_apply_solution(problem_instance_t *pi) { - FILE *in ; - - if (!(in = ffopen(pi->co->name, "sol", "rt"))) - return; +// else if (vars_section && sscanf(buf, "x%d_%d %d", &num, &col, &val) == 3 && val == 1) { +// set_irn_col(lpp, get_irn_for_graph_nr(lpp->irg, num), col); + int i; + double *sol; DBG((dbg, LEVEL_1, "Applying solution...\n")); - while (!feof(in)) { - char buf[1024]; - int num = -1, col = -1, val = -1; - - fgets(buf, sizeof(buf), in); - DBG((dbg, LEVEL_3, "Line: %s", buf)); - - if (strcmp(buf, "No integer feasible solution exists.") == 0) - assert(0 && "CPLEX says: No integer feasible solution exists!"); - - if (strcmp(buf, "TODO Out of memory") == 0) {} #ifdef DO_STAT - { - /* solution time */ - float sol_time; - int iter; - if (sscanf(buf, "Solution time = %f sec. Iterations = %d", &sol_time, &iter) == 2) { - DBG((dbg, LEVEL_2, " Time: %f Iter: %d\n", sol_time, iter)); - curr_vals[I_ILP_TIME] += 10 * sol_time; - curr_vals[I_ILP_ITER] += iter; - } - } + //TODO #endif - /* variable value */ - if (sscanf(buf, "x%d_%d %d", &num, &col, &val) == 3 && val == 1) { - DBG((dbg, LEVEL_2, " x%d_%d = %d\n", num, col, val)); - set_irn_col(pi->co, get_irn_for_graph_nr(pi->co->irg, num), col); - } + sol = xmalloc(pi->last_x_var * sizeof(*sol)); + lpp_get_solution(pi->curr_lp, sol, 1, pi->last_x_var); + for (i=0; ilast_x_var; ++i) + if (sol[i] == 1) { /* split varibale name into components */ + int nnr, col; + const char *var_name = lpp_get_var_name(pi->curr_lp, 1+i); + if (split_var(var_name, &nnr, &col) == 2) { + DBG((dbg, LEVEL_2, " x%d = %d\n", nnr, col)); + set_irn_col(pi->co, get_irn_for_graph_nr(pi->co->irg, nnr), col); + } else + assert(0 && "this should be a x-var"); } - fclose(in); pi_set_simplicials(pi); } -#endif /* DO_SOLVE */ - -#ifdef DELETE_FILES -static void pi_delete_files(problem_instance_t *pi) { - char buf[1024]; - int end = snprintf(buf, sizeof(buf), "%s", pi->co->name); - DBG((dbg, LEVEL_1, "Deleting files...\n")); -#ifdef DUMP_MATRICES - snprintf(buf+end, sizeof(buf)-end, ".matrix"); - remove(buf); -#endif -#ifdef DUMP_Q2ILP - snprintf(buf+end, sizeof(buf)-end, ".q2ilp"); - remove(buf); -#endif -#ifdef DUMP_DILP - snprintf(buf+end, sizeof(buf)-end, ".dilp"); - remove(buf); -#endif -#ifdef DO_SOLVE - snprintf(buf+end, sizeof(buf)-end, ".cmd"); - remove(buf); - snprintf(buf+end, sizeof(buf)-end, ".mst"); - remove(buf); - snprintf(buf+end, sizeof(buf)-end, ".sol"); - remove(buf); - remove(EXPECT_FILENAME ".exp"); -#endif -} -#endif void co_ilp_opt(copy_opt_t *co) { problem_instance_t *pi; - dbg = firm_dbg_register("ir.be.copyoptilp"); - firm_dbg_set_mask(dbg, DEBUG_LVL); if (!strcmp(co->name, DEBUG_IRG)) firm_dbg_set_mask(dbg, -1); + else + firm_dbg_set_mask(dbg, DEBUG_LVL); pi = new_pi(co); - DBG((dbg, 0, "\t\t\t %5d %5d %5d\n", pi->x_dim, pi->A_dim, pi->B_dim)); - - if (pi->x_dim > 0) { -#ifdef DUMP_MATRICES - pi_dump_matrices(pi); -#endif - -#ifdef DUMP_Q2ILP - pi_dump_q2ilp(pi); -#endif - -#ifdef DUMP_DILP - pi_dump_dilp(pi); -#endif - -#ifdef DUMP_MST - pi_dump_start_sol(pi); -#endif -#ifdef DO_SOLVE pi_solve_ilp(pi); pi_apply_solution(pi); -#endif - -#ifdef DELETE_FILES - pi_delete_files(pi); -#endif - } free_pi(pi); } diff --git a/ir/be/becopyopt.h b/ir/be/becopyopt.h index 632c6b27a..65ae75af0 100644 --- a/ir/be/becopyopt.h +++ b/ir/be/becopyopt.h @@ -38,7 +38,7 @@ * Data representing the problem of copy minimization. */ typedef struct _copy_opt_t { - be_chordal_env_t *chordal_env; + be_chordal_env_t *chordal_env; ir_graph *irg; /**< the irg to process */ char *name; /**< ProgName__IrgName__RegClass */ const arch_env_t *env; /**< Environment (isa + handlers) */ diff --git a/ir/be/lpp.c b/ir/be/lpp.c deleted file mode 100644 index d9b4399e9..000000000 --- a/ir/be/lpp.c +++ /dev/null @@ -1,292 +0,0 @@ -/** - * Author: Daniel Grund - * Date: Fri 13.05.2005 - * Copyright: (c) Universitaet Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. - */ - -#include -#include -#include -#include -#include "lpp.h" -#include "xmalloc.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 */ - - /* 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 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_lp(char *name, opt_t opt_type) { - lpp_t *lpp = xcalloc(1, sizeof(*lpp)); - lpp->name = 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->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)); - return lpp; -} - -void free_lp(lpp_t *lpp) { - del_set(lpp->cst2nr); - del_set(lpp->var2nr); - del_matrix(lpp->m); - free(lpp->csts); - free(lpp->vars); - free(lpp->rhs); - 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) { - 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; -} - -#define cst_nr(lp, name) name2nr(lpp->cst2nr, name) -#define var_nr(lp, 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 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); - } -} - -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; -} - -void lpp_set_all_constr(lpp_t *lpp, char *cst_name, char **var_names, int *values) { - assert(0 && "NYI"); -} - -/****************************************************************************** - 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 = ""; - - 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 %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); - } - } - - 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; -} - -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; 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=0; ivar_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; - - /* 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 */ - - /* RHS */ - mps_write_line(out, style, l_ind_rhs); - for(i=0; irhs_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]); - - /* ENDATA */ - mps_write_line(out, style, l_ind_end); -} - -/****************************************************************************** - LP-STUFF -******************************************************************************/ - -static void lpp_dump_lp(lpp_t *lpp, FILE *out) { - assert(0 && "NYI"); -} - -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); - } -} diff --git a/ir/be/lpp.h b/ir/be/lpp.h index 60b1254b2..13b45fe83 100644 --- a/ir/be/lpp.h +++ b/ir/be/lpp.h @@ -9,56 +9,100 @@ 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, real=1, binary=2} var_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; + +#define ERR_NAME_NOT_ALLOWED -2 /** - * Fixed-column mps where spaces are allowed in identifiers :-0 - * Free mps where whitespace is a seperator :-) - * LP format + * Creates a new problem. Optimization type is minimize or maximize. + * Implicit row with name "obj" is inserted. + * Implicit col with name "rhs" is inserted. */ -typedef enum _style_t {s_mps_fixed, s_mps_free, s_lp} style_t; +lpp_t *new_lpp(const char *name, opt_t opt_type); -typedef struct _lpp_t lpp_t; +void free_lpp(lpp_t *lpp); /** - * Creates a new problem. Optimization type is minimize or maximize + * 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 */ -lpp_t *new_lp(char *name, opt_t opt_type); +int lpp_add_cst(lpp_t *lpp, const char *cst_name, cst_t cst_type, double rhs); -void free_lp(lpp_t *lpp); +/** + * 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, char *cst_name); /** - * Adds a constraint to a problem. If a constraint with the same name already exists result is undefined. - * @param cst_name The name of the constraint. - * @param cst_type The type of constraint: objective, equality, less-or-equal, greater-or-equal + * Returns the name of a constraint. + * @param index The internal index of a constraint. */ -void lpp_add_constr(lpp_t *lpp, const char *cst_name, cst_t cst_type); +const char *lpp_get_cst_name(lpp_t *lpp, int index); /** - * Adds a variable to a problem. If a variable with the same name already exists result is undefined. - * @param var_name The name of the variable. - * @param var_type The type of the var: real or binary + * 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 objactive value coefficient for this variable. + * @return The (new or existing) index of the variable + * * NOTE: common integer or semi-continous vars are not (yet) implemented */ -void lpp_add_var(lpp_t *lpp, const char *var_name, var_t var_type); +int lpp_add_var(lpp_t *lpp, const char *var_name, var_t var_type, double obj); + +/** + * 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, char *var_name); + +/** + * Returns the name of a variable. + * @param index The internal index of a variable. + */ +const char *lpp_get_var_name(lpp_t *lpp, int index); /** * 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 + */ +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 */ -void lpp_set_factor(lpp_t *lpp, const char *cst_name, const char *var_name, int value); +int lpp_set_factor_fast(lpp_t *lpp, int cst_idx, int var_idx, double value); /** - * Sets the value for the right hand side of constraint @p cst_name to @p 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_rhs(lpp_t *lpp, char *cst_name, int value); +void lpp_set_start_value(lpp_t *lpp, int var_idx, double value); /** - * Sets, for constraint @p cst_name, all factors of all variables - * given in @p var_names to the values given in @p values. + * Solve the problem. + * @return -1 if an error ocurred, 0 otherwise */ -void lpp_set_all_constr(lpp_t *lpp, char *cst_name, char **var_names, int *values); +int lpp_solve(lpp_t *lpp, int use_start_values); /** - * Writes out the problem in the format specified be @p style. + * @return The solution values of the variables from index begin to index end. */ -void lpp_dump(lpp_t *lpp, FILE *out, style_t style); +sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end); diff --git a/ir/be/lpp_rzcpx.c b/ir/be/lpp_rzcpx.c new file mode 100644 index 000000000..d92858e67 --- /dev/null +++ b/ir/be/lpp_rzcpx.c @@ -0,0 +1,559 @@ +/** + * Author: Daniel Grund + * Date: Fri 13.05.2005 + * Copyright: (c) Universitaet Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ + +#include +#include +#include +#include +#include +#include + +#include "debug.h" +#include "lpp.h" +#include "xmalloc.h" +#include "assert.h" +#include "hashptr.h" +#include "set.h" +#include "sp_matrix.h" + +/* CPLEX-account related stuff */ +#undef 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 */ + +typedef struct _name_t name_t; +typedef enum _value_kind_t {none=0, start, solution} value_kind_t; + +#define DEBUG_LVL SET_LEVEL_1 +static firm_dbg_module_t *dbg = NULL; + + +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; +}; + +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 */ + char *error; + sol_state_t sol_state; + double sol_time; + unsigned iterations; + + unsigned next_name_number; +}; + +#define HASH_NAME_T(n) HASH_STR((n)->name, strlen((n)->name)) + +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 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) { + dbg = firm_dbg_register("ir.be.copyoptilp"); + firm_dbg_set_mask(dbg, DEBUG_LVL); + + lpp_t *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, const 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); +} + +const char *lpp_get_cst_name(lpp_t *lpp, int index) { + DBG((dbg, LEVEL_2, "%d --> %s\n", index, lpp->csts[index]->name)); + return lpp->csts[index]->name; +} + +int lpp_add_var(lpp_t *lpp, const 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); +} + +const char *lpp_get_var_name(lpp_t *lpp, int index) { + DBG((dbg, LEVEL_2, "%d --> %s\n", index, lpp->vars[index]->name)); + return lpp->vars[index]->name; +} + +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); + if (cst == -1 || var == -1) + return -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); + if (cst_idx >= lpp->cst_next || var_idx >= lpp->var_next || cst_idx < 0 || var_idx < 0) + return -1; + 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 = start; +} + + +/****************************************************************************** + MPS-STUFF +******************************************************************************/ + +/** + * Fixed-column mps where spaces are allowed in identifiers :-0 + * Free mps where whitespace is a seperator :-) + * LP format + */ +typedef enum _style_t {s_mps_fixed, s_mps_free} style_t; + +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_data_mst, 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 = ""; + + 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; +} + +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, "set mip strategy branch 1\n"); /* branch up first */ + 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_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; + var_t last_type; + assert(style == s_mps_fixed || style == s_mps_free); + + out = ffopen(lpp->name, "mps", "wt"); + /* 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; 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); + fclose(out); +} + +static void lpp_write_mst(lpp_t *lpp, style_t style) { + int i; + FILE *out = ffopen(lpp->name, "mst", "wt"); + 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 == start) + mps_write_line(out, style, l_data_mst, var->name, (double)var->value); + } + mps_write_line(out, style, l_ind_end); + 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); +} + +/** + * Sets the colors of irns according to the values of variables found in the + * output file of the solver. + */ +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 = no_solution_file; + 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 = 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[var_nr(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 + +int lpp_solve(lpp_t *lpp, int use_start_values) { + lpp_write_cmd(lpp); + lpp_write_mps(lpp, s_mps_free); + if (use_start_values) + lpp_write_mst(lpp, s_mps_free); + 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 + return 0; +} + +sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end) { + int i; + if (lpp->sol_state < 4) + return lpp->sol_state; + /* here we are feasible or optimal */ + for (i=0; ivars[begin+i]->value; + return lpp->sol_state; +} -- 2.20.1