nsz Git - libfirm/blob - ir/lpp/lpp_cplex.c

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @author  Daniel Grund
   9  */
  10 #include "config.h"
  11
  12 #include "lpp_cplex.h"
  13 #include "error.h"
  14
  15 #ifdef WITH_CPLEX
  16
  17 #include <stdio.h>
  18 #include <stdlib.h>
  19 #include <assert.h>
  20 #include <ilcplex/cplex.h>
  21
  22 #include "obst.h"
  23 #include "stat_timing.h"
  24 #include "sp_matrix.h"
  25
  26 static char cpx_cst_encoding[4] = "?ELG";
  27 static char cpx_var_encoding[4] = "??CB";
  28
  29 typedef struct _cpx_t {
  30         lpp_t *lpp;
  31         CPXENVptr env;
  32         CPXLPptr prob;
  33         int status;
  34         char buf[1024];
  35 } cpx_t;
  36
  37 static void chk_cpx_err(cpx_t *cpx)
  38 {
  39         if (cpx->status) {
  40                 if (CPXgeterrorstring(cpx->env, cpx->status, cpx->buf))
  41                         printf("%s", cpx->buf);
  42                 else
  43                         printf("Unknown CPLEX error\n");
  44                 assert(0);
  45         }
  46 }
  47
  48 static cpx_t *new_cpx(lpp_t *lpp)
  49 {
  50         cpx_t *cpx = XMALLOCZ(cpx_t);
  51         cpx->lpp = lpp;
  52         cpx->env = CPXopenCPLEX(&cpx->status);
  53         chk_cpx_err(cpx);
  54         cpx->prob = CPXcreateprob(cpx->env, &cpx->status, lpp->name);
  55         chk_cpx_err(cpx);
  56         CPXchgobjsen(cpx->env, cpx->prob, (lpp->opt_type == lpp_minimize)?1:-1);
  57         chk_cpx_err(cpx);
  58         if (lpp->log && CPXsetlogfile(cpx->env, lpp->log))
  59                 lpp->log = NULL;
  60         return cpx;
  61 }
  62
  63 static void free_cpx(cpx_t *cpx)
  64 {
  65         CPXfreeprob(cpx->env, &cpx->prob);
  66         CPXcloseCPLEX(&cpx->env);
  67         free(cpx);
  68 }
  69
  70 /**
  71  * Build CPLEX data structure from LPP matrix.
  72  * @note: The LPP matrix is freed after this step, to save memory.
  73  */
  74 static void cpx_construct(cpx_t *cpx)
  75 {
  76         int            i, o, sv_cnt;
  77         int            numcols, numrows, numentries;
  78         int            objsen, *matbeg, *matcnt, *matind, *indices;
  79         double        *obj, *rhs, *matval, *lb, *ub, *startv;
  80         char          *sense, *vartype;
  81         char         **colname, **rowname;
  82         struct obstack obst;
  83         lpp_t         *lpp = cpx->lpp;
  84
  85         numcols    = lpp->var_next-1;
  86         numrows    = lpp->cst_next-1;
  87         numentries = matrix_get_entries(lpp->m);
  88         objsen     = lpp->opt_type == lpp_minimize ? 1 : -1;
  89         obstack_init(&obst);
  90
  91         obj     = obstack_alloc(&obst, numcols * sizeof(*obj));
  92         lb      = obstack_alloc(&obst, numcols * sizeof(*lb));
  93         ub      = obstack_alloc(&obst, numcols * sizeof(*ub));
  94         colname = obstack_alloc(&obst, numcols * sizeof(*colname));
  95         rowname = obstack_alloc(&obst, numrows * sizeof(*rowname));
  96         vartype = obstack_alloc(&obst, numcols * sizeof(*vartype));
  97         indices = obstack_alloc(&obst, numcols * sizeof(*indices));
  98         startv  = obstack_alloc(&obst, numcols * sizeof(*startv));
  99         matbeg  = obstack_alloc(&obst, numcols * sizeof(*matbeg));
 100         matcnt  = obstack_alloc(&obst, numcols * sizeof(*matcnt));
 101         matind  = obstack_alloc(&obst, numentries * sizeof(*matind));
 102         matval  = obstack_alloc(&obst, numentries * sizeof(*matval));
 103         rhs     = obstack_alloc(&obst, numrows * sizeof(*rhs));
 104         sense   = obstack_alloc(&obst, numrows * sizeof(*sense));
 105
 106         o      = 0;
 107         sv_cnt = 0;
 108         /* fill the CPLEX matrix*/
 109         for (i = 0; i < numcols; ++i) {
 110                 lpp_name_t *curr_var = lpp->vars[1+i];
 111
 112                 obj[i] = matrix_get(lpp->m, 0, 1+i);
 113                 lb[i]  = 0.0;
 114                 ub[i]  = CPX_INFBOUND;
 115
 116                 colname[i] = (char*) curr_var->name;
 117                 vartype[i] = cpx_var_encoding[curr_var->type.var_type];
 118
 119                 if (curr_var->value_kind == lpp_value_start) {
 120                         indices[sv_cnt]  = i;
 121                         startv[sv_cnt++] = curr_var->value;
 122                 }
 123
 124                 matbeg[i] = o;
 125                 matcnt[i] = 0;
 126                 matrix_foreach_in_col(lpp->m, 1 + i, elem) {
 127                         if (elem->row == 0)
 128                                 continue;
 129                         matind[o] = elem->row-1;
 130                         matval[o] = elem->val;
 131                         matcnt[i]++;
 132                         o++;
 133                 }
 134         }
 135
 136         /* get constraint stuff (right hand side, type, name) */
 137         for (i = 0; i < numrows; ++i) {
 138                 lpp_name_t *curr_cst = lpp->csts[1 + i];
 139
 140                 rhs[i]     = matrix_get(lpp->m, 1 + i, 0);
 141                 sense[i]   = cpx_cst_encoding[curr_cst->type.cst_type];
 142                 rowname[i] = (char*) curr_cst->name;
 143         }
 144
 145         cpx->status = CPXcopylpwnames(cpx->env, cpx->prob,
 146                                                 numcols, numrows, objsen,
 147                                                 obj, rhs, sense,
 148                                                 matbeg, matcnt, matind, matval,
 149                                                 lb, ub, NULL,
 150                                                 colname, rowname);
 151         chk_cpx_err(cpx);
 152
 153         cpx->status = CPXcopyctype(cpx->env, cpx->prob, vartype);
 154         chk_cpx_err(cpx);
 155         cpx->status = CPXcopymipstart(cpx->env, cpx->prob, sv_cnt, indices, startv);
 156         chk_cpx_err(cpx);
 157
 158         obstack_free(&obst, NULL);
 159         lpp_free_matrix(lpp);
 160 }
 161
 162 static void cpx_solve(cpx_t *cpx)
 163 {
 164         int i, CPX_state, numcols;
 165         double *values;
 166         timing_ticks_t tvb;
 167         timing_ticks_t tva;
 168
 169         lpp_t *lpp = cpx->lpp;
 170         numcols = CPXgetnumcols(cpx->env, cpx->prob);
 171         chk_cpx_err(cpx);
 172
 173         /* set performance parameters */
 174         // CPXsetintparam(cpx->env, CPX_PARAM_MIPSTART, CPX_ON);
 175         CPXsetintparam(cpx->env, CPX_PARAM_MIPORDTYPE, CPX_MIPORDER_COST);
 176         /* output every search tree node */
 177         // CPXsetintparam(cpx->env, CPX_PARAM_MIPINTERVAL, 1);
 178
 179         /* experimental switches */
 180         // CPXsetintparam(cpx->env, CPX_PARAM_VARSEL, CPX_VARSEL_STRONG);
 181         // CPXsetdblparam(cpx->env, CPX_PARAM_BTTOL, 1.0);
 182         // CPXsetintparam(cpx->env, CPX_PARAM_BRDIR, CPX_BRDIR_UP);
 183
 184
 185         /* Set the time limit appropriately */
 186         if(lpp->time_limit_secs > 0.0)
 187                 CPXsetdblparam(cpx->env, CPX_PARAM_TILIM, lpp->time_limit_secs);
 188
 189         /*
 190          * If we have enough time, we instruct cplex to imply some
 191          * of its higher order magic to pursue the best solution
 192          */
 193         if(lpp->emphasis) {
 194           CPXsetintparam(cpx->env, CPX_PARAM_MIPEMPHASIS, lpp->emphasis);
 195         }
 196
 197         /*
 198          * If a bound of the objective function is supplied,
 199          * set it accordingly, dependign on minimization or maximization.
 200          */
 201         if(lpp->set_bound) {
 202                 CPXsetdblparam(cpx->env, (lpp->opt_type == lpp_minimize
 203                                         ? CPX_PARAM_OBJLLIM : CPX_PARAM_OBJULIM), lpp->bound);
 204         }
 205
 206         /* turn on the fancy messages :) */
 207         // CPXsetintparam (cpx->env, CPX_PARAM_SCRIND, CPX_ON);
 208
 209         /* solve */
 210         timing_ticks(tvb);
 211         cpx->status = CPXmipopt(cpx->env, cpx->prob);
 212         timing_ticks(tva);
 213         chk_cpx_err(cpx);
 214
 215         /* get solution status */
 216         CPX_state = CPXgetstat(cpx->env, cpx->prob);
 217         {
 218           char buf[512];
 219           CPXgetstatstring(cpx->env, CPX_state, buf);
 220           fprintf(stderr, "%s\n", buf);
 221         }
 222         switch (CPX_state) {
 223                 case CPXMIP_INFEASIBLE:
 224                 case CPX_STAT_INFEASIBLE:   lpp->sol_state = lpp_infeasible; break;
 225                 case CPXMIP_INForUNBD:
 226                 case CPX_STAT_INForUNBD:    lpp->sol_state = lpp_inforunb; break;
 227                 case CPXMIP_UNBOUNDED:
 228                 case CPX_STAT_UNBOUNDED:    lpp->sol_state = lpp_unbounded; break;
 229                 case CPXMIP_ABORT_FEAS:
 230                 case CPXMIP_FAIL_FEAS:
 231                 case CPXMIP_MEM_LIM_FEAS:
 232                 case CPXMIP_NODE_LIM_FEAS:
 233                 case CPXMIP_TIME_LIM_FEAS:  lpp->sol_state = lpp_feasible; break;
 234                 case CPXMIP_OPTIMAL:
 235                 case CPXMIP_OPTIMAL_TOL:    /* TODO: Is this ok? Read the docu more closely */
 236                 case CPX_STAT_OPTIMAL:      lpp->sol_state = lpp_optimal; break;
 237                 default:                    lpp->sol_state = lpp_unknown;
 238         }
 239
 240         /* get variable solution values */
 241         values = alloca(numcols * sizeof(*values));
 242         CPXgetmipx(cpx->env, cpx->prob, values, 0, numcols-1);
 243         chk_cpx_err(cpx);
 244         for(i=0; i<numcols; ++i) {
 245                 lpp->vars[1+i]->value = values[i];
 246                 lpp->vars[1+i]->value_kind = lpp_value_solution;
 247         }
 248
 249         /* Get the value of the objective function. */
 250         CPXgetmipobjval(cpx->env, cpx->prob, &lpp->objval);
 251         CPXgetbestobjval(cpx->env, cpx->prob, &lpp->best_bound);
 252
 253         /* get some statistics */
 254         timing_ticks_sub(tva, tvb);
 255         lpp->sol_time = timing_ticks_dbl(tva);
 256         lpp->iterations = CPXgetmipitcnt(cpx->env, cpx->prob);
 257 }
 258
 259 void lpp_solve_cplex(lpp_t *lpp)
 260 {
 261         cpx_t *cpx = new_cpx(lpp);
 262         cpx_construct(cpx);
 263         cpx_solve(cpx);
 264         free_cpx(cpx);
 265 }
 266
 267 #else
 268
 269 void lpp_solve_cplex(lpp_t *lpp)
 270 {
 271         (void)lpp;
 272         panic("libfirm compiled without cplex support");
 273 }
 274
 275 #endif