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