Linear Programs and Convex Hulls Over Fields of Puiseux Fractions

DOI10.1007/978-3-319-32859-1_37zbMATH Open1460.90106arXiv1507.08092OpenAlexW3099472040MaRDI QIDQ2807865FDOQ2807865

Authors: Michael Joswig, Georg Loho, Benjamin Lorenz, Benjamin Schröter 

Publication date: 25 May 2016

Published in: Mathematical Aspects of Computer and Information Sciences (Search for Journal in Brave)

Abstract: We describe the implementation of a subfield of the field of formal Puiseux series in polymake. This is employed for solving linear programs and computing convex hulls depending on a real parameter. Moreover, this approach is also useful for computations in tropical geometry.

Full work available at URL: https://arxiv.org/abs/1507.08092

Recommendations

• Convex analysis in \(\mathbb{Z}^n\) and applications to integer linear programming
• The complexity of linear problems in fields
• Separating hyperplanes for convex sets over ordered fields
• Coisotropic invariant tori of hamiltonian systems of the quasiclassical theory of motion of a conduction electron
• On the convex hull of solutions to polynomial congruences
• A Polyhedral Frobenius Theorem with Applications to Integer Optimization
• Semidefinite representation of convex hulls of rational varieties
• Solving linear constraints over real and rational fields
• On constraint sets of infinite linear programs over ordered fields
• Approximating some convex programs in terms of borel fields

zbMATH Keywords

rational functionsPuiseux seriesconvex hull computation over ordered fieldslinear programming over ordered fieldstropical convex hull computation

Mathematics Subject Classification ID

Linear programming (90C05) Symbolic computation and algebraic computation (68W30) Applications of tropical geometry (14T90)

Cited In (8)

• Moduli spaces of codimension-one subspaces in a linear variety and their tropicalization
• What Tropical Geometry Tells Us about the Complexity of Linear Programming
• Convergent Hahn series and tropical geometry of higher rank
• Computing convex hulls and counting integer points with \texttt{polymake}
• Log-Barrier Interior Point Methods Are Not Strongly Polynomial
• Face posets of tropical polyhedra and monomial ideals
• Tropical Computations in polymake
• A formalization of convex polyhedra based on the simplex method

Uses Software

• Magma
• Matlab
• polymake

This page was built for publication: Linear Programs and Convex Hulls Over Fields of Puiseux Fractions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2807865)