On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0-1 quadratic problems leading to quasi-Newton methods

• 成果类型: Article
• 署名作者: Malick, Jerome; Roupin, Frederic
• 署名单位: Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Inria; Universite Paris 13; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0628-6
• 发表日期: 2013
• 页码: 99-124
• 关键词: relaxation; algorithm

摘要

This article presents a family of semidefinite programming bounds, obtained by Lagrangian duality, for 0-1 quadratic optimization problems with linear or quadratic constraints. These bounds have useful computational properties: they have a good ratio of tightness to computing time, they can be optimized by a quasi-Newton method, and their final tightness level is controlled by a real parameter. These properties are illustrated on three standard combinatorial optimization problems: unconstrained 0-1 quadratic optimization, heaviest k-subgraph, and graph bisection.