My main research interest is the analysis, development, implementation and testing of solution approaches for large-scale structured optimization problems at the interface between continuous and combinatorial optimization, with emphasis on (re)formulation techniques to expose and exploit valuable structural properties, and their real-life application in several fields (energy, transportation, telecommunications, ...) I'm also interested in the numerical analysis, computer science, artificial intelligence and 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,
A37] have applications in such diverse
fields as network optimization
scheduling problems for electrical generators
or vehicles and crews
A64], 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
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 [A39].
I lead the implementation effort for 8 main software projects, for a total
of 16 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 or collected and made available at
http://www.di.unipi.it/optimize/Data/ almost 30 different data sets for
6 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 solve 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 [A44, A47, A19], applying parallel programming techniques to the solution of optimization poblems [A9, B2], applying optimization techniques to algorithm design issues [A40, A65], or working in the interplay between mathematical programming, artificial intelligence and machine learning [B5, B6, B14, B15]. 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;
From the applicative standpoint, I have mainly investigated the following problems:
When I had the chance to, I have also investigated other problems and methodologies.
Optimizing functions whose first derivatives are not continuous is
significantly more complex than the "smooth" case. Yet, large-scale nonsmooth
problems occur in many applications, among which decomposition approaches via
Lagrangian relaxation [A14] or Benders'
decomposition [A49], some of the prominent
techniques for the algorithmic solution of large-scale and/or difficult
structured optimization problems.
Subgradient Methods (SM) are popular for the solution of nondifferentiable problems, due to their ease of implementation and low computational cost. Novel classes of SM, combining deflection and projection, have been proposed in [A25] that also allow to compute the objective function only approximately, while retaining control on the quality of the final solution. A detailed computational comparison of several different SM, including but not limited to those of [A25],e has also been performed to provide guidelines about which variant is likely to be more effective in different applications [A52].
At the other extreme of the scale, "Bundle" methods (BM) [B10], 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 convergence speed 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 BM 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, A37, A38]. Furthermore, it has been shown that it is possible to exploit the structure of the problem in different ways to develop specialized master problems [A37, A38], leading to significant performance improvements. A related but different approach entails using second-order cone constraints in the master problem [A33] in order to incorporate (partial) second-order-type information. A novel convergence analysis of BM has been proposed which allow a more flexible handling of certain crucial steps, in particular leading to non-monotone (in the objective function sense) approaches [A41]. A thorough analysis of the impact of inexact function computation on the algorithm has been provided in [A55], where a variant is proposed that exploits upper models to avoid computing some of the components of a sum-functions, not only in "Null Steps" but also in "Serious Steps". Also, two new forms of "Noise Reduction Steps" are proposed that are useful for specific assumptions on how the oracles deal with not being able to compute the function with arbitrary accuracy.
Applying BM to the solution of the Lagrangian Duals (LD) of a structured optimization problems corresponds to "stablized" versions of the celebrated Dantzig-Wolfe decomposition method where slack variables are added which are given quadratic [A2] or more general [A7] penalty terms. This technique can be applied to extensions to the Dantzig-Wolfe approach such as column generation methods [A23], partial Dantzig-Wolfe approaches [A38] or structured Dantzig-Wolfe approaches [A37], giving rise to efficient solution codes for the solution of many different optimization problems, both in sequential [A4, A5, A10, A13, A14, A15, A21, A22, A32, A56, A64, A66>/A>, A68, B1, B12, C1, C2, C4] and in parallel [A9]. The issues arising when using these bound-computing techniques within enumerative approaches have also been addressed [T2].
While mostly studied for decomposition approaches using Lagrangian relaxation, these techniques can also be adopted to the different (dual) approach of Benders' decomposition, which ultimately still boils down to a cutting-plane type algorithm. Because the master problem in this case is a combinatorial (hard) problem, some properties do no easily extend and a specific convergence analysis is required. This is done in [A49] for different kinds of informative on-demand inexact oracles, which allow to lower the overall computational cost by computing the subproblem(s) only inexactly for most of the iterations. One specific application to the Cell Suppression problem in statistical tabular data protection proves that the approach signficantly improves w.r.t. by-the-book implementations [A63].
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 [A44, A47] 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
While this approach requires separability of the objective function, an effective way for extracting a separable approximation of the non-separable objective function has been proposed [A18]. This approach has been compared with a different reformulation, based on second-order cone constraints [A26]. Finding "exact" Perspective Reformulations for non-separable quadratic functions is difficult in general, but it can be done for kxk matrices with "small" k; then the original nonseparable function can be (possibly, approximately) decomposed as a sum of kxk matrices, which leads to tighter formulations [A60].
In order to improve the efficiency of the approach, projected versions have been proposed [A30] that retain a larger part of the structure of the original problem; this may be beneficial e.g. for network-structured problems [C5] or for problems related to confidentiality of statistical data [A42]. The challenge of exploiting these structural properties under less stringent assumptions on the structure of the problem has been tackled in [A48]. Since the Approximated Projected Perspective Reformulation approach proposed there may lead to a deterioration of the bound, a techique has been devised to restore the full strength of the Perspective Relaxation bound using dual information [A54].
The Perspective Reformulation technique has been shown to be useful in a surprisingly large number of quite different applications, among which energy problems, telecommunication problems, and the Sequential Convex MINLP Technique for the solution of MINLP where non-convex functions are only univariate ones [A62].
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, A36, A70]. These lines of research have been funded by three Italian national research projects (PRIN 2009, 2012 and 2015), the last two of which I've led.
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 logistic and communication networks operations and design
C7]. The developed approaches have shown
a good potential, both in sequential
[A4] and in parallel
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
A20]. This has allowed e.g. to easily
compare the performances of different MCF algorithms under cost reoptimization
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
T1], possibly using innovative versions
of the Bundle method [A38]. 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 [A37]. Due to the flexibility of
Lagrangian techniques, several new "node-based" relaxation schemes have been
proposed that offer a wide trade-off between bound computation cost and bound
quality [A68]. In several cases, Network
Design problems have a structure leading to Quasi-Separable Dantzig-Wolfe
Reformulations, which can be computationally exploited
Approaches based on the Perspective Reformulation have been shown to be useful for network design problems with nonlinear objective function [A48, A30, 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.
The design and management of energy systems are an almost endless source of
highly challenging optimization models. Among these, the Unit Commitment
problem in electrical power production is a fundamental tool for efficient
management of the complex electrical system. It has always been a large-scale,
non-convex difficult problem, especially in view of the fact that operational
requirements imply that it has to be solved in an unreasonably small time for
its size. Recently, the ever increasing capacity for renewable generation has
strongly increased the level of uncertainty in the system, making the (ideal)
Unit Commitment model a large-scale, non-convex, uncertain (stochastic,
robust, chance-constrained) program, as discussed in details in the survey
[A46] (and even more in details in the
updated version [A59]).
For this problem, 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]. The dynamic programming algorithm proposed in [A16] has also suggested "large but very tight" MINLP formulations of the problem, that have proven to be computationally useful [B11]. The combination of different techniques is crucial for solving stochastic versions of the problem taking into account the inherent uncertainty in electrical systems, such as that corresponding to production from renewable energy sources [A56]. The specific challenge of these problems has suggested a new primal recovery technique for Lagrangian-based approaches [A66] which may later find other applications.
A different research line has been about the development of models for optimization problems related to "energy communities", in particular taking into account aspects such as the "agency problem" and the correct sharing of the ecoomical gains between the community's participants, using different approaches such as cooperative game theory [A69] and bilevel optimization [C16]. Notably, this line of research has been funded by three Italian grants (Progetto Coordinato Agenzia2000 CNR, PRIN 2005, project "AUTENS" of the University of Pisa), by three international projects of the Gaspard-Monge Program for Optimization and Operations Research (2013—2017), by the H2020 project plan4res and by a the COST Action TD1207 "Mathematical Optimization in the Decision Support Systems for Efficient and Robust Energy Networks", in all of which I have been one of the leading investigators. In particular, in the COST Action I've organised the development of a Wiki on energy optimization, which has later became a book. I have also been the originator of Wikipedia entry "Unit commitment problem in electrical power production". 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. Some special cases relative su specific applications have also been studied, where the form of the columns (paths) can be exploited to obtain more efficient approaches [A57], for instance based on column generation techniques [C15]; the pricing problem of the column generation actually suggests a compact formulation that is show to provide the best results [A67]. In the context of urban transportation systems, these problems are just one of the several steps required to plan the whole service; it is therefore useful to study models that combine different aspects, such as (simultaneous) vehicle scheduling and timetabling [A64]. 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.
Problems related to telecommunication networks often, but not always, have
a strong flow or multiflow structure. Some
routing problems in a telecommunication network can actually be written as
minor variant of multicommodity flow problems, and hence efficiently solved
even with standard LP techniques [A34,
A specific issue in telecommunication problems is that the matrix of 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].
Routing in packet-based telecommunication networks also give rise to flow problems with nonlinear (delay) constraints on the flow. These are NP-hard already in the case of a single flow routed on a single path, and appropriate modeling and algorithmic techniques have to be used for their efficient solution [A45], especially when highly detailed models of the scheduling process at the routers are required [A51]. The developed MINLP models have been shown to yield promising results to improve network utilization metrics (e.g., blocking probability) in detailed network simulations [A43, A50], although the analysis also shows that the objective function of the models is not always perfectly aligned with the true objective of improving network performances [C14].
Not all telecommunication problems, however, have a predominantly flow structure. For instance, resource scheduling problems in cellular networks [A58, B7, C12, C10] have quite different structures, for which pattern-generation approaches may be efficient considering the need of obtaining good solutions in very short times. However, properly assessing the practical usefulness of advanced scheduling algorithms also requires the development of sophisticated simulation environments [C11].
Also, problems related to Internet-of-Things may require sophisticated combinations of broadcast and point-to-point communications, which give rise to extremely challening Mixed-Integer Nonlinear Programming formulations requiring ad-hoc approaches, such as Branch-and-Bound ones based on Lagrangian relaxation [B12].
I've also given contributions to a number of other applications and methodologies, such as:
optimization in the sharing economy setting [B9];
algortithms for nonlinear continuous knapsack problems [A39];
the Minimum Makespan Machine Scheduling Problem, for which local search approaches based on Very Large Neighborhoods have been proposed [A11];
special classes of BiLevel Programming problems, for which theoretical properties have been analyzed in order to develop more efficient solution algorithms [A1].