Hybridization of Bound-and-Decompose and Mixed Integer Feasibility Checking to Measure Redundancy in Structured Linear Systems
- Additional Document Info
- View All
Computing the degree of redundancy for structured linear systems is proven to be NP-hard. A linear system whose model matrix is of size n × p is considered structured if some p row vectors in the model matrix are linearly dependent. Bound-and-decompose and 0-1 mixed integer programming (MIP) are two approaches to compute the degree of redundancy, which were previously proposed and compared in the literature. In this paper, first we present an enhanced version of the bound-and-decompose algorithm, which is substantially (up to 30 times) faster than the original version. We then present a novel hybrid algorithm to measure redundancy in structured linear systems. This algorithm uses a 0-1 mixed integer feasibility checking algorithm embedded within a bound-and-decompose framework. Our computational study indicates that this new hybrid approach significantly outperforms the existing algorithms as well as our enhanced version of bound-and-decompose in several instances. We also perform a computational study that shows matrix density has a significant effect on the runtime of the algorithms. © 2004-2012 IEEE.
IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING
author list (cited authors)
Bansal, M., Kianfar, K., Ding, Y. u., & Moreno-Centeno, E.
complete list of authors
Bansal, Manish||Kianfar, Kiavash||Ding, Yu||Moreno-Centeno, Erick
Degree Of Redundancy
Mixed Integer Programming
Structured Linear Model
Digital Object Identifier (DOI)
Additional Document Info