nsz Git - libfirm/blob - ir/be/becopyilp.c

   1 /**
   2  * Minimizing copies with an exact algorithm using mixed integer programming (MIP).
   3  * Problem statement as a 'quadratic 0-1 program with linear constraints' with
   4  * n binary variables. Constraints are knapsack (enforce color for each node) and
   5  * cliques of ifg (interference constraints).
   6  * Transformation into a 'mixed integer program' with n binary variables and
   7  * additional 2n real variables. Constraints are the above the transformed
   8  * objective function and 'complementary conditions' for two var classes.
   9  * @author Daniel Grund
  10  *
  11  * NOTE: Unfortunately no good solver is available locally (or even for linking)
  12  *       We use CPLEX 9.0 which runs on a machine residing at the Rechenzentrum.
  13  * @date 12.04.2005
  14  */
  15
  16 #include "becopyopt.h"
  17 #include "becopystat.h"
  18
  19 #define DUMP_MILP                       /**< dumps the problem as Mixed Integer Linear Programming in "CPLEX"-MPS format. NOT fixed-column-MPS. */
  20 #undef DUMP_MIQP                        /**< dumps the problem as Mixed Integer Quadratic Programming in "CPLEX"-MPS format. NOT fixed-column-MPS. */
  21 #undef USE_SOS                          /**< uses Special Ordered Sets when using MPS */
  22 #undef DO_SOLVE                         /**< solve the MPS output with CPLEX */
  23 #undef DUMP_MATRICES            /**< dumps all matrices completely. only recommended for small problems */
  24 #undef DUMP_LP                          /**< dumps the problem in LP format. 'human-readable' equations etc... */
  25 #undef DELETE_FILES             /**< deletes all dumped files after use */
  26
  27 /* CPLEX-account related stuff */
  28 #define SSH_USER_HOST "kb61@sp-smp.rz.uni-karlsruhe.de"
  29 #define SSH_PASSWD_FILE "/ben/daniel/.smppw"
  30 #define EXPECT_FILENAME "runme" /** name of the expect-script */
  31
  32 #define DEBUG_LVL 0 //SET_LEVEL_1
  33 static firm_dbg_module_t *dbg = NULL;
  34
  35 #define SLOTS_NUM2POS 256
  36 #define SLOTS_LIVING 32
  37
  38 /* get_weight represents the _gain_ if node n and m have the same color. */
  39 #define get_weight(n,m) 1
  40
  41 /**
  42  * A type storing names of the x variables in the form x[NUMBER]_[COLOR]
  43  */
  44 typedef struct _x_name_t {
  45         int n, c;
  46 } x_name_t;
  47
  48 /**
  49  * For each node taking part in the opt-problem its position in the
  50  * x-variable-vector is stored in a set. This set maps the node-nr (given by
  51  * benumb) to the position in the vector.
  52  */
  53 typedef struct _num2pos_t {
  54         int num, pos;
  55 } num2pos_t;
  56
  57 /**
  58  * A type storing the unmodified '0-1 quadratic program' of the form
  59  * min f = xQx
  60  * udN:  Ax  = e
  61  *       Bx <= e
  62  *        x \in {0, 1}
  63  *
  64  * This problem is called the original problem
  65  */
  66 typedef struct _problem_instance_t {
  67         const copy_opt_t *co;                   /** the original copy_opt problem */
  68         int x_dim, A_dim, B_dim;                /**< number of: x variables (equals Q_dim), rows in A, rows in B */
  69         x_name_t *x;                                    /**< stores the names of the x variables. all possible colors for a node are ordered and occupy consecutive entries. lives in obstack ob. */
  70         set *num2pos;                                   /**< maps node numbers to positions in x. */
  71         sp_matrix_t *Q, *A, *B;                 /**< the (sparse) matrices of this problem */
  72
  73         /* needed only for linearizations */
  74         int bigM, maxQij, minQij;
  75
  76         /* overhead needed to build this */
  77         struct obstack ob;
  78         int curr_color;
  79         int curr_row;
  80 } problem_instance_t;
  81
  82 /* Nodes have consecutive numbers so this hash shoud be fine */
  83 #define HASH_NUM(num) num
  84
  85 static int set_cmp_num2pos(const void *x, const void *y, size_t size) {
  86         return ((num2pos_t *)x)->num != ((num2pos_t *)y)->num;
  87 }
  88
  89 /**
  90  * Sets the first position of node with number num to pos.
  91  * See x_name_t *x in _problem_instance_t.
  92  */
  93 static INLINE void pi_set_first_pos(problem_instance_t *pi, int num, int pos) {
  94         num2pos_t find;
  95         find.num = num;
  96         find.pos = pos;
  97         set_insert(pi->num2pos, &find, sizeof(find), HASH_NUM(num));
  98 }
  99
 100 /**
 101  * Get position by number. (First possible color)
 102  * returns -1 if not found.
 103  */
 104 static INLINE int pi_get_first_pos(problem_instance_t *pi, int num) {
 105         num2pos_t find, *found;
 106         find.num = num;
 107         found = set_find(pi->num2pos, &find, sizeof(find), HASH_NUM(num));
 108         if (found) {
 109                 assert(pi->x[found->pos].n == num && (found->pos == 0 || pi->x[found->pos-1].n != num) && "pi->num2pos is broken!");
 110                 return found->pos;
 111         } else
 112                 return -1;
 113 }
 114
 115 /**
 116  * Get position by number and color.
 117  * returns -1 if not found.
 118  */
 119 static INLINE int pi_get_pos(problem_instance_t *pi, int num, int col) {
 120         num2pos_t find, *found;
 121         find.num = num;
 122         int pos;
 123         found = set_find(pi->num2pos, &find, sizeof(find), HASH_NUM(num));
 124         if (!found)
 125                 return -1;
 126         pos = found->pos;
 127         while (pos < pi->x_dim && pi->x[pos].n == num && pi->x[pos].c < col)
 128                 pos++;
 129
 130         if (pi->x[pos].n == num && pi->x[pos].c == col)
 131                 return pos;
 132         else
 133                 return -1;
 134 }
 135
 136 #ifdef DUMP_MATRICES
 137 /**
 138  * Dump the raw matrices of the problem to a file for debugging.
 139  */
 140 static void pi_dump_matrices(problem_instance_t *pi) {
 141         int i;
 142         FILE *out = ffopen(pi->co->name, "matrix", "wt");
 143
 144         DBG((dbg, LEVEL_1, "Dumping raw...\n"));
 145         fprintf(out, "\n\nx-names =\n");
 146         for (i=0; i<pi->x_dim; ++i)
 147                 fprintf(out, "%5d %2d\n", pi->x[i].n, pi->x[i].c);
 148
 149         fprintf(out, "\n\n-Q =\n");
 150         matrix_dump(pi->Q, out, -1);
 151
 152         fprintf(out, "\n\nA =\n");
 153         matrix_dump(pi->A, out, 1);
 154
 155         fprintf(out, "\n\nB =\n");
 156         matrix_dump(pi->B, out, 1);
 157
 158         fclose(out);
 159 }
 160 #endif
 161
 162 #ifdef DUMP_LP
 163 /**
 164  * Dumps the problem instance as a MILP. The original problem is transformed into:
 165  * min f = es - Mex
 166  * udN:  Qx -y -s +Me = 0
 167  *       Ax  = e
 168  *       Bx <= e
 169  *        y <= 2M(e-x)
 170  *        x \in N   y, s >= 0
 171  *
 172  * with M >= max sum Q'ij * x_j
 173  *            i   j
 174  */
 175 static void pi_dump_lp(problem_instance_t *pi) {
 176         int i, max_abs_Qij;
 177         matrix_elem_t *e;
 178         FILE *out = ffopen(pi->co->name, "lpo", "wt");
 179
 180         DBG((dbg, LEVEL_1, "Dumping lp...\n"));
 181         /* calc the big M for Q */
 182         max_abs_Qij = pi->maxQij;
 183         if (-pi->minQij > max_abs_Qij)
 184                 max_abs_Qij = -pi->minQij;
 185         pi->bigM = pi->A_dim * max_abs_Qij;
 186         DBG((dbg, LEVEL_2, "BigM = %d\n", pi->bigM));
 187
 188         /* generate objective function */
 189         fprintf(out, "min: ");
 190         for (i=0; i<pi->x_dim; ++i)
 191                 fprintf(out, "+s%d_%d -%dx%d_%d ", pi->x[i].n, pi->x[i].c, pi->bigM, pi->x[i].n, pi->x[i].c);
 192         fprintf(out, ";\n\n");
 193
 194         /* constraints for former objective function */
 195         for (i=0; i<pi->x_dim; ++i)     {
 196                 matrix_foreach_in_row(pi->Q, i, e) {
 197                         int Qio = e->val;
 198                                 if (Qio == 1)
 199                                         fprintf(out, "+x%d_%d ", pi->x[e->col].n, pi->x[e->col].c);
 200                                 else if(Qio == -1)
 201                                         fprintf(out, "-x%d_%d ", pi->x[e->col].n, pi->x[e->col].c);
 202                                 else
 203                                         fprintf(out, "%+dx%d_%d ", Qio, pi->x[e->col].n, pi->x[e->col].c);
 204                 }
 205                 fprintf(out, "-y%d_%d -s%d_%d +%d= 0;\n", pi->x[i].n, pi->x[i].c, pi->x[i].n, pi->x[i].c, pi->bigM);
 206         }
 207         fprintf(out, "\n\n");
 208
 209         /* constraints for (special) complementary condition */
 210         for (i=0; i<pi->x_dim; ++i)
 211                 fprintf(out, "y%d_%d <= %d - %dx%d_%d;\n", pi->x[i].n, pi->x[i].c, 2*pi->bigM, 2*pi->bigM, pi->x[i].n, pi->x[i].c);
 212         fprintf(out, "\n\n");
 213
 214         /* knapsack constraints */
 215         for (i=0; i<pi->A_dim; ++i)     {
 216                 matrix_foreach_in_row(pi->Q, i, e)
 217                         fprintf(out, "+x%d_%d ", pi->x[e->col].n, pi->x[e->col].c);
 218                 fprintf(out, " = 1;\n");
 219         }
 220         fprintf(out, "\n\n");
 221
 222         /* interference graph constraints */
 223         for (i=0; i<pi->B_dim; ++i)     {
 224                 matrix_foreach_in_row(pi->Q, i, e)
 225                         fprintf(out, "+x%d_%d ", pi->x[e->col].n, pi->x[e->col].c);
 226                 fprintf(out, " <= 1;\n");
 227         }
 228         fprintf(out, "\n\n");
 229
 230         /* integer constraints */
 231         fprintf(out, "int x%d_%d", pi->x[0].n, pi->x[0].c);
 232         for (i=1; i<pi->x_dim; ++i)
 233                 fprintf(out, ", x%d_%d", pi->x[i].n, pi->x[i].c);
 234         fprintf(out, ";\n");
 235
 236         fclose(out);
 237 }
 238 #endif
 239
 240 #ifdef DO_SOLVE
 241 static void pi_dump_start_sol(problem_instance_t *pi) {
 242         int i;
 243         FILE *out = ffopen(pi->co->name, "mst", "wt");
 244         fprintf(out, "NAME\n");
 245         for (i=0; i<pi->x_dim; ++i) {
 246                 int val, n, c;
 247                 n = pi->x[i].n;
 248                 c = pi->x[i].c;
 249                 if (get_irn_color(get_irn_for_graph_nr(pi->co->irg, n)) == c)
 250                         val = 1;
 251                 else
 252                         val = 0;
 253                 fprintf(out, "    x%d_%d\t%d\n", n, c, val);
 254         }
 255         fprintf(out, "ENDATA\n");
 256         fclose(out);
 257 }
 258 #endif
 259
 260 #ifdef DUMP_MILP
 261 /**
 262  * Dumps an mps file representing the problem. This is NOT the old-style,
 263  * fixed-column format. Some white spaces are important, in general spaces
 264  * are separators, MARKER-lines are used in COLUMN section to define binaries.
 265  */
 266 //BETTER use last 2 fields in COLUMNS section. See MPS docu for details
 267 static void pi_dump_milp(problem_instance_t *pi) {
 268         int i, max_abs_Qij;
 269         const matrix_elem_t *e;
 270         FILE *out = ffopen(pi->co->name, "milp", "wt");
 271
 272         DBG((dbg, LEVEL_1, "Dumping milp...\n"));
 273         max_abs_Qij = pi->maxQij;
 274         if (-pi->minQij > max_abs_Qij)
 275                 max_abs_Qij = -pi->minQij;
 276         pi->bigM = pi->A_dim * max_abs_Qij;
 277         DBG((dbg, LEVEL_2, "BigM = %d\n", pi->bigM));
 278
 279         matrix_optimize(pi->Q);
 280         bitset_t *good_row = bitset_alloca(pi->x_dim);
 281         for (i=0; i<pi->x_dim; ++i)
 282                 if (matrix_row_first(pi->Q, i))
 283                         bitset_set(good_row, i);
 284
 285         fprintf(out, "NAME %s\n", pi->co->name);
 286
 287         fprintf(out, "ROWS\n");
 288         fprintf(out, " N obj\n");
 289         for (i=0; i<pi->x_dim; ++i)
 290                 if (bitset_is_set(good_row, i))
 291                         fprintf(out, " E cQ%d\n", i);
 292         for (i=0; i<pi->A_dim; ++i)
 293                 fprintf(out, " E cA%d\n", i);
 294         for (i=0; i<pi->B_dim; ++i)
 295                 fprintf(out, " L cB%d\n", i);
 296         for (i=0; i<pi->x_dim; ++i)
 297                 if (bitset_is_set(good_row, i))
 298                         fprintf(out, " L cy%d\n", i);
 299
 300         fprintf(out, "COLUMNS\n");
 301         /* the x vars come first */
 302         /* mark them as binaries */
 303         fprintf(out, "    MARKI0\t'MARKER'\t'INTORG'\n");
 304 #ifdef USE_SOS
 305         int sos_cnt = 0;
 306         fprintf(out, " S1 SOS_%d\t'MARKER'\t'SOSORG'\n", sos_cnt++);
 307 #endif
 308         for (i=0; i<pi->x_dim; ++i) {
 309 #ifdef USE_SOS
 310                 if (i>0 && pi->x[i].n != pi->x[i-1].n) {
 311                         fprintf(out, "    SOS_%d\t'MARKER'\t'SOSEND'\n", sos_cnt++);
 312                         fprintf(out, " S1 SOS_%d\t'MARKER'\t'SOSORG'\n", sos_cnt++);
 313                 }
 314 #endif
 315                 /* participation in objective */
 316                 if (bitset_is_set(good_row, i))
 317                         fprintf(out, "    x%d_%d\tobj\t%d\n", pi->x[i].n, pi->x[i].c, -pi->bigM);
 318                 /* in Q */
 319                 matrix_foreach_in_col(pi->Q, i, e)
 320                         fprintf(out, "    x%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val);
 321                 /* in A */
 322                 matrix_foreach_in_col(pi->A, i, e)
 323                         fprintf(out, "    x%d_%d\tcA%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val);
 324                 /* in B */
 325                 matrix_foreach_in_col(pi->B, i, e)
 326                         fprintf(out, "    x%d_%d\tcB%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val);
 327                 /* in y */
 328                 if (bitset_is_set(good_row, i))
 329                         fprintf(out, "    x%d_%d\tcy%d\t%d\n", pi->x[i].n, pi->x[i].c, i, 2*pi->bigM);
 330         }
 331
 332 #ifdef USE_SOS
 333         fprintf(out, "    SOS_%d\t'MARKER'\t'SOSEND'\n", sos_cnt++);
 334 #endif
 335         fprintf(out, "    MARKI1\t'MARKER'\t'INTEND'\n"); /* end of marking */
 336
 337         /* next the s vars */
 338         for (i=0; i<pi->x_dim; ++i)
 339                 if (bitset_is_set(good_row, i)) {
 340                         /* participation in objective */
 341                         fprintf(out, "    s%d_%d\tobj\t%d\n", pi->x[i].n, pi->x[i].c, 1);
 342                         /* in Q */
 343                         fprintf(out, "    s%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, i, -1);
 344                 }
 345
 346         /* next the y vars */
 347         for (i=0; i<pi->x_dim; ++i)
 348                 if (bitset_is_set(good_row, i)) {
 349                         /* in Q */
 350                         fprintf(out, "    y%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, i, -1);
 351                         /* in y */
 352                         fprintf(out, "    y%d_%d\tcy%d\t%d\n", pi->x[i].n, pi->x[i].c, i, 1);
 353                 }
 354
 355         fprintf(out, "RHS\n");
 356         for (i=0; i<pi->x_dim; ++i)
 357                 if (bitset_is_set(good_row, i))
 358                         fprintf(out, "    rhs\tcQ%d\t%d\n", i, -pi->bigM);
 359         for (i=0; i<pi->A_dim; ++i)
 360                 fprintf(out, "    rhs\tcA%d\t%d\n", i, 1);
 361         for (i=0; i<pi->B_dim; ++i)
 362                 fprintf(out, "    rhs\tcB%d\t%d\n", i, 1);
 363         for (i=0; i<pi->x_dim; ++i)
 364                 if (bitset_is_set(good_row, i))
 365                         fprintf(out, "    rhs\tcy%d\t%d\n", i, 2*pi->bigM);
 366
 367         fprintf(out, "ENDATA\n");
 368         fclose(out);
 369 }
 370 #endif
 371
 372 #ifdef DUMP_MIQP
 373 static void pi_dump_miqp(problem_instance_t *pi) {
 374         int i;
 375         matrix_elem_t *e;
 376         FILE *out = ffopen(pi->co->name, "miqp", "wt");
 377
 378         DBG((dbg, LEVEL_1, "Dumping miqp...\n"));
 379
 380         pi->bigM = 42;
 381         fprintf(out, "NAME %s\n", pi->co->name);
 382         fprintf(out, "ROWS\n");
 383         fprintf(out, " N obj\n");
 384         for (i=0; i<pi->A_dim; ++i)
 385                 fprintf(out, " E cA%d\n", i);
 386         for (i=0; i<pi->B_dim; ++i)
 387                 fprintf(out, " L cB%d\n", i);
 388
 389         fprintf(out, "COLUMNS\n");
 390         /* the x vars come first */
 391         /* mark them as binaries */
 392         fprintf(out, "    MARKI0\t'MARKER'\t'INTORG'\n");
 393         for (i=0; i<pi->x_dim; ++i) {
 394                 /* participation in objective */
 395                 fprintf(out, "    x%d_%d\tobj\t%d\n", pi->x[i].n, pi->x[i].c, -pi->bigM);
 396                 /* in A */
 397                 matrix_foreach_in_col(pi->A, i, e)
 398                         fprintf(out, "    x%d_%d\tcA%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val);
 399                 /* in B */
 400                 matrix_foreach_in_col(pi->B, i, e)
 401                         fprintf(out, "    x%d_%d\tcB%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val);
 402         }
 403         fprintf(out, "    MARKI1\t'MARKER'\t'INTEND'\n"); /* end of marking */
 404
 405         fprintf(out, "RHS\n");
 406         for (i=0; i<pi->A_dim; ++i)
 407                 fprintf(out, "    rhs\tcA%d\t%d\n", i, 1);
 408         for (i=0; i<pi->B_dim; ++i)
 409                 fprintf(out, "    rhs\tcB%d\t%d\n", i, 1);
 410
 411         fprintf(out, "QMATRIX\n"); /* 1/2 (Q + Q^T) */
 412         /* the diag entries */
 413         for (i=0; i<pi->x_dim; ++i) {
 414                 int val = matrix_get(pi->Q, i, i) + pi->bigM;
 415                 fprintf(out, "    x%d_%d\tx%d_%d\t%d\n", pi->x[i].n, pi->x[i].c, pi->x[i].n, pi->x[i].c, val);
 416         }
 417         /* the off-diag entries */
 418         for (i=0; i<matrix_get_rowcount(pi->Q); ++i)
 419                 matrix_foreach_in_row(pi->Q, i, e) {
 420                         int val;
 421                         if (e->col >= e->row)
 422                                 break;
 423                         val = e->val + matrix_get(pi->Q, e->col, e->row); /* the transposed entry */
 424                         fprintf(out, "    x%d_%d\tx%d_%d\t%d\n", pi->x[i].n, pi->x[i].c, pi->x[e->col].n, pi->x[e->col].c, val);
 425                         fprintf(out, "    x%d_%d\tx%d_%d\t%d\n", pi->x[e->col].n, pi->x[e->col].c, pi->x[i].n, pi->x[i].c, val);
 426                 }
 427
 428         fprintf(out, "ENDATA\n");
 429         fclose(out);
 430 }
 431 #endif
 432
 433 #ifdef DO_SOLVE
 434 /**
 435  * Invoke an external solver
 436  */
 437 static void pi_solve_ilp(problem_instance_t *pi) {
 438         FILE *out, *pwfile;
 439         char passwd[128];
 440
 441         DBG((dbg, LEVEL_1, "Solving with CPLEX@RZ...\n"));
 442         /* write command file for CPLEX */
 443         out = ffopen(pi->co->name, "cmd", "wt");
 444         fprintf(out, "set logfile %s.sol\n", pi->co->name);
 445 #ifdef DUMP_MILP
 446         fprintf(out, "read %s.milp mps\n", pi->co->name);
 447 #endif
 448 #ifdef DUMP_MIQP
 449         fprintf(out, "read %s.miqp mps\n", pi->co->name);
 450 #endif
 451         fprintf(out, "read %s.mst\n", pi->co->name);
 452         fprintf(out, "set mip strategy mipstart 1\n");
 453         fprintf(out, "set mip emphasis 3\n");
 454         fprintf(out, "optimize\n");
 455         fprintf(out, "display solution variables 1-%d\n", pi->x_dim);
 456         fprintf(out, "set logfile cplex.log\n");
 457         fprintf(out, "quit\n");
 458         fclose(out);
 459
 460         /* write expect-file for copying problem to RZ */
 461         pwfile = fopen(SSH_PASSWD_FILE, "rt");
 462         fgets(passwd, sizeof(passwd), pwfile);
 463         fclose(pwfile);
 464
 465         out = ffopen(EXPECT_FILENAME, "exp", "wt");
 466         fprintf(out, "#! /usr/bin/expect\n");
 467         fprintf(out, "spawn scp %s.miqp %s.milp %s.mst %s.cmd %s:\n", pi->co->name, pi->co->name, pi->co->name, pi->co->name, SSH_USER_HOST); /* copy problem files */
 468         fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd);
 469
 470         fprintf(out, "spawn ssh %s \"./cplex90 < %s.cmd\"\n", SSH_USER_HOST, pi->co->name); /* solve */
 471         fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd);
 472
 473         fprintf(out, "spawn scp %s:%s.sol .\n", SSH_USER_HOST, pi->co->name); /*copy back solution */
 474         fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd);
 475
 476         fprintf(out, "spawn ssh %s ./dell\n", SSH_USER_HOST); /* clean files on server */
 477         fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd);
 478         fclose(out);
 479
 480         /* call the expect script */
 481         chmod(EXPECT_FILENAME ".exp", 0700);
 482         system(EXPECT_FILENAME ".exp");
 483 }
 484
 485 /**
 486  * Sets the colors of irns according to the values of variables found in the
 487  * output file of the solver.
 488  */
 489 static void pi_apply_solution(problem_instance_t *pi) {
 490         FILE *in = ffopen(pi->co->name, "sol", "rt");
 491
 492         if (!in)
 493                 return;
 494         DBG((dbg, LEVEL_1, "Applying solution...\n"));
 495         while (!feof(in)) {
 496                 char buf[1024];
 497                 int num = -1, col = -1, val = -1;
 498
 499                 fgets(buf, sizeof(buf), in);
 500                 DBG((dbg, LEVEL_3, "Line: %s", buf));
 501
 502                 if (strcmp(buf, "No integer feasible solution exists.") == 0)
 503                         assert(0 && "CPLEX says: No integer feasible solution exists!");
 504
 505                 if (strcmp(buf, "TODO Out of memory") == 0) {}
 506
 507 #ifdef DO_STAT
 508                 {
 509                         /* solution time */
 510                         float sol_time;
 511                         int iter;
 512                         if (sscanf(buf, "Solution time = %f sec. Iterations = %d", &sol_time, &iter) == 2) {
 513                                 DBG((dbg, LEVEL_2, " Time: %f Iter: %d\n", sol_time, iter));
 514                                 curr_vals[I_ILP_TIME] += 10 * sol_time;
 515                                 curr_vals[I_ILP_ITER] += iter;
 516                         }
 517                 }
 518 #endif
 519
 520                 /* variable value */
 521                 if (sscanf(buf, "x%d_%d %d", &num, &col, &val) == 3 && val == 1) {
 522                         DBG((dbg, LEVEL_2, " x%d_%d = %d\n", num, col, val));
 523                         set_irn_color(get_irn_for_graph_nr(pi->co->irg, num), col);
 524                 }
 525         }
 526         fclose(in);
 527 }
 528 #endif /* DO_SOLVE */
 529
 530 #ifdef DELETE_FILES
 531 static void pi_delete_files(problem_instance_t *pi) {
 532         char buf[1024];
 533         int end = snprintf(buf, sizeof(buf), "%s", pi->co->name);
 534         DBG((dbg, LEVEL_1, "Deleting files...\n"));
 535 #ifdef DUMP_MATRICES
 536         snprintf(buf+end, sizeof(buf)-end, ".matrix");
 537         remove(buf);
 538 #endif
 539 #ifdef DUMP_MILP
 540         snprintf(buf+end, sizeof(buf)-end, ".mps");
 541         remove(buf);
 542         snprintf(buf+end, sizeof(buf)-end, ".mst");
 543         remove(buf);
 544         snprintf(buf+end, sizeof(buf)-end, ".cmd");
 545         remove(buf);
 546         remove(EXPECT_FILENAME ".exp");
 547 #endif
 548 #ifdef DO_SOLVE
 549         snprintf(buf+end, sizeof(buf)-end, ".sol");
 550         remove(buf);
 551 #endif
 552 #ifdef DUMP_LP
 553         snprintf(buf+end, sizeof(buf)-end, ".lp");
 554         remove(buf);
 555 #endif
 556 }
 557 #endif
 558
 559 /**
 560  * Collects all irns in currently processed register class
 561  */
 562 static void pi_collect_x_names(ir_node *block, void *env) {
 563         problem_instance_t *pi = env;
 564         struct list_head *head = &get_ra_block_info(block)->border_head;
 565         border_t *curr;
 566         bitset_t *pos_regs = bitset_alloca(pi->co->cls->n_regs);
 567
 568         list_for_each_entry_reverse(border_t, curr, head, list)
 569                 if (curr->is_def && curr->is_real) {
 570                         x_name_t xx;
 571                         pi->A_dim++;                    /* one knapsack constraint for each node */
 572
 573                         xx.n = get_irn_graph_nr(curr->irn);
 574                         pi_set_first_pos(pi, xx.n, pi->x_dim);
 575
 576                         // iterate over all possible colors in order
 577                         bitset_clear_all(pos_regs);
 578                         pi->co->isa->get_allocatable_regs(curr->irn, pi->co->cls, pos_regs);
 579                         bitset_foreach(pos_regs, xx.c) {
 580                                 DBG((dbg, LEVEL_2, "Adding %n %d\n", curr->irn, xx.c));
 581                                 obstack_grow(&pi->ob, &xx, sizeof(xx));
 582                                 pi->x_dim++;            /* one x variable for each node and color */
 583                         }
 584                 }
 585 }
 586
 587 /**
 588  * Checks if all nodes in living are live_out in block block.
 589  */
 590 static INLINE int all_live_in(ir_node *block, pset *living) {
 591         ir_node *n;
 592         for (n = pset_first(living); n; n = pset_next(living))
 593                 if (!is_live_in(block, n)) {
 594                         pset_break(living);
 595                         return 0;
 596                 }
 597         return 1;
 598 }
 599
 600 /**
 601  * Finds cliques in the interference graph, considering only nodes
 602  * for which the color pi->curr_color is possible. Finds only 'maximal-cliques',
 603  * viz cliques which are not conatained in another one.
 604  * This is used for the matrix B.
 605  */
 606 static void pi_clique_finder(ir_node *block, void *env) {
 607         problem_instance_t *pi = env;
 608         enum phase_t {growing, shrinking} phase = growing;
 609         struct list_head *head = &get_ra_block_info(block)->border_head;
 610         border_t *b;
 611         pset *living = pset_new_ptr(SLOTS_LIVING);
 612
 613         list_for_each_entry_reverse(border_t, b, head, list) {
 614                 const ir_node *irn = b->irn;
 615
 616                 if (b->is_def) {
 617                         DBG((dbg, LEVEL_2, "Def %n\n", irn));
 618                         pset_insert_ptr(living, irn);
 619                         phase = growing;
 620                 } else { /* is_use */
 621                         DBG((dbg, LEVEL_2, "Use %n\n", irn));
 622
 623                         /* before shrinking the set, store the current 'maximum' clique;
 624                          * do NOT if clique is a single node
 625                          * do NOT if all values are live_in (in this case they were contained in a live-out clique elsewhere) */
 626                         if (phase == growing && pset_count(living) >= 2 && !all_live_in(block, living)) {
 627                                 ir_node *n;
 628                                 for (n = pset_first(living); n; n = pset_next(living)) {
 629                                         int pos = pi_get_pos(pi, get_irn_graph_nr(n), pi->curr_color);
 630                                         matrix_set(pi->B, pi->curr_row, pos, 1);
 631                                         DBG((dbg, LEVEL_2, "B[%d, %d] := %d\n", pi->curr_row, pos, 1));
 632                                 }
 633                                 pi->curr_row++;
 634                         }
 635                         pset_remove_ptr(living, irn);
 636                         phase = shrinking;
 637                 }
 638         }
 639
 640         del_pset(living);
 641 }
 642
 643 /**
 644  * Generate the initial problem matrices and vectors.
 645  */
 646 static problem_instance_t *new_pi(const copy_opt_t *co) {
 647         DBG((dbg, LEVEL_1, "Generating new instance...\n"));
 648         problem_instance_t *pi = calloc(1, sizeof(*pi));
 649         pi->co = co;
 650         pi->num2pos = new_set(set_cmp_num2pos, SLOTS_NUM2POS);
 651         pi->bigM = 1;
 652
 653         /* Vector x
 654          * one entry per node and possible color */
 655         obstack_init(&pi->ob);
 656         dom_tree_walk_irg(co->irg, pi_collect_x_names, NULL, pi);
 657         pi->x = obstack_finish(&pi->ob);
 658
 659         /* Matrix Q
 660          * weights for the 'same-color-optimization' target */
 661         {
 662                 unit_t *curr;
 663                 pi->Q = new_matrix(pi->x_dim, pi->x_dim);
 664
 665                 list_for_each_entry(unit_t, curr, &co->units, units) {
 666                         const ir_node *root, *arg;
 667                         int rootnr, argnr;
 668                         unsigned rootpos, argpos;
 669                         int i;
 670
 671                         root = curr->nodes[0];
 672                         rootnr = get_irn_graph_nr(root);
 673                         rootpos = pi_get_first_pos(pi, rootnr);
 674                         for (i = 1; i < curr->node_count; ++i) {
 675                                 int weight = -get_weight(root, arg);
 676                                 arg = curr->nodes[i];
 677                                 argnr = get_irn_graph_nr(arg);
 678                                 argpos = pi_get_first_pos(pi, argnr);
 679
 680                                 DBG((dbg, LEVEL_2, "Q[%n, %n] := %d\n", root, arg, weight));
 681                                 /* for all colors root and arg have in common, set the weight for
 682                                  * this pair in the objective function matrix Q */
 683                                 while (rootpos < pi->x_dim && argpos < pi->x_dim &&
 684                                                 pi->x[rootpos].n == rootnr && pi->x[argpos].n == argnr) {
 685                                         if (pi->x[rootpos].c < pi->x[argpos].c)
 686                                                 ++rootpos;
 687                                         else if (pi->x[rootpos].c > pi->x[argpos].c)
 688                                                 ++argpos;
 689                                         else {
 690                                                 matrix_set(pi->Q, rootpos++, argpos++, weight);
 691
 692                                                 if (weight < pi->minQij) {
 693                                                         DBG((dbg, LEVEL_2, "minQij = %d\n", weight));
 694                                                         pi->minQij = weight;
 695                                                 }
 696                                                 if (weight > pi->maxQij) {
 697                                                         DBG((dbg, LEVEL_2, "maxQij = %d\n", weight));
 698                                                         pi->maxQij = weight;
 699                                                 }
 700                                         }
 701                                 }
 702                         }
 703                 }
 704         }
 705
 706         /* Matrix A
 707          * knapsack constraint for each node */
 708         {
 709                 int row = 0, col = 0;
 710                 pi->A = new_matrix(pi->A_dim, pi->x_dim);
 711                 while (col < pi->x_dim) {
 712                         int curr_n = pi->x[col].n;
 713                         while (col < pi->x_dim && pi->x[col].n == curr_n) {
 714                                 DBG((dbg, LEVEL_2, "A[%d, %d] := %d\n", row, col, 1));
 715                                 matrix_set(pi->A, row, col++, 1);
 716                         }
 717                         ++row;
 718                 }
 719                 assert(row == pi->A_dim);
 720         }
 721
 722         /* Matrix B
 723          * interference constraints using exactly those cliques not contained in others. */
 724         {
 725                 int color, expected_clipques = pi->A_dim/4 * pi->co->cls->n_regs;
 726                 pi->B = new_matrix(expected_clipques, pi->x_dim);
 727                 for (color = 0; color < pi->co->cls->n_regs; ++color) {
 728                         pi->curr_color = color;
 729                         dom_tree_walk_irg(pi->co->irg, pi_clique_finder, NULL, pi);
 730                 }
 731                 pi->B_dim = matrix_get_rowcount(pi->B);
 732         }
 733
 734         return pi;
 735 }
 736
 737 /**
 738  * clean the problem instance
 739  */
 740 static void free_pi(problem_instance_t *pi) {
 741         DBG((dbg, LEVEL_1, "Generating new instance...\n"));
 742         del_matrix(pi->Q);
 743         del_matrix(pi->A);
 744         del_matrix(pi->B);
 745         del_set(pi->num2pos);
 746         obstack_free(&pi->ob, NULL);
 747         free(pi);
 748 }
 749
 750 void co_ilp_opt(copy_opt_t *co) {
 751         dbg = firm_dbg_register("ir.be.copyoptilp");
 752         firm_dbg_set_mask(dbg, DEBUG_LVL);
 753         if (!strcmp(co->name, DEBUG_IRG))
 754                 firm_dbg_set_mask(dbg, -1);
 755
 756         problem_instance_t *pi = new_pi(co);
 757         DBG((dbg, 0, "\t\t\t %5d %5d %5d\n", pi->x_dim, pi->A_dim, pi->B_dim));
 758
 759         if (pi->x_dim > 0) {
 760 #ifdef DUMP_MATRICES
 761         pi_dump_matrices(pi);
 762 #endif
 763
 764
 765 #ifdef DUMP_LP
 766         pi_dump_lp(pi);
 767 #endif
 768
 769 #ifdef DUMP_MILP
 770         pi_dump_milp(pi);
 771 #endif
 772
 773 #ifdef DUMP_MIQP
 774         pi_dump_miqp(pi);
 775 #endif
 776
 777 #ifdef DO_SOLVE
 778         pi_dump_start_sol(pi);
 779         pi_solve_ilp(pi);
 780         pi_apply_solution(pi);
 781 #endif
 782
 783 #ifdef DELETE_FILES
 784         pi_delete_files(pi);
 785 #endif
 786         }
 787         free_pi(pi);
 788 }