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.
Keywords for this software
References in zbMATH (referenced in 4 articles , 1 standard article )
Showing results 1 to 4 of 4.
- Sotirov, Renata: On solving the densest (k)-subgraph problem on large graphs (2020)
- Anjos, Miguel F.; Neto, José: Spectral bounds for graph partitioning with prescribed partition sizes (2019)
- Billionnet, Alain; Elloumi, Sourour; Lambert, Amélie; Wiegele, Angelika: Using a conic bundle method to accelerate both phases of a quadratic convex reformulation (2017)
- Elloumi, Sourour; Lambert, Amélie: Comparison of quadratic convex reformulations to solve the Quadratic Assignment problem (2016)