We consider discrete bilevel optimization problems where the follower solves an integer program with a fixed number of variables. Using recent results in parametric integer programming, we present polynomial time algorithms for pure and mixed integer bilevel problems. For the mixed integer case where the leader’s variables are continuous, our algorithm also detects whether the infimum cost fails to be attained, a difficulty that has been identified but not directly addressed in the literature. In this case, it yields a “better than fully polynomial time” approximation scheme with running time polynomial in the logarithm of the absolute precision. For the pure integer case where the leader’s variables are integer, and hence optimal solutions are guaranteed to exist, we present an algorithm which runs in polynomial time when the total number of variables is fixed.

Copyright © 2016 University College London. We continue our study of intermediate sums over polyhedra, interpolating between integrals and discrete sums, which were introduced by Barvinok [Computing the Ehrhart quasi-polynomial of a rational simplex. Math. Comp. 75 (2006), 1449-1466]. By well-known decompositions, it is sufficient to consider the case of affine cones s+c, where is an arbitrary real vertex and is a rational polyhedral cone. For a given rational subspace L, we define the intermediate generating functions SL(s+c)(ξ) by integrating an exponential function over all lattice slices of the affine cone s+c parallel to the subspace L and summing up the integrals. We expose the bidegree structure in parameters and ξ, which was implicitly used in the algorithms in our papers [Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra. Found. Comput. Math. 12 (2012), 435-469] and [Intermediate sums on polyhedra: computation and real Ehrhart theory. Mathematika 59 (2013), 1-22]. The bidegree structure is key to a new proof for the Baldoni-Berline-Vergne approximation theorem for discrete generating functions [Local Euler-Maclaurin expansion of Barvinok valuations and Ehrhart coefficients of rational polytopes. Contemp. Math. 452 (2008), 15-33], using the Fourier analysis with respect to the parameter and a continuity argument. Our study also enables a forthcoming paper, in which we study intermediate sums over multi-parameter families of polytopes.

We are interested in the fast computation of the exact value of integrals of polynomial functions over convex polyhedra. We present speed-ups and extensions of the algorithms presented in previous work by some of the authors. We provide a new software implementation and benchmark computations. The computation of integrals of polynomials over polyhedral regions has many applications; here we demonstrate our algorithmic tools solving a challenge from combinatorial voting theory. © 2012 Elsevier B.V.