Antonio Frangioni's Research Interests

Disponibile anche in italiano.

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:

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.

NonDifferentiable Optimization

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.

Interior Point methods

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.

Algorithms for nonlinear mixed-integer programs

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

Single- and multicommodity flow problems

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.

Network Design problems

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.

Problems related to energy systems

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.

Max-Cut problems

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

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.

Telecommunication problems

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

Other problems and methodologies

I've also given contributions to a number of other applications and methodologies, such as:


Last update: 07/07/2021