2
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ I think you need to swap necessary and sufficient in your question. Can you please check this and edit your question? $\endgroup$ – user3680510 Sep 30 '20 at 8:29
  • $\begingroup$ Done! Thanks... $\endgroup$ – James Alex Sep 30 '20 at 8:36
  • $\begingroup$ 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. $\endgroup$ – user3680510 Sep 30 '20 at 10:44
  • $\begingroup$ What if $w=1$ and $A$, $x$ and $y$ are integers (i.e., either 0 or 1s)? $\endgroup$ – James Alex Sep 30 '20 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.