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.

Filter by
Sorted by
Tagged with
2
votes
0answers
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
0answers
302 views

Proof of binary solution of a linear program with specific structure

When solving instances of the following linear program (LP), I always get an integral (actually binary) solution. Is it just a coincidence or is it possible to prove that there always exists a binary ...
1
vote
1answer
582 views

Integral solution of a linear program

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 ...