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 Daniel Grund
23 */
24 #include "config.h"
25
26 #ifdef WITH_CPLEX
27 #include "lpp_cplex.h"
28
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include <assert.h>
32 #include <ilcplex/cplex.h>
33
34 #include "obst.h"
35 #include "stat_timing.h"
36 #include "sp_matrix.h"
37
38 static char cpx_cst_encoding[4] = "?ELG";
39 static char cpx_var_encoding[4] = "??CB";
40
41 typedef struct _cpx_t {
42 lpp_t *lpp;
43 CPXENVptr env;
44 CPXLPptr prob;
45 int status;
46 char buf[1024];
47 } cpx_t;
48
chk_cpx_err(cpx_t * cpx)49 static void chk_cpx_err(cpx_t *cpx)
50 {
51 if (cpx->status) {
52 if (CPXgeterrorstring(cpx->env, cpx->status, cpx->buf))
53 printf("%s", cpx->buf);
54 else
55 printf("Unknown CPLEX error\n");
56 assert(0);
57 }
58 }
59
new_cpx(lpp_t * lpp)60 static cpx_t *new_cpx(lpp_t *lpp)
61 {
62 cpx_t *cpx = XMALLOCZ(cpx_t);
63 cpx->lpp = lpp;
64 cpx->env = CPXopenCPLEX(&cpx->status);
65 chk_cpx_err(cpx);
66 cpx->prob = CPXcreateprob(cpx->env, &cpx->status, lpp->name);
67 chk_cpx_err(cpx);
68 CPXchgobjsen(cpx->env, cpx->prob, (lpp->opt_type == lpp_minimize)?1:-1);
69 chk_cpx_err(cpx);
70 if (lpp->log && CPXsetlogfile(cpx->env, lpp->log))
71 lpp->log = NULL;
72 return cpx;
73 }
74
free_cpx(cpx_t * cpx)75 static void free_cpx(cpx_t *cpx)
76 {
77 CPXfreeprob(cpx->env, &cpx->prob);
78 CPXcloseCPLEX(&cpx->env);
79 free(cpx);
80 }
81
82 /**
83 * Build CPLEX data structure from LPP matrix.
84 * @note: The LPP matrix is freed after this step, to save memory.
85 */
cpx_construct(cpx_t * cpx)86 static void cpx_construct(cpx_t *cpx)
87 {
88 int i, o, sv_cnt;
89 int numcols, numrows, numentries;
90 int objsen, *matbeg, *matcnt, *matind, *indices;
91 double *obj, *rhs, *matval, *lb, *ub, *startv;
92 char *sense, *vartype;
93 char **colname, **rowname;
94 struct obstack obst;
95 lpp_t *lpp = cpx->lpp;
96
97 numcols = lpp->var_next-1;
98 numrows = lpp->cst_next-1;
99 numentries = matrix_get_entries(lpp->m);
100 objsen = lpp->opt_type == lpp_minimize ? 1 : -1;
101 obstack_init(&obst);
102
103 obj = obstack_alloc(&obst, numcols * sizeof(*obj));
104 lb = obstack_alloc(&obst, numcols * sizeof(*lb));
105 ub = obstack_alloc(&obst, numcols * sizeof(*ub));
106 colname = obstack_alloc(&obst, numcols * sizeof(*colname));
107 rowname = obstack_alloc(&obst, numrows * sizeof(*rowname));
108 vartype = obstack_alloc(&obst, numcols * sizeof(*vartype));
109 indices = obstack_alloc(&obst, numcols * sizeof(*indices));
110 startv = obstack_alloc(&obst, numcols * sizeof(*startv));
111 matbeg = obstack_alloc(&obst, numcols * sizeof(*matbeg));
112 matcnt = obstack_alloc(&obst, numcols * sizeof(*matcnt));
113 matind = obstack_alloc(&obst, numentries * sizeof(*matind));
114 matval = obstack_alloc(&obst, numentries * sizeof(*matval));
115 rhs = obstack_alloc(&obst, numrows * sizeof(*rhs));
116 sense = obstack_alloc(&obst, numrows * sizeof(*sense));
117
118 o = 0;
119 sv_cnt = 0;
120 /* fill the CPLEX matrix*/
121 for (i = 0; i < numcols; ++i) {
122 lpp_name_t *curr_var = lpp->vars[1+i];
123
124 obj[i] = matrix_get(lpp->m, 0, 1+i);
125 lb[i] = 0.0;
126 ub[i] = CPX_INFBOUND;
127
128 colname[i] = (char*) curr_var->name;
129 vartype[i] = cpx_var_encoding[curr_var->type.var_type];
130
131 if (curr_var->value_kind == lpp_value_start) {
132 indices[sv_cnt] = i;
133 startv[sv_cnt++] = curr_var->value;
134 }
135
136 matbeg[i] = o;
137 matcnt[i] = 0;
138 matrix_foreach_in_col(lpp->m, 1 + i, elem) {
139 if (elem->row == 0)
140 continue;
141 matind[o] = elem->row-1;
142 matval[o] = elem->val;
143 matcnt[i]++;
144 o++;
145 }
146 }
147
148 /* get constraint stuff (right hand side, type, name) */
149 for (i = 0; i < numrows; ++i) {
150 lpp_name_t *curr_cst = lpp->csts[1 + i];
151
152 rhs[i] = matrix_get(lpp->m, 1 + i, 0);
153 sense[i] = cpx_cst_encoding[curr_cst->type.cst_type];
154 rowname[i] = (char*) curr_cst->name;
155 }
156
157 cpx->status = CPXcopylpwnames(cpx->env, cpx->prob,
158 numcols, numrows, objsen,
159 obj, rhs, sense,
160 matbeg, matcnt, matind, matval,
161 lb, ub, NULL,
162 colname, rowname);
163 chk_cpx_err(cpx);
164
165 cpx->status = CPXcopyctype(cpx->env, cpx->prob, vartype);
166 chk_cpx_err(cpx);
167 cpx->status = CPXcopymipstart(cpx->env, cpx->prob, sv_cnt, indices, startv);
168 chk_cpx_err(cpx);
169
170 obstack_free(&obst, NULL);
171 lpp_free_matrix(lpp);
172 }
173
cpx_solve(cpx_t * cpx)174 static void cpx_solve(cpx_t *cpx)
175 {
176 int i, CPX_state, numcols;
177 double *values;
178 timing_ticks_t tvb;
179 timing_ticks_t tva;
180
181 lpp_t *lpp = cpx->lpp;
182 numcols = CPXgetnumcols(cpx->env, cpx->prob);
183 chk_cpx_err(cpx);
184
185 /* set performance parameters */
186 // CPXsetintparam(cpx->env, CPX_PARAM_MIPSTART, CPX_ON);
187 CPXsetintparam(cpx->env, CPX_PARAM_MIPORDTYPE, CPX_MIPORDER_COST);
188 /* output every search tree node */
189 // CPXsetintparam(cpx->env, CPX_PARAM_MIPINTERVAL, 1);
190
191 /* experimental switches */
192 // CPXsetintparam(cpx->env, CPX_PARAM_VARSEL, CPX_VARSEL_STRONG);
193 // CPXsetdblparam(cpx->env, CPX_PARAM_BTTOL, 1.0);
194 // CPXsetintparam(cpx->env, CPX_PARAM_BRDIR, CPX_BRDIR_UP);
195
196
197 /* Set the time limit appropriately */
198 if(lpp->time_limit_secs > 0.0)
199 CPXsetdblparam(cpx->env, CPX_PARAM_TILIM, lpp->time_limit_secs);
200
201 /*
202 * If we have enough time, we instruct cplex to imply some
203 * of its higher order magic to pursue the best solution
204 */
205 if(lpp->emphasis) {
206 CPXsetintparam(cpx->env, CPX_PARAM_MIPEMPHASIS, lpp->emphasis);
207 }
208
209 /*
210 * If a bound of the objective function is supplied,
211 * set it accordingly, dependign on minimization or maximization.
212 */
213 if(lpp->set_bound) {
214 CPXsetdblparam(cpx->env, (lpp->opt_type == lpp_minimize
215 ? CPX_PARAM_OBJLLIM : CPX_PARAM_OBJULIM), lpp->bound);
216 }
217
218 /* turn on the fancy messages :) */
219 // CPXsetintparam (cpx->env, CPX_PARAM_SCRIND, CPX_ON);
220
221 /* solve */
222 timing_ticks(tvb);
223 cpx->status = CPXmipopt(cpx->env, cpx->prob);
224 timing_ticks(tva);
225 chk_cpx_err(cpx);
226
227 /* get solution status */
228 CPX_state = CPXgetstat(cpx->env, cpx->prob);
229 {
230 char buf[512];
231 CPXgetstatstring(cpx->env, CPX_state, buf);
232 fprintf(stderr, "%s\n", buf);
233 }
234 switch (CPX_state) {
235 case CPXMIP_INFEASIBLE:
236 case CPX_STAT_INFEASIBLE: lpp->sol_state = lpp_infeasible; break;
237 case CPXMIP_INForUNBD:
238 case CPX_STAT_INForUNBD: lpp->sol_state = lpp_inforunb; break;
239 case CPXMIP_UNBOUNDED:
240 case CPX_STAT_UNBOUNDED: lpp->sol_state = lpp_unbounded; break;
241 case CPXMIP_ABORT_FEAS:
242 case CPXMIP_FAIL_FEAS:
243 case CPXMIP_MEM_LIM_FEAS:
244 case CPXMIP_NODE_LIM_FEAS:
245 case CPXMIP_TIME_LIM_FEAS: lpp->sol_state = lpp_feasible; break;
246 case CPXMIP_OPTIMAL:
247 case CPXMIP_OPTIMAL_TOL: /* TODO: Is this ok? Read the docu more closely */
248 case CPX_STAT_OPTIMAL: lpp->sol_state = lpp_optimal; break;
249 default: lpp->sol_state = lpp_unknown;
250 }
251
252 /* get variable solution values */
253 values = alloca(numcols * sizeof(*values));
254 CPXgetmipx(cpx->env, cpx->prob, values, 0, numcols-1);
255 chk_cpx_err(cpx);
256 for(i=0; i<numcols; ++i) {
257 lpp->vars[1+i]->value = values[i];
258 lpp->vars[1+i]->value_kind = lpp_value_solution;
259 }
260
261 /* Get the value of the objective function. */
262 CPXgetmipobjval(cpx->env, cpx->prob, &lpp->objval);
263 CPXgetbestobjval(cpx->env, cpx->prob, &lpp->best_bound);
264
265 /* get some statistics */
266 timing_ticks_sub(tva, tvb);
267 lpp->sol_time = timing_ticks_dbl(tva);
268 lpp->iterations = CPXgetmipitcnt(cpx->env, cpx->prob);
269 }
270
lpp_solve_cplex(lpp_t * lpp)271 void lpp_solve_cplex(lpp_t *lpp)
272 {
273 cpx_t *cpx = new_cpx(lpp);
274 cpx_construct(cpx);
275 cpx_solve(cpx);
276 free_cpx(cpx);
277 }
278
279 #endif
280