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 #define 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 #undef LOGFILE //stdout
  25 #define TIME_LIMIT 5*60 /* 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 #ifdef LOGFILE
  58         if (CPXsetlogfile(cpx->env, LOGFILE))
  59                 assert(0 && "Could not set logfile");
  60 #endif
  61         return cpx;
  62 }
  63
  64 static void free_cpx(cpx_t *cpx) {
  65         CPXfreeprob(cpx->env, &cpx->prob);
  66         CPXcloseCPLEX(&cpx->env);
  67         free(cpx);
  68 }
  69
  70 static void cpx_construct(cpx_t *cpx) {
  71         const matrix_elem_t *elem;
  72         int i, o, sv_cnt, numcols, numrows, numentries, objsen, *matbeg, *matcnt, *matind, *indices;
  73         double *obj, *rhs, *matval, *lb, *ub, *startv;
  74         char *sense, *vartype, **colname;
  75         lpp_t *lpp = cpx->lpp;
  76
  77         numcols = lpp->var_next-1;
  78         numrows = lpp->cst_next-1;
  79         numentries = matrix_get_entries(lpp->m);
  80         objsen  = lpp->opt_type == minimize ? 1 : -1;
  81
  82         obj     = alloca(numcols * sizeof(*obj));
  83         lb      = alloca(numcols * sizeof(*lb));
  84         ub      = alloca(numcols * sizeof(*ub));
  85         colname = alloca(numcols * sizeof(*colname));
  86         vartype = alloca(numcols * sizeof(*vartype));
  87         indices = alloca(numcols * sizeof(*indices));
  88         startv  = alloca(numcols * sizeof(*startv));
  89         matbeg  = alloca(numcols * sizeof(*matbeg));
  90         matcnt  = alloca(numcols * sizeof(*matcnt));
  91         matind  = alloca(numentries * sizeof(*matind));
  92         matval  = alloca(numentries * sizeof(*matval));
  93         rhs     = alloca(numrows * sizeof(*rhs));
  94         sense   = alloca(numrows * sizeof(*sense));
  95
  96         o = 0;
  97         sv_cnt = 0;
  98         for(i=0; i<numcols; ++i) {
  99                 name_t *curr_var = lpp->vars[1+i];
 100                 obj[i] = matrix_get(lpp->m, 0, 1+i);
 101                 lb[i] = 0.0;
 102                 ub[i] = CPX_INFBOUND;
 103                 colname[i] = curr_var->name;
 104                 vartype[i] = cpx_var_encoding[curr_var->type.var_type];
 105                 if(curr_var->value_kind == value_start) {
 106                         indices[sv_cnt]  = i;
 107                         startv[sv_cnt++] = curr_var->value;
 108                 }
 109                 matbeg[i] = o;
 110                 matcnt[i] = 0;
 111                 matrix_foreach_in_col(lpp->m, 1+i, elem) {
 112                         if (elem->row == 0)
 113                                 continue;
 114                         matind[o] = elem->row-1;
 115                         matval[o] = elem->val;
 116                         matcnt[i]++;
 117                         o++;
 118                 }
 119         }
 120
 121         for(i=0; i<numrows; ++i) {
 122                 rhs[i]   = matrix_get(lpp->m, 1+i, 0);
 123                 sense[i] = cpx_cst_encoding[lpp->csts[1+i]->type.cst_type];
 124         }
 125
 126         cpx->status = CPXcopylpwnames(cpx->env, cpx->prob,
 127                                                 numcols, numrows, objsen,
 128                                                 obj, rhs, sense,
 129                                                 matbeg, matcnt, matind, matval,
 130                                                 lb, ub, NULL,
 131                                                 colname, NULL);
 132         chk_cpx_err(cpx);
 133         cpx->status = CPXcopyctype(cpx->env, cpx->prob, vartype);
 134         chk_cpx_err(cpx);
 135         cpx->status = CPXcopymipstart(cpx->env, cpx->prob, sv_cnt, indices, startv);
 136         chk_cpx_err(cpx);
 137 }
 138
 139 static void cpx_solve(cpx_t *cpx) {
 140         int i, CPX_state, numcols;
 141         double *values;
 142         struct timeval tvb, tva;
 143
 144         lpp_t *lpp = cpx->lpp;
 145         numcols = CPXgetnumcols(cpx->env, cpx->prob);
 146         chk_cpx_err(cpx);
 147
 148         /* set performance parameters */
 149         CPXsetintparam(cpx->env, CPX_PARAM_MIPSTART, CPX_ON);
 150         CPXsetintparam(cpx->env, CPX_PARAM_MIPEMPHASIS, CPX_MIPEMPHASIS_BESTBOUND);
 151         CPXsetintparam(cpx->env, CPX_PARAM_VARSEL, CPX_VARSEL_STRONG);
 152         if (TIME_LIMIT)
 153                 CPXsetdblparam(cpx->env, CPX_PARAM_TILIM, TIME_LIMIT);
 154
 155         /* solve */
 156         gettimeofday(&tvb, NULL);
 157         cpx->status = CPXmipopt(cpx->env, cpx->prob);
 158         gettimeofday(&tva, NULL);
 159         chk_cpx_err(cpx);
 160
 161         /* get solution status */
 162         CPX_state = CPXgetstat(cpx->env, cpx->prob);
 163         switch (CPX_state) {
 164                 case CPXMIP_INFEASIBLE:
 165                 case CPX_STAT_INFEASIBLE:       lpp->sol_state = infeasible; break;
 166                 case CPXMIP_INForUNBD:
 167                 case CPX_STAT_INForUNBD:        lpp->sol_state = inforunb; break;
 168                 case CPXMIP_UNBOUNDED:
 169                 case CPX_STAT_UNBOUNDED:        lpp->sol_state = unbounded; break;
 170                 case CPXMIP_ABORT_FEAS:
 171                 case CPXMIP_FAIL_FEAS:
 172                 case CPXMIP_MEM_LIM_FEAS:
 173                 case CPXMIP_NODE_LIM_FEAS:
 174                 case CPXMIP_TIME_LIM_FEAS:      lpp->sol_state = feasible; break;
 175                 case CPXMIP_OPTIMAL:
 176                 case CPX_STAT_OPTIMAL:          lpp->sol_state = optimal; break;
 177                 default:                                        lpp->sol_state = unknown;
 178         }
 179         assert(lpp->sol_state == optimal || lpp->sol_state == feasible);
 180
 181         /* get variable solution values */
 182         values = alloca(numcols * sizeof(*values));
 183         CPXgetmipx(cpx->env, cpx->prob, values, 0, numcols-1);
 184         chk_cpx_err(cpx);
 185         for(i=0; i<numcols; ++i) {
 186                 lpp->vars[1+i]->value = values[i];
 187                 lpp->vars[1+i]->value_kind = value_solution;
 188         }
 189
 190         /* get some statistics */
 191         lpp->sol_time = tva.tv_sec - tvb.tv_sec;
 192         lpp->iterations = CPXgetmipitcnt(cpx->env, cpx->prob);
 193 }
 194
 195 void lpp_solve_local(lpp_t *lpp) {
 196         cpx_t *cpx = new_cpx(lpp);
 197         cpx_construct(cpx);
 198         cpx_solve(cpx);
 199         free_cpx(cpx);
 200 }
 201
 202 #else
 203
 204 void lpp_solve_local(lpp_t *lpp) {
 205         fprintf(stderr, "CPLEX not available!\n");
 206 }
 207 #endif