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