Accès direct au contenu


Version anglaise


Recherche - Valorisation

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

le 16 décembre 2015
Mercredi 16 décembre 2016 de 10h30 à 11h30

Nelson Maculan Professor Emérito Universidade Federal do Rio de Janeiro PESC-COPPE e Instituto de Matemática

Nelson Maculan (Professeur, Rio de Janeiro, brasil)

Nelson Maculan (Professeur, Rio de Janeiro, brasil)

1-The Euclidean Steiner tree problem (ESTP) in R^n consists of finding a tree of minimal Euclidean length that spans a given set of points in R^n, using or not additional points. Only a few papers consider the exact solution for the ESTP in R^n (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 (B&B) algorithm. This work presents techniques to improve the performance of the B&B algorithm in order to implement this formulation.

2-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.

Slideshow : Part 1, Part 2

Type :
Séminaires - conférences
Contact :
Hisham Abou-Kandil (laboratoire SATIE)
Lieu(x) :
Campus de Cachan
Bâtiment d'Alembert
Amphithéâtre 63

Recherche d'une actualité

Recherche d'une actualité