-static void pi_dump_lp(problem_instance_t *pi) {
- int i, max_abs_Qij;
- matrix_elem_t *e;
- FILE *out = ffopen(pi->co->name, "lpo", "wt");
-
- DBG((dbg, LEVEL_1, "Dumping lp...\n"));
- /* calc the big M for Q */
- max_abs_Qij = pi->maxQij;
- if (-pi->minQij > max_abs_Qij)
- max_abs_Qij = -pi->minQij;
- pi->bigM = pi->A_dim * max_abs_Qij;
- DBG((dbg, LEVEL_2, "BigM = %d\n", pi->bigM));
-
- /* generate objective function */
- fprintf(out, "min: ");
- for (i=0; i<pi->x_dim; ++i)
- 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);
- fprintf(out, ";\n\n");
-
- /* constraints for former objective function */
- for (i=0; i<pi->x_dim; ++i) {
- matrix_foreach_in_row(pi->Q, i, e) {
- int Qio = e->val;
- if (Qio == 1)
- fprintf(out, "+x%d_%d ", pi->x[e->col].n, pi->x[e->col].c);
- else if(Qio == -1)
- fprintf(out, "-x%d_%d ", pi->x[e->col].n, pi->x[e->col].c);
- else
- fprintf(out, "%+dx%d_%d ", Qio, pi->x[e->col].n, pi->x[e->col].c);
- }
- 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);
- }
- fprintf(out, "\n\n");
-
- /* constraints for (special) complementary condition */
- for (i=0; i<pi->x_dim; ++i)
- 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);
- fprintf(out, "\n\n");
-
- /* knapsack constraints */
- for (i=0; i<pi->A_dim; ++i) {
- matrix_foreach_in_row(pi->Q, i, e)
- fprintf(out, "+x%d_%d ", pi->x[e->col].n, pi->x[e->col].c);
- fprintf(out, " = 1;\n");
- }
- fprintf(out, "\n\n");
-
- /* interference graph constraints */
- for (i=0; i<pi->B_dim; ++i) {
- matrix_foreach_in_row(pi->Q, i, e)
- fprintf(out, "+x%d_%d ", pi->x[e->col].n, pi->x[e->col].c);
- fprintf(out, " <= 1;\n");
- }
- fprintf(out, "\n\n");
-
- /* integer constraints */
- fprintf(out, "int x%d_%d", pi->x[0].n, pi->x[0].c);
- for (i=1; i<pi->x_dim; ++i)
- fprintf(out, ", x%d_%d", pi->x[i].n, pi->x[i].c);
- fprintf(out, ";\n");
-
- fclose(out);
-}
-#endif
-
-#ifdef DO_SOLVE
-static void pi_dump_start_sol(problem_instance_t *pi) {
- int i;
- FILE *out = ffopen(pi->co->name, "mst", "wt");
- fprintf(out, "NAME\n");
- for (i=0; i<pi->x_dim; ++i) {
- int val, n, c;
- n = pi->x[i].n;
- c = pi->x[i].c;
- if (get_irn_color(get_irn_for_graph_nr(pi->co->irg, n)) == c)
- val = 1;
- else
- val = 0;
- fprintf(out, " x%d_%d\t%d\n", n, c, val);
- }
- fprintf(out, "ENDATA\n");
- fclose(out);
-}
-#endif
-
-#ifdef DUMP_MILP
-/**
- * Dumps an mps file representing the problem. This is NOT the old-style,
- * fixed-column format. Some white spaces are important, in general spaces
- * are separators, MARKER-lines are used in COLUMN section to define binaries.
- */
-//BETTER use last 2 fields in COLUMNS section. See MPS docu for details
-static void pi_dump_milp(problem_instance_t *pi) {
- int i, max_abs_Qij;
- const matrix_elem_t *e;
- FILE *out = ffopen(pi->co->name, "milp", "wt");
-
- DBG((dbg, LEVEL_1, "Dumping milp...\n"));
- max_abs_Qij = pi->maxQij;
- if (-pi->minQij > max_abs_Qij)
- max_abs_Qij = -pi->minQij;
- pi->bigM = pi->A_dim * max_abs_Qij;
- DBG((dbg, LEVEL_2, "BigM = %d\n", pi->bigM));
-
- matrix_optimize(pi->Q);
- bitset_t *good_row = bitset_alloca(pi->x_dim);
- for (i=0; i<pi->x_dim; ++i)
- if (matrix_row_first(pi->Q, i))
- bitset_set(good_row, i);
-
- fprintf(out, "NAME %s\n", pi->co->name);
-
- fprintf(out, "ROWS\n");
- fprintf(out, " N obj\n");
- for (i=0; i<pi->x_dim; ++i)
- if (bitset_is_set(good_row, i))
- fprintf(out, " E cQ%d\n", i);
- for (i=0; i<pi->A_dim; ++i)
- fprintf(out, " E cA%d\n", i);
- for (i=0; i<pi->B_dim; ++i)
- fprintf(out, " L cB%d\n", i);
- for (i=0; i<pi->x_dim; ++i)
- if (bitset_is_set(good_row, i))
- fprintf(out, " L cy%d\n", i);
-
- fprintf(out, "COLUMNS\n");
- /* the x vars come first */
- /* mark them as binaries */
- fprintf(out, " MARKI0\t'MARKER'\t'INTORG'\n");
-#ifdef USE_SOS
- int sos_cnt = 0;
- fprintf(out, " S1 SOS_%d\t'MARKER'\t'SOSORG'\n", sos_cnt++);
-#endif
- for (i=0; i<pi->x_dim; ++i) {
-#ifdef USE_SOS
- if (i>0 && pi->x[i].n != pi->x[i-1].n) {
- fprintf(out, " SOS_%d\t'MARKER'\t'SOSEND'\n", sos_cnt++);
- fprintf(out, " S1 SOS_%d\t'MARKER'\t'SOSORG'\n", sos_cnt++);
- }
-#endif
- /* participation in objective */
- if (bitset_is_set(good_row, i))
- fprintf(out, " x%d_%d\tobj\t%d\n", pi->x[i].n, pi->x[i].c, -pi->bigM);
- /* in Q */
- matrix_foreach_in_col(pi->Q, i, e)
- fprintf(out, " x%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val);
- /* in A */
- matrix_foreach_in_col(pi->A, i, e)
- fprintf(out, " x%d_%d\tcA%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val);
- /* in B */
- matrix_foreach_in_col(pi->B, i, e)
- fprintf(out, " x%d_%d\tcB%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val);
- /* in y */
- if (bitset_is_set(good_row, i))
- fprintf(out, " x%d_%d\tcy%d\t%d\n", pi->x[i].n, pi->x[i].c, i, 2*pi->bigM);
- }
-
-#ifdef USE_SOS
- fprintf(out, " SOS_%d\t'MARKER'\t'SOSEND'\n", sos_cnt++);
-#endif
- fprintf(out, " MARKI1\t'MARKER'\t'INTEND'\n"); /* end of marking */
-
- /* next the s vars */
- for (i=0; i<pi->x_dim; ++i)
- if (bitset_is_set(good_row, i)) {
- /* participation in objective */
- fprintf(out, " s%d_%d\tobj\t%d\n", pi->x[i].n, pi->x[i].c, 1);
- /* in Q */
- fprintf(out, " s%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, i, -1);
- }
-
- /* next the y vars */
- for (i=0; i<pi->x_dim; ++i)
- if (bitset_is_set(good_row, i)) {
- /* in Q */
- fprintf(out, " y%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, i, -1);
- /* in y */
- fprintf(out, " y%d_%d\tcy%d\t%d\n", pi->x[i].n, pi->x[i].c, i, 1);
- }
-
- fprintf(out, "RHS\n");
- for (i=0; i<pi->x_dim; ++i)
- if (bitset_is_set(good_row, i))
- fprintf(out, " rhs\tcQ%d\t%d\n", i, -pi->bigM);
- for (i=0; i<pi->A_dim; ++i)
- fprintf(out, " rhs\tcA%d\t%d\n", i, 1);
- for (i=0; i<pi->B_dim; ++i)
- fprintf(out, " rhs\tcB%d\t%d\n", i, 1);
- for (i=0; i<pi->x_dim; ++i)
- if (bitset_is_set(good_row, i))
- fprintf(out, " rhs\tcy%d\t%d\n", i, 2*pi->bigM);
-
- fprintf(out, "ENDATA\n");
- fclose(out);
-}
-#endif
-
-#ifdef DUMP_MIQP
-static void pi_dump_miqp(problem_instance_t *pi) {
- int i;
- matrix_elem_t *e;
- FILE *out = ffopen(pi->co->name, "miqp", "wt");
-
- DBG((dbg, LEVEL_1, "Dumping miqp...\n"));
-
- pi->bigM = 42;
- fprintf(out, "NAME %s\n", pi->co->name);
- fprintf(out, "ROWS\n");
- fprintf(out, " N obj\n");
- for (i=0; i<pi->A_dim; ++i)
- fprintf(out, " E cA%d\n", i);
- for (i=0; i<pi->B_dim; ++i)
- fprintf(out, " L cB%d\n", i);
-
- fprintf(out, "COLUMNS\n");
- /* the x vars come first */
- /* mark them as binaries */
- fprintf(out, " MARKI0\t'MARKER'\t'INTORG'\n");
- for (i=0; i<pi->x_dim; ++i) {
- /* participation in objective */
- fprintf(out, " x%d_%d\tobj\t%d\n", pi->x[i].n, pi->x[i].c, -pi->bigM);
- /* in A */
- matrix_foreach_in_col(pi->A, i, e)
- fprintf(out, " x%d_%d\tcA%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val);
- /* in B */
- matrix_foreach_in_col(pi->B, i, e)
- fprintf(out, " x%d_%d\tcB%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val);
- }
- fprintf(out, " MARKI1\t'MARKER'\t'INTEND'\n"); /* end of marking */
-
- fprintf(out, "RHS\n");
- for (i=0; i<pi->A_dim; ++i)
- fprintf(out, " rhs\tcA%d\t%d\n", i, 1);
- for (i=0; i<pi->B_dim; ++i)
- fprintf(out, " rhs\tcB%d\t%d\n", i, 1);
-
- fprintf(out, "QMATRIX\n"); /* 1/2 (Q + Q^T) */
- /* the diag entries */
- for (i=0; i<pi->x_dim; ++i) {
- int val = matrix_get(pi->Q, i, i) + pi->bigM;
- 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);
- }
- /* the off-diag entries */
- for (i=0; i<matrix_get_rowcount(pi->Q); ++i)
- matrix_foreach_in_row(pi->Q, i, e) {
- int val;
- if (e->col >= e->row)
- break;
- val = e->val + matrix_get(pi->Q, e->col, e->row); /* the transposed entry */
- 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);
- 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);
- }
-
- fprintf(out, "ENDATA\n");
- fclose(out);
-}
-#endif
-
-#ifdef DO_SOLVE
-/**
- * Invoke an external solver
- */
-static void pi_solve_ilp(problem_instance_t *pi) {
- FILE *out, *pwfile;
- char passwd[128];
-
- DBG((dbg, LEVEL_1, "Solving with CPLEX@RZ...\n"));
- /* write command file for CPLEX */
- out = ffopen(pi->co->name, "cmd", "wt");
- fprintf(out, "set logfile %s.sol\n", pi->co->name);
-#ifdef DUMP_MILP
- fprintf(out, "read %s.milp mps\n", pi->co->name);
-#endif
-#ifdef DUMP_MIQP
- fprintf(out, "read %s.miqp mps\n", pi->co->name);
-#endif
- fprintf(out, "read %s.mst\n", pi->co->name);
- fprintf(out, "set mip strategy mipstart 1\n");
- fprintf(out, "set mip emphasis 3\n");
- fprintf(out, "optimize\n");
- fprintf(out, "display solution variables 1-%d\n", pi->x_dim);
- fprintf(out, "set logfile cplex.log\n");
- fprintf(out, "quit\n");
- fclose(out);
-
- /* write expect-file for copying problem to RZ */
- pwfile = fopen(SSH_PASSWD_FILE, "rt");
- fgets(passwd, sizeof(passwd), pwfile);
- fclose(pwfile);
-
- out = ffopen(EXPECT_FILENAME, "exp", "wt");
- fprintf(out, "#! /usr/bin/expect\n");
- 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 */
- fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd);
-
- fprintf(out, "spawn ssh %s \"./cplex90 < %s.cmd\"\n", SSH_USER_HOST, pi->co->name); /* solve */
- fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd);
-
- fprintf(out, "spawn scp %s:%s.sol .\n", SSH_USER_HOST, pi->co->name); /*copy back solution */
- fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd);
-
- fprintf(out, "spawn ssh %s ./dell\n", SSH_USER_HOST); /* clean files on server */
- fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd);
- fclose(out);
-
- /* call the expect script */
- chmod(EXPECT_FILENAME ".exp", 0700);
- system(EXPECT_FILENAME ".exp");