A Newton-Bracketing method for a simple conic optimization problem

NewtBracket is a Matlab package for solving a simple conic optimization problem that minimizes a linear objective function subject to a single linear equality constraint and a convex cone constraint. The problem is converted into the problem of finding the largest zero y* of a continuously differentiable (except at y*) convex function g such that g(y) = 0 if y <= y* and g(y) > 0 otherwise. The Newton-bracketing method generates a sequence of lower and upper bounds of y* both converging to y*. For applications, we present the Lagrangian doubly nonnegative relaxation of binary quadratic optimization problems, quadratic multiple knapsack problems, quadratic assignment problems, and maximum stable set problems.

S. Kim, M. Kojima and K.C. Toh, June 9, 2021

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 scale QAPs” [3] by Fujii, Ito, Kim, Kojima, Shinano and Toh, an intermediate progress report on the authors’ joint project for solve large-scale QAP instances in QAPLIB whose exact optimal values are unknown [2]. For large scale QAPs, the authors have been developing a C++ version of the method, QapNB, which works on the Ubiquity Generator (UG) framework utilizing more than 100,000 cores, based on MatQapNB. We refer to the article [3] for theoretical and technical details on the parallel branch-and-method implemented in MatQapNB. This user guide describes the usage of MatQapNB. MatQapNB is included in the software package NewtBracket-v2.0 as an application.

K. Fujii, N. Ito, S. Kim, M. Kojima, H. Mittelmann, Y. Shinano and K.C. Toh, June 9, 2021

Reference:

S. Kim, M. Kojima and K.C. Toh, "A Newton-bracketing method for a simple conic optimization problem", Optimization Methods and Software, 36(1) 371-288 (2021).

K. Fujii, N. Itoh, N. Kim, M. Kojima, Y. Shinano, and K. C. Toh. Solving challenging scale QAPs. Technical Report ZIB-Report-21-02, Zuse Institute Berlin, 14195 Berlin, Germany, January 2021.