Quadratic integer programming for large scale banded matricesThis paper is concerned with the integer quadratic program where the variables are constrained to belong to a given set of discrete values. This quadratic integer program is shown to be equivalent to a problem of finding the shortest path in a particular directed graph called a trellis when the matrix is a positive-definite symmetric banded matrix. An efficient procedure for solving this shortest path problem is presented which allows the solution of the integer quadratic program. This method is particularly effective when the half-bandwidth of the matrix is significantly smaller than its dimension.
Document ID
19840059598
Acquisition Source
Legacy CDMS
Document Type
Conference Paper
Authors
Yan, T. Y. (California Institute of Technology, Jet Propulsion Laboratory, Pasadena CA, United States)
Tan, H. H. (Jet Propulsion Lab., California Inst. of Tech. Pasadena, CA, United States)