|
 
|
[BEL17] Using a conic bundle method to accelerate both phases of a quadratic convex reformulation
Revue Internationale avec comité de lecture : Journal Informs journal on Computing, vol. 29(2), pp. 318-331, 2017, (doi:10.1287/ijoc.2016.0731)Mots clés: Semidefinite programming, Lagrangian duality, Subgradient algorithm, Bundle method, Convex reformulation, Quadratic 0-1 programming, k-cluster, Densest sub-graph
Résumé:
We present algorithm MIQCR-CB that is an advancement of method MIQCR (Billionnet, Elloumi and Lambert, 2012). 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 ), and, in the second phase, the equivalent formulation is solved by a standard solver. As the reformulation relies on the solution of a large-scale semidefinite program, it is not tractable by existing semidefinite solvers, already 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 origi-
nal MIQCR. We also compare MIQCR-CB with QCR (Billionnet, Elloumi and Plateau, 2009) and with BiqCrunch (Krislock, Malick and Roupin, 2013)
two methods devoted to binary quadratic programming. We show that MIQCR-CB is able to solve most of the 225 considered instances within 3
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 while Couenne and Cplex12.6 are not able to solve half out of them.
BibTeX
| @article { | |||
| BEL17, | |||
| title | = | "{Using a conic bundle method to accelerate both phases of a quadratic convex reformulation}", | |
| author | = | "A. Billionnet and S. Elloumi and A. Lambert and A. Wiegele", | |
| journal | = | "Informs journal on Computing", | |
| year | = | 2017, | |
| volume | = | 29, | |
| number | = | 2, | |
| pages | = | "318-331", | |
| doi | = | "10.1287/ijoc.2016.0731", | |
| } | |||
