A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems
针对经济学和运筹学中常见的无增益列昂惕夫替代系统线性规划问题，提出了首个组合认证算法，能在强多项式时间内验证解的可行性，并解决了Horn系统可行性问题的长期公开难题。
Abstract Linear programming (LP) problems with gainfree Leontief substitution systems have been intensively studied in economics and operations research, and include the feasibility problem of a class of Horn systems, which arises in, e.g., polyhedral combinatorics and logic. This subclass of LP problems admits a strongly polynomial time algorithm, where devising such an algorithm for general LP problems is one of the major theoretical open questions in mathematical optimization and computer science. Recently, much attention has been paid to devising certifying algorithms in software engineering, since those algorithms enable one to confirm the correctness of outputs of programs with simple computations. Devising a combinatorial certifying algorithm for the feasibility for a fundamental class of Horn systems remains open for almost a decade. In this paper, we provide the first combinatorial (and strongly polynomial time) certifying algorithm for LP problems with gainfree Leontief substitution systems. As a by-product, we resolve the open question on the feasibility for the class of Horn systems.