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