Jeudi 11 Février
Heure: 
10:30  11:30 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
Linearization techniques for MINLP 
Description: 
Sandra Ulrich Ngueveu We review stateoftheart linearization and approximation techniques for the solution of nonlinear mixedinteger programs. We show in particular how to ensure an a priori guarantee on the quality/feasibility of the solution, a reduction of the size of the converted problem and a minimization of the computing time. We then present an iterative method for the solution of a class of nonlinear mixedinteger programs to arbitrary numerical precision. By keeping the scope of the update local from one iteration to another, the computational burden is only slightly increased from iteration to iteration. As a consequence, our method presents very nice scalability properties and is little sensitive to the desired precision. We assess its efficiency for approximating the nonlinear variants of three problems: the uncapacitated facility location problem, the multicommodity network design problem, and the transportation problem. Our results indicate that, as the desired precision becomes smaller, our approach can lead to significant gains in computing times, often being orders of magnitude faster than a baseline method, and scales to approximate larger problems. 
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 reallife networks will be presented. 

