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

Alain Billionnet (), Sourour Elloumi (), Amélie Lambert () and Angelika Wiegele ()
Additional contact information
Alain Billionnet: ENSIIE-CEDRIC, FR-91025 Evry, France
Sourour Elloumi: ENSTA-CEDRIC, 91762 Palaiseau Cedex, France
Amélie Lambert: CNAM-CEDRIC, FR-75141 Paris Cedex 03, France
Angelika Wiegele: Institut für Mathematik, Alpen-Adria-Universität Klagenfurt, Austria

INFORMS Journal on Computing, 2017, vol. 29, issue 2, 318-331

Abstract: 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: semidefinite programming; Lagrangian duality; subgradient algorithm; bundle method; convex reformulation; quadratic 0–1 programming; k -cluster; densest subgraph (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2016.0731 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:29:y:2017:i:2:p:318-331

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().