2
$\begingroup$

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?

-Thanks

Improve this question
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Dima Pasechnik
    Commented Apr 2, 2014 at 18:06
  • $\begingroup$ 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. $\endgroup$
    – Ali
    Commented Apr 2, 2014 at 18:34
  • $\begingroup$ 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. $\endgroup$
    – Dima Pasechnik
    Commented Apr 2, 2014 at 19:41

0

Reset to default

You must log in to answer this question.