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

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