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