Hybridization of Bound-and-Decompose and Mixed Integer Feasibility Checking to Measure Redundancy in Structured Linear Systems

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.