Computing deep facet-defining disjunctive cuts for mixed-integer programming

Florent Cadoux (1)

1 BIPOP - Modelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems

The problem of separation is to find an affine hyperplane, or ''cut'', that lies between the origin O and a given closed convex set Q in a Euclidean space. We focus on cuts which are deep for the Euclidean distance, and facet-defining. The existence of a unique deepest cut is shown and cases when it is decomposable as a combination of facet-defining cuts are characterized using the reverse polar set. When Q is a split polyhedron, a new description of the reverse polar is given. A theoretical successive projections algorithm is proposed that could be used to compute deep facet-defining split cuts.

Mots clés: integer programming; separation; cut generation; disjunctive cut; convex analysis; reverse polar

Domaines: Optimisation et contrôle [math.OC]

Florent Cadoux. Computing deep facet-defining disjunctive cuts for mixed-integer programming. [Research Report] RR-6177, INRIA. 2007, pp.22. ⟨inria-00144289v2⟩