Deletion Presolve for Accelerating Infeasibility Diagnosis in Optimization Models

Yash Puranik () and Nikolaos V. Sahinidis ()
Additional contact information
Yash Puranik: Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Nikolaos V. Sahinidis: Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213

INFORMS Journal on Computing, 2017, vol. 29, issue 4, 754-766

Abstract: Whereas much research in the area of optimization is directed toward developing algorithms for optimization of feasible models, the diagnosis of infeasible models has not received as much attention. Identification of irreducible infeasible sets (IISs) can facilitate the process of correcting infeasible models. Several filtering algorithms have been proposed for IIS identification but efficient implementations are available only for linear programs. We propose a novel approach for IIS identification that is applicable to linear programs (LPs), nonlinear programs (NLPs), mixed-integer linear programs (MIPs), and mixed-integer nonlinear programs (MINLPs). The approach makes use of a deletion presolve procedure that exploits bounds tightening techniques to reduce the model to an infeasible set (IS) in a computationally efficient manner. The IS is subsequently reduced to an IIS by applying one of the currently available exact filtering algorithms for IIS identification. We implement the proposed deletion presolve along with four filtering algorithms for IIS identification within the global solver BARON. The effectiveness and usefulness of the proposed approach is demonstrated through computational experiments on a test set of 790 infeasible LPs, NLPs, MIPs, and MINLPs. Deletion presolve rapidly eliminates a large fraction of the problem constraints and speeds up the filtering algorithms by over forty times on average. Speedups of as high as 1,000 times are observed for some problems, while, for 40% of the test problems, the deletion presolve itself reduces the original model to an IIS.

Keywords: infeasibility analysis; irreducible infeasible sets; constraint programming; MINLP (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0761 (application/pdf)

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:inm:orijoc:v:29:y:2017:i:4:p:754-766

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().