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

[Andrew Makhorin]

-------- Forwarded Message --------
From: Sergey Kuznetsov <address@hidden>
To: GLPK help <address@hidden>
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();


  // Read parametrs
  glp_set_obj_dir(mip, GLP_MAX);


  // setting righthand side (beta)
  glp_add_rows(mip, numrows);
  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
  glp_add_cols(mip, numcols);
  // 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]);
  }


  // read constraint matrix
  // 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;
    }


  // Load matrix
  glp_load_matrix(mip, ne, ia, ja, ar);


  // 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;
  glp_adv_basis(mip, 0);
  
  // 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...
+     3: mip =     not found yet <=              +inf        (1; 0)
+     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