Conic Mixed-Binary Sets: Convex Hull Characterizations and Applications

• 成果类型: Article
• 署名作者: Kilinc-Karzan, Fatma; Kucukyavuz, Simge; Lee, Dabeen; Shafieezadeh-Abadeh, Soroosh
• 署名单位: Carnegie Mellon University; Northwestern University; Korea Advanced Institute of Science & Technology (KAIST)
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2020.0827
• 发表日期: 2025
• 关键词: programs

摘要

We consider a general conic mixed-binary set where each homogeneous conic constraint j involves an affine function of independent continuous variables and an epigraph variable associated with a nonnegative function, fj, of common binary variables. Sets of this form naturally arise as substructures in a number of applications, including mean-risk optimization, chance-constrained problems, portfolio optimization, lot sizing and scheduling, fractional programming, variants of the best subset selection problem, a class of sparse semidefinite programs, and distributionally robust chance-constrained programs. We give a convex hull description of this set that relies on simultaneous characterization of the epigraphs of fj's, which is easy to do when all functions fj's are submodular. Our result unifies and generalizes an existing result in two important directions. First, it considers multiple general convex cone constraints instead of a single second-order cone type constraint. Second, it takes arbitrary nonnegative functions instead of a specific submodular function obtained from the square root of an affine function. We close by demonstrating the applicability of our results in the context of a number of problem classes.