Sonia Cafieri

Sonia Cafieri

Auto-generated profile, based on publicly available information

Sonia Cafieri

ENAC, Université de Toulouse, Toulouse, France

Research Focus & Metrics

Academic Career Length

17Years (2010-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
21 October 2010 in Physical Review E
Verified
Journal Article
Closed access
PDF file
DADaniel Aloise
Daniel Aloise
SCSonia Cafieri
Sonia Cafieri
GCGilles Caporossi
Gilles Caporossi
PHPierre Hansen
Pierre Hansen
SPSylvain Perron
Sylvain Perron
LLLeo Liberti
Leo Liberti
Finding modules, or clusters, in networks currently attracts much attention in several domains. The most studied criterion for doing so, due to Newman and Girvan [ Phys. Rev. E 69, 026113 (2004)], is modularity maximization. Many heuristics have been proposed for maximizing modularity and yield rapidly near optimal solution or sometimes optimal ones but without a guarantee of optimality. There are few exact algorithms, prominent among which is a paper by Xu et al. [ Eur. Phys. J. B 60, 231 (2007)]. Modularity maximization can also be expressed as a clique partitioning problem and the row generation algorithm of Grötschel and Wakabayashi [ Math. Program. 45, 59 (1989)] applied. We propose to extend both of these algorithms using the powerful column generation methods for linear and non linear integer programming. Performance of the four resulting algorithms is compared on problems from the literature. Instances with up to 512 entities are solved exactly. Moreover, the computing time of previously solved problems are reduced substantially.

30 April 2013 in Journal of Global Optimization
Verified
Journal Article
Closed access
PDF file
SCSonia Cafieri
Sonia Cafieri
NDNicolas Durand
Nicolas Durand

2 April 2010 in Physical Review E
Verified
Journal Article
Closed access
SCSonia Cafieri
Sonia Cafieri
PHPierre Hansen
Pierre Hansen
LLLeo Liberti
Leo Liberti
The modularity maximization model proposed by Newman and Girvan for the identification of communities in networks works for general graphs possibly with loops and multiple edges. However, the applications usually correspond to simple graphs. These graphs are compared to a null model where the degree distribution is maintained but edges are placed at random. Therefore, in this null model there will be loops and possibly multiple edges. Sharp bounds on the expected number of loops, and their impact on the modularity, are derived. Then, building upon the work of Massen and Doye, but using algebra rather than simulation, we propose modified null models associated with graphs without loops but with multiple edges, graphs with loops but without multiple edges and graphs without loops nor multiple edges. We validate our models by using the exact algorithm for clique partitioning of Gr\"otschel and Wakabayashi.

6 May 2011 in Physical Review E
Verified
Journal Article
Closed access
SCSonia Cafieri
Sonia Cafieri
PHPierre Hansen
Pierre Hansen
LLLeo Liberti
Leo Liberti
Community detection in networks based on modularity maximization is currently done with hierarchical divisive or agglomerative as well as partitioning heuristics, hybrids, and, in a few papers, exact algorithms. We consider here the case of hierarchical networks in which communities should be detected and propose a divisive heuristic which is locally optimal in the sense that each of the successive bipartitions is done in a provably optimal way. This heuristic is compared with the spectral-based hierarchical divisive heuristic of Newman [Proc. Natl. Acad. Sci. USA 103, 8577 (2006).] and with the hierarchical agglomerative heuristic of Clauset, Newman, and Moore [Phys. Rev. E 70, 066111 (2004).]. Computational results are given for a series of problems of the literature with up to 4941 vertices and 6594 edges. They show that the proposed divisive heuristic gives better results than the divisive heuristic of Newman and than the agglomerative heuristic of Clauset et al.

1 July 2020 in Transportation Science
Verified
Journal Article
Closed access
AKAhmed Khassiba
Ahmed Khassiba
FBFabian Bastin
Fabian Bastin
SCSonia Cafieri
Sonia Cafieri
BGBernard Gendron
Bernard Gendron
MMMarcel Mongeau
Marcel Mongeau
The extended aircraft arrival management problem, as an extension of the classic aircraft landing problem, seeks to preschedule aircraft on a destination airport a few hours before their planned landing times. A two-stage stochastic mixed-integer programming model enriched by chance constraints is proposed in this paper. The first-stage optimization problem determines an aircraft sequence and target times over a reference point in the terminal area, called initial approach fix (IAF), so as to minimize the landing sequence length. Actual times over the IAF are assumed to deviate randomly from target times following known probability distributions. In the second stage, actual times over the IAF are assumed to be revealed, and landing times are to be determined in view of minimizing a time-deviation impact cost function. A Benders reformulation is proposed, and acceleration techniques to Benders decomposition are sketched. Extensive results on realistic instances from Paris Charles-de-Gaulle airport show the benefit of two-stage stochastic and chance-constrained programming over a deterministic policy.

29 December 2012 in Annals of Operations Research
Verified
Journal Article
Closed access
PDF file
SCSonia Cafieri
Sonia Cafieri
ACAlberto Costa
Alberto Costa
PHPierre Hansen
Pierre Hansen