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