Leo Liberti's pages --- Academic Interests
Please look at the publications list to get full bibliographical information about the papers cited in this page. Full details are given in my CV.

Combinatorial Optimization

I started working in combinatorial optimization during my post-doctoral stay at Politecnico di Milano, Italy.

Main research interests

  • Minimum fundamental cycle bases in graphs. Each spanning tree T in an undirected graph G=(V,E) identifies a set of chords C (i.e. the edges in G \ T). Each chord c identifies a unique cycle consisting of c and the unique path in T joining the vertices incident to c. The set of unique cycles thus obtained is a cycle basis of the cycle space of G, and in particular it is defined to be a strongly fundamental cycle basis. Each spanning tree defines a fundamental cycle basis: this mapping is surjective but generally not injective. Weakly fundamental cycle bases are those cycle bases where at least an order on the cycles c(1),...,c(K) exists such that ∀ i≤K we have c(i) \ ∪(i>j) (c(j)) ≠ ∅. Incidentally, a weakly fundamental cycle basis is also strongly fundamental if the above condition holds for all orders of the K cycles. In a series of papers (including [ALMM2003], [ALMM2004A], [ALMM2004B], [LAMM2005]) we have explored various heuristics, metaheuristics and models for finding strongly fundamental cycle bases of minimum cost. The main ongoing work concerns now weakly fundamental cycle bases. The proposed algorithms have been implemented into the minfcb code.
  • Kissing number problem. When rigid balls touch each other, in billiard-room terms, they ``kiss''. In mathematical terms, the kissing number in D dimensions is the maximum number of D-spheres of unit radius that can be arranged around a central D-sphere of unit radius so that each of the surrounding spheres touches the central one without overlapping. Determining the maximum kissing number in various dimensions has become a well-known problem in Combinatorial Geometry. In 2D the result is trivial: the maximum kissing number is 6. The situation is far from trivial in 3D. The problem earned its fame because, according to Newton, the maximum kissing number in 3D was 12, whereas according to his contemporary fellow mathematician David Gregory, the maximum kissing number in 3D was 13 (this fact was stated without proof). This question was settled, at long last, more than 250 years after having been stated, when J. Leech finally proved that the solution in 3D is 12. In a 2004 conference paper ([LM2004], accepted for publication on Discrete Applied Mathematics [KBLM]) we propose a nonconvex mathematical programming model of the problem an solve it in 4D using some heuristic global optimization solvers. Our experiments point to 24 as the kissing number in 4D. Very recently, a theoretical proof of this result was given by O. Musin.
  • Molecular Distance Geometry Problem applied to proteins. The Molecular Distance Geometry Problem consists in finding the positions in 3D of the atoms of a molecule, given some of the inter-atomic distances. We show that under an additional requirement on the given distances (which most proteins obey) this can be transformed to a combinatorial problem. We propose a Branch-and-Prune algorithm for the solution of this problem and report on very promising computational results. We submitted a paper [LLMB] to the RAIRO-RO journal.
  • Scheduling with communication delays. We present a mixed-integer quadratic mathematical programming formulation for static scheduling of dependent tasks onto homogeneous multiprocessor system of an arbitrary architecture with communication delays. We reduce the number of constraints by applying an RLT-type reformulation to the model. We solve several small-scale instances of the reformulated problem by using CPLEX 8.1. Upper bounds are computed with the Variable Neighborhood Search meta-heuristic applied directly to the graph-based formulation of the problem, whereas lower bounds are obtained by solving linear relaxations of the MILP formulation, further tightened by using load balancing and critical path method arguments ([DLMM2004]). Ongoing work includes: a second (much more efficient) formulation based on packing rectangles, and a combinatorial branch-and-bound.

Global Optimization

My interest in global optimization came about when I started my Ph.D. at Imperial College in March 1999, at the Centre for Process Systems Engineering.

Main research interests

  • Reformulation of quadratic programs. Nonlinear (possibly mixed-integer) programming problems which exhibit some quadratic/bilinear products and at least one linear equality constraints are sometimes amenable to a very particular exact reformulation, which decreases the number of products in the problem and increases the number of linear equation constraints. In the scope of a spatial Branch-and-Bound (sBB) solution, where the lower bound at each node is obtained by solving a convex relaxation of the problem, this is very beneficial. The way the convex relaxation is automatically generated is as follows: (1) each nonlinear term is replaced by a linearizing variable, and a defining constraint "variable = term" is added to the problem; (2) each defining constraint is replaced by a lower convex underestimating inequality and an upper concave overestimating inequality. In other words, the nonconvex surface represented by the defining constraint is "enveloped" in a convex volume (which must be as small as possible). The smallest convex volume enveloping the bilinear surface xy is a tetrahedron which, in relative terms, is not small at all! That means that nonconvex programming problems exhibiting product terms are not well-solved by the sBB algorithm. Coming back to the reformulation, it should now appear clear why reformulating some products to a set of linear equation constraints is beneficial: the linear equation constraints are convex, so they do not need to be over- and under-estimated. This reformulation in fact generates a subset of the well-known Reformulation-Linearization Technique (RLT) constraints. The main results can be found on my Ph.D. Thesis, the published extended abstract and the abstract appearing in the proceedings of the ROADEF 2006 conference (6-8/2/06). The sequence of papers describing all the results in the correct logical order is: [L2004A], [LP], [L2005], [L2004C].
  • Approximating spatial orbitals in quantum mechanics: the Hartree-Fock problem. The Hartree-Fock method is well known in quantum chemistry, and widely used to obtain atomic and molecular eletronic wave functions, based on the minimization of a functional of the energy. This gives rise to a multi-extremal, nonconvex, polynomial optimization problem. We give a novel mathematical programming formulation of the problem, which we solve by using a spatial Branch-and-Bound algorithm. Lower bounds are obtained by solving a tight linear relaxation of the problem derived from an exact reformulation based on reduction constraints (a subset of RLT constraints). The proposed approach was successfully applied to the ground-state of the He and Be atoms. A technical report was filed on the Optimization Online website.
  • General Molecular Distance Geometry Problem. The molecular distance geometry problem can be defined as the determination of the three-dimensional structure of a molecule based on distances between some pairs of atoms. We address the problem as a nonconvex least-squares problem. In [LLMA], we apply three global optimization algorithms (spatial Branch-and-Bound, Variable Neighbourhood Search, Multi Level Single Linkage) to two sets of instances, one taken from the literature and the other new.
  • Deterministic global optimization of MINLPs. Starting from the paper [E. Smith and C. Pantelides, A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs, Computers and Chemical Engineering 23 (1999) 457-478], I implemented an improved spatial Branch-and-Bound (sBB) algorithm where the lower bounding convex relaxation is constructed automatically. The sBB solver, incorporating features for dealing with piecewise convex/concave terms (see [LP2003]) and the RLT reduced constraints graph-based generation algorithm (see [LP]), is described in detail in my PhD. Thesis [L2004B], as well as in [L]. In the early stages of my Ph.D. at Imperial College I had also tried to look for classes of problems which were nonconvex but unimodal (hence did not need to be underestimated by a convex relaxation during the sBB); I found an elegant characterization which is unfortunately difficult to verify algorithmically. The result is described in [L2004D].
  • Variable Neighbourhood Search in global optimization. In practice, only small to medium scale MINLPs can be solved with the exact sBB method. Variable Neighbourhood Search (VNS) is a very good metaheuristic that can be applied to the setting of global optimization. A VNS implementation for continuous global optimization is described in [LD2005]. Work is ongoing to devise and test a VNS implementation for MINLPs.
  • Software frameworks for global optimization. As a research assistant at Imperial College, I was employed to work on the Global CAPE-OPEN EU-sponsored project. I was a co-author of the MINLP Specification and of the consequent announcement in the Global CAPE-OPEN News magazine. This work resulted into the optimization software framework ooOPS (object-oriented OPtimization System), which currently hosts 3 local (SNOPT, lp_solve, NAG VCF) and 3 global (sBB, SobolOpt, VNS) optimization solvers. Unfortunately, the only part of ooOPS available for download is the API specification, as the code currently belongs to Imperial College, who is unwilling to distribute it (on the positive side, ooOPS has a web interface and can be tested online). Exactly for this reason, I set out to produce a second software framework, which I called MORON (MINLP Optimization and Reformulation Object-oriented Navigator), that shared no source code with ooOPS. At the moment, MORON is not yet ready for release, but it already embeds 2 local solvers (SNOPT, glpk) and several heuristic global solvers. Both ooOPS and MORON have been coded along the guidelines given in [L].
  • Symbolic computation software. Both ooOPS and MORON have symbolic computation capabilities to compute symbolic derivatives and generate the convex relaxation automatically. The symbolic computation library is called E (v2 for ooOPS and v3 for MORON). Here is a technical report to introduce Ev3. The software itself (no documentation, see the main example or contact me if you need help) can be downloaded here.

Invertible Cellular Automata

My dissertation (in Italian) at Turin University was about Invertible Cellular Automata (CA). The most important result herein is a description of the structure of the group of all invertible CA evolution laws applied to 1-dimensional, finite-state, finite CAs with "wrap-around" contour conditions. The main result of the dissertation was published in [L1999].
primary: liberti at (same domain as this website); also at leoliberti@yahoo.com