It would be fun to have a list of misleading ideas and traps in CO. I will update this post for new problems.

1 Polytope for s-t cut

$$\begin{array}{c}\begin{array}{rlrl}\sum _{e\in p}{x}_e& \ge 1& & \forall \text{ s-t path p}\\ x_e& \ge 0& & \forall e\in E\end{array}\end{array}$$ Is this polytope integral?

Initially I thought, we have max flow min cut thm and flow polytope is integral and this path formulation of s-t cut should be the dual of flow problem and thus it is integral. However, hitting spanning tree (dual to tree packing) formulation has a integrality gap of 2. Make sense.

However, LP(1) is not the dual of Max-flow.

2 Size of support

Given a linear program with a rank $r$ constraint matrix, what is the size of support of its optimal solution?

This is mentioned in a previous post. The description there is not precise. Consider the following linear program,

$$\begin{array}{c}\begin{array}{rlrl}\min & & c^{T}x& \\ s.t.& & Ax& \le b\\ & & x& \ge 0\end{array}\end{array}$$

Let $r$ be the rank of $A$. We may assume $b\ge 0$. For any $c$ that this LP has a bounded solution, there must exist an optimal solution $x^{\ast }$ with support at most $r$. There are at most $r$ tight constraints in $Ax\le b$ and hence the optimal solution $x^{\ast }$ lies in the intersection of ${\mathbb{R}}_{+}^n$ and a rank $\ge n-r$ affine subspace, which is a convex polyhedron. If the LP has a bounded solution, then the optimal $x^{\ast }$ must be some vertex of the polyhedron. To make a point in our affine subspace a vertex in the polyhedron, we need at least $n-r$ hyperplanes $x_i=0$, each of the hyperplanes gives us a zero coordinate. Thus for any bounded solution, the support is at most $r$.

What about integer programs? One may think that the support should also be at most $r$, since the 0s in the optimal solution of its linear relaxation are integers. But rounding the fractional coordinates may break the feasibility. The currently best upperbound is roughly $m(3\Vert A{\Vert }_1+\sqrt{\log (\Vert A{\Vert }_1)})$ [1].

References