Journal Article

Identifying relatively irreducible infeasible subsystems of linear inequalities

Poss, Michael, Omer Jérémy

2021

Overview

A classical problem in the study of an infeasible system of linear inequalities is to determine irreducible infeasible subsystems of inequalities (IISs), i.e., infeasible subsets of inequalities whose proper subsets are feasible. In this article, we examine a particular situation where only a given subsystem is of interest for the analysis of infeasibility. For this, we define relatively irreducible infeasible subsystems (RIISs) as infeasible subsystems of inequalities that are irreducible with respect to a given subsystem. It is a generalization of the definition of an IIS, since an IIS is irreducible with respect to the full system. We provide a practical characterization of RIISs, making the link with the alternative polyhedron commonly used in the detection of IISs. We then turn to the study of the RIISs that can be obtained from the Phase I of the simplex algorithm. We answer an open question regarding the covering of the clusters of IISs and show that this result cannot be generalized to RIISs. We thus develop a practical algorithm to find a covering of the clusters of RIISs. Our findings are numerically illustrated on the Netlib infeasible linear programs.

• Publisher: Springer Nature B.V
• Subject: Algorithms / Clusters / Inequalities / Linear functions / Linear programming / Operations research / Subsystems