Total Unimodularity and Strongly Polynomial Solvability of Constrained Minimum Input Selections for Structural Controllability: An LP-Based Method

This article investigates several cost-sparsity-induced optimal input selection problems for structured systems. Given an autonomous system and a prescribed set of input links, where each input link has a nonnegative cost, the problems include selecting the minimum cost of input links and selecting the input links with the smallest possible cost while bounding their cardinality to achieve system structural controllability. Current studies show that in the dedicated input case, the former problem is polynomially solvable by some graph-theoretic algorithms, while the general nontrivial constrained case is largely unexplored. We show that these problems can be formulated as equivalent integer linear programming (ILP) problems. Subject to the “source strongly connected component grouped input constraint,” which contains the dedicated input one as a special case, we demonstrate that the constraint matrices of these ILPs are
totally unimodular
. This property allows us to solve these ILPs efficiently via their linear programming (LP) relaxations, leading to a unifying algebraic method for these problems with polynomial time complexity. We further show that these problems can be solved in strongly polynomial time, independent of the size of the costs and cardinality bounds. Finally, we provide an example to illustrate the power of the proposed method.