Relaxações Convexas e Desigualdades Válidas para o Problema da Michila Quadrático Binário

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.