Solving nonconvex formulations of Euclidean steiner tree problems in N-space

• Grant number: 14/50309-0
• Support Opportunities: Regular Research Grants
• Start date: September 01, 2014
• End date: August 31, 2016
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Agreement: University of Michigan
• Principal Investigator: Sandra Augusta Santos
• Grantee: Sandra Augusta Santos
• Principal researcher abroad: Jon Lee
• Institution abroad: University of Michigan , United States
• Host Institution: Instituto de Matemática, Estatística e Computação Científica (IMECC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• City of the host institution: Campinas
• Associated research grant: 13/05475-7 - Computational methods in optimization, AP.TEM

Abstract

This project was motivated by recent and preliminary numerical experiments with the nonconvex model for the Euclidean Steiner tree problem. It aims to overcome two difficulties observed with the experiments, namely: the weakness of the lower bounds given by the relaxations, and the non-differentiability of the model at points where the solution degenerates. We propose to investigate strategies to deal with these difficulties: a heuristic procedure to generate upper bounds on the optimal solution value that leads to valid integer cuts, and the use of approximate differentiable functions for the Euclidean norm. Our over-arching goal is to develop the best algorithm and solver for Euclidean Steiner problems in dimension greater than two, and to have a strong repercussion on techniques that can impact all kinds of geometric optimization problems (e.g., in chemical engineering, and O.R. logistics). (AU)