Use este identificador para citar ou linkar para este item: http://repositorio.ufc.br/handle/riufc/36601
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.advisorCampêlo Neto, Manoel Bezerra-
dc.contributor.authorSoares, Pablo Luiz Braga-
dc.date.accessioned2018-10-19T15:58:19Z-
dc.date.available2018-10-19T15:58:19Z-
dc.date.issued2018-
dc.identifier.citationSOARES, 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.pt_BR
dc.identifier.urihttp://www.repositorio.ufc.br/handle/riufc/36601-
dc.description.abstractThe 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.pt_BR
dc.language.isopt_BRpt_BR
dc.subjectt-linearizaçãopt_BR
dc.subjectSuavização hiperbólicapt_BR
dc.subjectProgramação quadrática 0-1pt_BR
dc.subjectDesigualdades válidaspt_BR
dc.titleProblemas quadráticos binários: abordagem teórica e computacionalpt_BR
dc.typeTesept_BR
dc.description.abstract-ptbrO 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.pt_BR
dc.title.enBinary quadratic problems: theoretical and computational approachpt_BR
Aparece nas coleções:DCOMP - Teses defendidas na UFC

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2018_tese_plbsoares.pdf1,21 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.