Identifying relatively irreducible infeasible subsystems of linear inequalities - Centre Henri Lebesgue Accéder directement au contenu
Article Dans Une Revue Annals of Operations Research Année : 2021

Identifying relatively irreducible infeasible subsystems of linear inequalities

Résumé

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.
Fichier principal
Vignette du fichier
IIS_anor_rev3.pdf (364.65 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03251527 , version 1 (01-09-2021)

Identifiants

Citer

Jérémy Omer, Michael Poss. Identifying relatively irreducible infeasible subsystems of linear inequalities. Annals of Operations Research, 2021, 304 (1-2), pp.361-379. ⟨10.1007/s10479-021-04126-9⟩. ⟨hal-03251527⟩
241 Consultations
1153 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More