Back to Search
Start Over
A graph-based decomposition method for convex quadratic optimization with indicators
- Source :
- Mathematical Programming.
- Publication Year :
- 2022
- Publisher :
- Springer Science and Business Media LLC, 2022.
-
Abstract
- 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, we propose a novel decomposition method for general (sparse) $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.
Details
- ISSN :
- 14364646 and 00255610
- Database :
- OpenAIRE
- Journal :
- Mathematical Programming
- Accession number :
- edsair.doi.dedup.....1a7623c7c08fc8adb0bdd4133ce747e8