MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider the following linear program:

$\left\{ \begin{array}{l} \underset{x}{max} \;\;c^Tx\\ [I, \;B]x = \mathbf{1}\\ x\geq 0 \end{array} \right.$

where $c$ is a vector of length $n$ with strictly positive integer values, $I_{m\times m}$ is the identity matrix, $B$ is an $m\times(n-m)$ matrix of binary $0/1$ values and $\mathbf{1}$ is a vector of all ones. Another property of $B$ is on every column there are at least two entries of value 1, but other than this $B$ takes a rather random binary structure.

It seems that in the majority of cases this linear program has a binary 0/1 solution (and therefore the cost at the optimal point is integer). Aside from $B$ being totally unimodular, are there more general results that warrant a binary solution? For instance, are there any results that discuss under some mild conditions on $c$ and $B$, with a high probability this LP has a binary solution? Are there any similar problems in the literature that can be referred to?


share|cite|improve this question
Please qualify what exactly you mean by a 0-1 solution. The underlying polyhedron of the LP has an optimal face, say, $F$. Are you asking for a criterion for $F$ to contain a 0-1 vector? Something else? – Dima Pasechnik Apr 2 '14 at 18:06
That is right, among the optimal points for the LP, it seems that there is always a binary vector. BTW, $B$ is often a fat matrix if this helps. – Ali Apr 2 '14 at 18:34
any sufficiently generic $c$ will give optimal face consisting of just one vertex. How often your polyhedron will have this vertex being 0-1? This will not happen very often, for sure. – Dima Pasechnik Apr 2 '14 at 19:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.