Improved semidefinite bounding procedure for solving Max-Cut problems to optimalityReport as inadecuate

Improved semidefinite bounding procedure for solving Max-Cut problems to optimality - Download this document for free, or read online. Document in PDF available to download.

* Corresponding author 1 BIPOP - Modelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble 2 LIPN - Laboratoire d-Informatique de Paris-Nord

Abstract : We present an improved algorithm for finding exact solutions to Max-Cut and the related binary quadratic programming problem, both classic problems of combinatorial optimization. The algorithm uses a branch-and-cut-and-bound paradigm, using standard valid inequalities and nonstandard semidefinite bounds. More specifically, we add a quadratic regularization term to the strengthened semidefinite relaxation in order to use a quasi-Newton method to compute the bounds. The ratio of the tightness of the bounds to the time required to compute them can be controlled by two real parameters; we show how adjusting these parameters and the set of strengthening inequalities gives us a very efficient bounding procedure. Embedding our bounding procedure in a generic branch-and-bound platform, we get a competitive algorithm: extensive experiments show that our algorithm dominates the best existing method.

keyword : combinatorial optimization semidefinite programming quasi-Newton algorithm triangle inequalities

Author: Nathan Krislock - Jérôme Malick - Frédéric Roupin -



Related documents