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] Genetic Algorithm Designed for Solving Linear or Nonlinear Mixed-Integer Constrained Optimization Problems
Jalota, Hemant
Thakur, Manoj
INTERNATIONAL PROCEEDINGS ON ADVANCES IN SOFT COMPUTING, INTELLIGENT SYSTEMS AND APPLICATIONS, ASISA 2016, 2018, 628 : 277 - 290
[42] Cut Scheduling Optimization in Plate Mill Finishing Area Through Mixed-Integer Linear Programming
Aurora, Claudio
Cettolo, Doretta
Cuzzola, Francesco Alessandro
IEEE TRANSACTIONS ON CONTROL SYSTEMS TECHNOLOGY, 2010, 18 (01) : 118 - 127
[43] A neural network-based distributional constraint learning methodology for mixed-integer stochastic optimization
Alcantara, Antonio
Ruiz, Carlos
EXPERT SYSTEMS WITH APPLICATIONS, 2023, 232
[44] Unit commitment considering generator outages through a mixed-integer particle swarm optimization algorithm
Wang, Lingfeng
Singh, Chanan
APPLIED SOFT COMPUTING, 2009, 9 (03) : 947 - 953
[45] PAPER Mixed-Integer Linear Optimization Formulations for Feature Subset Selection in Kernel SVM Classification
Tamura, Ryuta
Takano, Yuichi
Miyashiro, Ryuhei
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2024, E107A (08) : 1151 - 1162
[46] A decomposition heuristic for mixed-integer supply chain problems
Schewe, Lars
Schmidt, Martin
Weninger, Dieter
OPERATIONS RESEARCH LETTERS, 2020, 48 (03) : 225 - 232
[47] Technical Note: Multistage Robust Mixed-Integer Programming
Postek, Krzysztof
Romeijnders, Ward
Wiesemann, Wolfram
OPERATIONS RESEARCH, 2025,
[48] A mixed-integer optimization for bifacial two-terminal perovskite-on-perovskite tandem solar cells
Zhao, Xinhai
Tan, Hu Quee
Birgersson, Erik
Xue, Hansong
SOLAR ENERGY, 2023, 262
[49] Benchmarking CMA-ES with Basic Integer Handling on a Mixed-Integer Test Problem Suite
Marty, Tristan
Semet, Yann
Auger, Anne
Heron, Sebastien
Hansen, Nikolaus
PROCEEDINGS OF THE 2023 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE COMPANION, GECCO 2023 COMPANION, 2023, : 1628 - 1635
[50] Energy-Efficient Cooperative Routing in Wireless Sensor Networks: A Mixed-Integer Optimization Framework and Explicit Solution
Habibi, Jalal
Ghrayeb, Ali
Aghdam, Amir G.
IEEE TRANSACTIONS ON COMMUNICATIONS, 2013, 61 (08) : 3424 - 3437

← 1 2 3 4 5 →