(426d) A Systematic Approach for Infeasibility Diagnosis in NLP and MINLP

With increase in the computing power available, optimization models used to make business and engineering decisions are becoming more and more complex. As models continue to grow larger, analyzing models giving erroneous results and correcting them becomes increasingly difficult. Identification of Irreducible Inconsistent Sets (IIS) in a model can help speed up the process of correcting infeasible models [1]. An Irreducible Inconsistent Set is defined as an infeasible set of constraints with every proper subset being feasible. Identifying an IIS provides the modeller with a set of mutual inconsistencies that need to be eliminated. However, efficient implementations for IIS isolation are only available for linear programs (LPs).

We propose a novel approach for IIS identification that is applicable to NLPs and MINLPs. This approach makes use of feasibility-based reduction techniques in a computationally inexpensive preprocessing stage to test for infeasibility in subparts of the infeasible model. This stage allows for rapid elimination of a large number of constraints in the model. Further, this preprocessing step itself could be sufficient to eliminate all constraints not part of an IIS for a large number of problems. The reduced model obtained can be filtered with any standard IIS isolation algorithm to obtain an IIS. The benefits of the approach lie in the efficient reduction in the model obtained by the preprocessing stage which leads to speedups in IIS identification.

We implement our proposed preprocessing algorithm in the global solver BARON along with four different filtering algorithms: deletion filter, addition filter, addition-deletion filter and depth-first binary search filter [2]. We have compiled a test library of more than a 1000 infeasible models derived from problems submitted to BARON over the NEOS server in 2012 and 2013. We exhaustively test our implementation on this library and present computational results on the efficacy of the proposed preprocessing algorithm, as well as comparisons on the performance of different filtering algorithms.

This work was inspired by interactions with Air Liquide.

[1] H. J. Greenberg. An empirical analysis of infeasibility diagnosis for instances of linear programming blending models. IMA Journal of Mathematics in Business and Industry, 3:163-210, 1992.

[2] J. W. Chinneck. Feasibility and infeasibility in optimization. Springer, 2008.