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
  30 #define HASH_NAME_T(n) HASH_STR((n)->name, strlen((n)->name))
  31
  32 static firm_dbg_module_t *dbg = NULL;
  33
  34 static inline char *obst_xstrdup(struct obstack *obst, const char *str) {
  35         return obstack_copy0(obst, str, strlen(str));
  36 }
  37
  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);
  43 }
  44
  45 /**
  46  * Update statistic information about matrix usage.
  47  */
  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;
  52 }
  53
  54 #define INITIAL_SIZE 64
  55
  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);
  58 }
  59
  60 lpp_t *new_lpp_userdef(const char *name, lpp_opt_t opt_type,
  61                            int estimated_vars, int estimated_csts, double grow_factor)
  62 {
  63         lpp_t *lpp;
  64         int   idx;
  65
  66         dbg = firm_dbg_register("lpp");
  67         lpp = XMALLOCZ(lpp_t);
  68         obstack_init(&lpp->obst);
  69
  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);
  82         assert(idx == 0);
  83         idx              = lpp_add_var(lpp, "rhs", lpp_rhs, 0);
  84         assert(idx == 0);
  85
  86         return lpp;
  87 }
  88
  89 void free_lpp_matrix(lpp_t *lpp) {
  90         del_matrix(lpp->m);
  91         lpp->m = NULL;
  92 }
  93
  94 void free_lpp(lpp_t *lpp) {
  95         obstack_free(&lpp->obst, NULL);
  96
  97         del_set(lpp->cst2nr);
  98         del_set(lpp->var2nr);
  99
 100         /* matrix might have been already deleted */
 101         if (lpp->m)
 102                 del_matrix(lpp->m);
 103
 104         free(lpp->csts);
 105         free(lpp->vars);
 106
 107         free(lpp);
 108 }
 109
 110 double lpp_get_fix_costs(lpp_t *lpp) {
 111         return matrix_get(lpp->m, 0, 0);
 112 }
 113
 114 void lpp_set_fix_costs(lpp_t *lpp, double value) {
 115         matrix_set(lpp->m, 0, 0, value);
 116 }
 117
 118 static inline int name2nr(set *where, const char *name) {
 119         lpp_name_t find, *found;
 120         find.name = name;
 121         found = set_find(where, &find, sizeof(find), HASH_NAME_T(&find));
 122         return (found ? found->nr : -1);
 123 }
 124
 125 #define cst_nr(lpp, name) name2nr(lpp->cst2nr, name)
 126 #define var_nr(lpp, name) name2nr(lpp->var2nr, name)
 127
 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++);
 131         return res;
 132 }
 133
 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;
 136
 137         DBG((dbg, LEVEL_2, "%s %d %g\n", cst_name, cst_type, rhs));
 138
 139         if (cst_name && cst_name[0] == '_')
 140                 return ERR_NAME_NOT_ALLOWED;
 141
 142         if (cst_name)
 143                 n.name = obst_xstrdup(&lpp->obst, cst_name);
 144         else
 145                 n.name = get_next_name(lpp);
 146
 147         n.nr  = -1;
 148         inner = set_insert(lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n));
 149         assert(inner);
 150
 151         if (inner->nr == -1) {
 152                 inner->value_kind    = lpp_none;
 153                 inner->value         = 0.0;
 154                 inner->nr            = lpp->cst_next;
 155                 inner->type.cst_type = cst_type;
 156
 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);
 160                 }
 161
 162                 lpp->csts[lpp->cst_next] = inner;
 163                 lpp->cst_next++;
 164                 matrix_set(lpp->m, inner->nr, 0, rhs);
 165         }
 166
 167         update_stats(lpp);
 168         return inner->nr;
 169 }
 170
 171 int lpp_add_cst_uniq(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs) {
 172         if (cst_name) {
 173                 lpp_name_t n;
 174
 175                 n.name = cst_name;
 176                 n.nr   = -1;
 177                 assert(!set_find(lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n)) &&
 178                     "constraint already exists");
 179         }
 180         return lpp_add_cst(lpp, cst_name, cst_type, rhs);
 181 }
 182
 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);
 186 }
 187
 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);
 191 }
 192
 193 int lpp_add_var_default(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj, double startval) {
 194         int val;
 195
 196         val = lpp_add_var(lpp, var_name, var_type, obj);
 197         lpp_set_start_value(lpp, val, startval);
 198
 199         return val;
 200 }
 201
 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;
 204
 205         DBG((dbg, LEVEL_2, "%s %d %g\n", var_name, var_type, obj));
 206
 207         assert(var_type != lpp_invalid && "invalid is for internal use only");
 208
 209         if (var_name && var_name[0] == '_')
 210                 return ERR_NAME_NOT_ALLOWED;
 211
 212         if (var_name)
 213                 n.name = obst_xstrdup(&lpp->obst, var_name);
 214         else
 215                 n.name = get_next_name(lpp);
 216
 217         n.nr  = -1;
 218         inner = set_insert(lpp->var2nr, &n, sizeof(n), HASH_NAME_T(&n));
 219         assert(inner);
 220
 221         if (inner->nr == -1) {
 222                 inner->nr            = lpp->var_next;
 223                 inner->value_kind    = 0;
 224                 inner->value         = 0;
 225                 inner->type.var_type = var_type;
 226
 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);
 230                 }
 231
 232                 lpp->vars[lpp->var_next] = inner;
 233                 lpp->var_next++;
 234                 matrix_set(lpp->m, 0, inner->nr, obj);
 235         }
 236
 237         update_stats(lpp);
 238         return inner->nr;
 239 }
 240
 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);
 244 }
 245
 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);
 249 }
 250
 251 int lpp_set_factor(lpp_t *lpp, const char *cst_name, const char *var_name, double value) {
 252         int cst, var;
 253
 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);
 259         update_stats(lpp);
 260         return 0;
 261 }
 262
 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);
 268         update_stats(lpp);
 269         return 0;
 270 }
 271
 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);
 277         update_stats(lpp);
 278         return 0;
 279 }
 280
 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;
 286 }
 287
 288 lpp_sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end) {
 289         int i;
 290
 291         if (lpp->sol_state < lpp_feasible)
 292                 return lpp->sol_state;
 293
 294         /* here we are feasible or optimal */
 295         for (i = 0; i < end - begin + 1; ++i)
 296                 values[i] = lpp->vars[begin + i]->value;
 297
 298         return lpp->sol_state;
 299 }
 300
 301 void lpp_check_startvals(lpp_t *lpp) {
 302         int cst_idx;
 303
 304         for (cst_idx = 1; cst_idx < lpp->cst_next; ++cst_idx) {
 305                 double     sum     = 0.0;
 306                 lpp_name_t *cst    = lpp->csts[cst_idx];
 307                 double     cst_val = matrix_get(lpp->m, cst_idx, 0);
 308                 int        var_idx;
 309
 310                 for (var_idx = 1; var_idx < lpp->var_next; ++var_idx) {
 311                                 if (lpp->vars[var_idx]->value_kind != lpp_value_start)
 312                                         goto next;
 313
 314                                 sum += lpp->vars[var_idx]->value *
 315                                         matrix_get(lpp->m, cst_idx, var_idx);
 316                 }
 317                 switch(cst->type.cst_type) {
 318                         case lpp_equal:
 319                                 if(sum != cst_val) {
 320                                         fprintf(stderr, "constraint %s unsatisfied: %g != %g\n", cst->name, sum, cst_val);
 321                                 }
 322                                 break;
 323                         case lpp_less:
 324                                 if(sum > cst_val) {
 325                                         fprintf(stderr, "constraint %s unsatisfied: %g > %g\n", cst->name, sum, cst_val);
 326                                 }
 327                                 break;
 328                         case lpp_greater:
 329                                 if(sum < cst_val) {
 330                                         fprintf(stderr, "constraint %s unsatisfied: %g < %g\n", cst->name, sum, cst_val);
 331                                 }
 332                                 break;
 333                         default:
 334                                 assert(0 && "unknown constraint type");
 335                 }
 336 next: ;
 337         }
 338 }
 339
 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);
 343         fclose(out);
 344 }
 345
 346 void lpp_set_log(lpp_t *lpp, FILE *log)
 347 {
 348         lpp->log = log;
 349 }
 350
 351
 352 static const char *lpp_cst_op_to_str(lpp_cst_t cst)
 353 {
 354   switch(cst) {
 355     case lpp_equal:
 356       return "=";
 357     case lpp_less:
 358       return "<=";
 359     case lpp_greater:
 360       return ">=";
 361         default:
 362           return "";
 363   }
 364 }
 365
 366 void lpp_dump_plain(lpp_t *lpp, FILE *f)
 367 {
 368   int i;
 369
 370   for(i = 0; i < lpp->cst_next; ++i) {
 371     const matrix_elem_t *elm;
 372     lpp_name_t *cst = lpp->csts[i];
 373
 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 */
 378       if(elm->col > 0)
 379         fprintf(f, "%+4.1f*%-16s ", elm->val, var->name);
 380     }
 381
 382     fprintf(f, "%3s %+4.1f\n",
 383         lpp_cst_op_to_str(cst->type.cst_type), matrix_get(lpp->m, cst->nr, 0));
 384   }
 385 }
 386
 387 /**
 388  * Serialize a lpp to a file descriptor.
 389  * @param comm The file descriptor.
 390  * @param lpp The lpp.
 391  */
 392 void lpp_serialize(lpp_comm_t *comm, const lpp_t *lpp, int with_names)
 393 {
 394         int n, i;
 395
 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);
 401
 402         /* write options */
 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);
 407
 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);
 413
 414                 if(with_names)
 415                         lpp_writes(comm, name->name);
 416         }
 417
 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);
 423
 424                 if(with_names)
 425                         lpp_writes(comm, name->name);
 426         }
 427
 428         {
 429                 const matrix_elem_t *elm;
 430                 n = 0;
 431
 432                 matrix_foreach(lpp->m, elm)
 433                         n++;
 434
 435                 assert(n == matrix_get_entries(lpp->m));
 436                 lpp_writel(comm, n);
 437                 matrix_foreach(lpp->m, elm) {
 438                         lpp_writel(comm, elm->row);
 439                         lpp_writel(comm, elm->col);
 440                         lpp_writed(comm, elm->val);
 441                 }
 442         }
 443 }
 444
 445 #define NAMELEN 64
 446
 447 /**
 448  * Deserialize an lpp from a file descriptor.
 449  * @param comm The file descriptor.
 450  * @return The Problem.
 451  */
 452 lpp_t *lpp_deserialize(lpp_comm_t *comm)
 453 {
 454         int i, n;
 455         int with_names;
 456
 457         lpp_t *lpp = XMALLOCZ(lpp_t);
 458
 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);
 465
 466         /* read options */
 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);
 471
 472         lpp->cst_size = lpp->cst_next;
 473         lpp->var_size = lpp->var_next;
 474
 475         lpp->cst2nr   = new_set(cmp_name_t, lpp->cst_next);
 476         lpp->var2nr   = new_set(cmp_name_t, lpp->var_next);
 477
 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);
 481
 482         for(i = 0; i < lpp->cst_next; ++i) {
 483                 lpp_name_t name, *res;
 484
 485                 name.nr            = lpp_readl(comm);
 486                 name.value_kind    = lpp_readl(comm);
 487                 name.type.cst_type = lpp_readl(comm);
 488
 489                 if(with_names)
 490                         name.name          = lpp_reads(comm);
 491                 else {
 492                         char* buf = XMALLOCN(char, NAMELEN);
 493                         snprintf(buf, NAMELEN, "c%d\n", name.nr);
 494                         name.name = buf;
 495                 }
 496
 497                 res = set_insert(lpp->cst2nr, &name, sizeof(name), HASH_NAME_T(&name));
 498                 lpp->csts[name.nr] = res;
 499         }
 500
 501         for(i = 0; i < lpp->var_next; ++i) {
 502                 lpp_name_t name, *res;
 503
 504                 name.nr            = lpp_readl(comm);
 505                 name.value_kind    = lpp_readl(comm);
 506                 name.type.var_type = lpp_readl(comm);
 507
 508                 if(with_names)
 509                         name.name          = lpp_reads(comm);
 510                 else {
 511                         char* buf = XMALLOCN(char, NAMELEN);
 512                         snprintf(buf, NAMELEN, "v%d\n", name.nr);
 513                         name.name = buf;
 514                 }
 515
 516                 res = set_insert(lpp->var2nr, &name, sizeof(name), HASH_NAME_T(&name));
 517                 lpp->vars[name.nr] = res;
 518         }
 519
 520         n = lpp_readl(comm);
 521         for(i = 0; i < n; ++i) {
 522                 matrix_elem_t elm;
 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);
 527         }
 528
 529         return lpp;
 530 }
 531
 532 void lpp_serialize_values(lpp_comm_t *comm, const lpp_t *lpp, lpp_value_kind_t value_kind)
 533 {
 534   int i, n;
 535
 536   for(i = 0, n = 0; i < lpp->var_next; ++i)
 537     n += lpp->vars[i]->value_kind == value_kind;
 538
 539   /* Write the number of values to expect */
 540   lpp_writel(comm, n);
 541
 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);
 548     }
 549   }
 550 }
 551
 552 void lpp_deserialize_values(lpp_comm_t *comm, lpp_t *lpp, lpp_value_kind_t value_kind)
 553 {
 554   int i, n;
 555
 556   /* Get the number of values to read */
 557   n = lpp_readl(comm);
 558
 559   for(i = 0; i < n; ++i) {
 560     int nr = lpp_readl(comm);
 561     lpp_name_t *name = lpp->vars[nr];
 562
 563     name->value_kind = value_kind;
 564     name->value = lpp_readd(comm);
 565   }
 566 }
 567
 568 void lpp_serialize_stats(lpp_comm_t *comm, const lpp_t *lpp)
 569 {
 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);
 575 }
 576
 577 void lpp_deserialize_stats(lpp_comm_t *comm, lpp_t *lpp)
 578 {
 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);
 584 }