e-journal

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 is considered structured if some 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. Note to Practitioners—People have long realized the importance of having sensor or measurement redundancy in a system as this redundancy
safeguards the system against sensor failures or measurement anomalies, so much so that the degree of redundancy is a reflection of the system’s reliability or fault-tolerance capability. Because of dependence relationship among the system’s components or subsystems, computing the degree of
redundancy is not a straightforward matter for practical systems which embed certain structure. Our paper presents an enhanced version of an existing method as well as a novel hybrid algorithm to calculate degree
of redundancy, which are significantly faster than the existing methods in many cases. These algorithms are a step forward in addressing this challenging problem.
Index Terms—Degree of redundancy, mixed integer programming, bound-and-decompose, NP-hard, structured linear model.

---

Ketersediaan

Tidak ada salinan data

Informasi Detail

Judul Seri

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING

No. Panggil

-

Penerbit

New York : IEEE., 2013

Deskripsi Fisik

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, VOL. 10, NO. 4, OCTOBER 2013

Bahasa

English

ISBN/ISSN

1545-5955

Klasifikasi

-

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

VOL. 10, NO. 4

Subjek

TEKNIK

Info Detail Spesifik

-

Pernyataan Tanggungjawab

yuli/agus

Versi lain/terkait

Lampiran Berkas

Komentar

---

Anda harus masuk sebelum memberikan komentar