Informações:

Publicações do PESC

Título
Relaxações Convexas e Desigualdades Válidas para o Problema da Michila Quadrático Binário
Linha de pesquisa
Otimização
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
15/3/2019
Resumo

Consideramos a relaxação de programação quadrática paramétrica convexa, convex quadratic programming, CQP, para o problema da mochila quadrático, quadratic knapsack problem, QKP. Nesta relaxação mantêm-se informações quadráticas parciais da função objetivo original do QKP, perturbando a função objetivo para obter-se um termo quadrático côncavo. A parte não côncava, gerada pela perturbação, é linearizada utilizando um procedimento padrão no qual o problema é reescrito no espaço matricial. Apresentamos um método de pontos interiores primal-dual para otimizar a perturbação da função quadrática, em busca de limites superiores mais apertados para o QKP. Provamos que o mesmo procedimento que perturba a função objetivo, quando aplicado no contexto de relaxações de programação semidefinida, semidefinite programming, SDP, para o QKP, não pode melhorar o limite superior dado pela relaxação linear SDP correspondente. O resultado também pode ser aplicado para os problemas mais gerais de programação quadrática inteira. Finalmente, propomos novas desigualdades válidas para as variáveis matriciais derivadas das desigualdades de cobertura e das desigualdades de mochila, para o QKP, e apresentamos problemas de separação para gerar cortes para a solução corrente da relaxação CQP. Nossos melhores limites são obtidos ao alternarmos entre a otimização da relaxação quadrática paramétrica e a adição de planos de cortes gerados pelas desigualdades propostas.

Abstract

We consider a parametric convex quadratic programming, CQP, relaxation for the quadratic knapsack problem, QKP. This relaxation maintains partial quadratic information from the original QKPby perturbing the objective function to obtain a concave quadratic term. The nonconcave part generated by the perturbation is then linearized by a standard approach that lifts the problem to the matrix space. We present a primal-dual interior point method to optimize the perturbation of the quadratic function, in a search for the tightest upper bound for the QKP. We prove that the same perturbation approach, when applied in the context of semidefinite programming, SDP, relaxations of the QKP, cannot improve the upper bound given by the corresponding linear SDP relaxation. The result also applies to more general integer quadratic problems. Finally, we propose new valid inequalities on the lifted matrix variable, derived from cover and knapsack inequalities for the QKP, and present the separation problems to generate cuts for the current solution of the CQPrelaxation. Our best bounds are obtained from alternating between optimizing the parametric quadratic relaxation over the perturbation and adding cutting planes generated by the valid inequalities proposed.

Arquivo
Topo