Hi I have a integer program and i have theoretically proved that one of the optimal solution of the lp relaxation is guaranteed to be integer. On the smaller to medium size instances I always get integral solution on solving the lp relaxation using cplex. But on large instances with millions of variables, lp relaxation returns a non integral solution. I have also solved the integer program with this and gap between lp relaxation objective and ip objective is less than 10^-3. Its a maximization problem and the objective function is of the form c1x1+c2x2+c3x3+...+cnxn. All coefficients of objective function are positive floating point numbers and smallest value is 4. So with only 10^-3 difference its highly unlikely that there is a better solution with lp relaxation, it just seems to me some numerical precision error. All constraints of the form Ax<= b where A contains 0,1 and -1 and b contains all integers. Am i correct in judging it to be precision issue.And if so can somebody please help me with this.
asked
Meghna |

From what you've stated about the matrix A, this seems like a network flow problem. I might be wrong in my assumption, but if there are only 0's, 1's, and -1's in your A matrix, then it might be. In any case, these A matrices usually have the total unimodularity property which as a consequence, produces integer LP solutions at no additional cost. You might want to look into that (I'm not really an expert in this area yet). But if it turns out to be a network flow problem, or if you have an A matrix that possesses the total unimodularity property (all square sub matrices of A have determinants +1, 0, or -1), then your LP solution should be integral, and you are correct in assuming that it is most likely a precision issue. I hope I've helped.
answered
baubaid |

You might look at the kappa value of the final basis and the solution quality metrics to see if anything looks goofy. A large kappa value (unstable basis) could signal numerical issues. You could also try turning on the numerical emphasis switch, but be warned that you might see a significant slow down as a result.
answered
Paul Rubin ♦♦ |

What is the average precision error for integer variables?