Identifying relatively irreducible infeasible subsystems of linear inequalities

Jérémy Omer () and Michael Poss ()
Additional contact information
Jérémy Omer: Univ Rennes
Michael Poss: University of Montpellier

Annals of Operations Research, 2021, vol. 304, issue 1, No 14, 379 pages

Abstract: Abstract 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.

Keywords: Systems of linear inequalities; Irreducible infeasible set; Conflict analysis; Linear programming (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-021-04126-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:304:y:2021:i:1:d:10.1007_s10479-021-04126-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-021-04126-9

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().