# Questions tagged [integrality-gap]

The integrality gap is the maximum ratio between the values of the optima of the integer program (IP) and of its LP relaxation.

5 questions
Filter by
Sorted by
Tagged with
33 views

### How to prove LP integral solution when total unimodularity fails?

I have a problem that I managed to write as a binary integer linear program. As a natural first step, I relaxed the integrality constraint to solve a regular LP. To my surprise, the solutions where ...
301 views

### Adapting a proof to show that a polyhedron has integer extreme points

Prove that the polyhedron $$P =\{(x_1, \ldots , x_m, x_{m+1}): 0\leq x_m \leq 1, 0 \leq x_i \leq x_{m+1} \text{ for } i = 1, \ldots , m \}$$ has integer extreme points. My Attempt: I have a similar ...
630 views

### Proving that a polyhedron has integer vertices

Prove that the polyhedron $P =\{(x_1, \ldots , x_m, y) \in \mathbb R_{+}^{m+1}: y \leq 1,x_i \leq y \text{ for } i = 1, \ldots , m \}$ has integer vertices. It seems obvious to me but don't know how ...
Consider the following linear program (LP)  \begin{align*} &\text{maximize }& &c^\prime x\\ &\text{subject to }& &Ax \leq b\\ & && 0\leq x_i \leq 1 \quad \forall ...