2
$\begingroup$

Decision problems in Integer Linear Programming have Lenstra type algorithms (https://www.math.leidenuniv.nl/~lenstrahw/PUBLICATIONS/1983i/art.pdf) have been generalized to convex integer program techniques (See Complexity of integer quasiconvex polynomial optimization by Sebastian Heinz).

What is the difficulty in generalizing Barvinok type counting integer points in Linear Integer Programming techniques (https://barvinok.sourceforge.io/) to counting integer points in convex integer programming?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ Not sure exactly what you're asking. Higher-degree polynomials are a lot harder to handle than linear polynomials. Even in two dimensions, we have Pick's formula for a polygon, but even counting the exact number of integer points inside a circle is not a trivial problem. $\endgroup$
    – Timothy Chow
    Commented Sep 5 at 11:48

0

Reset to default

You must log in to answer this question.