Universität zu Köln

Aardal, Karen and von Heymann, Frederik ORCID: 0000-0001-9640-543X (2014). On the Structure of Reduced Kernel Lattice Bases. Math. Oper. Res., 39 (3). S. 823 - 841. CATONSVILLE: INFORMS. ISSN 1526-5471

Full text not available from this repository.

Abstract

Lattice-based reformulation techniques have been used successfully both theoretically and computationally. One such reformulation is obtained from the kernel lattice associated with an input matrix. Some of the hard instances in the literature that have been successfully tackled by lattice-based techniques have randomly generated input. 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 the kernel lattice 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 nontrivial way. In this paper we partially explain, through a probabilistic analysis, the obtained structure of the LLL-reduced basis in the case that the input matrix consists of one row. The key ingredient is a bound on the probability that the LLL-algorithm will interchange two subsequent basis vectors.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Aardal, Karen UNSPECIFIED UNSPECIFIED UNSPECIFIED von Heymann, Frederik UNSPECIFIED orcid.org/0000-0001-9640-543X UNSPECIFIED
URN:	urn:nbn:de:hbz:38-432237
DOI:	10.1287/moor.2013.0628
Journal or Publication Title:	Math. Oper. Res.
Volume:	39
Number:	3
Page Range:	S. 823 - 841
Date:	2014
Publisher:	INFORMS
Place of Publication:	CATONSVILLE
ISSN:	1526-5471
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language BASIS REDUCTION; INTEGER KNAPSACKS; VARIABLES; INEQUALITIES; PROBABILITY; PROGRAMS; NUMBERS; BOUNDS Multiple languages Operations Research & Management Science; Mathematics, Applied Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/43223