Lattice based extended formulations for integer linear equality systems


Karen Aardal, CWI Amsterdam and TU Eindhoven


We describe how lattices can be used to solve integer linear programming problems. We start by recalling a lattice reformulation proposed by Aardal, Hurkens, and Lenstra, certain results for knapsack problems derived by Aardal and Lenstra, and a broad family of extended formulations by Aardal and Wolsey.

We illustrate several of our theoretical results by computational examples.


back to EIDMA Seminar Combinatorial Theory announcements