Prof. Nelson Maculan

Federal University of Rio de Janeiro, Brazil

June 17, 2015, 14:30, Room GC B3 30 (click here for the map)

Two Applications of Mixed Integer Nonlinear Programming (MINLP) in R^n: the Euclidean Steiner Tree Problem and Covering a Solid with Different Spheres

The Euclidean Steiner tree problem (ESTP) in Rn consists of finding a tree of minimal Euclidean length that spans a given set of points in Rn, using or not additional points. Only a few papers consider the exact solution for the ESTP in Rn (n>2) and there are just two works that considered a mathematical programming formulation for the ESTP. One of them presented a convex mixed integer formulation that could be implemented in a Branch and Bound algorithm. This work presents techniques to improve the performance of the algorithm in order to implement this formulation. After, we present a mathematical programming model for the problem of covering solids by spheres of different radii. Given a set of spheres, possibly with different diameters, and a solid, the goal is to locate the spheres in such a way their union forms a coverage for this solid, using the smallest possible number of spheres of this set. This problem has an application in the radio-surgical treatment planning known as Gamma Knife and can be formulated as a non-convex optimization problem with quadratic constraints and a linear objective function.


Nelson Maculan is full Professor of Optimization at the Dept. of Systems Engineering and Computer Science, Graduate School of Engineering, COPPE, Federal University of Rio de Janeiro, Brazil. He is the President of the International Federation of Operational Research Societies, IFORS (since Jan 2013), was the State Secretary for Education, Rio de Janeiro State, Brazil (Jan 2007-Feb 2008), the National Secretary of Higher Education, Ministry of Education (SESu-MEC), Brasilia, Brazil (Feb 2004-Dec2006) and the President of the Federal University of Rio de Janeiro (UFRJ), Brazil (Jul 1990-Jul 1994).