6
$\begingroup$

Say that I have a binary IP $$z=\max_x \{c^\top x: Ax=b, x\in 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, 0\leq x\leq 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$?

Improve this question
$\endgroup$
2
  • 6
    $\begingroup$ If A and b are integer, unimodularity of A is a sufficient criterion, i.e. det(A) = +-1. $\endgroup$
    – T_O
    Commented Jul 1, 2020 at 10:00
  • 2
    $\begingroup$ also check the answers here and here $\endgroup$
    – Marco Lübbecke
    Commented Jul 1, 2020 at 12:26

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ wouldn't cuts potentially improve on the LP objective value, and thus actually disprove what @k88074 wants to show? $\endgroup$
    – Marco Lübbecke
    Commented Jul 1, 2020 at 12:16
  • $\begingroup$ @MarcoLübbecke They will, but only because the LP objective value won't be integral. Once it becomes integral it should stop improving. $\endgroup$
    – Nikos Kazazakis
    Commented Jul 1, 2020 at 12:33
  • $\begingroup$ yes, but then we would have $z^{LP}>z$ but they want to prove $z^{LP}=z$; maybe your method can be used like: when we do not find any Gomory cuts any more, then... $\endgroup$
    – Marco Lübbecke
    Commented Jul 1, 2020 at 12:39
  • 1
    $\begingroup$ @MarcoLübbecke Gotcha, you are right (technically it would be greater or equal because the values have to match at the vertex), I'll update the answer! $\endgroup$
    – Nikos Kazazakis
    Commented Jul 1, 2020 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.