A graph-based decomposition method for convex quadratic optimization with indicators

• 成果类型: Article
• 署名作者: Liu, Peijing; Fattahi, Salar; Gomez, Andres; Kucukyavuz, Simge
• 署名单位: University of Southern California; University of Michigan System; University of Michigan; Northwestern University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01845-0
• 发表日期: 2023
• 页码: 669-701
• 关键词: markov random-fields; lot-sizing problems; subset-selection; REFORMULATION; formulations; PROGRAMS; cuts

摘要

In this paper, we consider convex quadratic optimization problems with indicator variables when the matrix Q defining the quadratic term in the objective is sparse. We use a graphical representation of the support of Q, and show that if this graph is a path, then we can solve the associated problem in polynomial time. This enables us to construct a compact extended formulation for the closure of the convex hull of the epigraph of the mixed-integer convex problem. Furthermore, motivated by inference problems with graphical models, we propose a novel decomposition method for a class of general (sparse) strictly diagonally dominant Q, which leverages the efficient algorithm for the path case. Our computational experiments demonstrate the effectiveness of the proposed method compared to state-of-the-art mixed-integer optimization solvers.