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,
A14,
A25,
A37] 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,
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
[A45,
A43,
A42,
A30,
A18,
A74]. 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],
as documented in the corresponding section
of my CV that describes the software packages I have contributed to (often
with a leading role), which 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
https://commalab.di.unipi.it/datasets/
many different data sets for several different classes of optimization
problems, and I have contributed to standard libraries of instances
[A61].
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,
C18,
A73
E1]. This is due to the realization that
one must continuously adapt 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:
NonDifferentiable Optimization algorithms, with a specific focus on their use in decomposition approaches (and therefore the convex case);
enumerative algorithms for nonlinear mixed-integer programs.
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]. A very specific issue
that appears in the use of SM within training of Neural Network is running
these algorithms with very-low-precision number formats; a study has been
performed about the convergence properties of SM with errors corresponding to
this use case for quasi-convex functions
[C18], that are generally believed to be
a reasonable approximation (better than convex ones, anyway) of the loss
function of real Neural Networks (at least close to a stationary point).
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
[A24].
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, the
Sequential Convex MINLP Technique for the solution of MINLP where
non-convex functions are only univariate ones
[A62,
A75>], and the "pruning" of Deep Neural
Networks [A74].
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]. But, as it sometimes happens, two
apparently distinct research lines can be joined yielding a result that is
more than the sum of the individual contributions: combining the formulation
inherent the dynamic programming approach with perspective reformulation
techniques yields the first "perfect" formulation for single-Unit Commitment
problems with all the main operating constraints and nonlinear objective
[A72], meanwhile proving a general result on
the convex hull of problems with specific structure that has an independent
interest. Remarkably, a wrong version of the result had been previously
published [T6].
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
[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].
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,
B16] 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 [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
[B13].
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,
A72], also leading to the proof of a general
convex hull result that has an independent interest (and that was previously
proven in a wrong way [T6]). 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].
Yet another different research line has concerned the development of approaches
for optimal placement of marine energy turbines
[C19].
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,
C7].
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]. A simewhat similar, but quite
different, flow-based approach can be used to compute the worst-case delay
for DRAM access [A71], although in
this case the graph is the transition diagram of the DRAM controller and
complex side constraints are required.
Not all telecommunication problems, however, have a predominantly flow
structure. For instance, resource scheduling problems in cellular networks
[A58,
B7,
C12,
C10,
C17] have rather 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:
combining optimization and Machine Learning techniques in the context of the Algorithm Configuration Problem [B14, B15, C18, E1];
optimization techniques applied to Machine Learning approaches such as Neural Networks [C18, A74] and Support Vector Machines [A73];
optimization in the sharing economy setting [B9];
optimization problems related to confidentiality of statistical tables [A42, A63];
the design of LZ77 compressors with optimal time/space trade-offs [C9, A65];
algortithms for nonlinear continuous knapsack problems [A39];
cutting plane approaches for nonlinear nonconvex problems expressed in "DC" (difference of convex functions) form, [A28, A27] or their generalizations [A35];
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] and that of pairwise compatibility graphs [A40];
special classes of BiLevel Programming problems, for which theoretical properties have been analyzed in order to develop more efficient solution algorithms [A1].