A simple effective heuristic for embedded mixed-integer quadratic programming
A simple effective heuristic for embedded mixed-integer quadratic programming
复制标题
DOI：
10.1080/00207179.2017.1316016
复制
发表时间：
2020-01-01
影响因子：
2.1
通讯作者：
Bemporad, Alberto
中科院分区：
文献类型：
--
作者：
Takapoui, Reza;Moehle, Nicholas;Bemporad, Alberto
在本文中，我们提出了一个快速优化算法近似最小化凸二次函数的仿射和可分离的约束（即笛卡尔积的可能非凸真实的集）的交集。这类问题包含许多NP难问题，如混合整数二次规划。我们的启发式是基于交替方向的乘法器（ADMM），用于解决凸优化问题的算法的变化。我们讨论了有利的计算方面，我们的算法，这使得它能够快速运行，即使在非常温和的计算平台，如嵌入式处理器。我们给出了几个例子，其中一个近似的解决方案应该很快找到，如混合动力电动汽车传动系统的管理和开关模式电源转换器的控制。我们的数值实验表明，我们的方法是非常有效的，在寻找一个可行的点与小的目标值;事实上，我们看到，在许多情况下，它找到了全局解。
In this paper, we propose a fast optimisation algorithm for approximately minimising convex quadratic functions over the intersection of affine and separable constraints (i.e. the Cartesian product of possibly nonconvex real sets). This problem class contains many NP-hard problems such as mixed-integer quadratic programming. Our heuristic is based on a variation of the alternating direction method of multipliers (ADMM), an algorithm for solving convex optimisation problems. We discuss the favourable computational aspects of our algorithm, which allow it to run quickly even on very modest computational platforms such as embedded processors. We give several examples for which an approximate solution should be found very quickly, such as management of a hybrid-electric vehicle drivetrain and control of switched-mode power converters. Our numerical experiments suggest that our method is very effective in finding a feasible point with small objective value; indeed, we see that in many cases, it finds the global solution.