A Sparse Doubly Nonnegative Relaxation of Polynomial Optimization Problems with Binary, Box and Complementarity Constraints
N. Ito, S. Kim, M. Kojima, A. Takeda, and K.C. Toh
The software package BBCPOP is a MATLAB implementation of a hierarchy of sparse doubly nonnegative (DNN) relaxations of a class of polynomial optimization (minimization) problems (POPs) with binary, box and complementarity (BBC) constraints. Given a POP in the class and a relaxation order, BBCPOP constructs a simple conic optimization problem (COP), which serves as a DNN relaxation of the POP, and then solves the COP by applying the bisection and projection (BP) method. The COP is expressed with a linear objective function and constraints described as a single hyperplane and two cones, which are the Cartesian product of positive semidefinite cones and a polyhedral cone induced from the BBC constraints. BBCPOP aims to compute a tight lower bound for the optimal value of a large-scale POP in the class that is beyond the comfort zone of existing software packages.
Paper: N. Ito, S. Kim, M. Kojima, A. Takeda and K.C. Toh, "BBCPOP: A Sparse Doubly Nonnegative Relaxation of Polynomial Optimization Problems with Binary, Box and Complementarity Constraints," arXiv:1804.00761, to appear in ACM Transaction on Mathematical Software.
Improved QAPLIB lower bounds using BBCPOP by H.D. Mittelmann