2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
23 #include "sp_matrix.h"
27 #include "lpp_solvers.h"
30 #define HASH_NAME_T(n) hash_str((n)->name)
32 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
34 static inline char *obst_xstrdup(struct obstack *obst, const char *str)
36 return (char*)obstack_copy0(obst, str, strlen(str));
39 static int cmp_name_t(const void *x, const void *y, size_t size)
41 const lpp_name_t *n = (const lpp_name_t*)x;
42 const lpp_name_t *m = (const lpp_name_t*)y;
44 return strcmp(n->name, m->name);
48 * Update statistic information about matrix usage.
50 static void update_stats(lpp_t *lpp)
52 lpp->n_elems = matrix_get_entries(lpp->m);
53 lpp->matrix_mem = lpp->n_elems * matrix_get_elem_size();
54 lpp->density = (double)lpp->n_elems / (double)(lpp->cst_next * lpp->var_next) * 100.0;
57 lpp_t *lpp_new(const char *name, lpp_opt_t opt_type)
59 return lpp_new_userdef(name, opt_type, 64, 64, 2.0);
62 lpp_t *lpp_new_userdef(const char *name, lpp_opt_t opt_type,
63 int estimated_vars, int estimated_csts,
69 DEBUG_ONLY(dbg = firm_dbg_register("lpp");)
70 lpp = XMALLOCZ(lpp_t);
71 obstack_init(&lpp->obst);
73 lpp->name = obst_xstrdup(&lpp->obst, name);
74 lpp->opt_type = opt_type;
75 lpp->grow_factor = grow_factor;
76 lpp->cst2nr = new_set(cmp_name_t, estimated_csts);
77 lpp->var2nr = new_set(cmp_name_t, estimated_vars);
78 lpp->cst_size = estimated_csts;
79 lpp->var_size = estimated_vars;
80 lpp->csts = XMALLOCNZ(lpp_name_t *, estimated_csts);
81 lpp->vars = XMALLOCNZ(lpp_name_t *, estimated_vars);
82 lpp->m = new_matrix(estimated_csts, estimated_vars);
83 lpp->emphasis = lpp_balanced;
84 idx = lpp_add_cst(lpp, "obj", lpp_objective, 0);
86 idx = lpp_add_var(lpp, "rhs", lpp_rhs, 0);
92 void lpp_free_matrix(lpp_t *lpp)
98 void lpp_free(lpp_t *lpp)
100 obstack_free(&lpp->obst, NULL);
102 del_set(lpp->cst2nr);
103 del_set(lpp->var2nr);
105 /* matrix might have been already deleted */
115 double lpp_get_fix_costs(lpp_t *lpp)
117 return matrix_get(lpp->m, 0, 0);
120 void lpp_set_fix_costs(lpp_t *lpp, double value)
122 matrix_set(lpp->m, 0, 0, value);
125 static int name2nr(set *where, const char *name)
127 lpp_name_t find, *found;
129 found = set_find(lpp_name_t, where, &find, sizeof(find), HASH_NAME_T(&find));
130 return (found ? found->nr : -1);
133 static int cst_nr(const lpp_t *lpp, const char *name)
135 return name2nr(lpp->cst2nr, name);
138 static int var_nr(const lpp_t *lpp, const char *name)
140 return name2nr(lpp->var2nr, name);
143 static inline char *get_next_name(lpp_t *lpp)
145 char *res = OALLOCN(&lpp->obst, char, 12);
146 snprintf(res, 12, "_%u", lpp->next_name_number++);
150 int lpp_add_cst(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs)
152 lpp_name_t n, *inner;
154 DBG((dbg, LEVEL_2, "%s %d %g\n", cst_name, cst_type, rhs));
156 if (cst_name && cst_name[0] == '_')
157 return ERR_NAME_NOT_ALLOWED;
160 n.name = obst_xstrdup(&lpp->obst, cst_name);
162 n.name = get_next_name(lpp);
165 inner = set_insert(lpp_name_t, lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n));
168 if (inner->nr == -1) {
169 inner->value_kind = lpp_none;
171 inner->nr = lpp->cst_next;
172 inner->type.cst_type = cst_type;
174 if (lpp->cst_next == lpp->cst_size) {
175 lpp->cst_size = (int)((double)lpp->cst_size * lpp->grow_factor) + 1;
176 lpp->csts = XREALLOC(lpp->csts, lpp_name_t *, lpp->cst_size);
179 lpp->csts[lpp->cst_next] = inner;
181 matrix_set(lpp->m, inner->nr, 0, rhs);
188 int lpp_add_cst_uniq(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs)
195 assert(!set_find(lpp_name_t, lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n)) &&
196 "constraint already exists");
198 return lpp_add_cst(lpp, cst_name, cst_type, rhs);
201 int lpp_get_cst_idx(lpp_t *lpp, const char *cst_name)
203 DBG((dbg, LEVEL_2, "%s --> %d\n", cst_name, cst_nr(lpp, cst_name)));
204 return cst_nr(lpp, cst_name);
207 void lpp_get_cst_name(lpp_t *lpp, int index, char *buf, size_t buf_size)
209 DBG((dbg, LEVEL_2, "%d --> %s\n", index, lpp->csts[index]->name));
210 strncpy(buf, lpp->csts[index]->name, buf_size);
213 int lpp_add_var_default(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj, double startval)
217 val = lpp_add_var(lpp, var_name, var_type, obj);
218 lpp_set_start_value(lpp, val, startval);
223 int lpp_add_var(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj)
225 lpp_name_t n, *inner;
227 DBG((dbg, LEVEL_2, "%s %d %g\n", var_name, var_type, obj));
229 assert(var_type != lpp_invalid && "invalid is for internal use only");
231 if (var_name && var_name[0] == '_')
232 return ERR_NAME_NOT_ALLOWED;
235 n.name = obst_xstrdup(&lpp->obst, var_name);
237 n.name = get_next_name(lpp);
240 inner = set_insert(lpp_name_t, lpp->var2nr, &n, sizeof(n), HASH_NAME_T(&n));
243 if (inner->nr == -1) {
244 inner->nr = lpp->var_next;
245 inner->value_kind = lpp_none;
247 inner->type.var_type = var_type;
249 if (lpp->var_next == lpp->var_size) {
250 lpp->var_size = (int)((double)lpp->var_size * lpp->grow_factor) + 1;
251 lpp->vars = XREALLOC(lpp->vars, lpp_name_t *, lpp->var_size);
254 lpp->vars[lpp->var_next] = inner;
256 matrix_set(lpp->m, 0, inner->nr, obj);
263 int lpp_get_var_idx(lpp_t *lpp, const char *var_name)
265 DBG((dbg, LEVEL_2, "%s --> %d\n", var_name, var_nr(lpp, var_name)));
266 return var_nr(lpp, var_name);
269 void lpp_get_var_name(lpp_t *lpp, int index, char *buf, size_t buf_size)
271 DBG((dbg, LEVEL_2, "%d --> %s\n", index, lpp->vars[index]->name));
272 strncpy(buf, lpp->vars[index]->name, buf_size);
275 int lpp_set_factor(lpp_t *lpp, const char *cst_name, const char *var_name, double value)
279 cst = cst_nr(lpp, cst_name);
280 var = var_nr(lpp, var_name);
281 assert(cst != -1 && var != -1);
282 DBG((dbg, LEVEL_2, "%s[%d] %s[%d] %g\n", cst_name, cst, var_name, var, value));
283 matrix_set(lpp->m, cst, var, value);
288 int lpp_set_factor_fast(lpp_t *lpp, int cst_idx, int var_idx, double value)
290 assert(cst_idx >= 0 && var_idx >= 0);
291 assert(cst_idx < lpp->cst_next && var_idx < lpp->var_next);
292 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));
293 matrix_set(lpp->m, cst_idx, var_idx, value);
298 int lpp_set_factor_fast_bulk(lpp_t *lpp, int cst_idx, int *var_idx, int num_vars, double value)
300 assert(cst_idx >= 0 && cst_idx < lpp->cst_next);
301 assert(num_vars < lpp->var_next);
302 DBG((dbg, LEVEL_2, "row %s[%d] %d vars %g\n", lpp->csts[cst_idx]->name, cst_idx, num_vars, value));
303 matrix_set_row_bulk(lpp->m, cst_idx, var_idx, num_vars, value);
308 void lpp_set_start_value(lpp_t *lpp, int var_idx, double value)
310 assert(var_idx > 0 && var_idx < lpp->var_next);
311 DBG((dbg, LEVEL_2, "%d %s %g\n", var_idx, lpp->vars[var_idx]->name, value));
312 lpp->vars[var_idx]->value = value;
313 lpp->vars[var_idx]->value_kind = lpp_value_start;
316 lpp_sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end)
320 if (lpp->sol_state < lpp_feasible)
321 return lpp->sol_state;
323 /* here we are feasible or optimal */
324 for (i = 0; i < end - begin + 1; ++i)
325 values[i] = lpp->vars[begin + i]->value;
327 return lpp->sol_state;
330 void lpp_check_startvals(lpp_t *lpp)
334 for (cst_idx = 1; cst_idx < lpp->cst_next; ++cst_idx) {
336 lpp_name_t *cst = lpp->csts[cst_idx];
337 double cst_val = matrix_get(lpp->m, cst_idx, 0);
340 for (var_idx = 1; var_idx < lpp->var_next; ++var_idx) {
341 if (lpp->vars[var_idx]->value_kind != lpp_value_start)
344 sum += lpp->vars[var_idx]->value *
345 matrix_get(lpp->m, cst_idx, var_idx);
347 switch(cst->type.cst_type) {
350 fprintf(stderr, "constraint %s unsatisfied: %g != %g\n", cst->name, sum, cst_val);
355 fprintf(stderr, "constraint %s unsatisfied: %g >= %g\n", cst->name, sum, cst_val);
358 case lpp_greater_equal:
360 fprintf(stderr, "constraint %s unsatisfied: %g <= %g\n", cst->name, sum, cst_val);
364 assert(0 && "unknown constraint type");
370 void lpp_dump(lpp_t *lpp, const char *filename)
372 FILE *out = fopen(filename, "wt");
373 mps_write_mps(lpp, s_mps_fixed, out);
377 void lpp_set_log(lpp_t *lpp, FILE *log)
383 static const char *lpp_cst_op_to_str(lpp_cst_t cst)
390 case lpp_greater_equal:
397 void lpp_dump_plain(lpp_t *lpp, FILE *f)
401 fprintf(f, lpp->opt_type == lpp_minimize ? "Minimize\n" : "Maximize\n");
402 for(i = 0; i < lpp->cst_next; ++i) {
403 lpp_name_t *cst = lpp->csts[i];
406 fprintf(f, "%16s: ", cst->name);
407 matrix_foreach_in_row(lpp->m, cst->nr, elm) {
408 lpp_name_t *var = lpp->vars[elm->col];
409 /* TODO Perhaps better a define LPP_COL_RHS */
411 fprintf(f, "%+4.1f %-16s ", elm->val, var->name);
415 fprintf(f, "\nSubject To\n");
419 fprintf(f, "%3s %+4.1f\n",
420 lpp_cst_op_to_str(cst->type.cst_type), matrix_get(lpp->m, cst->nr, 0));
423 fprintf(f, "Binary\n");
424 for(i = 0; i < lpp->var_next; ++i) {
425 lpp_name_t *var = lpp->vars[i];
426 if (var->type.var_type == lpp_binary)
427 fprintf(f, "%16s\n", var->name);
433 * Serialize a lpp to a file descriptor.
434 * @param comm The file descriptor.
435 * @param lpp The lpp.
437 void lpp_serialize(lpp_comm_t *comm, const lpp_t *lpp, int with_names)
441 lpp_writel(comm, with_names);
442 lpp_writel(comm, lpp->cst_next);
443 lpp_writel(comm, lpp->var_next);
444 lpp_writel(comm, lpp->opt_type);
445 lpp_writes(comm, lpp->name);
448 lpp_writel(comm, lpp->set_bound);
449 lpp_writed(comm, lpp->bound);
450 lpp_writed(comm, lpp->time_limit_secs);
451 lpp_writel(comm, lpp->emphasis);
453 for(i = 0; i < lpp->cst_next; ++i) {
454 lpp_name_t *name = lpp->csts[i];
455 lpp_writel(comm, name->nr);
456 lpp_writel(comm, name->value_kind);
457 lpp_writel(comm, name->type.cst_type);
460 lpp_writes(comm, name->name);
463 for(i = 0; i < lpp->var_next; ++i) {
464 lpp_name_t *name = lpp->vars[i];
465 lpp_writel(comm, name->nr);
466 lpp_writel(comm, name->value_kind);
467 lpp_writel(comm, name->type.var_type);
470 lpp_writes(comm, name->name);
474 matrix_foreach(lpp->m, elm)
477 assert(n == matrix_get_entries(lpp->m));
479 matrix_foreach(lpp->m, elm) {
480 lpp_writel(comm, elm->row);
481 lpp_writel(comm, elm->col);
482 lpp_writed(comm, elm->val);
487 * Deserialize an lpp from a file descriptor.
488 * @param comm The file descriptor.
489 * @return The Problem.
491 lpp_t *lpp_deserialize(lpp_comm_t *comm)
496 lpp_t *lpp = XMALLOCZ(lpp_t);
498 /* read general settings */
499 with_names = lpp_readl(comm);
500 lpp->cst_next = lpp_readl(comm);
501 lpp->var_next = lpp_readl(comm);
502 lpp->opt_type = (lpp_opt_t)lpp_readl(comm);
503 lpp->name = lpp_reads(comm);
506 lpp->set_bound = lpp_readl(comm);
507 lpp->bound = lpp_readd(comm);
508 lpp->time_limit_secs = lpp_readd(comm);
509 lpp->emphasis = (lpp_emphasis_t)lpp_readl(comm);
511 lpp->cst_size = lpp->cst_next;
512 lpp->var_size = lpp->var_next;
514 lpp->cst2nr = new_set(cmp_name_t, lpp->cst_next);
515 lpp->var2nr = new_set(cmp_name_t, lpp->var_next);
517 lpp->csts = XMALLOCNZ(lpp_name_t*, lpp->cst_next);
518 lpp->vars = XMALLOCNZ(lpp_name_t*, lpp->var_next);
519 lpp->m = new_matrix(lpp->cst_next, lpp->var_next);
521 for(i = 0; i < lpp->cst_next; ++i) {
522 lpp_name_t name, *res;
524 name.nr = lpp_readl(comm);
525 name.value_kind = (lpp_value_kind_t)lpp_readl(comm);
526 name.type.cst_type = (lpp_cst_t)lpp_readl(comm);
529 name.name = lpp_reads(comm);
531 char* buf = XMALLOCN(char, 32);
532 snprintf(buf, 32, "c%d\n", name.nr);
536 res = set_insert(lpp_name_t, lpp->cst2nr, &name, sizeof(name), HASH_NAME_T(&name));
537 lpp->csts[name.nr] = res;
540 for(i = 0; i < lpp->var_next; ++i) {
541 lpp_name_t name, *res;
543 name.nr = lpp_readl(comm);
544 name.value_kind = (lpp_value_kind_t)lpp_readl(comm);
545 name.type.var_type = (lpp_var_t)lpp_readl(comm);
548 name.name = lpp_reads(comm);
550 char* buf = XMALLOCN(char, 32);
551 snprintf(buf, 32, "v%d\n", name.nr);
555 res = set_insert(lpp_name_t, lpp->var2nr, &name, sizeof(name), HASH_NAME_T(&name));
556 lpp->vars[name.nr] = res;
560 for(i = 0; i < n; ++i) {
562 elm.row = lpp_readl(comm);
563 elm.col = lpp_readl(comm);
564 elm.val = lpp_readd(comm);
565 matrix_set(lpp->m, elm.row, elm.col, elm.val);
571 void lpp_serialize_values(lpp_comm_t *comm, const lpp_t *lpp, lpp_value_kind_t value_kind)
575 for(i = 0, n = 0; i < lpp->var_next; ++i)
576 n += lpp->vars[i]->value_kind == value_kind;
578 /* Write the number of values to expect */
581 /* send the values */
582 for(i = 0, n = lpp->var_next; i < n; ++i) {
583 const lpp_name_t *name = lpp->vars[i];
584 if(name->value_kind == value_kind) {
585 lpp_writel(comm, name->nr);
586 lpp_writed(comm, name->value);
591 void lpp_deserialize_values(lpp_comm_t *comm, lpp_t *lpp, lpp_value_kind_t value_kind)
595 /* Get the number of values to read */
598 for(i = 0; i < n; ++i) {
599 int nr = lpp_readl(comm);
600 lpp_name_t *name = lpp->vars[nr];
602 name->value_kind = value_kind;
603 name->value = lpp_readd(comm);
607 void lpp_serialize_stats(lpp_comm_t *comm, const lpp_t *lpp)
609 lpp_writel(comm, lpp->sol_state);
610 lpp_writel(comm, lpp->iterations);
611 lpp_writed(comm, lpp->sol_time);
612 lpp_writed(comm, lpp->objval);
613 lpp_writed(comm, lpp->best_bound);
616 void lpp_deserialize_stats(lpp_comm_t *comm, lpp_t *lpp)
618 lpp->sol_state = (lpp_sol_state_t)lpp_readl(comm);
619 lpp->iterations = lpp_readl(comm);
620 lpp->sol_time = lpp_readd(comm);
621 lpp->objval = lpp_readd(comm);
622 lpp->best_bound = lpp_readd(comm);
625 void lpp_solve(lpp_t *lpp, const char* host, const char* solver)
627 if (host == NULL || strlen(host) == 0) {
628 lpp_solver_func_t* f = lpp_find_solver(solver);
632 lpp_solve_net(lpp, host, solver);