# Condition for an integer program and its linear relaxation to have the same value

Let $$A$$ be a $$(0,1)$$-matrix where no row or column is a zero vector, and consider the following optimization programs \begin{align}(1):\min&\quad y\cdot1\\\text{s.t.}&\quad yA\ge w\\&\quad y\ge0\\(2):\max&\quad w\cdot x\\\text{s.t.}&\quad Ax\le 1\\&\quad x\ge0\end{align} where $$1$$ denotes the vector $$\begin{pmatrix}1&\cdots&1\end{pmatrix}^\top$$.

It is well-known that if $$x,y$$ run through non-negative real vectors, the min-max has a common optimum (strong duality of linear programming). However, this might not be true for other types of problems like integer programming.

I was able to find some sufficient conditions for the question to be true. For example:

1. If $$A$$ is totally unimodular; that is, if and only if $$\det S\in\{−1, 0, 1\}$$ for all square submatrices $$S$$ (not necessarily formed from contiguous rows or columns).
2. If $$A$$ is balanced; that is, if $$A$$ contains no square submatrix of odd order whose row and column sums are all two.
3. If $$A$$ is totally balanced; that is, if $$A$$ contains no square submatrix having no repeated columns and its row and column sums are all two.

Question: Is there a necessary condition for which min-max holds for all (or some) integer programs?

• I think you need to swap necessary and sufficient in your question. Can you please check this and edit your question? – user3680510 Sep 30 '20 at 8:29
• Done! Thanks... – James Alex Sep 30 '20 at 8:36
• For general $w$ you need that the polytope $Ax\leq1, x\geq 0$ has only integral vertices. If you consider a specific $w$ than this can be relaxed via the total dual integral (tdi) condition. – user3680510 Sep 30 '20 at 10:44
• What if $w=1$ and $A$, $x$ and $y$ are integers (i.e., either 0 or 1s)? – James Alex Sep 30 '20 at 17:58