What are examples of integral polytopes, where there exists an algorithm to write a given point as a convex combination of integral points?

Question

Given a set of integer points $S$, one is often interested in finding $\operatorname{conv}(S)$ or characterizing certain cases, where $\operatorname{conv}(S)$ is described by few inequalities. Examples would be stable set polytope on perfect graphs or the min-cost flow polytope.

There are certain techniques to prove this; for example, total unimodularity, and total dual integrality (TDI). I am looking for examples, where given a point in the relaxation, there is an algorithm which retrieves the convex combinators to write this point as a convex combination of integral points.

Can you point to some examples? It would be great if you can also link to a paper or something where the algorithm is described.

Answer 1

The argument from the paper Geometric proofs for convex hull defining formulations, Operations Research Letters 44 (2016), 625-629, can be turned into a simple algorithm for writing a point in the stable set polytope for a chordal graph $G$ as a convex combination of incidence vectors of stable sets. Let the vertex set of $G$ be $\{1,\dots,n\}$, and let $x=(x_1,\dots,x_n)$ be a point in the stable set polytope. Proceeding along a perfect elimination order, we find sets $X_i\subseteq[0,1)$, such that $X_i$ has measure $x_i$ and $X_i\cap X_j=\emptyset$ for every edge $ij$. Thus, for every $t\in[0,1)$, the set $I(t)=\{i\,:\,t\in X_i\}$ is a stable set, and if we define $\lambda(\xi)$ for $\xi\in\{0,1\}^n$ to be the measure of the set $$\{t\,:\,\xi\text{ is the characteristic vector of }I(t)\}$$ then $x=\sum_{\xi}\lambda(\xi)\xi$ is the required convex representation of $x$, where the sum is over the characteristic vectors of stable sets.

Answer 2

Here is a rough attempt at solving your problem. Let us denote the polytope $P = \operatorname{conv}(S)$ (if I am to understand your OP correctly, we know that $P$ is an integral polytope), and let $x \in P$ be the point you want to find the convex combinators for. Further you mentioned in the comments that $P$ is specified in H representation, so let us assume that $P = \lbrace{x \in \mathbb{R}^n \mid Ax \leq b \rbrace}$.

1. Find a direction $d$ such that both points $x + d$ and $x - d$ lie in $P$. You can compute such a $d$ by solving an optimization problem.
2. Using ray tracing, find out which inequality in $Ax \leq b$ the ray $d$ starting at $x$ intersects first. Let that inequality be $\alpha_1 x \leq b_1$. Denote the point of intersection of the ray and $\alpha_1 x \leq b_1$ by $x_1$. Similarly using ray tracing figure out which inequality in $Ax \leq b$ the ray $-d$ intersects first starting at $x$. Let that inequality be $\alpha_2 x \leq b_2$. Let that point of intersection of the ray and $\alpha_2 x \leq b_2$ be $x_2$. So $x$ is a convex combination of $x_1$ and $x_2$.
3. Now my suppose we knew how $x_1$ and $x_2$ can be represented as a convex combination of the vertices of $P$, then we can represent $x$ as a convex combination using the vertices of $P$ used to represent $x_1$ and $x_2$. My goal below is to figure out how to represent $x_1$ as a convex combination of the vertices of $P$. We can analogously do similar steps for $x_2$.
4. Since we know that $x_1 \in P$ and $\alpha_1 x_1 = b_1$, we know that $x_1$ can be represented as a convex combination of the vertices of $P_1 = P \cap (\alpha_1 x_1 = b_1)$. Note that $P_1$ is just a face of $P$, so the vertices of $P_1$ are also integral. However crucially, $\dim(P_1) \leq \dim(P)$. So now, if we had a method to compute $x_1$ as a convex combination of the vertices of $P_1$ (which by the way equivalent to your original question), then we are done. Note that suppose $\dim(P_1) = 1$, then $P_1$ is just a line segment, so $x_1$ is just a convex combination of the end points of the line segment. The end points of the line segment can be found using some linear programming solver.
5. The observation in 4 suggests for finding $x_1$ as a convex combination of the vertices of $P_1$, we can simply replace $x$ by $x_1$ and $P$ with $P_1$ in steps 1 and 2. So this leads to a recursive procedure over all.

Hopefully the explanation above gives you one way of computing the convex combinators. There a few minor details you would have deal with if you were to implement this method, but hopefully you should be able to figure them out.