University of Washington
Bilevel optimization problems are heirarchical optimization problems where a leader optimizes an objective subject to a second optimization problem of a follower. Much attention has been given to the study of linear bilevel optimization problems, with some recent attention being given to the less developed study of discrete linear bilevel optimization. We present an approach to discrete bilevel optimization using the algebraic methods from Groebner basis theory and generating functions for encoding sets of integer points in polytopes. We explore a particular case where the follower solves an integer programming problem, and where both the right-hand side and unit cost of this program are influenced by the leader. Groebner bases are used to derive an algorithm whereby the general problem is decomposed into a finite set of subproblems where the unit cost is fixed. Then, in the case of a fixed unit cost, a algorithm for solving discrete bilevel linear programs is obtained using rational generating functions. This latter algorithm runs in polynomial time in fixed dimension.
University of Washington