3
$\begingroup$

Consider a non-empty, bounded $\mathcal H$-polyhedron described by

$$P = \left\{ x \in \mathbb{R}^n : Ax \leq b \right\}$$

Is there an algorithm to determine the minimum distance (in the $\ell_1$, $\ell_2$ or $\ell_\infty$ sense, say) between two distinct vertices of $P$ without converting it to its vertex representation?

What about a good (non-trivial) lower bound on the minimum distance instead?

More generally, suppose I'm also given another non-empty, bounded $\mathcal H$-polyhedron

$$Q = \left\{x \in \mathbb{R}^n: Cx \leq d\right\}$$

such that $P \cap Q$ may be non-empty. What is (a lower bound to) the minimum distance between a vertex $p$ of $P$ and a vertex $q$ of $Q$ such that $p \neq q$?

$\endgroup$
1
+50
$\begingroup$

Assuming that the inequalities are linearly independent, $x \in \mathbb{R}^n$ is a vertex if and only if $Ax \leq b$ and $a_i^Tx = b_i$ for $n$ (out of $m$) inequalities (the equivalence between a vertex and a basic feasible solution is well known). Let $L_i$ be a lower bound of $a_i^T x$ over the polyhedron. The set of vertices can be represented as: $$\{ x \in \mathbb{R}^n : L_i + (b_i-L_i)y_i\leq a_i^T x \leq b_i \; (i=1,\ldots,m), \sum_i y_i=n, y \in \{0,1\}^m \}.$$ For the second vertex you get: $$\{ x' \in \mathbb{R}^n : L'_i + (d_i-L'_i)y'_i\leq c_i^T x' \leq d_i \; (i=1,\ldots,m'), \sum_i y'_i=n, y' \in \{0,1\}^m \}.$$ The $\ell_1$ and $\ell_\infty$ norm can be represented in linear optimization. This gives rise to a mixed integer linear optimization problem. Solvers for such problems (such as cplex) often find the optimum or provide meaningful bounds. You will get better results if you use the strongest lower bound for $L_i$, which can be computed via linear programming: $\min \{ a_i^T x : Ax \leq b\}$.

The only challenge now is to add a constraint that two vertices are distinct. Maybe it is sufficient to have $y \neq y'$. One way to do this is to add the following linear constraints: $$\{1-z_i \leq y_i+y'_i \leq 1+z_i, \sum_i z_i \leq m-1, z \in \{0,1\}^m\}.$$

Combining everything, for the $\ell_1$ norm, you get: $$\begin{align}\min \quad &\sum_i w_i \\ \text{s.t.}\quad & -w \leq x-x' \leq w \\ & L_i + (b_i-L_i)y_i\leq a_i^T x \leq b_i \; (i=1,\ldots,m) \\ &L'_i + (d_i-L'_i)y'_i\leq c_i^T x' \leq d_i \; (i=1,\ldots,m') \\ &\sum_i y_i=n \\ &\sum_i y'_i=n \\ & 1-z_i \leq y_i+y'_i \leq 1+z_i \; (i=1,\ldots,m') \\ &\sum_i z_i \leq m-1 \\ &w \in \mathbb{R}^n, x \in \mathbb{R}^n, x' \in \mathbb{R}^n, y \in \{0,1\}^m, y' \in \{0,1\}^m, z \in \{0,1\}^m \end{align}$$ Suppose the solution $(\hat{y},\hat{y}')$ is invalid you can add a cut to invalidate that solution: $$\sum_{i=1}^m (1-y_i) 1_{\hat{y}_i=1} + y_i 1_{\hat{y}_i=0} + \sum_{i=1}^{m'} (1-y'_i) 1_{\hat{y}'_i=1} + y'_i 1_{\hat{y}'_i=0} \geq 1.$$

$\endgroup$
  • $\begingroup$ The way you encode two vertices being distinct is not guaranteed to work. Consider the square pyramid defined by $P = \{x \in \mathbb{R}^3 : x_3 \geq 0, \alpha_1 x_1 + \alpha_2 x_2 + x_3 \leq 1 \; \forall (\alpha_1, \alpha_2) \in \{-1, 1\}^2\}$ $\endgroup$ – OtherwiseWorth Apr 9 '18 at 16:19
  • $\begingroup$ @user3834629 I can replace it with a constraint that forces $x$ and $x'$ to differ by at least some prescribed threshold $\varepsilon$ in at least one coordinate. Would that be usable? $\endgroup$ – LinAlg Apr 9 '18 at 16:40
  • $\begingroup$ It would be only if there is a systematic way/guideline to choose a safe value for the threshold. $\endgroup$ – OtherwiseWorth Apr 9 '18 at 17:27
  • $\begingroup$ I'm afraid there isn't. $\endgroup$ – LinAlg Apr 9 '18 at 19:23
  • 1
    $\begingroup$ Do you think iteratively adding canonical/integer cuts (if the optimal value of your problem is 0) in the $(y, y^\prime)$ space might work? $\endgroup$ – OtherwiseWorth Apr 10 '18 at 13:42

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.