Information Complexity of Mixed-Integer Convex Optimization

被引：0

作者：

Basu, Amitabh ^{[1
]}

Jiang, Hongyi ^{[2
]}

Kerger, Phillip ^{[1
]}

Molinaro, Marco ^{[3
,4
]}

机构：

[1] Johns Hopkins Univ, Dept Appl Math & Stat, Baltimore, MD USA

[2] Cornell Univ, Sch Civil & Environm Engn, Ithaca, NY 14853 USA

[3] Microsoft Res, Redmond, WA 98052 USA

[4] Pontificia Univ Catolica Rio de Janeiro, Comp Sci Dept, Rio de Janeiro, Brazil

来源：

INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2023 | 2023年 / 13904卷

基金：

美国国家科学基金会;

关键词：

Mixed-integer optimization; Information complexity;

D O I：

10.1007/978-3-031-32726-1_1

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We investigate the information complexity of mixed-integer convex optimization under different kinds of oracles. We establish new lower bounds for the standard first-order oracle, improving upon the previous best known lower bound. This leaves only a lower order linear term (in the dimension) as the gap between the lower and upper bounds. Further, we prove the first set of results in the literature (to the best of our knowledge) on information complexity with respect to oracles based on first-order information but restricted to binary queries, and discuss various special cases of interest thereof.

引用

页码：1 / 13

页数：13

共 50 条

[41] Complexity of Branch-and-Bound and Cutting Planes in Mixed-Integer Optimization - II
Basu, Amitabh
Conforti, Michele
Di Summa, Marco
Jiang, Hongyi
COMBINATORICA, 2022, 42 (SUPPL 1) : 971 - 996
[42] Complexity of Branch-and-Bound and Cutting Planes in Mixed-Integer Optimization - II
Basu, Amitabh
Conforti, Michele
Di Summa, Marco
Jiang, Hongyi
INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2021, 2021, 12707 : 383 - 398
[43] Global mixed-integer dynamic optimization
Chachuat, B
Singer, AB
Barton, PI
AICHE JOURNAL, 2005, 51 (08) : 2235 - 2253
[44] Mixed-Integer Optimization with Constraint Learning
Maragno, Donato
Wiberg, Holly
Bertsimas, Dimitris
Birbil, S. . Ilker
den Hertog, Dick
Fajemisin, Adejuyigbe O.
OPERATIONS RESEARCH, 2023,
[45] Online Mixed-Integer Optimization in Milliseconds
Bertsimas, Dimitris
Stellato, Bartolomeo
INFORMS JOURNAL ON COMPUTING, 2022, 34 (04) : 2229 - 2248
[46] Convex Hull Formulations for Mixed-Integer Multilinear Functions
Nagarajan, Harsha
Sundar, Kaarthik
Hijazi, Hassan
Bent, Russell
14TH INTERNATIONAL GLOBAL OPTIMIZATION WORKSHOP (LEGO), 2019, 2070
[47] Irreducible Infeasible Sets in Convex Mixed-Integer Programs
Wiesława T. Obuchowska
Journal of Optimization Theory and Applications, 2015, 166 : 747 - 766
[48] Feasible partition problem in reverse convex and convex mixed-integer programming
Obuchowska, Wieslawa T.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2014, 235 (01) : 129 - 137
[49] Convex approximations for a class of mixed-integer recourse models
Van der Vlerk, Maarten H.
ANNALS OF OPERATIONS RESEARCH, 2010, 177 (01) : 139 - 150
[50] Irreducible Infeasible Sets in Convex Mixed-Integer Programs
Obuchowska, Wiesawa T.
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2015, 166 (03) : 747 - 766

← 1 2 3 4 5 →