TY - JOUR
T1 - On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study
AU - Lima, Ricardo
AU - Grossmann, Ignacio E.
N1 - KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: Fundação para a Ciência e a Tecnologia[DFRH/WIIA/67/2011]
PY - 2016/6/16
Y1 - 2016/6/16
N2 - This paper addresses the solution of a cardinality Boolean quadratic programming problem using three different approaches. The first transforms the original problem into six mixed-integer linear programming (MILP) formulations. The second approach takes one of the MILP formulations and relies on the specific features of an MILP solver, namely using starting incumbents, polishing, and callbacks. The last involves the direct solution of the original problem by solvers that can accomodate the nonlinear combinatorial problem. Particular emphasis is placed on the definition of the MILP reformulations and their comparison with the other approaches. The results indicate that the data of the problem has a strong influence on the performance of the different approaches, and that there are clear-cut approaches that are better for some instances of the data. A detailed analysis of the results is made to identify the most effective approaches for specific instances of the data. © 2016 Springer Science+Business Media New York
AB - This paper addresses the solution of a cardinality Boolean quadratic programming problem using three different approaches. The first transforms the original problem into six mixed-integer linear programming (MILP) formulations. The second approach takes one of the MILP formulations and relies on the specific features of an MILP solver, namely using starting incumbents, polishing, and callbacks. The last involves the direct solution of the original problem by solvers that can accomodate the nonlinear combinatorial problem. Particular emphasis is placed on the definition of the MILP reformulations and their comparison with the other approaches. The results indicate that the data of the problem has a strong influence on the performance of the different approaches, and that there are clear-cut approaches that are better for some instances of the data. A detailed analysis of the results is made to identify the most effective approaches for specific instances of the data. © 2016 Springer Science+Business Media New York
UR - http://hdl.handle.net/10754/621502
UR - http://link.springer.com/10.1007/s10589-016-9856-7
UR - http://www.scopus.com/inward/record.url?scp=84975109884&partnerID=8YFLogxK
U2 - 10.1007/s10589-016-9856-7
DO - 10.1007/s10589-016-9856-7
M3 - Article
SN - 0926-6003
VL - 66
SP - 1
EP - 37
JO - Computational Optimization and Applications
JF - Computational Optimization and Applications
IS - 1
ER -