Optimum Turn-Restricted Paths, Nested Compatibility, and Optimum Convex Polygons

Maurice Queyranne and Laurence A. Wolsey ()
Additional contact information
Maurice Queyranne: Université catholique de Louvain, CORE, Belgium
Laurence A. Wolsey: Université catholique de Louvain, CORE, Belgium

No 2016020, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: 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.

Keywords: hortest paths; acyclic networks; turn restrictions; convex polygons; convex subsets; extended formulation; dynamic programming (search for similar items in EconPapers)
Date: 2016-06-02
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2016.html (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2016020

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().