Invited Session Wed.2.H 2033

Wednesday, 13:15 - 14:45 h, Room: H 2033

Cluster 11: Integer & mixed-integer programming [...]

Lattices and integer programming


Chair: Karen Aardal



Wednesday, 13:15 - 13:40 h, Room: H 2033, Talk 1

Karen Aardal
The structure of LLL-reduced kernel lattice bases: background and outline of the main result

Coauthors: Frederik von J. Heymann, Andrea Lodi, Laurence A. Wolsey


The so-called lattice reformulation of an integer program has been used to solve very hard instances. In this reformulation one expresses the vector of variables in terms of an integer linear combination of kernel lattice basis vectors. Most of the instances tackled so far have been extremely hard even in lower dimensions, so almost all of the computational experience so far is obtained for such instances. When solving larger instances one can observe a certain structure of the reduced kernel lattice bases. More specifically, a lattice basis will contain an identity matrix as a submatrix. This means that some of the variables will have a “rich” translation in terms of the lattice basis vectors, and that the other variables will be merely variable substitutions. In this presentation we address the theoretical reason for the structure to form. We give the necessary background and outline the main ingredients of the theoretical analysis.



Wednesday, 13:45 - 14:10 h, Room: H 2033, Talk 2

Frederik von Heymann
The structure of LLL-reduced kernel lattice bases: Theoretical details

Coauthors: Karen Aardal, Andrea Lodi, Laurence Wolsey


This presentation is continuation of the previous one. Here we go in more detail on how the various parts of the analysis are derived, and present several of the proofs. The key ingredient in our analysis is the result that, after a certain number
of iterations, the LLL-algorithm, with high probability, only performs size reductions and no swaps. In our derivation we use an
inequality derived by Azuma, as well as some Jensen-type inequalities. We illustrate our results computationally.



Wednesday, 14:15 - 14:40 h, Room: H 2033, Talk 3

Andrea Lodi
On cutting planes and lattice reformulations

Coauthors: Karen Aardal, Frederik von Heymann, Laurence A. Wolsey


Lattice reformulations have been traditionally used to deal with Integer Programming problems that are difficult to solve by branching on variables. We discuss full and/or partial lattice reformulations performed with the aim of generating cutting planes, which are then mapped back in the original space of variables.


  Payday Loans In New Jersey. But at the same time, it acts only with sexual arousal. Buy Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.