| ILOG CPLEX Problem Representations |
|
CPLEX offers multiple ways to represent problems. Consider the following
linear program:
| maximize |
x1 |
+ |
2x2 |
+ |
3x3 |
|
|
| subject to |
-x1 |
+ |
x2 |
+ |
x3 |
< |
20 |
| |
x1 |
- |
3x2 |
+ |
x3 |
< |
30 |
| |
|
|
|
|
x1 |
< |
40 |
| |
x1 |
, |
x2 |
, |
x3 |
> |
0 |
CPLEX accepts the following ways of representing a mathematical programming
problem:
File representations
The table below shows the representation of this problem using CPLEX LP
Format and standard MPS format:
| CPLEX LP Format |
MPS Format |
Maximize
obj: x1 + 2 x2 + 3 x3
Subject To
c1: - x1 + x2 + x3 <= 20
c2: x1 - 3 x2 + x3 <= 30
Bounds
0 <= x1 <= 40
End
|
NAME
ROWS
N obj
L c1
L c2
COLUMNS
x1 obj -1 c1 -1
x1 c2 1
x2 obj -2 c1 1
x2 c2 -3
x3 obj -3 c1 1
x3 c2 1
RHS
rhs c1 20 c2 30
BOUNDS
UP bnd x1 40
ENDATA
|
Note that MPS Format does not have a standard way of specifying an objective
sense, so that the objective coefficients are output with the negative
of their true values, and that an MPS file is assumed to be a minimization
problem.
Concert Technology representation (C++ version)
Here is the same problem represented using ILOG Concert Technology:
IloEnv env;
IloModel model(env);
IloNumVarArray x(env);
x.add(IloNumVar(env, 0.0, 40.0));
x.add(IloNumVar(env));
x.add(IloNumVar(env));
model.add(IloMaximize(env, x[0] + 2 * x[1] + 3 * x[2]));
model.add( - x[0] + x[1] + x[2] <= 20);
model.add( x[0] - 3 * x[1] + x[2] <= 30);
/* Remainder of C++ code for solving problem removed */
|
Note that models, decision variables and constraints are all C++ objects,
and that the representation of the problem is very close to the algebraic
representation.
Sparse Matrix representation
When using the CPLEX Callable Library, a sparse matrix representation is
used. CPLEX supports using a row-based sparse matrix representation and
a column-based sparse matrix representation. For the row-based sparse matrix
representation, three arrays are used. These three arrays are:
| rmatbeg |
rmatbeg[k] is a "pointer" to the beginning of data for row
k
in the arrays rmatind and rmatval |
| rmatind |
The column numbers of the nonzero indices |
| rmatval |
The nonzero values for the corresponding columns |
|
In other words, for a particular row i, the columns that have nonzero
values in that row are stored in rmatind[rmatbeg[i]], rmatind[rmatbeg[i]+1],...,
rmatind[rmatbeg[i+1]-1].
The corresponding nonzero values are stored in rmatval[rmatbeg[i]],
rmatval[rmatbeg[i]+1],...,
rmatval[rmatbeg[i+1]-1].
For the example problem, the contents of these arrays is:
| rmatbeg |
0 |
3 |
6 |
|
|
|
| rmatind |
0 |
1 |
2 |
0 |
1 |
2 |
| rmatval |
-1 |
1 |
1 |
1 |
-3 |
1 |
|
Here is C source code using the CPLEX Callable Library to represent
the example problem:
&##35;define NUMROWS 2
&##35define NUMCOLS 3
&##35define NUMNZ 6
int
main (int argc, char **argv)
{
int status = 0;
CPXENVptr env = NULL;
CPXLPptr lp = NULL;
double obj[NUMCOLS];
double lb[NUMCOLS];
double ub[NUMCOLS];
double x[NUMCOLS];
int rmatbeg[NUMROWS];
int rmatind[NUMNZ];
double rmatval[NUMNZ];
double rhs[NUMROWS];
char sense[NUMROWS];
env = CPXopenCPLEX (&status);
if ( env == NULL ) {
char errmsg[1024];
fprintf (stderr, "Could not open CPLEX environment.\n");
CPXgeterrorstring (env, status, errmsg);
fprintf (stderr, "%s", errmsg);
goto TERMINATE;
}
lp = CPXcreateprob (env, &status, "lpex1");
if ( lp == NULL ) {
fprintf (stderr, "Failed to create LP.\n");
goto TERMINATE;
}
CPXchgobjsen (env, lp, CPX_MAX);
obj[0] = 1.0; obj[1] = 2.0; obj[2] = 3.0;
lb[0] = 0.0; lb[1] = 0.0; lb[2] = 0.0;
ub[0] = 40.0; ub[1] = CPX_INFBOUND; ub[2] = CPX_INFBOUND;
status = CPXnewcols (env, lp, NUMCOLS, obj, lb, ub, NULL, NULL);
if ( status ) {
fprintf (stderr, "Failed to populate problem.\n");
goto TERMINATE;
}
rmatbeg[0] = 0;
rmatind[0] = 0; rmatind[1] = 1; rmatind[2] = 2; sense[0] = 'L';
rmatval[0] = -1.0; rmatval[1] = 1.0; rmatval[2] = 1.0; rhs[0] = 20.0;
rmatbeg[1] = 3;
rmatind[3] = 0; rmatind[4] = 1; rmatind[5] = 2; sense[1] = 'L';
rmatval[3] = 1.0; rmatval[4] = -3.0; rmatval[5] = 1.0; rhs[1] = 30.0;
status = CPXaddrows (env, lp, 0, NUMROWS, NUMNZ, rhs, sense, rmatbeg,
rmatind, rmatval, NULL, NULL);
if ( status ) {
fprintf (stderr, "Failed to populate problem.\n");
goto TERMINATE;
}
/* Remainder of C code for solving problem removed */
|
|
