nsz Git - libfirm/blob - ir/lpp/lpp.c

   1 /**
   2  * Author:      Daniel Grund
   3  * Date:        Fri 13.05.2005
   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 $
   7  */
   8
   9 #include "config.h"
  10
  11 #include <stdlib.h>
  12 #include <stdio.h>
  13 #include <string.h>
  14
  15 #include "assert.h"
  16 #include "obst.h"
  17 #include "hashptr.h"
  18 #include "debug.h"
  19 #include "set.h"
  20
  21 #include "sp_matrix.h"
  22 #include "mps.h"
  23 #include "lpp_t.h"
  24 #include "lpp_comm.h"
  25 #include "lpp_solvers.h"
  26 #include "lpp_net.h"
  27
  28 #define HASH_NAME_T(n) HASH_STR((n)->name, strlen((n)->name))
  29
  30 static firm_dbg_module_t *dbg = NULL;
  31
  32 static inline char *obst_xstrdup(struct obstack *obst, const char *str)
  33 {
  34         return obstack_copy0(obst, str, strlen(str));
  35 }
  36
  37 static int cmp_name_t(const void *x, const void *y, size_t size)
  38 {
  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);
  43 }
  44
  45 /**
  46  * Update statistic information about matrix usage.
  47  */
  48 static void update_stats(lpp_t *lpp)
  49 {
  50         lpp->n_elems    = matrix_get_entries(lpp->m);
  51         lpp->matrix_mem = lpp->n_elems * matrix_get_elem_size();
  52         lpp->density    = (double)lpp->n_elems / (double)(lpp->cst_next * lpp->var_next) * 100.0;
  53 }
  54
  55 #define INITIAL_SIZE 64
  56
  57 lpp_t *new_lpp(const char *name, lpp_opt_t opt_type)
  58 {
  59         return new_lpp_userdef(name, opt_type, INITIAL_SIZE, INITIAL_SIZE, 2.0);
  60 }
  61
  62 lpp_t *new_lpp_userdef(const char *name, lpp_opt_t opt_type,
  63                            int estimated_vars, int estimated_csts, double grow_factor)
  64 {
  65         lpp_t *lpp;
  66         int   idx;
  67
  68         dbg = firm_dbg_register("lpp");
  69         lpp = XMALLOCZ(lpp_t);
  70         obstack_init(&lpp->obst);
  71
  72         lpp->name        = obst_xstrdup(&lpp->obst, name);
  73         lpp->opt_type    = opt_type;
  74         lpp->grow_factor = grow_factor;
  75         lpp->cst2nr      = new_set(cmp_name_t, estimated_csts);
  76         lpp->var2nr      = new_set(cmp_name_t, estimated_vars);
  77         lpp->cst_size    = estimated_csts;
  78         lpp->var_size    = estimated_vars;
  79         lpp->csts        = XMALLOCNZ(lpp_name_t *, estimated_csts);
  80         lpp->vars        = XMALLOCNZ(lpp_name_t *, estimated_vars);
  81         lpp->m           = new_matrix(estimated_csts, estimated_vars);
  82         lpp->emphasis    = lpp_balanced;
  83         idx              = lpp_add_cst(lpp, "obj", lpp_objective, 0);
  84         assert(idx == 0);
  85         idx              = lpp_add_var(lpp, "rhs", lpp_rhs, 0);
  86         assert(idx == 0);
  87
  88         return lpp;
  89 }
  90
  91 void free_lpp_matrix(lpp_t *lpp)
  92 {
  93         del_matrix(lpp->m);
  94         lpp->m = NULL;
  95 }
  96
  97 void free_lpp(lpp_t *lpp)
  98 {
  99         obstack_free(&lpp->obst, NULL);
 100
 101         del_set(lpp->cst2nr);
 102         del_set(lpp->var2nr);
 103
 104         /* matrix might have been already deleted */
 105         if (lpp->m)
 106                 del_matrix(lpp->m);
 107
 108         free(lpp->csts);
 109         free(lpp->vars);
 110
 111         free(lpp);
 112 }
 113
 114 double lpp_get_fix_costs(lpp_t *lpp)
 115 {
 116         return matrix_get(lpp->m, 0, 0);
 117 }
 118
 119 void lpp_set_fix_costs(lpp_t *lpp, double value)
 120 {
 121         matrix_set(lpp->m, 0, 0, value);
 122 }
 123
 124 static inline int name2nr(set *where, const char *name)
 125 {
 126         lpp_name_t find, *found;
 127         find.name = name;
 128         found = set_find(where, &find, sizeof(find), HASH_NAME_T(&find));
 129         return (found ? found->nr : -1);
 130 }
 131
 132 #define cst_nr(lpp, name) name2nr(lpp->cst2nr, name)
 133 #define var_nr(lpp, name) name2nr(lpp->var2nr, name)
 134
 135 static inline char *get_next_name(lpp_t *lpp)
 136 {
 137         char *res = obstack_alloc(&lpp->obst, 12);
 138         snprintf(res, 12, "_%u", lpp->next_name_number++);
 139         return res;
 140 }
 141
 142 int lpp_add_cst(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs)
 143 {
 144         lpp_name_t n, *inner;
 145
 146         DBG((dbg, LEVEL_2, "%s %d %g\n", cst_name, cst_type, rhs));
 147
 148         if (cst_name && cst_name[0] == '_')
 149                 return ERR_NAME_NOT_ALLOWED;
 150
 151         if (cst_name)
 152                 n.name = obst_xstrdup(&lpp->obst, cst_name);
 153         else
 154                 n.name = get_next_name(lpp);
 155
 156         n.nr  = -1;
 157         inner = set_insert(lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n));
 158         assert(inner);
 159
 160         if (inner->nr == -1) {
 161                 inner->value_kind    = lpp_none;
 162                 inner->value         = 0.0;
 163                 inner->nr            = lpp->cst_next;
 164                 inner->type.cst_type = cst_type;
 165
 166                 if (lpp->cst_next == lpp->cst_size) {
 167                         lpp->cst_size = (int)((double)lpp->cst_size * lpp->grow_factor) + 1;
 168                         lpp->csts     = XREALLOC(lpp->csts, lpp_name_t *, lpp->cst_size);
 169                 }
 170
 171                 lpp->csts[lpp->cst_next] = inner;
 172                 lpp->cst_next++;
 173                 matrix_set(lpp->m, inner->nr, 0, rhs);
 174         }
 175
 176         update_stats(lpp);
 177         return inner->nr;
 178 }
 179
 180 int lpp_add_cst_uniq(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs)
 181 {
 182         if (cst_name) {
 183                 lpp_name_t n;
 184
 185                 n.name = cst_name;
 186                 n.nr   = -1;
 187                 assert(!set_find(lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n)) &&
 188                     "constraint already exists");
 189         }
 190         return lpp_add_cst(lpp, cst_name, cst_type, rhs);
 191 }
 192
 193 int lpp_get_cst_idx(lpp_t *lpp, const char *cst_name)
 194 {
 195         DBG((dbg, LEVEL_2, "%s --> %d\n", cst_name, cst_nr(lpp, cst_name)));
 196         return cst_nr(lpp, cst_name);
 197 }
 198
 199 void lpp_get_cst_name(lpp_t *lpp, int index, char *buf, size_t buf_size)
 200 {
 201         DBG((dbg, LEVEL_2, "%d --> %s\n", index, lpp->csts[index]->name));
 202         strncpy(buf, lpp->csts[index]->name, buf_size);
 203 }
 204
 205 int lpp_add_var_default(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj, double startval)
 206 {
 207         int val;
 208
 209         val = lpp_add_var(lpp, var_name, var_type, obj);
 210         lpp_set_start_value(lpp, val, startval);
 211
 212         return val;
 213 }
 214
 215 int lpp_add_var(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj)
 216 {
 217         lpp_name_t n, *inner;
 218
 219         DBG((dbg, LEVEL_2, "%s %d %g\n", var_name, var_type, obj));
 220
 221         assert(var_type != lpp_invalid && "invalid is for internal use only");
 222
 223         if (var_name && var_name[0] == '_')
 224                 return ERR_NAME_NOT_ALLOWED;
 225
 226         if (var_name)
 227                 n.name = obst_xstrdup(&lpp->obst, var_name);
 228         else
 229                 n.name = get_next_name(lpp);
 230
 231         n.nr  = -1;
 232         inner = set_insert(lpp->var2nr, &n, sizeof(n), HASH_NAME_T(&n));
 233         assert(inner);
 234
 235         if (inner->nr == -1) {
 236                 inner->nr            = lpp->var_next;
 237                 inner->value_kind    = 0;
 238                 inner->value         = 0;
 239                 inner->type.var_type = var_type;
 240
 241                 if (lpp->var_next == lpp->var_size) {
 242                         lpp->var_size = (int)((double)lpp->var_size * lpp->grow_factor) + 1;
 243                         lpp->vars     = XREALLOC(lpp->vars, lpp_name_t *, lpp->var_size);
 244                 }
 245
 246                 lpp->vars[lpp->var_next] = inner;
 247                 lpp->var_next++;
 248                 matrix_set(lpp->m, 0, inner->nr, obj);
 249         }
 250
 251         update_stats(lpp);
 252         return inner->nr;
 253 }
 254
 255 int lpp_get_var_idx(lpp_t *lpp, const char *var_name)
 256 {
 257         DBG((dbg, LEVEL_2, "%s --> %d\n", var_name, var_nr(lpp, var_name)));
 258         return var_nr(lpp, var_name);
 259 }
 260
 261 void lpp_get_var_name(lpp_t *lpp, int index, char *buf, size_t buf_size)
 262 {
 263         DBG((dbg, LEVEL_2, "%d --> %s\n", index, lpp->vars[index]->name));
 264         strncpy(buf, lpp->vars[index]->name, buf_size);
 265 }
 266
 267 int lpp_set_factor(lpp_t *lpp, const char *cst_name, const char *var_name, double value)
 268 {
 269         int cst, var;
 270
 271         cst = cst_nr(lpp, cst_name);
 272         var = var_nr(lpp, var_name);
 273         assert(cst != -1 && var != -1);
 274         DBG((dbg, LEVEL_2, "%s[%d] %s[%d] %g\n", cst_name, cst, var_name, var, value));
 275         matrix_set(lpp->m, cst, var, value);
 276         update_stats(lpp);
 277         return 0;
 278 }
 279
 280 int lpp_set_factor_fast(lpp_t *lpp, int cst_idx, int var_idx, double value)
 281 {
 282         assert(cst_idx >= 0 && var_idx >= 0);
 283         assert(cst_idx < lpp->cst_next && var_idx < lpp->var_next);
 284         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));
 285         matrix_set(lpp->m, cst_idx, var_idx, value);
 286         update_stats(lpp);
 287         return 0;
 288 }
 289
 290 int lpp_set_factor_fast_bulk(lpp_t *lpp, int cst_idx, int *var_idx, int num_vars, double value)
 291 {
 292         assert(cst_idx >= 0 && cst_idx < lpp->cst_next);
 293         assert(num_vars < lpp->var_next);
 294         DBG((dbg, LEVEL_2, "row %s[%d] %d vars %g\n", lpp->csts[cst_idx]->name, cst_idx, num_vars, value));
 295         matrix_set_row_bulk(lpp->m, cst_idx, var_idx, num_vars, value);
 296         update_stats(lpp);
 297         return 0;
 298 }
 299
 300 void lpp_set_start_value(lpp_t *lpp, int var_idx, double value)
 301 {
 302         assert(var_idx > 0 && var_idx < lpp->var_next);
 303         DBG((dbg, LEVEL_2, "%d %s %g\n", var_idx, lpp->vars[var_idx]->name, value));
 304         lpp->vars[var_idx]->value = value;
 305         lpp->vars[var_idx]->value_kind = lpp_value_start;
 306 }
 307
 308 lpp_sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end)
 309 {
 310         int i;
 311
 312         if (lpp->sol_state < lpp_feasible)
 313                 return lpp->sol_state;
 314
 315         /* here we are feasible or optimal */
 316         for (i = 0; i < end - begin + 1; ++i)
 317                 values[i] = lpp->vars[begin + i]->value;
 318
 319         return lpp->sol_state;
 320 }
 321
 322 void lpp_check_startvals(lpp_t *lpp)
 323 {
 324         int cst_idx;
 325
 326         for (cst_idx = 1; cst_idx < lpp->cst_next; ++cst_idx) {
 327                 double     sum     = 0.0;
 328                 lpp_name_t *cst    = lpp->csts[cst_idx];
 329                 double     cst_val = matrix_get(lpp->m, cst_idx, 0);
 330                 int        var_idx;
 331
 332                 for (var_idx = 1; var_idx < lpp->var_next; ++var_idx) {
 333                                 if (lpp->vars[var_idx]->value_kind != lpp_value_start)
 334                                         goto next;
 335
 336                                 sum += lpp->vars[var_idx]->value *
 337                                         matrix_get(lpp->m, cst_idx, var_idx);
 338                 }
 339                 switch(cst->type.cst_type) {
 340                         case lpp_equal:
 341                                 if(sum != cst_val) {
 342                                         fprintf(stderr, "constraint %s unsatisfied: %g != %g\n", cst->name, sum, cst_val);
 343                                 }
 344                                 break;
 345                         case lpp_less:
 346                                 if(sum > cst_val) {
 347                                         fprintf(stderr, "constraint %s unsatisfied: %g > %g\n", cst->name, sum, cst_val);
 348                                 }
 349                                 break;
 350                         case lpp_greater:
 351                                 if(sum < cst_val) {
 352                                         fprintf(stderr, "constraint %s unsatisfied: %g < %g\n", cst->name, sum, cst_val);
 353                                 }
 354                                 break;
 355                         default:
 356                                 assert(0 && "unknown constraint type");
 357                 }
 358 next: ;
 359         }
 360 }
 361
 362 void lpp_dump(lpp_t *lpp, const char *filename)
 363 {
 364         FILE *out = fopen(filename, "wt");
 365         mps_write_mps(lpp, s_mps_fixed, out);
 366         fclose(out);
 367 }
 368
 369 void lpp_set_log(lpp_t *lpp, FILE *log)
 370 {
 371         lpp->log = log;
 372 }
 373
 374
 375 static const char *lpp_cst_op_to_str(lpp_cst_t cst)
 376 {
 377         switch(cst) {
 378         case lpp_equal:
 379                 return "=";
 380         case lpp_less:
 381                 return "<=";
 382         case lpp_greater:
 383                 return ">=";
 384         default:
 385                 return "";
 386         }
 387 }
 388
 389 void lpp_dump_plain(lpp_t *lpp, FILE *f)
 390 {
 391         int i;
 392
 393         for(i = 0; i < lpp->cst_next; ++i) {
 394                 const matrix_elem_t *elm;
 395                 lpp_name_t *cst = lpp->csts[i];
 396
 397                 fprintf(f, "%16s: ", cst->name);
 398                 matrix_foreach_in_row(lpp->m, cst->nr, elm) {
 399                         lpp_name_t *var = lpp->vars[elm->col];
 400                         /* TODO Perhaps better a define LPP_COL_RHS */
 401                         if(elm->col > 0)
 402                                 fprintf(f, "%+4.1f*%-16s ", elm->val, var->name);
 403                 }
 404
 405                 fprintf(f, "%3s %+4.1f\n",
 406                                 lpp_cst_op_to_str(cst->type.cst_type), matrix_get(lpp->m, cst->nr, 0));
 407         }
 408 }
 409
 410 /**
 411  * Serialize a lpp to a file descriptor.
 412  * @param comm The file descriptor.
 413  * @param lpp The lpp.
 414  */
 415 void lpp_serialize(lpp_comm_t *comm, const lpp_t *lpp, int with_names)
 416 {
 417         int n, i;
 418
 419         lpp_writel(comm, with_names);
 420         lpp_writel(comm, lpp->cst_next);
 421         lpp_writel(comm, lpp->var_next);
 422         lpp_writel(comm, lpp->opt_type);
 423         lpp_writes(comm, lpp->name);
 424
 425         /* write options */
 426         lpp_writel(comm, lpp->set_bound);
 427         lpp_writed(comm, lpp->bound);
 428         lpp_writed(comm, lpp->time_limit_secs);
 429         lpp_writed(comm, lpp->emphasis);
 430
 431         for(i = 0; i < lpp->cst_next; ++i) {
 432                 lpp_name_t *name = lpp->csts[i];
 433                 lpp_writel(comm, name->nr);
 434                 lpp_writel(comm, name->value_kind);
 435                 lpp_writel(comm, name->type.cst_type);
 436
 437                 if(with_names)
 438                         lpp_writes(comm, name->name);
 439         }
 440
 441         for(i = 0; i < lpp->var_next; ++i) {
 442                 lpp_name_t *name = lpp->vars[i];
 443                 lpp_writel(comm, name->nr);
 444                 lpp_writel(comm, name->value_kind);
 445                 lpp_writel(comm, name->type.var_type);
 446
 447                 if(with_names)
 448                         lpp_writes(comm, name->name);
 449         }
 450
 451         {
 452                 const matrix_elem_t *elm;
 453                 n = 0;
 454
 455                 matrix_foreach(lpp->m, elm)
 456                         n++;
 457
 458                 assert(n == matrix_get_entries(lpp->m));
 459                 lpp_writel(comm, n);
 460                 matrix_foreach(lpp->m, elm) {
 461                         lpp_writel(comm, elm->row);
 462                         lpp_writel(comm, elm->col);
 463                         lpp_writed(comm, elm->val);
 464                 }
 465         }
 466 }
 467
 468 #define NAMELEN 64
 469
 470 /**
 471  * Deserialize an lpp from a file descriptor.
 472  * @param comm The file descriptor.
 473  * @return The Problem.
 474  */
 475 lpp_t *lpp_deserialize(lpp_comm_t *comm)
 476 {
 477         int i, n;
 478         int with_names;
 479
 480         lpp_t *lpp = XMALLOCZ(lpp_t);
 481
 482         /* read general settings */
 483         with_names    = lpp_readl(comm);
 484         lpp->cst_next = lpp_readl(comm);
 485         lpp->var_next = lpp_readl(comm);
 486         lpp->opt_type = lpp_readl(comm);
 487         lpp->name     = lpp_reads(comm);
 488
 489         /* read options */
 490         lpp->set_bound       = lpp_readl(comm);
 491         lpp->bound           = lpp_readd(comm);
 492         lpp->time_limit_secs = lpp_readd(comm);
 493         lpp->emphasis        = lpp_readd(comm);
 494
 495         lpp->cst_size = lpp->cst_next;
 496         lpp->var_size = lpp->var_next;
 497
 498         lpp->cst2nr   = new_set(cmp_name_t, lpp->cst_next);
 499         lpp->var2nr   = new_set(cmp_name_t, lpp->var_next);
 500
 501         lpp->csts     = XMALLOCNZ(lpp_name_t*, lpp->cst_next);
 502         lpp->vars     = XMALLOCNZ(lpp_name_t*, lpp->var_next);
 503         lpp->m        = new_matrix(lpp->cst_next, lpp->var_next);
 504
 505         for(i = 0; i < lpp->cst_next; ++i) {
 506                 lpp_name_t name, *res;
 507
 508                 name.nr            = lpp_readl(comm);
 509                 name.value_kind    = lpp_readl(comm);
 510                 name.type.cst_type = lpp_readl(comm);
 511
 512                 if(with_names) {
 513                         name.name = lpp_reads(comm);
 514                 } else {
 515                         char* buf = XMALLOCN(char, NAMELEN);
 516                         snprintf(buf, NAMELEN, "c%d\n", name.nr);
 517                         name.name = buf;
 518                 }
 519
 520                 res = set_insert(lpp->cst2nr, &name, sizeof(name), HASH_NAME_T(&name));
 521                 lpp->csts[name.nr] = res;
 522         }
 523
 524         for(i = 0; i < lpp->var_next; ++i) {
 525                 lpp_name_t name, *res;
 526
 527                 name.nr            = lpp_readl(comm);
 528                 name.value_kind    = lpp_readl(comm);
 529                 name.type.var_type = lpp_readl(comm);
 530
 531                 if(with_names) {
 532                         name.name = lpp_reads(comm);
 533                 } else {
 534                         char* buf = XMALLOCN(char, NAMELEN);
 535                         snprintf(buf, NAMELEN, "v%d\n", name.nr);
 536                         name.name = buf;
 537                 }
 538
 539                 res = set_insert(lpp->var2nr, &name, sizeof(name), HASH_NAME_T(&name));
 540                 lpp->vars[name.nr] = res;
 541         }
 542
 543         n = lpp_readl(comm);
 544         for(i = 0; i < n; ++i) {
 545                 matrix_elem_t elm;
 546                 elm.row = lpp_readl(comm);
 547                 elm.col = lpp_readl(comm);
 548                 elm.val = lpp_readd(comm);
 549                 matrix_set(lpp->m, elm.row, elm.col, elm.val);
 550         }
 551
 552         return lpp;
 553 }
 554
 555 void lpp_serialize_values(lpp_comm_t *comm, const lpp_t *lpp, lpp_value_kind_t value_kind)
 556 {
 557         int i, n;
 558
 559         for(i = 0, n = 0; i < lpp->var_next; ++i)
 560                 n += lpp->vars[i]->value_kind == value_kind;
 561
 562         /* Write the number of values to expect */
 563         lpp_writel(comm, n);
 564
 565         /* send the values */
 566         for(i = 0, n = lpp->var_next; i < n; ++i) {
 567                 const lpp_name_t *name = lpp->vars[i];
 568                 if(name->value_kind == value_kind) {
 569                         lpp_writel(comm, name->nr);
 570                         lpp_writed(comm, name->value);
 571                 }
 572         }
 573 }
 574
 575 void lpp_deserialize_values(lpp_comm_t *comm, lpp_t *lpp, lpp_value_kind_t value_kind)
 576 {
 577         int i, n;
 578
 579         /* Get the number of values to read */
 580         n = lpp_readl(comm);
 581
 582         for(i = 0; i < n; ++i) {
 583                 int nr = lpp_readl(comm);
 584                 lpp_name_t *name = lpp->vars[nr];
 585
 586                 name->value_kind = value_kind;
 587                 name->value = lpp_readd(comm);
 588         }
 589 }
 590
 591 void lpp_serialize_stats(lpp_comm_t *comm, const lpp_t *lpp)
 592 {
 593         lpp_writel(comm, lpp->sol_state);
 594         lpp_writel(comm, lpp->iterations);
 595         lpp_writed(comm, lpp->sol_time);
 596         lpp_writed(comm, lpp->objval);
 597         lpp_writed(comm, lpp->best_bound);
 598 }
 599
 600 void lpp_deserialize_stats(lpp_comm_t *comm, lpp_t *lpp)
 601 {
 602         lpp->sol_state  = lpp_readl(comm);
 603         lpp->iterations = lpp_readl(comm);
 604         lpp->sol_time   = lpp_readd(comm);
 605         lpp->objval     = lpp_readd(comm);
 606         lpp->best_bound = lpp_readd(comm);
 607 }
 608
 609 void lpp_solve(lpp_t *lpp, const char* host, const char* solver)
 610 {
 611         if (host == NULL || strlen(host) == 0) {
 612                 lpp_solver_func_t* f = lpp_find_solver(solver);
 613                 if (f != NULL)
 614                         f(lpp);
 615         } else {
 616                 lpp_solve_net(lpp, host, solver);
 617         }
 618 }
 619