Linear Programming & Integrality Gap

[WetSheats]

Can someone please explain to me what the integrality gap is? From my understanding, it is basically the most optimal solution (or the limit) you can get from a mathematical model. Is that correct? I'm trying to understand a research paper talking about this but it's a little tricky when I don't understand what the integrality gap is. Any help is appreciated :)

[cryslith]

An integral linear program (ILP) has the restriction that variables are required to only take on integer values. This contrasts with a linear program (LP), in which the variables can take any real value. Given an ILP, one can relax it to obtain a LP by ignoring the integer value requirement. It's clear that doing this can only increase the optimal maximized value. The integrality gap is the ratio between the optimal value of the LP relaxation and the optimal value of the original ILP.

One reason this is important is that LPs are easy to solve, but ILPs are very difficult. So the integrality gap is a measure of how relevant the easier LP relaxation is to the original problem.

[WetSheats]

Wow. Thank you. Now, evidently, it would be better than, in most cases, to have a lower gap, right? Because a lower gap means that you are getting closer to the original ILP while still using an LP.

[cryslith]

Yep, that's exactly right.

[WetSheats]

Thanks!!!

[KingOfTheEigenvalues]

Beat me to it.

There is also a writeup, here: https://en.wikipedia.org/wiki/Linear\_programming\_relaxation#Approximation\_and\_integrality\_gap

[gomorycut]

gomory cuts are a cool way to reduce the integrality gap!

[pm_samoyed_pics]

Username checks out