5
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Borelian
    Oct 5 '20 at 2:47
  • $\begingroup$ 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$. $\endgroup$ Oct 5 '20 at 6:28
  • $\begingroup$ @Borelian yes this would be an example, but i am looking for more complex scenarios like well-studied polytopes. $\endgroup$ Oct 5 '20 at 6:29
  • $\begingroup$ @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) $\endgroup$ Oct 5 '20 at 11:30
  • $\begingroup$ 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? $\endgroup$
    – batwing
    Oct 5 '20 at 17:35
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.