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

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.

• What do you mean with an algorithm? Do you mean a “general” algorithm? If you just want an example, if your polytope is an interval [a,b] with a,b integer, you can find the convex combination of any point by rounding up/down its value. Oct 5, 2020 at 2:47
• Yes i mean a general algorithm, given a point $h$ inside $conv(S)$ return $\lambda_1, \ldots, \lambda_k$, and integral $r_1, \ldots, r_k \in conv(S)$, such that $h = \lambda_1r_1 + \ldots \lambda_kr_k$. Oct 5, 2020 at 6:28
• @Borelian yes this would be an example, but i am looking for more complex scenarios like well-studied polytopes. Oct 5, 2020 at 6:29
• @Borelian just to be clear i am looking not for an algorithm which works for all polytopes, but examples of pairs of sufficient complex (polytope, algorithm) Oct 5, 2020 at 11:30
• How is $conv(S)$ provided, in H-representation (hyper plane) or the V-representation ? Also, what is the relaxation you are talking about in the 2nd paragraph? Oct 5, 2020 at 17:35

2 Answers

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.

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.