Autores

6659
Hacene Ouzia
44,2987
6660
44,2987

Informações:

Publicações do PESC

Título
Mixed Integer Nonlinear Optimization Models for the Euclidean Steiner Tree Problem in Rd
Linha de pesquisa
Otimização
Tipo de publicação
Relatório Técnico
Número de registro
ES-758/18
Data
12/2018
Resumo

Neste trabalho novos modelos de otimização não-linear mista-inteira para o problema euclidiano de Steiner em Rd são apresentados. Quando as restrições de integralidade são relaxadas, cada modelo possui uma função objetivo não-diferenciável com um conjunto convexo de soluções viáveis. Visando à obtenção de boas cotas inferiores para problemas de minimização seis relaxações foram consideradas, para as quais novos resultados numéricos são comparados e discutidos.

Abstract

New mixed integer nonlinear optimization models for the Euclidean Steiner tree problem in d-space (with d >= 3) will be presented in this work. Each model has a non smooth objective function but a convex set of feasible solutions. All these models are theoretically equivalent in the sens that for any optimal solution of one model there exists an optimal solution of the other model having the same objective value. From these models six mixed integer linear and nonlinear relaxations will be considered. Each relaxation has the same set of feasible solutions as the model from which it is derived. Finally, computational results showing the main features of the presented relaxations will be discussed.

Keywords: Euclidean Steiner tree problem, Steiner tree, Nonlinear optimization models, Mixed integer nonlinear optimization, Relaxation.

Arquivo
Topo