Feasibility in reverse convex mixed-integer programming

In this paper we address the problem of the infeasibility of systems defined by reverse convex inequality constraints, where some or all of the variables are integer. In particular, we provide a polynomial algorithm that identifies a set of all constraints critical to feasibility (CF)(CF), that is constraints that may affect a feasibility status of the system after some perturbation of the right-hand sides. Furthermore, we will investigate properties of the irreducible infeasible sets and infeasibility sets, showing in particular that every irreducible infeasible set as well as infeasibility sets in the considered system, are subsets of the set CFCF of constraints critical to feasibility.

► We study the problem of infeasibility of mixed-integer systems of reverse convex constraints. ► Polynomial algorithm identifying a set of constraints critical to feasibility is proposed. ► Constraints critical to feasibility may affect a feasibility status of the system after perturbation of the right-hand sides. ► Irreducible infeasible sets and infeasibility sets belong to the set of constraints critical to feasibility.