On partial convexification cuts for mixed-integer quadratic programs with 0-1 indicators
Rui Ma, Renaud Chicoisne, Pierre Latouche
Abstract
This paper studies mixed-integer quadratic programming (MIQP) problems with 0--1 indicator constraints.We propose two cut-generation algorithms under three reformulation schemes, which can be seamlessly embedded into a branch-and-bound framework.The algorithms are based on a partial convexification strategy applied to selected subsets of variables, enabling the efficient generation of both quadratic and linear cuts.We provide theoretical insights by characterizing the generated cuts as deepest cuts and by comparing quadratic cuts with their linear counterparts in different variable spaces, thereby bridging convexification theory and practical MIQP solution methods.Furthermore, we develop three practical strengthening techniques that exploit structural properties of the quadratic terms.Extensive computational experiments demonstrate that the proposed cut-generation algorithms meaningfully improve solver performance by accelerating convergence to optimal solutions.