Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem
- PDF / 407,337 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 78 Downloads / 152 Views
Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem Alexander Engau · Miguel F. Anjos · Immanuel Bomze
Received: 21 May 2012 / Accepted: 4 February 2013 / Published online: 6 March 2013 © Springer-Verlag Berlin Heidelberg 2013
Abstract The stable-set problem is an NP-hard problem that arises in numerous areas such as social networking, electrical engineering, environmental forest planning, bioinformatics clustering and prediction, and computational chemistry. While some relaxations provide high-quality bounds, they result in very large and expensive conic optimization problems. We describe and test an integrated interior-point cutting-plane method that efficiently handles the large number of nonnegativity constraints in the popular doubly-nonnegative relaxation. This algorithm identifies relevant inequalities dynamically and selectively adds new constraints in a build-up fashion. We present computational results showing the significant benefits of this approach in comparison to a standard interior-point cutting-plane method. Keywords Stable set · Maximum clique · Theta number · Semidefinite programming · Interior-point algorithms · Cutting-plane methods · Combinatorial optimization
Alexander Engau: Research partially supported by the DFG Emmy Noether project “Combinatorial Optimization in Physics (COPhy)” at the University of Cologne, Germany and by MITACS, a Network of Centres of Excellence for the Mathematical Sciences in Canada. Miguel F. Anjos: Research partially supported by the Natural Sciences and Engineering Research Council of Canada, and by a Humboldt Research Fellowship. A. Engau (B) University of Colorado Denver, Denver, CO, USA e-mail: [email protected] M. F. Anjos GERAD & École Polytechnique de Montréal, Montréal, QC , Canada e-mail: [email protected] I. Bomze University of Vienna, Vienna, Austria e-mail: [email protected]
123
36
Mathematical Subject Classifications 90C35 · 90C51 · 90C90
A. Engau et al.
90C09 · 90C20 · 90C22 · 90C27 ·
1 Introduction The generalization of interior-point methods (IPMs) from linear programming (LP) to conic convex optimization by Nesterov and Nemirovskii (1994) and specifically to semidefinite programming (SDP) by Alizadeh (1995) has had a major impact on the development of tractable approximations for many NP-hard combinatorial problems. As summarized in the recent survey by Rendl (2012), however, in contrast to algorithms for LP that have reached a high level of sophistication and have become accessible even for non-experts, there is still no standard way to solve medium-sized SDP problems beyond a few hundred variables in a routine manner. In particular, Rendl (2012) stresses the great relevance of the open problem of finding efficient ways to solve optimization problems over the set of so-called doubly nonnegative matrices, i.e., semidefinite matrices with nonnegative entries. Such problems arise in a variety of settings, most notably in network optimization and extr
Data Loading...
