K-best feasible clusters - ranking optimal solutions from an infeasible LP

Research output: Contribution to journalArticle

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.

Original languageEnglish
Pages (from-to)402-423
Number of pages22
JournalINFOR
Volume58
Issue number4(SI)
DOIs
Publication statusPublished - 2020

Keywords

  • computer assisted methods
  • feasible clusters
  • Infeasibility analysis
  • infeasible LP
  • ranking of solutions

Cite this