Optimization Online


Simple Explicit Formula for Counting Lattice Points of Polyhedra

J.B. Lasserre(lasserre***at***laas.fr)
E.S. Zeron(eszeron***at***math.cinvestav.mx)

Abstract: Given $z\in C^n$ and $A\in Z^{m\times n}$, we consider the problem of evaluating the counting function $h(y;z):=\sum\{z^x : x \in Z^n; Ax = y, x \geq 0\}$. We provide an explicit expression for $h(y;z)$ as well as an algorithm with possibly numerous but simple computations. In addition, we exhibit finitely many fixed convex cones of $R^n$ explicitly and exclusively defined by $A$ such that for any $y\in Z^m$, the sum $h(y;z)$ can be obtained by a simple formula involving the evaluation of $\sum z^x$ over the integral points of those cones only. At last, we also provide an alternative (and different) formula from a decomposition of the generating function into simpler rational fractions, easy to invert.

Keywords: Computational geometry; lattice polytopes.

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Integer Programming (Other )

Citation: To be presented at IPCO 2007, Cornell, June 2007

Download: [PDF]

Entry Submitted: 02/14/2007
Entry Accepted: 02/14/2007
Entry Last Modified: 02/14/2007

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 Programming Society