Abstract:

Infeasibility is frequent in the early stages of developing a complex optimization model. For linear programs, algorithmic tools that assist in the analysis of infeasibility are well developed, and are available in most commercial LP solvers. There are two main approaches: (1) finding an irreducible infeasible subset of constraints and (2) finding the smallest set of constraints to remove such that the remainder constitute a feasible set. This tutorial talk will focus on these, with the goal of helping modellers make the most effective use of the available tools. Time permitting, we will also briefly explore the state of the art in infeasibility analysis for integer and nonlinear programs, and will also survey how infeasibility analysis algorithms are proving useful in applications such as data mining and logic programming.