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.
|
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.
|