nsz Git - libfirm/blob - ir/lpp/lpp_gurobi.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  Matthias Braun
  23  */
  24 #include "config.h"
  25
  26 #ifdef WITH_GUROBI
  27 #include "lpp_gurobi.h"
  28
  29 #include <stdio.h>
  30 #include <stdlib.h>
  31
  32 #include "obst.h"
  33
  34 #include <gurobi_c.h>
  35
  36 #include "error.h"
  37 #include "sp_matrix.h"
  38
  39 static char gurobi_cst_encoding[4] = { 0, GRB_EQUAL, GRB_LESS_EQUAL, GRB_GREATER_EQUAL };
  40 static char gurobi_var_encoding[4] = { 0, 0, GRB_CONTINUOUS, GRB_BINARY };
  41
  42 typedef struct _gurobi_t {
  43         lpp_t *lpp;
  44         GRBenv *env;
  45         GRBmodel *model;
  46 } gurobi_t;
  47
  48 static void check_gurobi_error(gurobi_t *grb, int error)
  49 {
  50         if (error != 0) {
  51                 panic("gurobi error: %s", GRBgeterrormsg(grb->env));
  52         }
  53 }
  54
  55 static gurobi_t *new_gurobi(lpp_t *lpp)
  56 {
  57         int error;
  58
  59         gurobi_t *grb = XMALLOCZ(gurobi_t);
  60         grb->lpp = lpp;
  61         /* /tmp/firm_gurobi.log is a hack (see below) */
  62         error = GRBloadenv(&grb->env, "/tmp/firm_gurobi.log");
  63         check_gurobi_error(grb, error);
  64         /* Matze: do not set the FILE* for logging output. Because:
  65          *  a) the function is deprecated
  66          *  b) gurobi closes the FILE handle when it is done, which leads to
  67          *     very unexpected effects when you pass stdout or stderr as logging
  68          *     output.
  69          * The only thing gurobi sanely supports is giving a string with a filename
  70          * :-( ...so we use /tmp/firm_gurobi.log as a temporary measure...
  71          */
  72 #if 0
  73         error = GRBsetlogfile(grb->env, lpp->log);
  74         check_gurobi_error(grb, error);
  75 #endif
  76
  77         return grb;
  78 }
  79
  80 static void free_gurobi(gurobi_t *grb)
  81 {
  82         GRBfreeenv(grb->env);
  83         free(grb);
  84 }
  85
  86 /**
  87  * Build CPLEX data structure from LPP matrix.
  88  * @note: The LPP matrix is freed after this step, to save memory.
  89  */
  90 static void gurobi_construct(gurobi_t *grb)
  91 {
  92         const matrix_elem_t *elem;
  93         int                  i, o;
  94         //int                  sv_cnt;
  95         //int                 *indices;
  96         //double              *startv;
  97         int                  numcols, numrows, numentries;
  98         int                  objsen, *matbeg, *matcnt, *matind;
  99         double               *obj, *rhs, *matval, *lb;
 100         char                 *sense, *vartype;
 101         char                 **colname, **rowname;
 102         struct obstack       obst;
 103         lpp_t                *lpp = grb->lpp;
 104         int                  error;
 105
 106         numcols    = lpp->var_next-1;
 107         numrows    = lpp->cst_next-1;
 108         numentries = matrix_get_entries(lpp->m);
 109         objsen     = lpp->opt_type == lpp_minimize ? 1 : -1;
 110         obstack_init(&obst);
 111
 112         obj     = obstack_alloc(&obst, numcols * sizeof(*obj));
 113         lb      = obstack_alloc(&obst, numcols * sizeof(*lb));
 114         colname = obstack_alloc(&obst, numcols * sizeof(*colname));
 115         rowname = obstack_alloc(&obst, numrows * sizeof(*rowname));
 116         vartype = obstack_alloc(&obst, numcols * sizeof(*vartype));
 117         //indices = obstack_alloc(&obst, numcols * sizeof(*indices));
 118         //startv  = obstack_alloc(&obst, numcols * sizeof(*startv));
 119         matbeg  = obstack_alloc(&obst, numcols * sizeof(*matbeg));
 120         matcnt  = obstack_alloc(&obst, numcols * sizeof(*matcnt));
 121         matind  = obstack_alloc(&obst, numentries * sizeof(*matind));
 122         matval  = obstack_alloc(&obst, numentries * sizeof(*matval));
 123         rhs     = obstack_alloc(&obst, numrows * sizeof(*rhs));
 124         sense   = obstack_alloc(&obst, numrows * sizeof(*sense));
 125
 126         o      = 0;
 127         //sv_cnt = 0;
 128         /* fill the CPLEX matrix*/
 129         for (i = 0; i < numcols; ++i) {
 130                 lpp_name_t *curr_var = lpp->vars[1+i];
 131
 132                 obj[i] = matrix_get(lpp->m, 0, 1+i);
 133                 lb[i]  = 0.0;
 134
 135                 colname[i] = (char*) curr_var->name;
 136                 vartype[i] = gurobi_var_encoding[curr_var->type.var_type];
 137
 138 #if 0
 139                 if (curr_var->value_kind == lpp_value_start) {
 140                         panic("start values not supported in gurobi yet");
 141                         indices[sv_cnt]  = i;
 142                         startv[sv_cnt++] = curr_var->value;
 143                 }
 144 #endif
 145
 146                 matbeg[i] = o;
 147                 matcnt[i] = 0;
 148                 matrix_foreach_in_col(lpp->m, 1 + i, elem) {
 149                         if (elem->row == 0)
 150                                 continue;
 151                         matind[o] = elem->row-1;
 152                         matval[o] = elem->val;
 153                         matcnt[i]++;
 154                         o++;
 155                 }
 156         }
 157
 158         /* get constraint stuff (right hand side, type, name) */
 159         for (i = 0; i < numrows; ++i) {
 160                 lpp_name_t *curr_cst = lpp->csts[1 + i];
 161
 162                 rhs[i]     = matrix_get(lpp->m, 1 + i, 0);
 163                 sense[i]   = gurobi_cst_encoding[curr_cst->type.cst_type];
 164                 rowname[i] = (char*) curr_cst->name;
 165         }
 166
 167         error = GRBloadmodel(grb->env, &grb->model, lpp->name, numcols, numrows,
 168                              objsen, 0, obj, sense, rhs, matbeg, matcnt, matind,
 169                              matval, lb, NULL, vartype, colname, rowname);
 170         check_gurobi_error(grb, error);
 171
 172         obstack_free(&obst, NULL);
 173         lpp_free_matrix(lpp);
 174 }
 175
 176 static void gurobi_solve(gurobi_t *grb)
 177 {
 178         lpp_t *lpp = grb->lpp;
 179         int i;
 180         int optimstatus;
 181         int error;
 182         int numcols = lpp->var_next-1;
 183         double *values;
 184         double  iterations;
 185
 186         /* set performance parameters */
 187         // CPXsetintparam(grb->env, CPX_PARAM_MIPSTART, CPX_ON);
 188         //CPXsetintparam(grb->env, CPX_PARAM_MIPORDTYPE, CPX_MIPORDER_COST);
 189         /* output every search tree node */
 190         // CPXsetintparam(grb->env, CPX_PARAM_MIPINTERVAL, 1);
 191
 192         /* experimental switches */
 193         // CPXsetintparam(grb->env, CPX_PARAM_VARSEL, CPX_VARSEL_STRONG);
 194         // CPXsetdblparam(grb->env, CPX_PARAM_BTTOL, 1.0);
 195         // CPXsetintparam(grb->env, CPX_PARAM_BRDIR, CPX_BRDIR_UP);
 196
 197         /* Set the time limit appropriately */
 198         if(lpp->time_limit_secs > 0.0) {
 199                 error = GRBsetdblparam(grb->env, GRB_DBL_PAR_TIMELIMIT, lpp->time_limit_secs);
 200                 check_gurobi_error(grb, error);
 201         }
 202
 203         /*
 204          * If we have enough time, we instruct cplex to imply some
 205          * of its higher order magic to pursue the best solution
 206          */
 207         if(lpp->emphasis) {
 208                 /* not implemented */
 209         }
 210
 211         /*
 212          * If a bound of the objective function is supplied,
 213          * set it accordingly, dependign on minimization or maximization.
 214          */
 215         if(lpp->set_bound) {
 216                 //panic("bound not implemented yet");
 217                 fprintf(stderr, "Warning: gurobi bound not implemented yet\n");
 218         }
 219
 220         /* solve */
 221         error = GRBoptimize(grb->model);
 222         check_gurobi_error(grb, error);
 223
 224         /* get solution status */
 225         error = GRBgetintattr(grb->model, GRB_INT_ATTR_STATUS, &optimstatus);
 226         check_gurobi_error(grb, error);
 227
 228         switch (optimstatus) {
 229         case GRB_OPTIMAL:           lpp->sol_state = lpp_optimal; break;
 230         case GRB_INFEASIBLE:        lpp->sol_state = lpp_infeasible; break;
 231         case GRB_INF_OR_UNBD:       lpp->sol_state = lpp_inforunb; break;
 232         case GRB_UNBOUNDED:         lpp->sol_state = lpp_unbounded; break;
 233         /* TODO: is this correct? */
 234         default:                    lpp->sol_state = lpp_feasible; break;
 235         }
 236
 237         if (lpp->sol_state >= lpp_feasible) {
 238                 /* get variable solution values */
 239                 values = alloca(numcols * sizeof(*values));
 240                 error = GRBgetdblattrarray(grb->model, GRB_DBL_ATTR_X, 0, numcols,
 241                                            values);
 242                 check_gurobi_error(grb, error);
 243                 for(i=0; i<numcols; ++i) {
 244                         lpp->vars[1+i]->value      = values[i];
 245                         lpp->vars[1+i]->value_kind = lpp_value_solution;
 246                 }
 247
 248                 /* Get the value of the objective function. */
 249                 error = GRBgetdblattr(grb->model, GRB_DBL_ATTR_OBJVAL, &lpp->objval);
 250                 check_gurobi_error(grb, error);
 251                 error = GRBgetdblattr(grb->model , GRB_DBL_ATTR_OBJBOUND,
 252                                       &lpp->best_bound);
 253                 check_gurobi_error(grb, error);
 254         }
 255
 256         /* get some statistics */
 257         error = GRBgetdblattr(grb->model, GRB_DBL_ATTR_ITERCOUNT, &iterations);
 258         check_gurobi_error(grb, error);
 259         lpp->iterations = (unsigned) iterations;
 260
 261         error = GRBgetdblattr(grb->model, GRB_DBL_ATTR_RUNTIME, &lpp->sol_time);
 262         check_gurobi_error(grb, error);
 263 }
 264
 265 void lpp_solve_gurobi(lpp_t *lpp)
 266 {
 267         gurobi_t *grb = new_gurobi(lpp);
 268         gurobi_construct(grb);
 269         gurobi_solve(grb);
 270         free_gurobi(grb);
 271 }
 272
 273 #endif