Hybrid Constructive Heuristics for the Critical Node Problem

We consider the Critical Node Problem: given an undirected graph and an integer number K, at most K nodes have to be deleted from the graph in order to minimize a connectivity measure in the residual graph. We combine the basic steps used in common greedy algorithms with some flavour of local search, in order … Read more

Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth

We consider the problem of deleting a limited number of nodes from a graph in order to minimize a connectivity measure between the surviving nodes. We prove that the problem is $NP$-complete even on quite particular types of graph, and define a dynamic programming recursion that solves the problem in polynomial time when the graph … Read more

Neighborhood based heuristics for a Two-level Hierarchical Location Problem with modular node capacities

In many telecommunication network architectures a given set of client nodes must be served by different kinds of facility, which provide di fferent services and have diff erent capabilities. Such facilities must be located and dimensioned in the design phase. We tackle a particular location problem in which two sets of facilities, mid level and high level, … Read more

Exactly solving a Two-level Hierarchical Location Problem with modular node capacities

In many telecommunication networks a given set of client nodes must be served by different sets of facilities, providing different services and having different capabilities, which must be located and dimensioned in the design phase. Network topology must be designed as well, by assigning clients to facilities and facilities to higher level entities, when necessary. … Read more

Global Optimization for the Design of Space Trajectories

The problem of optimally designing a trajectory for a space mission is considered in this paper. Actual mission design is a complex, multi-disciplinary and multi-objective activity with relevant economic implications. In this paper we will consider some simplified models proposed by the European Space Agency as test problems for global optimization. We show that many … Read more

Improved bounds for interatomic distance in Morse clusters

We improve the best known lower bounds on the distance between two points of a Morse cluster in $\mathbb{R}^3$, with $\rho \in [4.967,15]$. Our method is a generalization of the one applied to the Lennard-Jones potential in~\cite{Schac}, and it also leads to improvements of lower bounds for the energy of a Morse cluster. Some of … Read more

Efficiently packing unequal disks in a circle: a computational approach which exploits the continuous and combinatorial structure of the problem

Placing $N$ non-overlapping circles in a smallest container is a well known, widely studied problem that can be easily formulated as a mathematical programming model. Solving this problem is notoriously extremely hard. Recently a public contest has been held for finding putative optimal solutions to a special case in circle packing. The contest saw the … Read more

Disk Packing in a Square: A New Global Optimization Approach

We present a new computational approach to the problem of placing $n$ identical non overlapping disks in the unit square in such a way that their radius is maximized. The problem has been studied in a large number of papers, both from a theoretical and from a computational point of view. In this paper we … Read more

A new class of test functions for global optimization

In this paper we propose a new class of test functions for unconstrained global optimization problems for which, however, it is a priori known that the global minimum lies in the interior of a sphere centered at the origin. The class depends on some parameters through which the difficulty of the test problems can be … Read more

New results for molecular formation under pairwise potential minimization

We establish new lower bounds on the distance between two points of a minimum energy configuration of $N$ points in $\mathbb{R}^3$ interacting according to a pairwise potential function. For the Lennard-Jones case, this bound is 0.67985 (and 0.7633 in the planar case). A similar argument yields an estimate for the minimal distance in Morse clusters, … Read more