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 01 Nov '15, 09:39

Meghna's gravatar image

Meghna
114
accept rate: 0%

edited 01 Nov '15, 09:41

What is the average precision error for integer variables?

(02 Nov '15, 10:58) Ehsan ♦

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.

link

answered 07 Nov '15, 09:43

baubaid's gravatar image

baubaid
715
accept rate: 0%

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.

link

answered 07 Nov '15, 17:27

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×191
×8
×4

Asked: 01 Nov '15, 09:39

Seen: 792 times

Last updated: 07 Nov '15, 17:27

OR-Exchange! Your site for questions, answers, and announcements about operations research.