This article presents
BiqCrunch
, an exact solver for binary quadratic optimization problems.
BiqCrunch
is a branch-and-bound method that uses an original, efficient semidefinite-optimization-based ...bounding procedure. It has been successfully tested on a variety of well-known combinatorial optimization problems, such as Max-Cut, Max-
k
-Cluster, and Max-Independent-Set. The code is publicly available online; a web interface and many conversion tools are also provided.
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 depends on 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.
This computational paper presents a method to solve k-cluster problems exactly by intersecting semidefinite and polyhedral relaxations. Our algorithm uses a generic branch-and-bound method featuring ...an improved semidefinite bounding procedure. Extensive numerical experiments show that this algorithm outperforms the best known methods both in time and ability to solve large instances. For the first time, numerical results are reported for k-cluster problems on unstructured graphs with 160 vertices.
•Semidefinite-based method to solve k-cluster problems to optimality.•Extensive numerical experiments and theoretical analysis.•Compared favorably with best existing methods.•For the first time, k-cluster instances on graphs with 160 nodes solved to optimality.
This article presents a family of semidefinite programming bounds, obtained by Lagrangian duality, for 0–1 quadratic optimization problems with linear or quadratic constraints. These bounds have ...useful computational properties: they have a good ratio of tightness to computing time, they can be optimized by a quasi-Newton method, and their final tightness level is controlled by a real parameter. These properties are illustrated on three standard combinatorial optimization problems: unconstrained 0–1 quadratic optimization, heaviest
-subgraph, and graph bisection.
(ProQuest: ... denotes formulae and/or non-USASCII text omitted; see image) Issue Title: Special Issue on Mixed Integer Nonlinear Programming (MINLP) This paper deals with the computation of exact ...solutions of a classical NP-hard problem in combinatorial optimization, the ...-cluster problem. This problem consists in finding a heaviest subgraph with ... nodes in an edge weighted graph. We present a branch-and-bound algorithm that applies a novel bounding procedure, based on recent semidefinite programming techniques. We use new semidefinite bounds that are less tight than the standard semidefinite bounds, but cheaper to get. The experiments show that this approach is competitive with the best existing ones.PUBLICATION ABSTRACT
We present a survey about the maximum integral multiflow and minimum multicut problems and their subproblems, such as the multiterminal cut and the unsplittable flow problems. We consider neither ...continuous multiflow nor minimum cost multiflow. Most of the results are very recent and some are new. We recall the dual relationship between both problems, give complexity results and algorithms, firstly in unrestricted graphs and secondly in several special graphs: trees, bipartite or planar graphs. A table summarizes the most important results.
This paper proposes a new method for solving the Machine Reassignment Problem in a very short computational time. The problem has been proposed by Google as subject of the Challenge ROADEF/EURO 2012. ...The Machine Reassignment Problem consists in looking for a reassignment of processes to machines in order to minimize a complex objective function, subject to a rich set of constraints including multidimensional resource, conflict and dependency constraints. In this study, a cooperative search approach is presented for machine reassignment. This approach uses two components: Adaptive Variable Neighbourhood Search and Simulated Annealing based Hyper-Heuristic, running in parallel on two threads and exchanging solutions. Both algorithms employ a rich set of heuristics and a learning mechanism to select the best neighborhood/move type during the search process. The cooperation mechanism acts as a multiple restart which gets triggered whenever a new better solution is achieved by a thread and then shared with the other thread. Computational results on the Challenge instances as well as instances of a Generalized Assignment-like problem are given to show the relevance of the chosen methods and the high benefits of cooperation.
We give a complete characterization of constant quadratic functions over an affine variety. This result is used to convexify the objective function of a general quadratic programming problem (Pb) ...which contains linear equality constraints. Thanks to this convexification, we show that one can express as a semidefinite program the dual of the partial Lagrangian relaxation of (Pb) where the linear constraints are not relaxed. We apply these results by comparing two semidefinite relaxations made from two sets of null quadratic functions over an affine variety.
Multicuts and integral multiflows in rings Bentz, Cédric; Costa, Marie-Christine; Létocart, Lucas ...
European journal of operational research,
08/2009, Letnik:
196, Številka:
3
Journal Article
Recenzirano
Odprti dostop
We show how to solve in polynomial time the multicut and the maximum integral multiflow problems in rings. Moreover, we give linear-time procedures to solve both problems in rings with uniform ...capacities.
PDF
