Deriving intersection cuts from wide split disjunctions

30/04/2015 - 15:00
Sala del Consiglio
Sven Wiese

A classical way to derive Intersection cuts is based on simple split disjunctions that are valid for the integer variables of a Mixed Integer Linear Programming (MILP) model. Instead, we consider MILP models with integer variables that have natural "holes'' inside their domain, i.e., there are integer values inside the bounds of the variable that cannot be taken in a feasible (or optimal) solution. This kind of disjunctions, that we call wide split disjunctions, are stronger than simple splits, and we show how to separate Intersection cuts from these wide splits in optimal simplex tableuas. We show preliminary computational results on a small set of MIPLIB 2010 instances with holes that were generated randomly.