Paper Info
Title
Lattice preconditioning for the real relaxation branch-and-bound approach for integer least squares problems
Abstract
The integer least squares problem is an important problem that arises in numerous applications. We propose a real relaxation-based branch-and-bound (RRBB) method for this problem. First, we define a quantity called the distance to integrality, propose it as a measure of the number of nodes in the RRBB enumeration tree, and provide computational evidence that the size of the RRBB tree is proportional to this distance. Since we cannot know the distance to integrality a priori, we prove that the norm of the Moore−Penrose generalized inverse of the matrix of coefficients is a key factor for bounding this distance, and then we propose a preconditioning method to reduce this norm using lattice reduction techniques. We also propose a set of valid box constraints that help accelerate the RRBB method. Our computational results show that the proposed preconditioning significantly reduces the size of the RRBB enumeration tree, that the preconditioning combined with the proposed set of box constraints can significantly reduce the computational time of RRBB, and that the resulting RRBB method can outperform the Schnorr and Eucher method, a widely used method for solving integer least squares problems, on some types of problem data.
Year
DOI
Venue
2014
10.1007/s10898-014-0148-4
Journal of Global Optimization
Keywords
Field
DocType
Integer least squares,Branch-and-bound methods,Lattice reduction,Preconditioning,Box constraints
Branch and bound,Mathematical optimization,Lattice (order),Matrix (mathematics),Enumeration,A priori and a posteriori,Generalized inverse,Mathematics,Lattice reduction,Bounding overwatch
Journal
Volume
Issue
ISSN
59
2-3
0925-5001
Citations 
PageRank 
References 
3
0.40
21
Authors
3
Name
Order
Citations
PageRank
Miguel F. Anjos133732.09
Xiao-Wen Chang220824.85
Wen-Yang Ku371.48