branch-and-bound methods – Optimization Online

The Largest Unsolved QAP Instance Tai256c Can Be Converted into A 256-dimensional Simple BQOP with A Single Cardinality Constraint

Published: 2022/10/28

0-1 Programming, Branch and Cut Algorithms, Semi-definite Programming branch-and-bound methods, exploiting symmetry, Lagrangian-DNN relaxation, largest unsolved instance, newton-bracketing method, quadratic assignment problems

Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB; a 1.48\% gap remains between the best known feasible objective value and lower bound of the unknown optimal value. This paper shows that the instance can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which … Read more

MatQapNB User Guide: A branch-and-bound program for QAPs in Matlab with the Newton-Bracketing method

Published: 2021/06/09, Updated: 2021/08/31

Global Optimization Applications, Optimization Software Design Principles, Quadratic Programming branch-and-bound methods, matlab toolbox, newton-bracketing methods, quadratic assignment problems

MatQapNB is a MATLAB toolbox that implements a parallel branch-and-bound method using NewtBracket (the Newton bracketing method [4]) for its lower bounding procedure. It can solve small to medium scale Quadratic Assignment Problem (QAP) instances with dimension up to 30. MatQapNB was used in the numerical experiments on QAPs in the recent article “Solving challenging … Read more

Parallel Interval Continuous Global Optimization Algorithms

Published: 2002/07/19, Updated: 2002/07/20

Abdeljalil Benyoub

Branch and Cut Algorithms, Global Optimization, Parallel Algorithms branch-and-bound methods, constrained global optimization, hansen's algorithm, interval arithmetic, load balancing, parallelization

We theorically study, on a distributed memory architecture, the parallelization of Hansen’s algorithm for the continuous global optimization with inequality constraints, using interval arithmetic. We propose a parallel algorithm based on a dynamic redistribution of the working list among the processors. On the other hand, we exploit the reduction technique, developped by Hansen, for computing … Read more