Displaying similar documents to “Tree Elaboration Strategies in Branch-and-Bound Algorithms for Solving the Quadratic Assignment Problem”

An ex-post bound on the greedy heuristic for the uncapacitated facility location problem

Jean-Michel Thizy (2006)

RAIRO - Operations Research

Similarity:

A bound for the greedy heuristic applied to the K-facility location problem can be calculated, using values gathered during the calculation of the heuristic. The bound strengthens a well-known bound for the heuristic. Computational experiments show that this bound can be beneficial when the number of facilities is small or close to the total number of potential sites. In addition, it is consistent with previous results about the influence of the data characteristics upon the optimal...

Un Algorithme pour la Bipartition d'un Graphe en Sous-graphes de Cardinalité Fixée

Philippe Michelon, Stéphanie Ripeau, Nelson Maculan (2010)

RAIRO - Operations Research

Similarity:

A branch-and-bound method for solving the min cut with size constraint problem is presented. At each node of the branch-and-bound tree the feasible set is approximated by an ellipsoid and a lower bound is computed by minimizing the quadratic objective function over this ellipsoid. An upper bound is also obtained by a Tabu search method. Numerical results will be presented.