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,
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;

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

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 *k*x*k* matrices with
"small" *k*; then the original nonseparable function can be (possibly,
approximately) decomposed as a sum of *k*x*k* 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
[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] 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]. 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,
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].

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