K-best feasible clusters - ranking optimal solutions from an infeasible LP. Issue 2 (2nd April 2020)

• Record Type: Journal Article
• Authors: Amaral, Paula Alexandra; Barahona, Pedro
• Is Part Of: Infor. Volume 58:Issue 2(2020)
• Page Start: 402
• Page End: 423
• Publication Date: 2020-04-02
• Subjects: Infeasibility analysis -- feasible clusters -- infeasible LP -- ranking of solutions -- computer assisted methods; Operations research -- Periodicals; Electronic data processing -- Periodicals; Systems engineering -- Periodicals; Systems engineering; Electronic data processing; Periodicals; 003.05
• DOI: 10.1080/03155986.2020.1729064
• Languages: English
• ISSNs: 0315-5986

Abstract

Abstract: Analysing conflicts in large optimization problems is an intricate and difficult task. In this paper we present a tool for infeasible LP, to guide the decision maker towards an adequate strategy for dealing with the infeasibility. We propose a mathematical formulation for the ranking of the optimal values and solutions among all feasible subsets of constraints, that is, to find (feasible) clusters of constraints that yield the K-best optimal values (K-Best Feasible Clusters). This, practical and easily interpretable information can be crucial for deciding which constraints to drop from the original infeasible model. Even for small problems this analysis cannot be conducted manually as a simple two-dimensional problem shows. Exploiting the structure of the formulation, an iterative procedure is proposed to solve the problem.