Facial reduction heuristics and the motivational example of mixed-integer conic optimization
Facial reduction heuristics and the motivational example of mixed-integer conic optimization
复制标题
面部缩减启发式和混合整数圆锥优化的动机示例
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Henrik A. Friberg
中科院分区：
文献类型：
--
作者：
Henrik A. Friberg
开发面部还原启发式方法是为了提高性能和混合锥优化方法的可靠性。具体而言，显示出分支和结合的过程被证明是难以解决圆锥松弛的子问题，并且线性弛豫的客观界限是任意弱的。尽管面部减少算法已经存在来解决这些问题，但由于其固有的速度和准确性，启发式变体代表了非常有效的补充。该论文涵盖了基于线性优化，亚级别匹配，单键分析和锥体分解的启发式方法。
Facial reduction heuristics are developed in the interest of added performance and reliability in methods for mixed-integer conic optimization. Specifically, the process of branch-and-bound is shown to spawn subproblems for which the conic relaxations are difficult to solve, and the objective bounds of linear relaxations are arbitrarily weak. While facial reduction algorithms already exist to deal with these issues, heuristic variants represent a very potent supplement due to their inherent speed and accuracy. The paper covers a family of heuristics based on linear optimization, subgradient matching, single-cone analysis, and cone factorization.