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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @author  Matthias Braun
   9  */
  10 #include "config.h"
  11
  12 #include "lpp_gurobi.h"
  13 #include "error.h"
  14
  15 #ifdef WITH_GUROBI
  16
  17 #include <stdio.h>
  18 #include <stdlib.h>
  19 #include <math.h>
  20
  21 #include "obst.h"
  22
  23 #include <gurobi_c.h>
  24
  25 #include "sp_matrix.h"
  26
  27 static char gurobi_cst_encoding[4] = { 0, GRB_EQUAL, GRB_LESS_EQUAL, GRB_GREATER_EQUAL };
  28 static char gurobi_var_encoding[4] = { 0, 0, GRB_CONTINUOUS, GRB_BINARY };
  29
  30 typedef struct _gurobi_t {
  31         lpp_t *lpp;
  32         GRBenv *env;
  33         GRBenv *modelenv;
  34         GRBmodel *model;
  35 } gurobi_t;
  36
  37 static void check_gurobi_error(gurobi_t *grb, int error)
  38 {
  39         if (error != 0) {
  40                 panic("gurobi error: %s", GRBgeterrormsg(grb->env));
  41         }
  42 }
  43
  44 static gurobi_t *new_gurobi(lpp_t *lpp)
  45 {
  46         int error;
  47
  48         gurobi_t *grb = XMALLOCZ(gurobi_t);
  49         grb->lpp = lpp;
  50         /* /tmp/firm_gurobi.log is a hack (see below) */
  51         error = GRBloadenv(&grb->env, "/tmp/firm_gurobi.log");
  52         check_gurobi_error(grb, error);
  53         /* Matze: do not set the FILE* for logging output. Because:
  54          *  a) the function is deprecated
  55          *  b) gurobi closes the FILE handle when it is done, which leads to
  56          *     very unexpected effects when you pass stdout or stderr as logging
  57          *     output.
  58          * The only thing gurobi sanely supports is giving a string with a filename
  59          * :-( ...so we use /tmp/firm_gurobi.log as a temporary measure...
  60          */
  61         if (lpp->log != stdout && lpp->log != stderr) {
  62                 error = GRBsetintparam(grb->env, GRB_INT_PAR_OUTPUTFLAG, 0);
  63                 check_gurobi_error(grb, error);
  64         }
  65
  66         return grb;
  67 }
  68
  69 static void free_gurobi(gurobi_t *grb)
  70 {
  71         GRBfreemodel(grb->model);
  72         GRBfreeenv(grb->env);
  73         free(grb);
  74 }
  75
  76 /**
  77  * Build CPLEX data structure from LPP matrix.
  78  * @note: The LPP matrix is freed after this step, to save memory.
  79  */
  80 static void gurobi_construct(gurobi_t *grb)
  81 {
  82         int            i, o;
  83         //int            sv_cnt;
  84         //int           *indices;
  85         //double        *startv;
  86         int            numcols, numrows, numentries;
  87         int            objsen, *matbeg, *matcnt, *matind;
  88         double        *obj, *rhs, *matval, *lb;
  89         char          *sense, *vartype;
  90         char         **colname, **rowname;
  91         struct obstack obst;
  92         lpp_t         *lpp = grb->lpp;
  93         int            error;
  94
  95         numcols    = lpp->var_next-1;
  96         numrows    = lpp->cst_next-1;
  97         numentries = matrix_get_entries(lpp->m);
  98         objsen     = lpp->opt_type == lpp_minimize ? 1 : -1;
  99         obstack_init(&obst);
 100
 101         obj     = obstack_alloc(&obst, numcols * sizeof(*obj));
 102         lb      = obstack_alloc(&obst, numcols * sizeof(*lb));
 103         colname = obstack_alloc(&obst, numcols * sizeof(*colname));
 104         rowname = obstack_alloc(&obst, numrows * sizeof(*rowname));
 105         vartype = obstack_alloc(&obst, numcols * sizeof(*vartype));
 106         //indices = obstack_alloc(&obst, numcols * sizeof(*indices));
 107         //startv  = obstack_alloc(&obst, numcols * sizeof(*startv));
 108         matbeg  = obstack_alloc(&obst, numcols * sizeof(*matbeg));
 109         matcnt  = obstack_alloc(&obst, numcols * sizeof(*matcnt));
 110         matind  = obstack_alloc(&obst, numentries * sizeof(*matind));
 111         matval  = obstack_alloc(&obst, numentries * sizeof(*matval));
 112         rhs     = obstack_alloc(&obst, numrows * sizeof(*rhs));
 113         sense   = obstack_alloc(&obst, numrows * sizeof(*sense));
 114
 115         o      = 0;
 116         //sv_cnt = 0;
 117         /* fill the CPLEX matrix*/
 118         for (i = 0; i < numcols; ++i) {
 119                 lpp_name_t *curr_var = lpp->vars[1+i];
 120
 121                 obj[i] = matrix_get(lpp->m, 0, 1+i);
 122                 lb[i]  = 0.0;
 123
 124                 colname[i] = (char*) curr_var->name;
 125                 vartype[i] = gurobi_var_encoding[curr_var->type.var_type];
 126
 127                 matbeg[i] = o;
 128                 matcnt[i] = 0;
 129                 matrix_foreach_in_col(lpp->m, 1 + i, elem) {
 130                         if (elem->row == 0)
 131                                 continue;
 132                         matind[o] = elem->row-1;
 133                         matval[o] = elem->val;
 134                         matcnt[i]++;
 135                         o++;
 136                 }
 137         }
 138
 139         /* get constraint stuff (right hand side, type, name) */
 140         for (i = 0; i < numrows; ++i) {
 141                 lpp_name_t *curr_cst = lpp->csts[1 + i];
 142
 143                 rhs[i]     = matrix_get(lpp->m, 1 + i, 0);
 144                 sense[i]   = gurobi_cst_encoding[curr_cst->type.cst_type];
 145                 rowname[i] = (char*) curr_cst->name;
 146         }
 147
 148         error = GRBloadmodel(grb->env, &grb->model, lpp->name, numcols, numrows,
 149                              objsen, 0, obj, sense, rhs, matbeg, matcnt, matind,
 150                              matval, lb, NULL, vartype, colname, rowname);
 151         check_gurobi_error(grb, error);
 152         grb->modelenv = GRBgetenv(grb->model);
 153
 154         obstack_free(&obst, NULL);
 155         lpp_free_matrix(lpp);
 156 }
 157
 158 static void gurobi_solve(gurobi_t *grb)
 159 {
 160         lpp_t *lpp = grb->lpp;
 161         int i;
 162         int optimstatus;
 163         int error;
 164         int numcols = lpp->var_next-1;
 165         double *values;
 166         double  iterations;
 167
 168         /* Set the time limit appropriately */
 169         if(lpp->time_limit_secs > 0.0) {
 170                 error = GRBsetdblparam(grb->modelenv, GRB_DBL_PAR_TIMELIMIT, lpp->time_limit_secs);
 171                 check_gurobi_error(grb, error);
 172         }
 173
 174         /* solve */
 175         error = GRBoptimize(grb->model);
 176         check_gurobi_error(grb, error);
 177
 178         /* get solution status */
 179         error = GRBgetintattr(grb->model, GRB_INT_ATTR_STATUS, &optimstatus);
 180         check_gurobi_error(grb, error);
 181
 182         switch (optimstatus) {
 183         case GRB_OPTIMAL:           lpp->sol_state = lpp_optimal; break;
 184         case GRB_INFEASIBLE:        lpp->sol_state = lpp_infeasible; break;
 185         case GRB_INF_OR_UNBD:       lpp->sol_state = lpp_inforunb; break;
 186         case GRB_UNBOUNDED:         lpp->sol_state = lpp_unbounded; break;
 187         /* TODO: is this correct? */
 188         default:                    lpp->sol_state = lpp_feasible; break;
 189         }
 190
 191         if (lpp->sol_state >= lpp_feasible) {
 192                 /* get variable solution values */
 193                 values = alloca(numcols * sizeof(*values));
 194                 error = GRBgetdblattrarray(grb->model, GRB_DBL_ATTR_X, 0, numcols,
 195                                            values);
 196                 check_gurobi_error(grb, error);
 197                 for(i=0; i<numcols; ++i) {
 198                         lpp->vars[1+i]->value      = values[i];
 199                         lpp->vars[1+i]->value_kind = lpp_value_solution;
 200                 }
 201
 202                 /* Get the value of the objective function. */
 203                 error = GRBgetdblattr(grb->model, GRB_DBL_ATTR_OBJVAL, &lpp->objval);
 204                 check_gurobi_error(grb, error);
 205                 error = GRBgetdblattr(grb->model , GRB_DBL_ATTR_OBJBOUND,
 206                                       &lpp->best_bound);
 207                 if (error != 0) {
 208                         lpp->best_bound = FP_NAN;
 209                 }
 210         }
 211
 212         /* get some statistics */
 213         error = GRBgetdblattr(grb->model, GRB_DBL_ATTR_ITERCOUNT, &iterations);
 214         check_gurobi_error(grb, error);
 215         lpp->iterations = (unsigned) iterations;
 216
 217         error = GRBgetdblattr(grb->model, GRB_DBL_ATTR_RUNTIME, &lpp->sol_time);
 218         check_gurobi_error(grb, error);
 219 }
 220
 221 void lpp_solve_gurobi(lpp_t *lpp)
 222 {
 223         gurobi_t *grb = new_gurobi(lpp);
 224         gurobi_construct(grb);
 225         gurobi_solve(grb);
 226         free_gurobi(grb);
 227 }
 228
 229 #else
 230
 231 void lpp_solve_gurobi(lpp_t *lpp)
 232 {
 233         (void)lpp;
 234 }
 235
 236 #endif