Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations

• 成果类型: Article; Proceedings Paper
• 署名作者: Lee, Jon; Skipper, Daphne; Speakman, Emily
• 署名单位: University of Michigan System; University of Michigan; United States Department of Defense; United States Navy; United States Naval Academy; Otto von Guericke University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1272-6
• 发表日期: 2018
• 页码: 121-140
• 关键词: polytope; optimization

摘要

This is mostly a survey on some mathematical results concerning volumes of polytopes of interest in non-convex optimization. Our motivation is in geometrically comparing relaxations in the context of mixed-integer linear and nonlinear optimization, with the goal of gaining algorithmic and modeling insights. We consider relaxations of: fixed-charge formulations, vertex packing polytopes, boolean-quadric polytopes, and relaxations of graphs of monomials on box domains. Besides surveying the area, we do give a few new results, and we provide many directions for further work.