Linear Programming, Integer Linear Programming, Global Optimization

- People

- Research Activities

Our research spans different topics in the field of optimization

• Molecular Conformation Problems: atoms in a molecule tend to reach configurations of minimum energy. Therefore, a mathematical method to foresee their most stable structure is the following: first, a mathematical model of the overall energy is given; next, the nergy function is globally minimized. Such function is usually highly multimodal so that local search methods are doomed to fail and only clever global optimization strategies can be successful. Well known energy functions are the Lennard-Jones and Morse ones. The global optimization of thes eenergy functions has been faced by methods based on a combination of a strategy (the Basin Hopping one) which exploits the peculiarities of the landscape of these functions, and a so called two-phase local search, which exploits the knowledge about the problem and, in particular, the fact that optimal solutions have compact structures which can be favoured by adding appropriate geometrical terms to the original energy function. The method allowed to detect with a uch greater efficiency putative global minima for the most challenging  Lennard-Jones cases (those having a nonicosahedral structure) and to detect all putative minima for a numer of atoms up to 80 for the most challenging Morse instances.
  
• D.C. Decompositions: given the problme of minimizing a nonconvex quadratic function over a polytope, we defined techniques to compute undominated  D.C. (Difference-of-Convex) decompositions employed to compute lower bounds for these problems. It has been observed that the use of undominated decompositions allows to compute better bounds.
• Landscape analyisis: we performed an analysis of the landscape of the objective function of a  global optimization problem  in order to relate the difficulty of the problem to the shape of the landscape. In particular, the concept of local minima at different levels has been introduced .
• Max-clique problem: we considered the max-clique problem. First, it has been proved the equivalence between a heuristic based on a continuous reformulation of this problem with a greedy heuristic. Then, new heuristics have been proposed based on node-swapping and node-weighting. The new heuristics have been tested on the standard DIMACS benchmarks with quite good results.
• Scheduling problems:  The single-machine scheduling problem of minimizing the weighted total tardiness for a set of jobs has been studied. The problem calls for sequencing a set of jobs -- each one having a positive processing time and a positive due date -- on a continously available machine without preemption, in order to minimize the total positive (and possbly weighted) lateness of the resulting sequence. The probelm is known to be unary NP-hard. Lower bound for the approximation  ratio of the most known approximation algorithms have been identified, showing that all such algorithms may exhibit an arbitrarily bad approximation ratio. Also, a local search algorithm for the weighted version of the problem has been developed. The algorithm belongs to the class of so-called "Very Large Neighbourhood" algorithms, since it explores neighbourhoods having exponential size (in the number of jobs) in polynomial time; the extended proposed neighbourhood proved to be more effective than previous similar very large neighbourhoods studied in literature.
  

- Publications

- Research Grants

Title of project	Project leader	Funding Organization	Kind of grant
FIRB-RBNE01WBBB "Ottimizzazione Non Lineare su Larga Scala"	Gianni DI PILLO - Universita' degli studi di Roma "La Sapienza"	MIUR	National