On the Structure of Reduced Kernel Lattice Bases

Karen Aardal, Frederik von Heymann

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

Abstract

Lattice-based reformulation techniques have been used successfully both theoretically and computationally. One such reformulation is obtained from the lattice kerℤ(A) = {x ∈ ℤ n |Ax = 0}. Some of the hard instances in the literature that have been successfully tackled by lattice-based techniques, such as market split and certain classes of knapsack instances, have randomly generated input A. These instances have been posed to stimulate algorithmic research. Since the considered instances are very hard even in low dimension, less experience is available for larger instances. Recently we have studied larger instances and observed that the LLL-reduced basis of kerℤ(A) has a specific sparse structure. In particular, this translates into a map in which some of the original variables get a “rich” translation into a new variable space, whereas some variables are only substituted in the new space. If an original variable is important in the sense of branching or cutting planes, this variable should be translated in a non-trivial way. In this paper we partially explain the obtained structure of the LLL-reduced basis in the case that the input matrix A consists of one row a. Since the input is randomly generated our analysis will be probabilistic. The key ingredient is a bound on the probability that the LLL algorithm will interchange two subsequent basis vectors. It is worth noticing that computational experiments indicate that the results of this analysis seem to apply in the same way also in the general case that A consists of multiple rows. Our analysis has yet to be extended to this general case. Along with our analysis we also present some computational indications that illustrate that the probabilistic analysis conforms well with the practical behavior.
Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization 16th International Conference, IPCO 2013
Subtitle of host publicationProceedings
EditorsMichel Goemans, José Correa
Place of PublicationHeidelberg
PublisherSpringer
Pages1-12
Number of pages12
ISBN (Electronic)978-3-642-36694-9
ISBN (Print)978-3-642-36693-2
DOIs
Publication statusPublished - 2013
EventIPCO 2013: 16th International Conference on Integer Programming and Combinatotical Optimization - Valparaiso, Chile
Duration: 18 Mar 201320 Mar 2013
Conference number: 16

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume7801

Conference

ConferenceIPCO 2013
Country/TerritoryChile
CityValparaiso
Period18/03/1320/03/13

Keywords

  • Basis Vector
  • Large Instance
  • Basis Reduction
  • Inal Variable
  • Practical Behavior

Fingerprint

Dive into the research topics of 'On the Structure of Reduced Kernel Lattice Bases'. Together they form a unique fingerprint.

Cite this