EURO Journal on Computational Optimization (Mar 2017)

A multiplicative weights update algorithm for MINLP

  • Luca Mencarelli,
  • Youcef Sahraoui,
  • Leo Liberti

Journal volume & issue
Vol. 5, no. 1
pp. 31 – 86

Abstract

Read online

We discuss an application of the well-known multiplicative weights update (MWU) algorithm to non-convex and mixed-integer non-linear programming. We present applications to: (a) the distance geometry problem, which arises in the positioning of mobile sensors and in protein conformation; (b) a hydro unit commitment problem arising in the energy industry, and (c) a class of Markowitz’ portfolio selection problems. The interest of the MWU with respect to one of its closest competitors (classic multi-start) is that it provides a relative approximation guarantee on a certain quality measure of the solution.

Keywords