11 Janvier - 17 Janvier


Retour à la vue des calendrier
Mardi 12 Janvier
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: An Exact Semidefinite Programming Approach for the Max-Mean Dispersion Problem
Description: Michele Garraffa This work proposes an exact algorithm for the Max-Mean Dispersion Problem (Max-Mean DP), an NP-hard combinatorial optimization problem whose aim is to select the subset of a set such that the average distance between elements is maximized. The problem admits a natural non-convex quadratic fractional formulation from which a semidefinite programming (SDP) relaxation can be derived. In general, semidefinite relaxations have been successfully used to determine tight (but usually computationally expensive) lower/upper bounds for challenging NP-hard problems, such as the Quadratic Assignment Problem and the Quadratic Knapsack Problem. The semidefinite relaxation for the Max-Mean DP can be further tightened by means of a cutting plane algorithm which iteratively adds the most violated triangular inequalities. The proposed approach embeds the SDP relaxation and the cutting plane algorithm into a branch and bound framework to solve Max-Mean DP instances to optimality. To authors' knowledge, this is the first exact algorithm that has been proposed for this problem. Computational experiments show that the proposed method is able to solve to optimality in reasonable time instances with up 100 elements, while standard methods for fractional combinatorial optimization manage instances whose size is less then or equal to 75. The presented approach can be generalized to other combinatorial problems with a quadratic fractional objective and linear constraints.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: TBC
Description: Julien Courtiel
Mercredi 13 Janvier
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: TBC [attention, c'est un mercredi]
Description: Julien Courtiel