2012/09/04 by Michel Baes, Timm Oertel, Baes, Michel +5
Computer Science · Engineering · Mathematics · #90C11 #Complexity and Algorithms in Graphs #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #math.OC #msc:90C11
paper · pdf · doi:10.48550/arxiv.1209.0686
arxiv created 2012/09/04 · openalex publication_date 2012/09/04 · arxiv updated 2012/09/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we address the problem of minimizing a convex function f over a convex set, with the extra constraint that some variables must be integer. This problem, even when f is a piecewise linear function, is NP-hard. We study an algorithmic approach to this problem, postponing its hardness to the realization of an oracle. If this oracle can be realized in polynomial time, then the problem can be solved in polynomial time as well. For problems with two integer variables, we show that the oracle can be implemented efficiently, that is, in O(ln(B)) approximate minimizations of f over the continuous variables, where B is a known bound on the absolute value of the integer variables.Our algorithm can be adapted to find the second best point of a purely integer convex optimization problem in two dimensions, and more generally its k-th best point. This observation allows us to formulate a finite-time algorithm for mixed-integer convex optimization.