Operations Research Asked by k88074 on August 19, 2021

Say that I have a binary IP

$$z=max_x {c^top x: Ax=b, xin B^n}$$

where $B^n$ is the set of $n$-dimensional $0-1$ vectors.

Its LP relaxation will be

$$z^{LP}=max_x {c^top x: Ax=b, 0leq xleq 1}$$

I empirically observe that $z^{LP}=z$ and the LP solves to a binary solution.

**How can I structure a proof to show that $z^{LP}=z$ and $x^{LP}in B^n$?**

You are looking for a proof for Total Unimodularity (TU). TU is a property by which a linear program will always have an integral solution. All you need to prove is that in your LP

- $A$ matrix is TU and
- $b$ column has only integers.

**What is TU**

- A matrix $A$ is unimodular if $det(A) = 1$ or $-1$.
- A matrix $A$ is Totally Unimodular (TU) if each square submatrix $S$ of $A$ has $det(S) = 0, 1$ or $-1$.

**Sufficient Condition For TU**

- A matrix $A$ is TU if the number of non-zeros in each column is $le2$
- The sum of the entries of a column is zero

**Why does TU guarantees integral solution for a LP**

Consider the LP problem $Ax = b$ with basis $B$, the value of basic variables $x_B$ can be obtained as $$x_B = B^{-1}b = frac{operatorname{adj}(B)}{det(B)}b.$$

- Since $det(B) = -1$ or $1$ (from TU of $A$ matrix) and the adjoint matrix is also integral it implies that $B^{-1}$ is integral
- Since $b$ is integral, then $x_B$ is also integral, hence guaranteeing and integral optimum for the LP.

All network flow problems (shortest path, maximal flow, etc..) exhibit this property.

Answered by Palaniappan Chellappan on August 19, 2021

If I'm understanding your question properly, this is not true in general. What you can prove is that this can be solved to integrality algorithmically, by adding Gomory cuts. Once enough cuts are added, the optimal vertex of the LP has to give an integer solution.

This is known as the cutting plane method.

In your case, you can use this to show that once no more Gomory cuts can be found, $z^{LP}$ has to be equal to $z$ (this happens much sooner in practice, but for the purposes of a proof it's fine to consider the worst-case scenario).

Answered by Nikos Kazazakis on August 19, 2021

Get help from others!

Recent Answers

- haakon.io on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Peter Machado on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP