Exponential mixed-integer lower bound for general binary oracles
Exponential mixed-integer lower bound for general binary oracles
Let be the number of integer variables, let be the continuous dimension, and let , , , and be the problem parameters. A first-order chart determines a general binary oracle. Mixed-integer binary lower-bound conjecture. There exists a first-order chart such that the general binary oracle based on has information complexity
The conjecture transfers the proposed quadratic continuous-case binary-oracle lower bound to mixed-integer convex optimization; the cited continuous-case results motivate it, but it remains open.
Sources & referencesView supporting material
Primary source
Amitabh Basu, Hongyi Jiang, Phillip Kerger and Marco Molinaro, “Information Complexity of Mixed-integer Convex Optimization”, arXiv:2308.11153 (2023).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.