Optimum turn-restricted paths, nested compatibility, and optimum convex polygons

We consider two apparently unrelated classes of combinatorial and geometric optimization problems. First, we give compact extended formulations, i.e., polynomial-size linear programming formulations with integer optima, for optimum path problems with turn restrictions satisfying a nested compatibility condition in acyclic digraphs. We then apply these results to optimum convex polygon problems in the plane, by interpreting certain dynamic programming algorithms as sequences of optimum turn-restricted path problems with nested compatibility in acyclic digraphs. As a result, we derive compact extended formulations for these geometric problems as well.

1. If needed, we could add an origin 0 and a destination n connected to all 0p nodes, and from all \(\overline{qn}\) nodes, respectively, with zero-revenue arcs, so we seek a maximum value (0, n)-path in the resulting expanded network. This is, however, unnecessary for our purposes.

2. Recall that both nodes 0 and \(n_t\) represent the point \(x^t\).

This work was completed while the first author was serving as Research Director of CORE, the Center for Operations Research and Econometrics, Université catholique de Louvain, whose hospitality is gratefully acknowledged. The authors would like to thank the following colleagues for useful discussions and suggestions on optimum convex polygon and convex subset problems—in approximate chronological order: Marcos Goycoolea (Universidad Adolfo Ibañez), Jeremy Barbay (Universidad de Chile), Miguel Constantino (Universidade de Lisboa), Marek Chrobak (University of California, Riverside), Keno Merckx and Jean-Paul Doignon (Université Libre de Bruxelles).

Authors and Affiliations

1. UBC Sauder School of Business, University of British Columbia, Vancouver, Canada

   Maurice Queyranne

2. Center for Operations Research and Econometrics (CORE), Université catholique de Louvain, Louvain-la-Neuve, Belgium

   Laurence A. Wolsey

Corresponding author

Correspondence to Maurice Queyranne.

Appendix

Proof (Proof of Lemma 1)

Consider any \(q \in \{1,\ldots ,n-1\}\). First, note that by assumptions (i)–(iii) we may assume that \(p^0_q = 0\) and \(r^{\sigma (q)}_q = n\). Note also that \(\pi (q) = |{{\mathrm{Pred}}}(q)|\) and \(\sigma (q) = |{{\mathrm{Pred}}}(q)|+|{{\mathrm{Succ}}}(q)|\). Let \(A^1_q = \{p\in {{\mathrm{Pred}}}(q) : (p,q,r)\in L \text{ for } \text{ all } r\in {{\mathrm{Succ}}}(q)\}\). If \(A^1_q = {{\mathrm{Pred}}}(q)\) then the Lemma holds with \(B^1_q = {{\mathrm{Succ}}}(q)\). Otherwise, we construct \(B^1_q\), \(A^2_q\), \(B^2_q\), etc., inductively as follows. Assume we have identified nonempty disjoint subsets \(A^1_q,\ldots ,A^h_q\) of \({{\mathrm{Pred}}}(q)\) and, if \(h > 1\), \(B^1_q,\ldots ,B^{h-1}_q\) of \({{\mathrm{Succ}}}(q)\) such that, for all \(p\in \bigcup _{j\le h}A^j_q\) and all \(r\in {{\mathrm{Succ}}}(q)\), \((p,q,r) \in L\) if and only if \((p,r) \in \bigcup _{k=1}^{h}\left( A^k_q \times \left( {{\mathrm{Succ}}}(q){\setminus }\bigcup _{\ell < h}B^\ell _q\right) \right) \), i.e., the conclusion of the Lemma holds for all such p and r. By assumption (iii) and by induction, \(A^h_q\) is a consecutive set of predecessors of q, i.e., \(A^h_q =\{p^i_q : \alpha (h-1)+1 \le i\le \alpha (h)\}\) for some \(\alpha (h)\in \{\alpha (h-1)+1,\ldots ,\pi (q)\}\) where, by assumption (i) we may assume \(\alpha (0) = -1\) (so \(A^1_q = \{p^i_q : 0 \le i\le \alpha (1)\}\)). As for the case \(h=1\) above, if \(\bigcup _{k=1}^h A^k_q = {{\mathrm{Pred}}}(q)\) then the Lemma holds with \(B^h_q = {{\mathrm{Succ}}}(q){\setminus }\bigcup _{\ell < h}B^\ell _q\) and we are done. Else \(\alpha (h) < \pi (q)\). Let \(B^h_q = \{r\in {{\mathrm{Succ}}}(q) : \left( p^{\alpha (h)+1}_q,q,r\right) \not \in L\}\). By assumption (iii) and induction, \(B^h_q\) is a consecutive set of successors of q, i.e., \(B^h_q =\{p^i_q : \beta (h-1)+1 \le i\le \beta (h)\}\) for some \(\beta (h)\in \{\beta (h-1)+1,\ldots ,\sigma (q)\}\) where, by assumption (ii) we may assume \(\beta (0) = \pi (q)\) (so \(B^1_q = \{p^i_q : \pi (q)+1 \le i\le \beta (1)\}\)). Letting \(A^{h+1}_q = \{p\in {{\mathrm{Pred}}}(q){\setminus }\bigcup _{k \le h}A^k_q : (p,q,r)\in L \text{ for } \text{ all } r\in {{\mathrm{Succ}}}(q){\setminus }\bigcup _{\ell \le h}B^\ell _q\}\) now satisfies the inductive assumption with h replaced by \(h+1\). This completes the inductive proof of the Lemma. \(\square \)

Reprints and permissions