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