Binary Extended Formulations and Sequential Convexification

• 成果类型: Article
• 署名作者: Aprile, Manuel; Conforti, Michele; Di Summa, Marco
• 署名单位: University of Padua
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.0129
• 发表日期: 2024
• 页码: 1566-1581
• 关键词: convex-hull

摘要

A binarization of a bounded variable x is obtained via a system of linear inequalities that involve x together with additional variables y(1), ... , y(t) in [0,1] so that the integrality of x is implied by the integrality of y(1), ... , y(t). A binary extended formulation of a mixedinteger 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.