A benchmark generator for boolean quadratic programming
For researchers in combinatorial optimization, this provides a method to generate test instances for BQP algorithms, but the contribution is incremental as it relies on classical Lagrangian duality.
The paper shows that under certain conditions there is no duality gap in boolean quadratic programming (BQP) and provides a benchmark generator for creating random BQP problems solvable in polynomial time, with numerical examples demonstrating effectiveness.
For boolean quadratic programming (BQP), we will show that there is no duality gap between the primal and dual problems under some conditions by using the classical Lagrangian duality. A benchmark generator is given to create random BQP problems which can be solved in polynomial time. Several numerical examples are generated to demonstrate the effectiveness of the proposed method.