Using a Conic Bundle Method to Accelerate Both Phases of a Quadratic Convex Reformulation

We present algorithm MIQCR‐CB that is an advancement of MIQCR. MIQCR is a method for solving mixed‐integer quadratic programs and works in two phases: the first phase determines an equivalent quadratic formulation with a convex objective function by solving a semidefinite problem (SDP); in the second phase, the equivalent formulation is solved by a standard solver. Because the reformulation relies on the solution of a large‐scale semidefinite program, it is not tractable by existing semidefinite solvers even for medium‐sized problems. To surmount this difficulty, we present in MIQCR‐CB a subgradient algorithm within a Lagrangian duality framework for solving (SDP) that substantially speeds up the first phase. Moreover, this algorithm leads to a reformulated problem of smaller size than the one obtained by the original MIQCR method, which results in a shorter time for solving the second phase. We present extensive computational results to show the efficiency of our algorithm. First, we apply MIQCR‐CB to the k‐cluster problem that can be formulated by a binary quadratic program. As an illustration of the efficiency of our new algorithm, for instances of size 80 and of density 25%, MIQCR‐CB is on average 78 times faster for phase 1 and 24 times faster for phase 2 than the original MIQCR. We also compare MIQCR‐CB with QCR and with BiqCrunch, two methods devoted to binary quadratic programming. We show that MIQCR‐CB is able to solve most of the 225 considered instances within three hours of CPU time. We also present experiments on two classes of general integer instances where we compare MIQCR‐CB with MIQCR, Couenne, and Cplex12.6. We demonstrate the significant improvement over the original MIQCR approach. Finally, we show that MIQCR‐CB is able to solve almost all of the considered instances, whereas Couenne and Cplex12.6 are not able to solve half of them.