2 * Copyright (C) 2005-2011 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @author Daniel Grund
37 #include "sp_matrix.h"
41 #include "lpp_solvers.h"
44 #define HASH_NAME_T(n) hash_str((n)->name)
46 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
48 static inline char *obst_xstrdup(struct obstack *obst, const char *str)
50 return (char*)obstack_copy0(obst, str, strlen(str));
53 static int cmp_name_t(const void *x, const void *y, size_t size)
55 const lpp_name_t *n = (const lpp_name_t*)x;
56 const lpp_name_t *m = (const lpp_name_t*)y;
58 return strcmp(n->name, m->name);
62 * Update statistic information about matrix usage.
64 static void update_stats(lpp_t *lpp)
66 lpp->n_elems = matrix_get_entries(lpp->m);
67 lpp->matrix_mem = lpp->n_elems * matrix_get_elem_size();
68 lpp->density = (double)lpp->n_elems / (double)(lpp->cst_next * lpp->var_next) * 100.0;
71 lpp_t *lpp_new(const char *name, lpp_opt_t opt_type)
73 return lpp_new_userdef(name, opt_type, 64, 64, 2.0);
76 lpp_t *lpp_new_userdef(const char *name, lpp_opt_t opt_type,
77 int estimated_vars, int estimated_csts,
83 DEBUG_ONLY(dbg = firm_dbg_register("lpp");)
84 lpp = XMALLOCZ(lpp_t);
85 obstack_init(&lpp->obst);
87 lpp->name = obst_xstrdup(&lpp->obst, name);
88 lpp->opt_type = opt_type;
89 lpp->grow_factor = grow_factor;
90 lpp->cst2nr = new_set(cmp_name_t, estimated_csts);
91 lpp->var2nr = new_set(cmp_name_t, estimated_vars);
92 lpp->cst_size = estimated_csts;
93 lpp->var_size = estimated_vars;
94 lpp->csts = XMALLOCNZ(lpp_name_t *, estimated_csts);
95 lpp->vars = XMALLOCNZ(lpp_name_t *, estimated_vars);
96 lpp->m = new_matrix(estimated_csts, estimated_vars);
97 lpp->emphasis = lpp_balanced;
98 idx = lpp_add_cst(lpp, "obj", lpp_objective, 0);
100 idx = lpp_add_var(lpp, "rhs", lpp_rhs, 0);
106 void lpp_free_matrix(lpp_t *lpp)
112 void lpp_free(lpp_t *lpp)
114 obstack_free(&lpp->obst, NULL);
116 del_set(lpp->cst2nr);
117 del_set(lpp->var2nr);
119 /* matrix might have been already deleted */
129 double lpp_get_fix_costs(lpp_t *lpp)
131 return matrix_get(lpp->m, 0, 0);
134 void lpp_set_fix_costs(lpp_t *lpp, double value)
136 matrix_set(lpp->m, 0, 0, value);
139 static int name2nr(set *where, const char *name)
141 lpp_name_t find, *found;
143 found = set_find(lpp_name_t, where, &find, sizeof(find), HASH_NAME_T(&find));
144 return (found ? found->nr : -1);
147 static int cst_nr(const lpp_t *lpp, const char *name)
149 return name2nr(lpp->cst2nr, name);
152 static int var_nr(const lpp_t *lpp, const char *name)
154 return name2nr(lpp->var2nr, name);
157 static inline char *get_next_name(lpp_t *lpp)
159 char *res = OALLOCN(&lpp->obst, char, 12);
160 snprintf(res, 12, "_%u", lpp->next_name_number++);
164 int lpp_add_cst(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs)
166 lpp_name_t n, *inner;
168 DBG((dbg, LEVEL_2, "%s %d %g\n", cst_name, cst_type, rhs));
170 if (cst_name && cst_name[0] == '_')
171 return ERR_NAME_NOT_ALLOWED;
174 n.name = obst_xstrdup(&lpp->obst, cst_name);
176 n.name = get_next_name(lpp);
179 inner = set_insert(lpp_name_t, lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n));
182 if (inner->nr == -1) {
183 inner->value_kind = lpp_none;
185 inner->nr = lpp->cst_next;
186 inner->type.cst_type = cst_type;
188 if (lpp->cst_next == lpp->cst_size) {
189 lpp->cst_size = (int)((double)lpp->cst_size * lpp->grow_factor) + 1;
190 lpp->csts = XREALLOC(lpp->csts, lpp_name_t *, lpp->cst_size);
193 lpp->csts[lpp->cst_next] = inner;
195 matrix_set(lpp->m, inner->nr, 0, rhs);
202 int lpp_add_cst_uniq(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs)
209 assert(!set_find(lpp_name_t, lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n)) &&
210 "constraint already exists");
212 return lpp_add_cst(lpp, cst_name, cst_type, rhs);
215 int lpp_get_cst_idx(lpp_t *lpp, const char *cst_name)
217 DBG((dbg, LEVEL_2, "%s --> %d\n", cst_name, cst_nr(lpp, cst_name)));
218 return cst_nr(lpp, cst_name);
221 void lpp_get_cst_name(lpp_t *lpp, int index, char *buf, size_t buf_size)
223 DBG((dbg, LEVEL_2, "%d --> %s\n", index, lpp->csts[index]->name));
224 strncpy(buf, lpp->csts[index]->name, buf_size);
227 int lpp_add_var_default(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj, double startval)
231 val = lpp_add_var(lpp, var_name, var_type, obj);
232 lpp_set_start_value(lpp, val, startval);
237 int lpp_add_var(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj)
239 lpp_name_t n, *inner;
241 DBG((dbg, LEVEL_2, "%s %d %g\n", var_name, var_type, obj));
243 assert(var_type != lpp_invalid && "invalid is for internal use only");
245 if (var_name && var_name[0] == '_')
246 return ERR_NAME_NOT_ALLOWED;
249 n.name = obst_xstrdup(&lpp->obst, var_name);
251 n.name = get_next_name(lpp);
254 inner = set_insert(lpp_name_t, lpp->var2nr, &n, sizeof(n), HASH_NAME_T(&n));
257 if (inner->nr == -1) {
258 inner->nr = lpp->var_next;
259 inner->value_kind = lpp_none;
261 inner->type.var_type = var_type;
263 if (lpp->var_next == lpp->var_size) {
264 lpp->var_size = (int)((double)lpp->var_size * lpp->grow_factor) + 1;
265 lpp->vars = XREALLOC(lpp->vars, lpp_name_t *, lpp->var_size);
268 lpp->vars[lpp->var_next] = inner;
270 matrix_set(lpp->m, 0, inner->nr, obj);
277 int lpp_get_var_idx(lpp_t *lpp, const char *var_name)
279 DBG((dbg, LEVEL_2, "%s --> %d\n", var_name, var_nr(lpp, var_name)));
280 return var_nr(lpp, var_name);
283 void lpp_get_var_name(lpp_t *lpp, int index, char *buf, size_t buf_size)
285 DBG((dbg, LEVEL_2, "%d --> %s\n", index, lpp->vars[index]->name));
286 strncpy(buf, lpp->vars[index]->name, buf_size);
289 int lpp_set_factor(lpp_t *lpp, const char *cst_name, const char *var_name, double value)
293 cst = cst_nr(lpp, cst_name);
294 var = var_nr(lpp, var_name);
295 assert(cst != -1 && var != -1);
296 DBG((dbg, LEVEL_2, "%s[%d] %s[%d] %g\n", cst_name, cst, var_name, var, value));
297 matrix_set(lpp->m, cst, var, value);
302 int lpp_set_factor_fast(lpp_t *lpp, int cst_idx, int var_idx, double value)
304 assert(cst_idx >= 0 && var_idx >= 0);
305 assert(cst_idx < lpp->cst_next && var_idx < lpp->var_next);
306 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));
307 matrix_set(lpp->m, cst_idx, var_idx, value);
312 int lpp_set_factor_fast_bulk(lpp_t *lpp, int cst_idx, int *var_idx, int num_vars, double value)
314 assert(cst_idx >= 0 && cst_idx < lpp->cst_next);
315 assert(num_vars < lpp->var_next);
316 DBG((dbg, LEVEL_2, "row %s[%d] %d vars %g\n", lpp->csts[cst_idx]->name, cst_idx, num_vars, value));
317 matrix_set_row_bulk(lpp->m, cst_idx, var_idx, num_vars, value);
322 void lpp_set_start_value(lpp_t *lpp, int var_idx, double value)
324 assert(var_idx > 0 && var_idx < lpp->var_next);
325 DBG((dbg, LEVEL_2, "%d %s %g\n", var_idx, lpp->vars[var_idx]->name, value));
326 lpp->vars[var_idx]->value = value;
327 lpp->vars[var_idx]->value_kind = lpp_value_start;
330 lpp_sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end)
334 if (lpp->sol_state < lpp_feasible)
335 return lpp->sol_state;
337 /* here we are feasible or optimal */
338 for (i = 0; i < end - begin + 1; ++i)
339 values[i] = lpp->vars[begin + i]->value;
341 return lpp->sol_state;
344 void lpp_check_startvals(lpp_t *lpp)
348 for (cst_idx = 1; cst_idx < lpp->cst_next; ++cst_idx) {
350 lpp_name_t *cst = lpp->csts[cst_idx];
351 double cst_val = matrix_get(lpp->m, cst_idx, 0);
354 for (var_idx = 1; var_idx < lpp->var_next; ++var_idx) {
355 if (lpp->vars[var_idx]->value_kind != lpp_value_start)
358 sum += lpp->vars[var_idx]->value *
359 matrix_get(lpp->m, cst_idx, var_idx);
361 switch(cst->type.cst_type) {
364 fprintf(stderr, "constraint %s unsatisfied: %g != %g\n", cst->name, sum, cst_val);
369 fprintf(stderr, "constraint %s unsatisfied: %g >= %g\n", cst->name, sum, cst_val);
372 case lpp_greater_equal:
374 fprintf(stderr, "constraint %s unsatisfied: %g <= %g\n", cst->name, sum, cst_val);
378 assert(0 && "unknown constraint type");
384 void lpp_dump(lpp_t *lpp, const char *filename)
386 FILE *out = fopen(filename, "wt");
387 mps_write_mps(lpp, s_mps_fixed, out);
391 void lpp_set_log(lpp_t *lpp, FILE *log)
397 static const char *lpp_cst_op_to_str(lpp_cst_t cst)
404 case lpp_greater_equal:
411 void lpp_dump_plain(lpp_t *lpp, FILE *f)
415 for(i = 0; i < lpp->cst_next; ++i) {
416 const matrix_elem_t *elm;
417 lpp_name_t *cst = lpp->csts[i];
419 fprintf(f, "%16s: ", cst->name);
420 matrix_foreach_in_row(lpp->m, cst->nr, elm) {
421 lpp_name_t *var = lpp->vars[elm->col];
422 /* TODO Perhaps better a define LPP_COL_RHS */
424 fprintf(f, "%+4.1f*%-16s ", elm->val, var->name);
427 fprintf(f, "%3s %+4.1f\n",
428 lpp_cst_op_to_str(cst->type.cst_type), matrix_get(lpp->m, cst->nr, 0));
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 const matrix_elem_t *elm;
477 matrix_foreach(lpp->m, elm)
480 assert(n == matrix_get_entries(lpp->m));
482 matrix_foreach(lpp->m, elm) {
483 lpp_writel(comm, elm->row);
484 lpp_writel(comm, elm->col);
485 lpp_writed(comm, elm->val);
491 * Deserialize an lpp from a file descriptor.
492 * @param comm The file descriptor.
493 * @return The Problem.
495 lpp_t *lpp_deserialize(lpp_comm_t *comm)
500 lpp_t *lpp = XMALLOCZ(lpp_t);
502 /* read general settings */
503 with_names = lpp_readl(comm);
504 lpp->cst_next = lpp_readl(comm);
505 lpp->var_next = lpp_readl(comm);
506 lpp->opt_type = (lpp_opt_t)lpp_readl(comm);
507 lpp->name = lpp_reads(comm);
510 lpp->set_bound = lpp_readl(comm);
511 lpp->bound = lpp_readd(comm);
512 lpp->time_limit_secs = lpp_readd(comm);
513 lpp->emphasis = (lpp_emphasis_t)lpp_readl(comm);
515 lpp->cst_size = lpp->cst_next;
516 lpp->var_size = lpp->var_next;
518 lpp->cst2nr = new_set(cmp_name_t, lpp->cst_next);
519 lpp->var2nr = new_set(cmp_name_t, lpp->var_next);
521 lpp->csts = XMALLOCNZ(lpp_name_t*, lpp->cst_next);
522 lpp->vars = XMALLOCNZ(lpp_name_t*, lpp->var_next);
523 lpp->m = new_matrix(lpp->cst_next, lpp->var_next);
525 for(i = 0; i < lpp->cst_next; ++i) {
526 lpp_name_t name, *res;
528 name.nr = lpp_readl(comm);
529 name.value_kind = (lpp_value_kind_t)lpp_readl(comm);
530 name.type.cst_type = (lpp_cst_t)lpp_readl(comm);
533 name.name = lpp_reads(comm);
535 char* buf = XMALLOCN(char, 32);
536 snprintf(buf, 32, "c%d\n", name.nr);
540 res = set_insert(lpp_name_t, lpp->cst2nr, &name, sizeof(name), HASH_NAME_T(&name));
541 lpp->csts[name.nr] = res;
544 for(i = 0; i < lpp->var_next; ++i) {
545 lpp_name_t name, *res;
547 name.nr = lpp_readl(comm);
548 name.value_kind = (lpp_value_kind_t)lpp_readl(comm);
549 name.type.var_type = (lpp_var_t)lpp_readl(comm);
552 name.name = lpp_reads(comm);
554 char* buf = XMALLOCN(char, 32);
555 snprintf(buf, 32, "v%d\n", name.nr);
559 res = set_insert(lpp_name_t, lpp->var2nr, &name, sizeof(name), HASH_NAME_T(&name));
560 lpp->vars[name.nr] = res;
564 for(i = 0; i < n; ++i) {
566 elm.row = lpp_readl(comm);
567 elm.col = lpp_readl(comm);
568 elm.val = lpp_readd(comm);
569 matrix_set(lpp->m, elm.row, elm.col, elm.val);
575 void lpp_serialize_values(lpp_comm_t *comm, const lpp_t *lpp, lpp_value_kind_t value_kind)
579 for(i = 0, n = 0; i < lpp->var_next; ++i)
580 n += lpp->vars[i]->value_kind == value_kind;
582 /* Write the number of values to expect */
585 /* send the values */
586 for(i = 0, n = lpp->var_next; i < n; ++i) {
587 const lpp_name_t *name = lpp->vars[i];
588 if(name->value_kind == value_kind) {
589 lpp_writel(comm, name->nr);
590 lpp_writed(comm, name->value);
595 void lpp_deserialize_values(lpp_comm_t *comm, lpp_t *lpp, lpp_value_kind_t value_kind)
599 /* Get the number of values to read */
602 for(i = 0; i < n; ++i) {
603 int nr = lpp_readl(comm);
604 lpp_name_t *name = lpp->vars[nr];
606 name->value_kind = value_kind;
607 name->value = lpp_readd(comm);
611 void lpp_serialize_stats(lpp_comm_t *comm, const lpp_t *lpp)
613 lpp_writel(comm, lpp->sol_state);
614 lpp_writel(comm, lpp->iterations);
615 lpp_writed(comm, lpp->sol_time);
616 lpp_writed(comm, lpp->objval);
617 lpp_writed(comm, lpp->best_bound);
620 void lpp_deserialize_stats(lpp_comm_t *comm, lpp_t *lpp)
622 lpp->sol_state = (lpp_sol_state_t)lpp_readl(comm);
623 lpp->iterations = lpp_readl(comm);
624 lpp->sol_time = lpp_readd(comm);
625 lpp->objval = lpp_readd(comm);
626 lpp->best_bound = lpp_readd(comm);
629 void lpp_solve(lpp_t *lpp, const char* host, const char* solver)
631 if (host == NULL || strlen(host) == 0) {
632 lpp_solver_func_t* f = lpp_find_solver(solver);
636 lpp_solve_net(lpp, host, solver);