Conic Mixed-Binary Sets: Convex Hull Characterizations and Applications

被引:1
作者
Kilinc-Karzan, Fatma [1 ]
Kucukyavuz, Simge [2 ]
Lee, Dabeen [3 ]
Shafieezadeh-Abadeh, Soroosh [1 ]
机构
[1] Carnegie Mellon Univ, Tepper Sch Business, Pittsburgh, PA 15213 USA
[2] Northwestern Univ, Dept Ind Engn & Management Sci, Evanston, IL 60208 USA
[3] Korea Adv Inst Sci & Technol, Dept Ind & Syst Engn, Daejeon 34141, South Korea
基金
新加坡国家研究基金会; 瑞士国家科学基金会;
关键词
conic mixed-binary sets; conic quadratic optimization; convex hull; submodularity; fractional binary optimization; best subset selection; PROGRAMS;
D O I
10.1287/opre.2020.0827
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
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.
引用
收藏
页码:251 / 269
页数:20
相关论文
共 38 条
[31]   Efficient computation of the convex hull on sets of points stored in a k-tree compact data structure [J].
Felipe Castro, Juan ;
Romero, Miguel ;
Gutierrez, Gilberto ;
Caniupan, Monica ;
Quijada-Fuentes, Carlos .
KNOWLEDGE AND INFORMATION SYSTEMS, 2020, 62 (10) :4091-4111
[32]   Efficient computation of the convex hull on sets of points stored in a k-tree compact data structure [J].
Juan Felipe Castro ;
Miguel Romero ;
Gilberto Gutiérrez ;
Mónica Caniupán ;
Carlos Quijada-Fuentes .
Knowledge and Information Systems, 2020, 62 :4091-4111
[33]   Some Classes of Valid Inequalities and Convex Hull Characterizations for Dynamic Fixed-Charge Problems under Nested Constraints [J].
Fred Glover ;
Hanif D. Sherali .
Annals of Operations Research, 2005, 140 :215-233
[34]   Some classes of valid inequalities and convex hull characterizations for dynamic fixed-charge problems under nested constraints [J].
Glover, F ;
Sherali, HD .
ANNALS OF OPERATIONS RESEARCH, 2005, 140 (01) :215-233
[35]   SOME CHARACTERIZATIONS OF ROBUST SOLUTION SETS FOR UNCERTAIN CONVEX OPTIMIZATION PROBLEMS WITH LOCALLY LIPSCHITZ INEQUALITY CONSTRAINTS [J].
Sisarat, Nithirat ;
Wangkeeree, Rabian ;
Lee, Gue Myung .
JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2020, 16 (01) :469-493
[36]   Convex hull method for the determination of vapour-liquid equilibria (VLE) phase diagrams for binary and ternary systems [J].
Joseph, Amieibibama ;
Sands, Christine M. ;
Hicks, Peter D. ;
Chandler, Howard W. .
FLUID PHASE EQUILIBRIA, 2017, 431 :34-47
[37]   Dual characterizations of set containments involving uncertain polyhedral sets in Banach spaces with applications [J].
Hedayat, A. ;
Mohebi, H. .
OPERATIONS RESEARCH LETTERS, 2020, 48 (05) :558-565
[38]   Characterizations of the Nonemptiness and Boundedness of Weakly Efficient Solution Sets of Convex Vector Optimization Problems in Real Reflexive Banach Spaces [J].
Deng, S. .
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2009, 140 (01) :1-7