15 Février - 21 Février


Retour à la vue des calendrier
Jeudi 18 Février
Heure: 10:30 - 11:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Combinatorial Optimization Theory and Algorithms for Set Packing and Location Problems
Description: Mercedes Pelegrin In this talk, we will cover modeling for two optimization problems, as well as Mathematical Programming methods that can be applied to solve them. The first part will be devoted to the set packing problem, one of the seminal problems in Combinatorial Optimization. We will focus on generating hyperplanes to describe the set packing polytope. Namely, we will present a new lifting theorem and illustrate its application to facility location. In the second part of the talk, we will address the problem of identifying a group of key nodes in a network. We will propose a mixed integer nonlinear program (MINLP) that embeds eigenvector centrality in a clustering partition. The resulting model uncovers the group of key nodes (the clusters centroids) and their communities (the clusters). Modeling this idea involves nonlinear equations, which will be linearized to produce a mixed integer linear program (MILP). Symmetry breaking, a recurrent topic in Combinatorial Optimization, will be also addressed. Computational results on synthetic and real-life networks will be presented.