4 * Copyright: (c) Universitaet Karlsruhe
5 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
6 * CVS-Id: $Id: lpp.c 27353 2010-04-07 13:33:16Z matze $
25 #include "sp_matrix.h"
30 #define HASH_NAME_T(n) HASH_STR((n)->name, strlen((n)->name))
32 static firm_dbg_module_t *dbg = NULL;
34 static inline char *obst_xstrdup(struct obstack *obst, const char *str) {
35 return obstack_copy0(obst, str, strlen(str));
38 static int cmp_name_t(const void *x, const void *y, size_t size) {
39 const lpp_name_t *n = x;
40 const lpp_name_t *m = y;
41 (void)size; /* stop warnings */
42 return strcmp(n->name, m->name);
46 * Update statistic information about matrix usage.
48 static void update_stats(lpp_t *lpp) {
49 lpp->n_elems = matrix_get_entries(lpp->m);
50 lpp->matrix_mem = lpp->n_elems * matrix_get_elem_size();
51 lpp->density = (double)lpp->n_elems / (double)(lpp->cst_next * lpp->var_next) * 100.0;
54 #define INITIAL_SIZE 64
56 lpp_t *new_lpp(const char *name, lpp_opt_t opt_type) {
57 return new_lpp_userdef(name, opt_type, INITIAL_SIZE, INITIAL_SIZE, 2.0);
60 lpp_t *new_lpp_userdef(const char *name, lpp_opt_t opt_type,
61 int estimated_vars, int estimated_csts, double grow_factor)
66 dbg = firm_dbg_register("lpp");
67 lpp = XMALLOCZ(lpp_t);
68 obstack_init(&lpp->obst);
70 lpp->name = obst_xstrdup(&lpp->obst, name);
71 lpp->opt_type = opt_type;
72 lpp->grow_factor = grow_factor;
73 lpp->cst2nr = new_set(cmp_name_t, estimated_csts);
74 lpp->var2nr = new_set(cmp_name_t, estimated_vars);
75 lpp->cst_size = estimated_csts;
76 lpp->var_size = estimated_vars;
77 lpp->csts = XMALLOCNZ(lpp_name_t *, estimated_csts);
78 lpp->vars = XMALLOCNZ(lpp_name_t *, estimated_vars);
79 lpp->m = new_matrix(estimated_csts, estimated_vars);
80 lpp->emphasis = lpp_balanced;
81 idx = lpp_add_cst(lpp, "obj", lpp_objective, 0);
83 idx = lpp_add_var(lpp, "rhs", lpp_rhs, 0);
89 void free_lpp_matrix(lpp_t *lpp) {
94 void free_lpp(lpp_t *lpp) {
95 obstack_free(&lpp->obst, NULL);
100 /* matrix might have been already deleted */
110 double lpp_get_fix_costs(lpp_t *lpp) {
111 return matrix_get(lpp->m, 0, 0);
114 void lpp_set_fix_costs(lpp_t *lpp, double value) {
115 matrix_set(lpp->m, 0, 0, value);
118 static inline int name2nr(set *where, const char *name) {
119 lpp_name_t find, *found;
121 found = set_find(where, &find, sizeof(find), HASH_NAME_T(&find));
122 return (found ? found->nr : -1);
125 #define cst_nr(lpp, name) name2nr(lpp->cst2nr, name)
126 #define var_nr(lpp, name) name2nr(lpp->var2nr, name)
128 static inline char *get_next_name(lpp_t *lpp) {
129 char *res = obstack_alloc(&lpp->obst, 12);
130 snprintf(res, 12, "_%d", lpp->next_name_number++);
134 int lpp_add_cst(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs) {
135 lpp_name_t n, *inner;
137 DBG((dbg, LEVEL_2, "%s %d %g\n", cst_name, cst_type, rhs));
139 if (cst_name && cst_name[0] == '_')
140 return ERR_NAME_NOT_ALLOWED;
143 n.name = obst_xstrdup(&lpp->obst, cst_name);
145 n.name = get_next_name(lpp);
148 inner = set_insert(lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n));
151 if (inner->nr == -1) {
152 inner->value_kind = lpp_none;
154 inner->nr = lpp->cst_next;
155 inner->type.cst_type = cst_type;
157 if (lpp->cst_next == lpp->cst_size) {
158 lpp->cst_size = (int)((double)lpp->cst_size * lpp->grow_factor) + 1;
159 lpp->csts = XREALLOC(lpp->csts, lpp_name_t *, lpp->cst_size);
162 lpp->csts[lpp->cst_next] = inner;
164 matrix_set(lpp->m, inner->nr, 0, rhs);
171 int lpp_add_cst_uniq(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs) {
177 assert(!set_find(lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n)) &&
178 "constraint already exists");
180 return lpp_add_cst(lpp, cst_name, cst_type, rhs);
183 int lpp_get_cst_idx(lpp_t *lpp, const char *cst_name) {
184 DBG((dbg, LEVEL_2, "%s --> %d\n", cst_name, cst_nr(lpp, cst_name)));
185 return cst_nr(lpp, cst_name);
188 void lpp_get_cst_name(lpp_t *lpp, int index, char *buf, size_t buf_size) {
189 DBG((dbg, LEVEL_2, "%d --> %s\n", index, lpp->csts[index]->name));
190 strncpy(buf, lpp->csts[index]->name, buf_size);
193 int lpp_add_var_default(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj, double startval) {
196 val = lpp_add_var(lpp, var_name, var_type, obj);
197 lpp_set_start_value(lpp, val, startval);
202 int lpp_add_var(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj) {
203 lpp_name_t n, *inner;
205 DBG((dbg, LEVEL_2, "%s %d %g\n", var_name, var_type, obj));
207 assert(var_type != lpp_invalid && "invalid is for internal use only");
209 if (var_name && var_name[0] == '_')
210 return ERR_NAME_NOT_ALLOWED;
213 n.name = obst_xstrdup(&lpp->obst, var_name);
215 n.name = get_next_name(lpp);
218 inner = set_insert(lpp->var2nr, &n, sizeof(n), HASH_NAME_T(&n));
221 if (inner->nr == -1) {
222 inner->nr = lpp->var_next;
223 inner->value_kind = 0;
225 inner->type.var_type = var_type;
227 if (lpp->var_next == lpp->var_size) {
228 lpp->var_size = (int)((double)lpp->var_size * lpp->grow_factor) + 1;
229 lpp->vars = XREALLOC(lpp->vars, lpp_name_t *, lpp->var_size);
232 lpp->vars[lpp->var_next] = inner;
234 matrix_set(lpp->m, 0, inner->nr, obj);
241 int lpp_get_var_idx(lpp_t *lpp, const char *var_name) {
242 DBG((dbg, LEVEL_2, "%s --> %d\n", var_name, var_nr(lpp, var_name)));
243 return var_nr(lpp, var_name);
246 void lpp_get_var_name(lpp_t *lpp, int index, char *buf, size_t buf_size) {
247 DBG((dbg, LEVEL_2, "%d --> %s\n", index, lpp->vars[index]->name));
248 strncpy(buf, lpp->vars[index]->name, buf_size);
251 int lpp_set_factor(lpp_t *lpp, const char *cst_name, const char *var_name, double value) {
254 cst = cst_nr(lpp, cst_name);
255 var = var_nr(lpp, var_name);
256 assert(cst != -1 && var != -1);
257 DBG((dbg, LEVEL_2, "%s[%d] %s[%d] %g\n", cst_name, cst, var_name, var, value));
258 matrix_set(lpp->m, cst, var, value);
263 int lpp_set_factor_fast(lpp_t *lpp, int cst_idx, int var_idx, double value) {
264 assert(cst_idx >= 0 && var_idx >= 0);
265 assert(cst_idx < lpp->cst_next && var_idx < lpp->var_next);
266 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));
267 matrix_set(lpp->m, cst_idx, var_idx, value);
272 int lpp_set_factor_fast_bulk(lpp_t *lpp, int cst_idx, int *var_idx, int num_vars, double value) {
273 assert(cst_idx >= 0 && cst_idx < lpp->cst_next);
274 assert(num_vars < lpp->var_next);
275 DBG((dbg, LEVEL_2, "row %s[%d] %d vars %g\n", lpp->csts[cst_idx]->name, cst_idx, num_vars, value));
276 matrix_set_row_bulk(lpp->m, cst_idx, var_idx, num_vars, value);
281 void lpp_set_start_value(lpp_t *lpp, int var_idx, double value) {
282 assert(var_idx > 0 && var_idx < lpp->var_next);
283 DBG((dbg, LEVEL_2, "%d %s %g\n", var_idx, lpp->vars[var_idx]->name, value));
284 lpp->vars[var_idx]->value = value;
285 lpp->vars[var_idx]->value_kind = lpp_value_start;
288 lpp_sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end) {
291 if (lpp->sol_state < lpp_feasible)
292 return lpp->sol_state;
294 /* here we are feasible or optimal */
295 for (i = 0; i < end - begin + 1; ++i)
296 values[i] = lpp->vars[begin + i]->value;
298 return lpp->sol_state;
301 void lpp_check_startvals(lpp_t *lpp) {
304 for (cst_idx = 1; cst_idx < lpp->cst_next; ++cst_idx) {
306 lpp_name_t *cst = lpp->csts[cst_idx];
307 double cst_val = matrix_get(lpp->m, cst_idx, 0);
310 for (var_idx = 1; var_idx < lpp->var_next; ++var_idx) {
311 if (lpp->vars[var_idx]->value_kind != lpp_value_start)
314 sum += lpp->vars[var_idx]->value *
315 matrix_get(lpp->m, cst_idx, var_idx);
317 switch(cst->type.cst_type) {
320 fprintf(stderr, "constraint %s unsatisfied: %g != %g\n", cst->name, sum, cst_val);
325 fprintf(stderr, "constraint %s unsatisfied: %g > %g\n", cst->name, sum, cst_val);
330 fprintf(stderr, "constraint %s unsatisfied: %g < %g\n", cst->name, sum, cst_val);
334 assert(0 && "unknown constraint type");
340 void lpp_dump(lpp_t *lpp, const char *filename) {
341 FILE *out = fopen(filename, "wt");
342 mps_write_mps(lpp, s_mps_fixed, out);
346 void lpp_set_log(lpp_t *lpp, FILE *log)
352 static const char *lpp_cst_op_to_str(lpp_cst_t cst)
366 void lpp_dump_plain(lpp_t *lpp, FILE *f)
370 for(i = 0; i < lpp->cst_next; ++i) {
371 const matrix_elem_t *elm;
372 lpp_name_t *cst = lpp->csts[i];
374 fprintf(f, "%16s: ", cst->name);
375 matrix_foreach_in_row(lpp->m, cst->nr, elm) {
376 lpp_name_t *var = lpp->vars[elm->col];
377 /* TODO Perhaps better a define LPP_COL_RHS */
379 fprintf(f, "%+4.1f*%-16s ", elm->val, var->name);
382 fprintf(f, "%3s %+4.1f\n",
383 lpp_cst_op_to_str(cst->type.cst_type), matrix_get(lpp->m, cst->nr, 0));
388 * Serialize a lpp to a file descriptor.
389 * @param comm The file descriptor.
390 * @param lpp The lpp.
392 void lpp_serialize(lpp_comm_t *comm, const lpp_t *lpp, int with_names)
396 lpp_writel(comm, with_names);
397 lpp_writel(comm, lpp->cst_next);
398 lpp_writel(comm, lpp->var_next);
399 lpp_writel(comm, lpp->opt_type);
400 lpp_writes(comm, lpp->name);
403 lpp_writel(comm, lpp->set_bound);
404 lpp_writed(comm, lpp->bound);
405 lpp_writed(comm, lpp->time_limit_secs);
406 lpp_writed(comm, lpp->emphasis);
408 for(i = 0; i < lpp->cst_next; ++i) {
409 lpp_name_t *name = lpp->csts[i];
410 lpp_writel(comm, name->nr);
411 lpp_writel(comm, name->value_kind);
412 lpp_writel(comm, name->type.cst_type);
415 lpp_writes(comm, name->name);
418 for(i = 0; i < lpp->var_next; ++i) {
419 lpp_name_t *name = lpp->vars[i];
420 lpp_writel(comm, name->nr);
421 lpp_writel(comm, name->value_kind);
422 lpp_writel(comm, name->type.var_type);
425 lpp_writes(comm, name->name);
429 const matrix_elem_t *elm;
432 matrix_foreach(lpp->m, elm)
435 assert(n == matrix_get_entries(lpp->m));
437 matrix_foreach(lpp->m, elm) {
438 lpp_writel(comm, elm->row);
439 lpp_writel(comm, elm->col);
440 lpp_writed(comm, elm->val);
448 * Deserialize an lpp from a file descriptor.
449 * @param comm The file descriptor.
450 * @return The Problem.
452 lpp_t *lpp_deserialize(lpp_comm_t *comm)
457 lpp_t *lpp = XMALLOCZ(lpp_t);
459 /* read general settings */
460 with_names = lpp_readl(comm);
461 lpp->cst_next = lpp_readl(comm);
462 lpp->var_next = lpp_readl(comm);
463 lpp->opt_type = lpp_readl(comm);
464 lpp->name = lpp_reads(comm);
467 lpp->set_bound = lpp_readl(comm);
468 lpp->bound = lpp_readd(comm);
469 lpp->time_limit_secs = lpp_readd(comm);
470 lpp->emphasis = lpp_readd(comm);
472 lpp->cst_size = lpp->cst_next;
473 lpp->var_size = lpp->var_next;
475 lpp->cst2nr = new_set(cmp_name_t, lpp->cst_next);
476 lpp->var2nr = new_set(cmp_name_t, lpp->var_next);
478 lpp->csts = XMALLOCNZ(lpp_name_t*, lpp->cst_next);
479 lpp->vars = XMALLOCNZ(lpp_name_t*, lpp->var_next);
480 lpp->m = new_matrix(lpp->cst_next, lpp->var_next);
482 for(i = 0; i < lpp->cst_next; ++i) {
483 lpp_name_t name, *res;
485 name.nr = lpp_readl(comm);
486 name.value_kind = lpp_readl(comm);
487 name.type.cst_type = lpp_readl(comm);
490 name.name = lpp_reads(comm);
492 char* buf = XMALLOCN(char, NAMELEN);
493 snprintf(buf, NAMELEN, "c%d\n", name.nr);
497 res = set_insert(lpp->cst2nr, &name, sizeof(name), HASH_NAME_T(&name));
498 lpp->csts[name.nr] = res;
501 for(i = 0; i < lpp->var_next; ++i) {
502 lpp_name_t name, *res;
504 name.nr = lpp_readl(comm);
505 name.value_kind = lpp_readl(comm);
506 name.type.var_type = lpp_readl(comm);
509 name.name = lpp_reads(comm);
511 char* buf = XMALLOCN(char, NAMELEN);
512 snprintf(buf, NAMELEN, "v%d\n", name.nr);
516 res = set_insert(lpp->var2nr, &name, sizeof(name), HASH_NAME_T(&name));
517 lpp->vars[name.nr] = res;
521 for(i = 0; i < n; ++i) {
523 elm.row = lpp_readl(comm);
524 elm.col = lpp_readl(comm);
525 elm.val = lpp_readd(comm);
526 matrix_set(lpp->m, elm.row, elm.col, elm.val);
532 void lpp_serialize_values(lpp_comm_t *comm, const lpp_t *lpp, lpp_value_kind_t value_kind)
536 for(i = 0, n = 0; i < lpp->var_next; ++i)
537 n += lpp->vars[i]->value_kind == value_kind;
539 /* Write the number of values to expect */
542 /* send the values */
543 for(i = 0, n = lpp->var_next; i < n; ++i) {
544 const lpp_name_t *name = lpp->vars[i];
545 if(name->value_kind == value_kind) {
546 lpp_writel(comm, name->nr);
547 lpp_writed(comm, name->value);
552 void lpp_deserialize_values(lpp_comm_t *comm, lpp_t *lpp, lpp_value_kind_t value_kind)
556 /* Get the number of values to read */
559 for(i = 0; i < n; ++i) {
560 int nr = lpp_readl(comm);
561 lpp_name_t *name = lpp->vars[nr];
563 name->value_kind = value_kind;
564 name->value = lpp_readd(comm);
568 void lpp_serialize_stats(lpp_comm_t *comm, const lpp_t *lpp)
570 lpp_writel(comm, lpp->sol_state);
571 lpp_writel(comm, lpp->iterations);
572 lpp_writed(comm, lpp->sol_time);
573 lpp_writed(comm, lpp->objval);
574 lpp_writed(comm, lpp->best_bound);
577 void lpp_deserialize_stats(lpp_comm_t *comm, lpp_t *lpp)
579 lpp->sol_state = lpp_readl(comm);
580 lpp->iterations = lpp_readl(comm);
581 lpp->sol_time = lpp_readd(comm);
582 lpp->objval = lpp_readd(comm);
583 lpp->best_bound = lpp_readd(comm);