Mirror-descent methods in mixed-integer convex optimization
Baes M, Oertel T, Wagner C, Weismantel R (2013)
Publication Type: Book chapter / Article in edited volumes
Publication year: 2013
Publisher: Springer-Verlag
Edited Volumes: Facets of Combinatorial Optimization
City/Town: Berlin, Heidelberg
Pages Range: 101-131
ISBN: 9783642381898
DOI: 10.1007/978-3-642-38189-8_5
Abstract
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 with a novel geometric construction how to implement the oracle 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.
Authors with CRIS profile
Involved external institutions
Switzerland (CH)How to cite
APA:
Baes, M., Oertel, T., Wagner, C., & Weismantel, R. (2013). Mirror-descent methods in mixed-integer convex optimization. In Michael Jünger, Gerhard Reinelt (Eds.), Facets of Combinatorial Optimization. (pp. 101-131). Berlin, Heidelberg: Springer-Verlag.
MLA:
Baes, Michel, et al. "Mirror-descent methods in mixed-integer convex optimization." Facets of Combinatorial Optimization. Ed. Michael Jünger, Gerhard Reinelt, Berlin, Heidelberg: Springer-Verlag, 2013. 101-131.
BibTeX: Download