Skip to content
Fabio Furini

Operations Research · Combinatorial Optimization

Fabio Furini

Associate Professor of Operations Research

Department of Computer, Control and Management Engineering "Antonio Ruberti", Sapienza University of Rome

Exact algorithms for combinatorial optimization — integer programming, decomposition and reformulation, applied to packing, coloring, clique, interdiction and location problems.

Industrial collaborations in production planning, telecommunications, network robustness and rail transport. Industrial collaborations →

About

I am an Associate Professor of Operations Research at the Department of Computer, Control and Management Engineering "Antonio Ruberti" (DIAG), Sapienza University of Rome. My research is on exact algorithms for hard combinatorial optimization problems: mixed-integer linear programming, decomposition and reformulation techniques, and combinatorial branch-and-bound, with a consistent focus on solving to proven optimality instances that were previously out of reach.

Before joining Sapienza in 2021, I was Maître de conférences at LAMSADE, Université Paris Dauphine-PSL (2013–2019), where I obtained the Habilitation à diriger des recherches in 2017, and a postdoctoral fellow at LIPN, Université Paris 13, and at the University of Bologna. I received my Ph.D. from the University of Bologna in 2011, under the supervision of Paolo Toth and Alberto Caprara. I hold the national qualification as Full Professor in Italy, France and Denmark.

I am Associate Editor of Omega, and Program Committee Chair and local organizer of the European Mixed Integer Programming Workshop (EUROMIP) 2026 in Rome.

Research

Lines of work

All research themes →

Bin Packing & Cutting Stock

Exact algorithms for packing items into bins and cutting stock into pieces: branch-price-and-cut, pattern enumeration, and numerically safe dual bounds, including variants with setups and the temporal and two-dimensional variants.

10 papers2012–2026

Knapsack Problems

Exact and approximation algorithms for knapsack variants with setups, conflicts, products, and time windows, together with the polyhedral study of cover inequalities.

8 papers2013–2022

Graph Coloring

Branch-and-price and DSATUR-based branch-and-bound for vertex, weighted, partition, and minimum-sum coloring, including reformulations as maximum weight stable set problems.

6 papers2012–2021

Clique & Stable Set

Exact combinatorial algorithms for maximum clique and its weighted and edge-weighted variants, with SAT-based filtering, tightened upper bounds, and relaxed-clique decompositions.

6 papers2019–2026

Interdiction, Blocker & Vertex Cut

Bilevel and interdiction problems on graphs: vertex k-cut, capacitated vertex separators, clique and edge interdiction, and maximum flow blockers.

6 papers2019–2026

Transportation & Scheduling

Real-world optimisation in air and rail traffic: aircraft sequencing, train timetabling and routing, and barge container ship routing.

5 papers2015–2026

Decomposition & Reformulation

Automatic Dantzig-Wolfe reformulation of mixed integer programs and perspective relaxations for problems with semi-continuous variables.

3 papers2015–2017

Covering, Location & Submodularity

Benders decomposition for very large scale covering and maximal covering location problems, and submodular maximization of concave utilities composed with a set-union operator.

2 papers2019–2022

Binary Quadratic Programming

Linearisation techniques for binary quadratic problems and QPLIB, the reference library of quadratic programming instances.

2 papers2019

Selection

Selected publications

All 62 publications →

Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem

F. Furini, I. Ljubić, E. Malaguti, P. Paronuzzi

Operations Research, 2022

Given an undirected graph, we study the capacitated vertex separator problem which asks to find a subset of vertices of minimum cardinality, the removal of which induces a graph having a bounded number of pairwise disconnected shores (subsets of vertices) of limited cardinality. The problem is of great importance in the analysis and protection of communication or social networks against possible viral attacks, and for matrix decomposition algorithms. In this article we provide a new bilevel interpretation of the problem, and model it as a two-player Stackelberg game, in which the leader interdicts the vertices (i.e., decides on the subset of vertices to remove), and the follower solves a combinatorial optimization problem on the resulting graph. This approach allows us to develop a computational framework based on an integer programming formulation in the natural space of the variables. Thanks to this bilevel interpretation, we derive three different families of strengthening inequalities and show that they can be separated in polynomial time. We also show how to extend these results to a min-max version of the problem. Our extensive computational study conducted on available benchmark instances from the literature reveals that our new exact method is competitive against the state-of-the-art algorithms for the capacitated vertex separator problem, and is able to improve the best known results for several difficult classes of instances. The ideas exploited in our framework can also be extended to other vertex/edge deletion/insertion problems or graph partitioning problems by modeling them as two-player Stackelberg games and solving them through bilevel optimization.

Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems

S. Coniglio, F. Furini, I. Ljubic

Mathematical Programming, 2022

We study a family of discrete optimization problems asking for the maximization of the expected value of a concave, strictly increasing, and differentiable function composed with a set-union operator. The expected value is computed with respect to a set of coefficients taking values from a discrete set of scenarios. The function models the utility function of the decision maker, while the set-union operator models a covering relationship between two ground sets, a set of items and a set of metaitems. This problem generalizes the problem introduced by, and it can be modeled as a mixed integer nonlinear program involving binary decision variables associated with the items and metaitems. Its goal is to find a subset of metaitems that maximizes the total utility corresponding to the items it covers. It has applications to, among others, maximal covering location, and influence maximization problems. In the paper, we propose a double-hypograph decomposition which allows for projecting out the variables associated with the items by separately exploiting the structural properties of the utility function and of the set-union operator. Thanks to it, the utility function is linearized via an exact outer-approximation technique, whereas the set-union operator is linearized in two ways: either (i) via a reformulation based on submodular cuts, or (ii) via a Benders decomposition. We analyze from a theoretical perspective the strength of the inequalities of the resulting reformulations, and embed them into two branch-and-cut algorithms. We also show how to extend our reformulations to the case where the utility function is not necessarily increasing. We then experimentally compare our algorithms inter se, to a standard reformulation based on submodular cuts, to a state-of-the-art global-optimization solver, and to the greedy algorithm for the maximization of a submodular function. The results reveal that, on our testbed, the method based on combining an outer approximation with Benders cuts significantly outperforms the other ones.

On Integer and Bilevel Formulations for the k-Vertex Cut Problem

F. Furini, I. Ljubic, E. Malaguti, P. Paronuzzi

Mathematical Programming Computation, 2020

The family of Critical Node Detection Problems asks for finding a subset of vertices, deletion of which minimizes or maximizes a predefined connectivity measure on the remaining network. We study a problem of this family called the k-vertex cut problem. The problems asks for determining the minimum weight subset of nodes whose removal disconnects a graph into at least k components. We provide two new integer linear programming formulations, along with families of strengthening valid inequalities. Both models involve an exponential number of constraints for which we provide poly-time separation procedures and design the respective branch-and-cut algorithms. In the first formulation one representative vertex is chosen for each of the k mutually disconnected vertex subsets of the remaining graph. In the second formulation, the model is derived from the perspective of a two-phase Stackelberg game in which a leader deletes the vertices in the first phase, and in the second phase a follower builds connected components in the remaining graph. Our computational study demonstrates that a hybrid model in which valid inequalities of both formulations are combined significantly outperforms the state-of-the-art exact methods from the literature.

QPLIB: A Library of Quadratic Programming Instances

F. Furini, E. Traversi, P. Belotti, A. Frangioni, A. Gleixner, N. Gould, L. Liberti, A. Lodi, R. Misener, H. Mittelmann, N. Sahinidis, S. Vigerske and A. Wiegele

Mathematical Programming Computation, 2019

This paper describes a new instance library for Quadratic Programming (QP), i.e., the family of continuous and (mixed)-integer optimization problems where the objective function, the constrains, or both are quadratic. QP is a very ``varied'' class of problems, comprising sub-classes of problems ranging from trivial to undecidable. Solution methods for QP are very diverse, ranging from entirely combinatorial ones to completely continuous ones, including many for which both aspects are fundamental. Selecting a set of instances of QP that is at the same time not overwhelmingly onerous but sufficiently challenging for the many different interested communities is therefore important. We propose a simple taxonomy for QP instances that leads to a systematic problem selection mechanism. We then briefly survey the field of QP, giving an overview of theory, methods and solvers. Finally, we describe how the library was put together, and detail its final contents.

Automatic Dantzig-Wolfe Reformulation of Mixed Integer Programs

M. Bergner, A. Caprara, A. Ceselli, F. Furini, M. E. Lübbecke, E. Malaguti, E. Traversi

Mathematical Programming, 2015

Dantzig-Wolfe decomposition (or reformulation) is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs). However, the method is not implemented in any state-of-the-art MIP solver as it is considered to require structural problem knowledge and tailoring to this structure. We provide a computational proof-of-concept that the reformulation can be automated. That is, we perform a rigorous experimental study, which results in identifying a score to estimate the quality of a decomposition: after building a set of potentially good candidates, we exploit such a score to detect which decomposition might be useful for Dantzig-Wolfe reformulation of a MIP. We experiment with general instances from MIPLIB2003 and MIPLIB2010 for which a decomposition method would not be the first choice, and demonstrate that strong dual bounds can be obtained from the automatically reformulated model using column generation. Our findings support the idea that Dantzig-Wolfe reformulation may hold more promise as a ge-ne-ral-pur-pose tool than previously acknowledged by the research community.