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