Marco Locatelli In this paper we consider the problem of computing the value and a supporting hyperplane of the convex envelope for quadratic and polynomial functions over polytopes with known vertex set. We show that for general quadratic functions the computation can be carried on through a copositive problem, but in some cases (including all the two-dimensional … Read more
In this paper we propose a heuristic approach for the problem of packing equal rectangles within a convex region. The approach is based on an Iterated Local Search scheme (or, using a terminology employed for continuous problems, a Monotonic Basin Hopping), in which the key step is the perturbation move. Different perturbation moves, both combinatorial … Read more
In this paper we deal with the Critical Node Problem (CNP), i.e., the problem of searching for a given number K of nodes in a graph G, whose removal minimizes the number of connections between pairs of nodes in the residual graph. While the NP-completeness of this problem for general graphs has been already established … Read more
In this paper we discuss convex underestimators for bivariate functions. We first present a method for deriving convex envelopes over the simplest two-dimensional polytopes, i.e., triangles. Next, we propose a technique to compute the value at some point of the convex envelope over a general two-dimensional polytope, together with a supporting hyperplane of the convex … Read more
In this paper we introduce the LeGO (Learning for Global Optimization) approach for global optimization in which machine learning is used to predict the outcome of a computationally expensive global optimization run, based upon a suitable training performed by standard runs of the same global optimization method. We propose to use a Support Vector Machine … Read more
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
In this paper we propose a Monotonic Basin Hopping approach and its population-based variant Population Basin Hopping to solve the problem of packing equal and unequal circles within a circular container with minimum radius. Extensive computational experiments have been performed both to analyze the problem at hand, and to choose in an appropriate way the … Read more
In this paper we propose a Fully Polynomial Time Approximation Scheme (FPTAS) for a class of optimization problems where the feasible region is a polyhedral one and the objective function is the sum or product of linear ratio functions. The class includes the well known ones of Linear (Sum-of-Ratios) Fractional Programming and Multiplicative Programming. ArticleDownload … Read more
Very hard optimization problems, i.e., problems with a large number of variables and local minima, have been effectively attacked with algorithms which mix local searches with heuristic procedures in order to widely explore the search space. A Population Based Approach based on a Monotonic Basin Hopping optimization algorithm has turned out to be very effective … Read more
In a paper published 1978, McEliece, Rodemich and Rumsey improved Lov\’asz’ bound for the Maximum Clique Problem. This strengthening has become well-known under the name Lov\’asz-Schrijver bound and is usually denoted by $\theta’$. This article now deals with situations where this bound is not exact. To provide instances for which the gap between this bound … Read more