2 * Copyright (C) 2005-2011 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @author Matthias Braun
27 #include "lpp_gurobi.h"
37 #include "sp_matrix.h"
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 };
42 typedef struct _gurobi_t {
48 static void check_gurobi_error(gurobi_t *grb, int error)
51 panic("gurobi error: %s", GRBgeterrormsg(grb->env));
55 static gurobi_t *new_gurobi(lpp_t *lpp)
59 gurobi_t *grb = XMALLOCZ(gurobi_t);
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
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...
73 error = GRBsetlogfile(grb->env, lpp->log);
74 check_gurobi_error(grb, error);
80 static void free_gurobi(gurobi_t *grb)
87 * Build CPLEX data structure from LPP matrix.
88 * @note: The LPP matrix is freed after this step, to save memory.
90 static void gurobi_construct(gurobi_t *grb)
92 const matrix_elem_t *elem;
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;
103 lpp_t *lpp = grb->lpp;
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;
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));
128 /* fill the CPLEX matrix*/
129 for (i = 0; i < numcols; ++i) {
130 lpp_name_t *curr_var = lpp->vars[1+i];
132 obj[i] = matrix_get(lpp->m, 0, 1+i);
135 colname[i] = (char*) curr_var->name;
136 vartype[i] = gurobi_var_encoding[curr_var->type.var_type];
139 if (curr_var->value_kind == lpp_value_start) {
140 panic("start values not supported in gurobi yet");
142 startv[sv_cnt++] = curr_var->value;
148 matrix_foreach_in_col(lpp->m, 1 + i, elem) {
151 matind[o] = elem->row-1;
152 matval[o] = elem->val;
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];
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;
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);
172 obstack_free(&obst, NULL);
173 lpp_free_matrix(lpp);
176 static void gurobi_solve(gurobi_t *grb)
178 lpp_t *lpp = grb->lpp;
182 int numcols = lpp->var_next-1;
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);
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);
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);
204 * If we have enough time, we instruct cplex to imply some
205 * of its higher order magic to pursue the best solution
208 /* not implemented */
212 * If a bound of the objective function is supplied,
213 * set it accordingly, dependign on minimization or maximization.
216 //panic("bound not implemented yet");
217 fprintf(stderr, "Warning: gurobi bound not implemented yet\n");
221 error = GRBoptimize(grb->model);
222 check_gurobi_error(grb, error);
224 /* get solution status */
225 error = GRBgetintattr(grb->model, GRB_INT_ATTR_STATUS, &optimstatus);
226 check_gurobi_error(grb, error);
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;
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,
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;
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,
253 check_gurobi_error(grb, error);
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;
261 error = GRBgetdblattr(grb->model, GRB_DBL_ATTR_RUNTIME, &lpp->sol_time);
262 check_gurobi_error(grb, error);
265 void lpp_solve_gurobi(lpp_t *lpp)
267 gurobi_t *grb = new_gurobi(lpp);
268 gurobi_construct(grb);