nsz Git - libfirm/blob - ir/lpp/lpp_cplex.c

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