My main research interest has been the analysis and development of solution approaches for large-scale structured optimization problems, with emphasis on (re)formulation techniques to expose and exploit valuable structural properties of the problems at the interface between continuous and combinatorial optimization. I'm also interested in the numerical analisys, computer science and artificial intelligence / machine learning issues arising within these solution approaches and, vice-versa, in the use of mathematical programming techniques in these disciplines.
I always try to combine three different aspects: methodology,
applications and implementation. This is necessary, in that the
development of a single general solution method may result in improved
performances in several different applications. For instance, the theoretical
results of [A7,
A14,
A25,
A35] have applications in such diverse
fields as network optimization
[A5,
A9,
[A22]],
scheduling problems for electrical generators
[C1,
C2,
C4,
A10,
A21]
or vehicles and crews
[N1,
A23], and Max-Cut problems
[A13]. On the other hand, investigation
on a specific application often motivates novel methodological developments;
this has been the case e.g. for the results in
[A17], which have been originally
motivated by the study of scheduling problems in electrical power
production, but that have later found very different applications
[A18,
C5]. Finally, the significance of
any methodological or applicative contribution can be vastly increased if
efficient and well-engineered software implementing the idea is made
available to potentially interested users in the academia and in
industry. This is especially true for the development of sophisticated
algorithmic schemes, whose implementation is typically far from trivial.
Because of this, I've taken specific care in developing well-engineered
and easy-to-use software packages, which have been made available under
different open source licenses. I lead the implementation effort for 6
main software projects, for a total of 13 software packages, which can be
downloaded from http://www.di.unipi.it/optimize/Software/; these represent a nontrivial fraction of all open source
optimization projects ever developed in Italy. For the same reasons I
also developed, collected and made available at http://www.di.unipi.it/optimize/Data/ over 20 different data sets for more than 4 different classes of
optimization problems (the site is in the top 10 Google hits for the
keyword "multicommodity" since several years).
I like in particular to thread across boundaries of different fields
such as numerical analysis, diverse aspects of mathematical
programming, and computer science. For instance, applying nonlinear
techniques to discrete problems
[A1,
A5,
A10,
A13,
A15,
A18,
A23,
A30] and vice-versa
[A16,
A17,
B4], investigating numerical analysis
aspects of optimization algorithms
[A6,
A12] and vice-versa
[A19], applying parallel programming
techniques to the solution of optimization poblems
[A9,
B2], or working in the interplay
between mathematical programming, artificial intelligence and machine learning
[B5,
B6]. This is due to my profound belief
in the need of continuously adapting the research tools to the needs of the
problem at hand, if necessary challenging the limits and the fences
that — often surreptitiously — divide disciplines.
From the methodological standpoint, the main algorithmic techniques that I have investigated are:
convex NonDifferentiable Optimization algorithms, with a specific focus on Lagrangian relaxation;
enumerative algorithms for nonlinear mixed-integer programs.
From the applicative standpoint, I have mainly investigated the following problems:
When appropriate, I have also investigated other problems and methodologies.
Optimizing functions whose first derivatives are not continuous is
significantly more complex than the "smooth" case. For these problems,
subgradient methods are popular for their ease of implementation and low
computational cost. Novel classes of (approximate) subgradient methods,
combining deflection and projection, have been proposed
[A25]. At the other extreme of the
scale, "Bundle" methods, which require the solution of an optimization
problem to define the next iterate, are significantly more complex to
implement and have a higher cost per iteration; however, their speed of
convergence can be significantly higher as well. Specific algorithms
and efficient software modules have been developed
[A3] in order to speed-up the solution
of the corresponding "master" problems. From the methodological viewpoint,
different extensions to the class of Bundle methods have been proposed in
order to exploit the specific structure of the applications. In
particular, the set of possible "stabilizing terms" in the master problem
has been significantly increased [A7];
this allows e.g. to use Linear Programming techniques instead of Quadratic
Programmin ones to solve them, which is crucial for performances in several
important applications [A23,
A35,
T6]. Furthermore, it has been shown that
it is possible to exploit the structure of the problem in different ways to
develop specialized master problems [A35,
T6], leading to significant performance
improvements. A related but different approach entails using second-order
cone constraints in the master problem
[A36] in order to incorporate (partial)
second-order-type information.
Our main motivation for the study of nondifferentiable optimization
problems lies in decomposition approaches via Lagrangian relaxation
[A14], a prominent technique for the
algorithmic solution of large-scale and/or difficult structured
optimization problems. Applying Bundle methods to the solution of the
Lagrangian dual has several positive aspects
[A2], and allows for the implementation
of efficient solution codes for the solution of several different
optimization problems, both in sequential
[A4,
A5,
A10,
A13,
A14,
A15,
A21,
A23,
A32,
A35,
T6,
B1,
C1,
C2,
C4] and in parallel
[A9]. The issues arising when using
these bound-computing techniques within enumerative approaches have also
been addressed [T2].
Currently, the focus of the research is on applying the developed
techniques on other classes of problems, on improving the obtained theoretical
results, and on further developing and making available the corresponding
solution codes.
Aim of the research is the development of "generic specialized" Interior Point methods, i.e., a generic approach which allows to exploit the different forms of structure available in different applications. For this purpose, a generic IP module has been developed which is parametric about the way in which the "core" KKT systems are solved. Building on this module, specialized IP approaches for problems with specific structures have been developed. In particular, Min-Cost Flow problems have been theoretically analyzed; [A6]; this has lead to the proposal of new classes of efficient preconditioners for the solution of the KKT systems via a Preconditioned Conjugate Gradient approach [A12, A19]. The preconditioners can also be successfully used within multi-iterative approaches [T5] where the projection and interpolation steps are appropriately performed in such a way to preserve the graph structure of the matrix at the lower levels. These IP approaches lend themselves well to be integrated with more traditional combinatorial MCF algorithms, a technique dubbed "extended crossover" [A20]. The research has also been extended to Multicommodity flow problems, for which a parallel IP approach has been proposed and tested [B2]. Currently, the focus of the research is on refining the obtained theoretical results and applying the developed techniques to other classes of structured optimization problems.
An interesting line of research has focussed on reformulation techniques for
Mixed-Integer NonLinear Programs (MINLP) with specific structures. For problems
with semi-continuous variables and nonlinear convex separable objective
function, the Perspective Reformulation has been proposed whose
continuous relaxation provides significantly improved lower bounds. Since the
Perspective Relaxation is a highly nonlinear program, a class of valid
inequalities, called Perspective Cuts, have been developed
[A17] which allow to model it as a
semi-infinite program with much simpler objective function. Generating a
finite number of these one obtains approximate solution methods, which have
been shown to be efficient in some applications
[A24]. While this approach requires
separability of the objective function, an effective way for applying it to
non-separable problems have been proposed
[A18]. This approach has been compared
with a different reformulation, based on second-order cone constraints
[A26]. Furthermore, projected
versions of the approach have been proposed that have the potential of
retaining a larger part of the structure of the original problem; this may
be beneficial e.g. for network problems
[C5].
A different line of work has instead focussed on dynamic programming algorithms
for MINLPs with "time-indexed" structure, representing scheduling problems
where the amount of available resource at one period influences that of the
immediately preceeding and following ones
[A16].
Currently, I'm pursuing different research directions: exploiting other sources
of structure in the MINLPs, developing other classes of valid inequalities
[A29], applying the obtained results to
other classes of problems, further improving the obtained theoretical results,
and, finally, exploring entirely different approaches such as "feasibility
pump" heuristics [B4,
A33].
The first target of the general algorithmic techniques I developed has been
multicommodity flow problems [V1]. These are often
difficult problems, even ore so because of their extremely large size, that
represent the basic modeling tool for very many applications, especially
related to communication networks operations and design
[A22,
B1,
A34,
C7]. The developed approaches have shown
a good potential, both in sequential
[A4] and in parallel
[A9,
B2]. As a by-product of this research, a
generic C++ interface for single-commodity Min-Cost Flow problem solvers have
been proposed, and several efficient MCF codes have been either developed from
scratch or ported under the interface
[A12,
A19,
A20]. This has allowed e.g. to easily
compare the performances of different MCF algorithms under cost reoptimization
[A15].
An interesting case is the one in which multicommodity flows represent routing
in a (tele)communication network [A34,
C7], where the communication demands may
not be precisely known. This gives rise to a host of difficult problems where
routing decisions may depend on demands. Some of these cases (where the
problems are actually easily solvable) have been studied in
[A31].
Currently, the research focuses on extending the set of flow problems covered,
e.g. considering nonlinear cost functions, on improving on each single
algorithmic technique and on combining different techniques.
Most Network Design problems [B1] have
an underlying Multicommodity flow structure, or at least a structure well
suited for the application of the developed large-scale optimization
approaches. For some of these problems, I have developed efficient lower
bounding techniques based on Lagrangian relaxation combined with flow
algorithms [A5,
T1], possibly using innovative versions
of the Bundle method [T6]. In
alternative, 0/1 reformulations coupled with an innovative simultaneous
row-and-column generation approach can be used
[A22]; when stabilized, the latter
gives rise to the Stabilized Structured Dantzig-Wolfe Decomposition
Method [A35].
Approaches based on the Perspective Reformulation have been shown to be
useful for network design problems with nonlinear objective function
[C5].
A different line of research focuses instead on techniques for efficient
optimization over the semi-metric polytope
[B3,
A13], that is an important component
of polyhedral techniques for Network Loading problems.
I have also studied chance-constrained Network Design problems, using
robust optimization techniques to construct different convex approximations
of the nonconvex probabilistic constraints, and comparing them from a
computational viewpoint [C6].
Currently, the research focuses on improving the performances of the
proposed lower bounding techniques, applying them to different forms of ND
problems, and developing exact and/or heuristic approaches exploiting them.
Unit Commitment problems in electrical power production are a fundamental tool for efficient management of the complex electrical system, in particular in the current free-market regime. For these problems, solution techniques based on Lagrangian relaxations have been developed, both for the monopolistic case [A10, A21, C4] and for the free-market case [C2]; these techniques have shown to be competitive with more traditional meta-heuristic approaches [C1]. An innovative two-stage dynamic programming algorithm has been proposed for the solution of the Lagrangian subproblems of UC problems with "ramp constraints" [A16]; the new algorithm has been shown to be a remarkably effective base for constructing Lagrangian heuristics for ramp-constrained UC problems [A21, C4]. The analysis of UC problems has also lead to the proposal of a new class of valid inequalities for MINLP problems with a specific structure [A17] that have later proven to be useful also for entirely different applications such as portfolio optimization problems [A18]. These valid inequalities have shown to be particularly effective for implementing MILP-based approximate algorithms for UC [A24], especially if used in combination with Lagrangian techniques. [A32]. Notably, this line of research has been funded by two Italian grants (Progetto Coordinato Agenzia2000 CNR and PRIN 2005), of which I have been one of the leading investigators. Currently, the research focuses on developing innovative models of UC problems, and the corresponding solution algorithms, capable of better taking into account real-world constraints that have been so far only approximately dealt with due to the need of making the problems more computationally tractable.
A standard formulation of the Max-Cut problem is the one based on cycle (triangle) inequalities; these define the semi-metric polytope. By carefully selecting a subset of these inequalities one obtains the rooted semi-metric polytope, whose strong combinatorial structure allows to solve linear optimization problems very efficiently with network flow techniques [B3, T3]. Properly combining efficient solution algorithms for the rooted semi-metric problem with Lagrangian techniques leads to solution approaches to optimization on the full semi-metric polytope [A13] which have been shown to potentially much more efficient than standard Linear Programming techniques. Currently, the research focuses on further improving the efficiency of the proposed solution technique and on embedding it in full-featured solution codes for the Max-Cut problem.
Crew and vehicle scheduling problems are most often formulated as very-large-scale Set Partitioning problems. For this kind of formulation, column-generation based heuristics [N1] appear the most promising solution approach, especially when exploiting Lagrangian techniques [A2, A3] for the efficient solution of the Master Problem. A crucial aspect for the effectiveness of these approaches is the stabilization of the column generation process, that can be obtained e.g. by means of stabilizing terms with the appropriate form [A7]. The impact of different forms of stabilization has been demonstrated in different cases, such as Multi-Depot Vehicle Scheduling problems and Crew Scheduling problems. Currently, the research focuses on improving the theoretical understanding of stabilization techniques, on improving the efficiency in practice of the developed approaches, and on studying specialized formulations for specific applications.
I've also given contributions to a number of other problems and methodologies, such as:
cutting plane approaches for nonlinear nonconvex problems expressed in "DC" (difference of convex functions) form, [A28, A27] or their generalization [T7];
the Minimum Makespan Machine Scheduling Problem, for which local search approaches based on Very Large Neighborhoods have been proposed [A11];
problems motivated by genetic and molecular biology, such as that of determining optimal paralogy trees for genomic sequences [A8];