Home > Publications > Manuscripts > On the Solution of Nonconvex Cardinality Boolean Quadratic Programming problems
Publications

On the Solution of Nonconvex Cardinality Boolean Quadratic Programming problems

Bibliography:

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

Authors:

R. Lima, I. Grossmann

Keywords:

Integer programming, Quadratic programming, Computing Science

Year:

2015

Abstract:

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.

ISSN:

2015