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:
- 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).
- If $A$ is balanced; that is, if $A$ contains no square submatrix of odd order whose row and column sums are all two.
- 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?
