Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/36601
Title in Portuguese: Problemas quadráticos binários: abordagem teórica e computacional
Title: Binary quadratic problems: theoretical and computational approach
Author: Soares, Pablo Luiz Braga
Advisor(s): Campêlo Neto, Manoel Bezerra
Keywords: t-linearização
Suavização hiperbólica
Programação quadrática 0-1
Desigualdades válidas
Issue Date: 2018
Citation: SOARES, Pablo Luiz Braga. Problemas quadráticos binários: abordagem teórica e computacional. 2018. 125 f. Tese (Doutorado em Ciência da Computação)-Universidade Federal do Ceará, Fortaleza, 2018.
Abstract in Portuguese: O objetivo principal deste trabalho é mostrar a aplicação de métodos das áreas de programação linear e não linear para tratar problemas de otimização cuja formulação 0 − 1 natural tem uma função objetivo quadrática. Para esse fim, desenvolvemos a extensão da técnica da t-linearização e mostramos como aplicá-la a problemas quadráticos tais como Corte Máximo, Diversidade Máxima e Clique Máxima Ponderada em Aresta. Adicionalmente, revisamos a técnica da suavização hiperbólica e mostramos como aplicá-la ao problema do corte máximo. Realizamos um estudo teórico de cada problema, onde apresentamos particularmente o desenvolvimento de novas desigualdades válidas e heurísticas simples para cada um deles. Mostramos como gerar restrições t-linearizadas mais fortes para os problemas da diversidade máxima e clique máxima ponderada em aresta. Executamos experimentos computacionais para avaliar o desempenho de cada técnica mostrada em separado, assim como combinadas com as novas restrições propostas. Os experimentos atestam a qualidade dos limites obtidos bem como a força das novas restrições. Construímos um método exato para cada problema, baseado nas técnicas apresentadas. Para o corte máximo e clique máxima ponderada em aresta, comparamos nosso método com formulações linearizadas. Já para diversidade máxima, comparamos nosso método com formulações linearizadas e com uma implementação nossa do melhor método exato, que não utiliza resolvedor matemático, conhecido da literatura. Experimentos computacionais com instâncias da literatura mostram um desempenho superior do nosso método.
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.
URI: http://www.repositorio.ufc.br/handle/riufc/36601
Appears in Collections:DCOMP - Teses defendidas na UFC

Files in This Item:
File Description SizeFormat 
2018_tese_plbsoares.pdf1,21 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.