Deletion Presolve for Accelerating Infeasibility Diagnosis in Optimization Models

摘要

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.