Irreducible Infeasible Sets in Convex Mixed-Integer Programs

摘要

In this paper, we address the problem of infeasibility of systems defined by convex inequality constraints, where some or all of the variables are integer valued. In particular, we provide a polynomial time algorithm to identify a set of all constraints which may affect a feasibility status of the system after some perturbation of the right-hand sides. We establish several properties of the irreducible infeasible sets and infeasibility sets in the systems with integer variables, proving in particular that all irreducible infeasible sets and infeasibility sets are subsets of the set of constraints critical to feasibility. Furthermore, the well-known Bohnenblust-Karlin-Shapley Theorem, which requires that a system of convex inequality constraints must be defined over a compact convex set, is generalized to convex systems without the assumption on compactness of the convex region. Extension of the latter result to convex systems defined over the set of integers is also provided.