On Constrained Input Selections for Structured Systems: Polynomially Solvable Cases

Yuan Zhang*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Citations (Scopus)

Abstract

This paper investigates two related optimal input selection problems for structured systems. Given are an autonomous system and a set of inputs, where whether an input can directly actuate a state variable is given a priori, and each input has a non-negative cost. The problems are, selecting the minimum cost of inputs, and selecting the inputs with the smallest possible cost with a bound on their cardinality, all to ensure system structural controllability. Those problems are known to be NP-hard in general. In this paper, instead of finding approximation algorithms, we explore classes of systems on which those problems are polynomially solvable. We show subject to the so-called source strongly-connected component separated input constraint, which contains all the currently known nontrivial polynomially solvable cases as special ones, those problems can be solvable in polynomial time. We do this by first formulating those problems as equivalent integer linear programmings (ILPs), and then proving that the corresponding constraint matrices are totally unimodular. This property allows us to solve those ILPs efficiently simply via their linear programming (LP) relaxations, leading to a unifying algebraic method for these problems with polynomial time complexity. A numerical example is given to illustrate these results.

Original languageEnglish
Title of host publication2022 IEEE 61st Conference on Decision and Control, CDC 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages7529-7534
Number of pages6
ISBN (Electronic)9781665467612
DOIs
Publication statusPublished - 2022
Event61st IEEE Conference on Decision and Control, CDC 2022 - Cancun, Mexico
Duration: 6 Dec 20229 Dec 2022

Publication series

NameProceedings of the IEEE Conference on Decision and Control
Volume2022-December
ISSN (Print)0743-1546
ISSN (Electronic)2576-2370

Conference

Conference61st IEEE Conference on Decision and Control, CDC 2022
Country/TerritoryMexico
CityCancun
Period6/12/229/12/22

Keywords

  • Structural controllability
  • input selection
  • integer programming
  • linear programming
  • total unimodularity

Fingerprint

Dive into the research topics of 'On Constrained Input Selections for Structured Systems: Polynomially Solvable Cases'. Together they form a unique fingerprint.

Cite this