On the Solution of Nonconvex Cardinality Boolean Quadratic Programming problems

by R. Lima, I. Grossmann
Manuscripts Year: 2015


R. Lima, I. Grossmann, On the Solution of Nonconvex Cardinality Boolean Quadratic Programming problems. A computational study. Computers & Chemical Engineering, Submitted (2015)


This paper addresses the solution of a nonlinear boolean quadratic programming problem using three different approaches. The first uses a classic linearization technique to transform the original problem into a Mixed-Integer Linear Programming (MILP) problem for which multiple formulations are studied. The second approach relies on the implementation of advanced features of an MILP solver. The last one involves the direct solution of the original problem by solvers that can deal with the nonlinear combinatorial problem. Special emphasis is placed on the definition of computationally efficient MILP reformulations and their comparison with the other approaches. The results indicate that the data of the problem has a strong influence in the performance of the different approaches, and there are clear-cut approaches that are better for some instances of the data. A detailed analysis of the results is made in order to identify the winning approaches for specific instances of the data.




Integer programming Quadratic programming Computing Science