Optimization Online


Short simplex paths in lattice polytopes

Alberto Del Pia (delpia***at***wisc.edu)
Carla Michini (michini***at***wisc.edu)

Abstract: We consider the problem of optimizing a linear function over a lattice polytope P contained in [0,k]^n and defined via m linear inequalities. We design a simplex algorithm that, given an initial vertex, reaches an optimal vertex by tracing a path along the edges of P of length at most O(n^6 k log k). The length of this path is independent on m and is the best possible up to a polynomial function, since it is only polynomially far from the worst case diameter. The number of arithmetic operations needed to compute the next vertex in the path is polynomial in n, m and log k. If k is polynomially bounded by n and m, the algorithm runs in strongly polynomial time.

Keywords: Lattice polytope, Simplex algorithm, Diameter, Strongly polynomial time

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: University of Wisconsin-Madison, December 2019

Download: [PDF]

Entry Submitted: 12/11/2019
Entry Accepted: 12/11/2019
Entry Last Modified: 01/04/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society