Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Mirror-descent methods in mixed-integer convex optimization

Baes, Michel, Oertel, Timm, Wagner, Christian and Weismantel, Robert 2013. Mirror-descent methods in mixed-integer convex optimization. In: Junger, Michael and Reinelt, Gerhard eds. Facets of Combinatorial Optimization: Festschrift for Martin Grötschel, Springer, pp. 101-131. (10.1007/978-3-642-38189-8_5)

[img]
Preview
PDF - Submitted Pre-Print Version
Download (261kB) | Preview

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.

Item Type: Book Section
Date Type: Publication
Status: Published
Schools: Mathematics
Subjects: Q Science > QA Mathematics
Publisher: Springer
ISBN: 9783642381881
Last Modified: 04 Jun 2017 08:52
URI: http://orca.cf.ac.uk/id/eprint/86765

Citation Data

Cited 1 time in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics