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

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