nsz Git - libfirm/blob - ir/be/lpp_local.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 #undef HAVE_CPLEX
   8
   9 #ifdef HAVE_CONFIG_H
  10 #include "config.h"
  11 #endif
  12 #include "lpp_local.h"
  13 #include <stdio.h>
  14
  15 #ifdef HAVE_CPLEX
  16 #include <alloca.h>
  17 #include <sys/time.h>
  18
  19 #include "xmalloc.h"
  20 #include "assert.h"
  21 #include "sp_matrix.h"
  22 #include "ilcplex/cplex.h"
  23
  24 #define LOGFILE stdout
  25 #define TIME_LIMIT 30 /* in sec. 0 for none */
  26
  27 static char cpx_cst_encoding[4] = {'?', 'E', 'L', 'G'};
  28 static char cpx_var_encoding[4] = {'?', '?', 'C', 'B'};
  29
  30 typedef struct _cpx_t {
  31         lpp_t *lpp;
  32         CPXENVptr env;
  33         CPXLPptr prob;
  34         int     status;
  35         char buf[1024];
  36 } cpx_t;
  37
  38 static INLINE void chk_cpx_err(cpx_t *cpx) {
  39         if (cpx->status) {
  40                 if (CPXgeterrorstring(cpx->env, cpx->status, cpx->buf))
  41                         printf(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         cpx_t *cpx = xcalloc(1, sizeof(*cpx));
  50         cpx->lpp = lpp;
  51         cpx->env = CPXopenCPLEX(&cpx->status);
  52         chk_cpx_err(cpx);
  53         cpx->prob = CPXcreateprob(cpx->env, &cpx->status, lpp->name);
  54         chk_cpx_err(cpx);
  55         CPXchgobjsen(cpx->env, cpx->prob, (lpp->opt_type == minimize)?1:-1);
  56         chk_cpx_err(cpx);
  57         if (CPXsetlogfile(cpx->env, LOGFILE))
  58                 assert(0 && "Could not set logfile");
  59         return cpx;
  60 }
  61
  62 static void free_cpx(cpx_t *cpx) {
  63         CPXfreeprob(cpx->env, &cpx->prob);
  64         CPXcloseCPLEX(&cpx->env);
  65         free(cpx);
  66 }
  67
  68 static void cpx_construct(cpx_t *cpx) {
  69         const matrix_elem_t *elem;
  70         int i, o, sv_cnt, numcols, numrows, numentries, objsen, *matbeg, *matcnt, *matind, *indices;
  71         double *obj, *rhs, *matval, *lb, *ub, *startv;
  72         char *sense, *vartype, **colname;
  73         lpp_t *lpp = cpx->lpp;
  74
  75         numcols = lpp->var_next-1;
  76         numrows = lpp->cst_next-1;
  77         numentries = matrix_get_entries(lpp->m);
  78         objsen  = lpp->opt_type == minimize ? 1 : -1;
  79
  80         obj     = alloca(numcols * sizeof(*obj));
  81         lb      = alloca(numcols * sizeof(*lb));
  82         ub      = alloca(numcols * sizeof(*ub));
  83         colname = alloca(numcols * sizeof(*colname));
  84         vartype = alloca(numcols * sizeof(*vartype));
  85         indices = alloca(numcols * sizeof(*indices));
  86         startv  = alloca(numcols * sizeof(*startv));
  87         matbeg  = alloca(numcols * sizeof(*matbeg));
  88         matcnt  = alloca(numcols * sizeof(*matcnt));
  89         matind  = alloca(numentries * sizeof(*matind));
  90         matval  = alloca(numentries * sizeof(*matval));
  91         rhs     = alloca(numrows * sizeof(*rhs));
  92         sense   = alloca(numrows * sizeof(*sense));
  93
  94         o = 0;
  95         sv_cnt = 0;
  96         for(i=0; i<numcols; ++i) {
  97                 name_t *curr_var = lpp->vars[1+i];
  98                 obj[i] = matrix_get(lpp->m, 0, 1+i);
  99                 lb[i] = 0.0;
 100                 ub[i] = CPX_INFBOUND;
 101                 colname[i] = curr_var->name;
 102                 vartype[i] = cpx_var_encoding[curr_var->type.var_type];
 103                 if(curr_var->value_kind == value_start) {
 104                         indices[sv_cnt]  = i;
 105                         startv[sv_cnt++] = curr_var->value;
 106                 }
 107                 matbeg[i] = o;
 108                 matcnt[i] = 0;
 109                 matrix_foreach_in_col(lpp->m, 1+i, elem) {
 110                         if (elem->row == 0)
 111                                 continue;
 112                         matind[o] = elem->row-1;
 113                         matval[o] = elem->val;
 114                         matcnt[i]++;
 115                         o++;
 116                 }
 117         }
 118
 119         for(i=0; i<numrows; ++i) {
 120                 rhs[i]   = matrix_get(lpp->m, 1+i, 0);
 121                 sense[i] = cpx_cst_encoding[lpp->csts[1+i]->type.cst_type];
 122         }
 123
 124         cpx->status = CPXcopylpwnames(cpx->env, cpx->prob,
 125                                                 numcols, numrows, objsen,
 126                                                 obj, rhs, sense,
 127                                                 matbeg, matcnt, matind, matval,
 128                                                 lb, ub, NULL,
 129                                                 colname, NULL);
 130         chk_cpx_err(cpx);
 131         cpx->status = CPXcopyctype(cpx->env, cpx->prob, vartype);
 132         chk_cpx_err(cpx);
 133         cpx->status = CPXcopymipstart(cpx->env, cpx->prob, sv_cnt, indices, startv);
 134         chk_cpx_err(cpx);
 135 }
 136
 137 static void cpx_solve(cpx_t *cpx) {
 138         int i, CPX_state, numcols;
 139         double *values;
 140         struct timeval tvb, tva;
 141
 142         lpp_t *lpp = cpx->lpp;
 143         numcols = CPXgetnumcols(cpx->env, cpx->prob);
 144         chk_cpx_err(cpx);
 145
 146         /* set performance parameters */
 147         CPXsetintparam(cpx->env, CPX_PARAM_MIPSTART, CPX_ON);
 148         CPXsetintparam(cpx->env, CPX_PARAM_MIPEMPHASIS, CPX_MIPEMPHASIS_BESTBOUND);
 149         CPXsetintparam(cpx->env, CPX_PARAM_VARSEL, CPX_VARSEL_STRONG);
 150         if (TIME_LIMIT)
 151                 CPXsetdblparam(cpx->env, CPX_PARAM_TILIM, TIME_LIMIT);
 152
 153         /* solve */
 154         gettimeofday(&tvb, NULL);
 155         cpx->status = CPXmipopt(cpx->env, cpx->prob);
 156         gettimeofday(&tva, NULL);
 157         chk_cpx_err(cpx);
 158
 159         /* get solution status */
 160         CPX_state = CPXgetstat(cpx->env, cpx->prob);
 161         switch (CPX_state) {
 162                 case CPXMIP_INFEASIBLE:
 163                 case CPX_STAT_INFEASIBLE:       lpp->sol_state = infeasible; break;
 164                 case CPXMIP_INForUNBD:
 165                 case CPX_STAT_INForUNBD:        lpp->sol_state = inforunb; break;
 166                 case CPXMIP_UNBOUNDED:
 167                 case CPX_STAT_UNBOUNDED:        lpp->sol_state = unbounded; break;
 168                 case CPXMIP_ABORT_FEAS:
 169                 case CPXMIP_FAIL_FEAS:
 170                 case CPXMIP_MEM_LIM_FEAS:
 171                 case CPXMIP_NODE_LIM_FEAS:
 172                 case CPXMIP_TIME_LIM_FEAS:      lpp->sol_state = feasible; break;
 173                 case CPXMIP_OPTIMAL:
 174                 case CPX_STAT_OPTIMAL:          lpp->sol_state = optimal; break;
 175                 default:                                        lpp->sol_state = unknown;
 176         }
 177         assert(lpp->sol_state == optimal || lpp->sol_state == feasible);
 178
 179         /* get variable solution values */
 180         values = alloca(numcols * sizeof(*values));
 181         CPXgetmipx(cpx->env, cpx->prob, values, 0, numcols-1);
 182         chk_cpx_err(cpx);
 183         for(i=0; i<numcols; ++i) {
 184                 lpp->vars[1+i]->value = values[i];
 185                 lpp->vars[1+i]->value_kind = value_solution;
 186         }
 187
 188         /* get some statistics */
 189         lpp->sol_time = tva.tv_sec - tvb.tv_sec;
 190         lpp->iterations = CPXgetmipitcnt(cpx->env, cpx->prob);
 191 }
 192
 193 void lpp_solve_local(lpp_t *lpp) {
 194         cpx_t *cpx = new_cpx(lpp);
 195         cpx_construct(cpx);
 196         cpx_solve(cpx);
 197         free_cpx(cpx);
 198 }
 199
 200 #else
 201
 202 void lpp_solve_local(lpp_t *lpp) {
 203         fprintf(stderr, "CPLEX not available!\n");
 204 }
 205 #endif