help-glpk
[Top][All Lists]

## [Help-glpk] [Fwd: Solving pure IP by calling MIP solver gives wrong stat

 From: Andrew Makhorin Subject: [Help-glpk] [Fwd: Solving pure IP by calling MIP solver gives wrong status] Date: Mon, 03 Jun 2013 22:20:12 +0400

```-------- Forwarded Message --------
Subject: Solving pure IP by calling MIP solver gives wrong status
Date: Mon, 3 Jun 2013 13:03:32 -0400

Hello,

I'm using GLPK (calling a function in c++ code) to solve a large number
of IP's, and have problems with the following pure IP (ll obj. func.
coeff. are >= 0):

Maximize 4 x1 + x2 + 6 x3
Subject to:
2 x1 + 8 x2 - x3 <= -1
- x1 - 5 x2 + 4 x3 <= 2
x1 >= 0
x2 >= 0
x3 >= 0
x1,x2,x3 - integers

Here's code:
double SolveIP (int **A, int *c, vector<double>& rhs, int numcols, int
numrows)
{
double z(-2.0); // value function
int ne = numcols*numrows;; // total # of nonzero elements
int k(1);
int *ia = new int[ne+1];
int *ja = new int[ne+1];
double *ar = new double[ne+1];

// Call GLPK:
glp_iocp param;
glp_smcp sim;
glp_prob *mip;
mip = glp_create_prob();

glp_set_obj_dir(mip, GLP_MAX);

// setting righthand side (beta)
for (int i=1; i<=numrows; ++i)
glp_set_row_bnds(mip, i, GLP_UP, 0.0, rhs[i-1]);

// setting x-vector bounds and obj. function coefficients
// int part
for (int j=1; j<=numcols; ++j){
glp_set_col_bnds(mip, j, GLP_LO, 0.0, 0.0);
glp_set_obj_coef(mip, j, c[j-1]);
}

// int part
for (int i=1; i<=numrows; ++i)
for (int j=1; j<=numcols; ++j){
ia[k] = i;
ja[k] = j;
ar[k] = double(A[i-1][j-1]);
++k;
}

// Indicate int and cont parts
for (int j=1; j<=numcols; ++j){
glp_set_col_kind(mip, j, GLP_IV);
}
//glp_term_out(GLP_OFF);
// construct initial basis
glp_init_iocp(&param);
param.msg_lev = GLP_MSG_ALL;

glp_init_smcp(&sim);
sim.msg_lev = GLP_MSG_ALL;

// Run simplex to solve LP-relaxation
glp_simplex(mip, &sim);

// Find optimal integer solution
glp_intopt(mip, &param);

// Get obj. value
const int status(glp_get_status(mip));
cout << "glpk status = " << status << endl;
if (status == GLP_OPT)

z = glp_mip_obj_val(mip);
else if (status == GLP_NOFEAS)
z = -1.0;
else
z = -2.0;

glp_erase_prob(mip); // work with erase problem
delete [] ia;

delete [] ja;
delete [] ar;

return z;

}

In the end I have the following output:

Constructing initial basis...
Size of triangular part = 2
GLPK Simplex Optimizer, v4.45
2 rows, 5 columns, 10 non-zeros
0: obj =   0.000000000e+00  infeas =  1.000e+00 (0)
*     1: obj =   1.666666667e-01  infeas =  0.000e+00 (0)
*     3: obj =   3.411764706e+00  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
GLPK Integer Optimizer, v4.45
2 rows, 5 columns, 10 non-zeros
5 integer variables, none of which are binary
Integer optimization begins...
+     4: mip =     not found yet <=     tree is empty        (0; 1)
PROBLEM HAS NO INTEGER FEASIBLE SOLUTION

glpk status = 5  (GLP_OPT = 5 ; GLP_NOFEAS = 4)
obj val = 0   ( in the code obj_val variable intialized by -1.0 )

Hence, given problem should be infeasible, status = 4, but instead in
has optimal solution.
Might it be a bug in the solver?
Thanks,

Sergey

```