Problemas quadráticos binários: abordagem teórica e computacional

Abstract

The main objective of this work is to show the application of linear and nonlinear programming methods to deal with problems whose natural 0−1 formulation has a quadratic objective function. To this end, we develop an extension of the t-linearization technique and show how to apply it to quadratic problems such as Maximum Cut, Maximum Diversity and Maximum Edge-Weighted Clique. In addition, we review the hyperbolic smoothing technique and show how to apply it to the maximum cut problem. We carry out a theoretical study of each problem, where we particularly present the development of new valid inequalities for each of them. We perform computational experiments to evaluate the performance of each technique separately, as well as combined with the proposed new constraints. The experiments attest the quality of the bounds obtained as well as the strength of the new inequalities. We develop an exact method for each problem, based on the presented techniques. For the maximum cut and maximum edge-weighted clique, we compare our method with linearized formulations. For maximum diversity, we compare our method with linearized formulations and with our implementation of the best exact method, which does not use mathematical solvers, known in the literature. Computational experiments with instances of the literature show superior performance of our method.