Can an infeasible MIP solve itself?

Abstract: The analysis of why a specific MIP instance is infeasible formally can be reduced to computing an Irreducible Infeasible Subset (IIS) of the constraints. Unlike the case of LP, for MIP there is no useful duality that can be employed to facilitate such computations. The process of determining an IIS for MIP is typically handled with brute force, e.g., by use of deletion filters and alike, thus rendering IIS determination for a MIP into a much harder computational task. We will discuss one approach to optimizing this process and what components of this approach could make it into the newest version of Gurobi.

Mathematics

Audience: researchers in the topic

PIMS-CORDS SFU Operations Research Seminar