Binary Extended Formulations and Sequential Convexification

A binarization of a bounded variable x is obtained via a system of linear inequalities that involve x together with additional variables $y_1,\dots ,y_t$ in $[0,1]$ so that the integrality of x is implied by the integrality of $y_1,\dots ,y_t$. A binary extended formulation of a mixed-integer linear set is obtained by adding to its original description binarizations of its integer variables. Binary extended formulations are useful in mixed-integer programming as imposing integrality on 0/1 variables rather than on general integer variables has interesting convergence properties and has been studied from both the theoretical and practical points of view. We study the behavior of binary extended formulations with respect to sequential convexification. In particular, given a binary extended formulation and one of its variables x, we study a parameter that measures the progress made toward enforcing the integrality of x via application of sequential convexification. We formulate this parameter, which we call rank, as the solution of a set-covering problem and express it exactly for the classic binarizations from the literature.

Funding: M. Aprile and M. Di Summa are supported by the University of Padova [SID 2019 Grant C94I20000280005].