Scientific Computation and Applied & Industrial Mathematics: S. Thomas McCormick

A lattice L is the set of vectors arising from integer linear combinations of given basis vectors in R^n. Given some vector x, the Closest Vector Problem (CVP) is to find a vector v in L of minimum l_2-norm distance to x. CVP is a fundamental problem for lattices with many applications, and it is in general NP Hard.

A zonotopal lattice is given as the set of integer points {v | Mv = 0} when M is a totally unimodular matrix. We show how to adapt the Cancel and Tighten algorithm of Karzanov and McCormick to solve CVP for zonotopal lattices in O(n^3) time via the Seymour decomposition of totally unimodular matrices. The algorithm uses the decomposition to reduce the problem to a series of subproblems that are piecewise linear convex circulation and co-circulation network flow problems. by Britta Peis, Robert Scheidweiler (RWTH Aachen) S. Thomas McCormick (UBC Sauder) Frank Vallentin (Cologne)