Marcia Fampa We study the D-optimal Data Fusion (DDF) problem, which aims to select new data points, given an existing Fisher information matrix, so as to maximize the logarithm of the determinant of the overall Fisher information matrix. We show that the DDF problem is NP-hard and has no constant-factor polynomial-time approximation algorithm unless P = NP. … Read more
We present well known properties related to the topology of Steiner minimal trees and to the geometric position of Steiner points, and investigate their application in the main exact algorithms that have been proposed for the Euclidean Steiner problem. We discuss the difficulty in the application of properties that were very successfully applied to solve … Read more
In this work, we present a new framework to increase effectiveness of metaheuristics in seeking good solutions for the general nonlinear optimization problem, called Cutting Box Strategy (CBS). CBS is based on progressive reduction of the search space through the use of intelligent multi-starts, where solutions already obtained cannot be revisited by the adopted metaheuristic. … Read more
We present a specialized branch-and-bound (b&b) algorithm for the Euclidean Steiner tree problem (ESTP) in R^n and apply it to a convex mixed-integer nonlinear programming (MINLP) formulation of the problem, presented by Fampa and Maculan. The algorithm contains procedures to avoid difficulties observed when applying a b&b algorithm for general MINLP problems to solve the … Read more
The Euclidean Steiner Tree Problem in dimension greater than two is notoriously difficult. The successful methods for exact solution are not based on mathematical-optimization methods — rather, they involve very sophisticated enumeration. There are two types of mathematical-optimization formulations in the literature, and it is an understatement to say that neither scales well enough to … Read more
We describe improvements to Smith’s branch-and-bound (B&B) algorithm for the Euclidean Steiner problem in R^d. Nodes in the B&B tree correspond to full Steiner topologies associated with a subset of the terminal nodes, and branching is accomplished by “merging” a new terminal node with each edge in the current Steiner tree. For a given topology … Read more