Actualités du LIPN

[LIPN] [CNRS] [Université Paris 13]

To content | To menu | To search

Séminaire AOC

The seminars of the AOC team usually take place on Tuesday, from 12:30 to 13:30, in room B311.

Entries feed - Click here to abridge

Past posts

Tuesday 13 March 2012

Systèmes Algébro-différentiels et Optimisation Combinatoire

fr 

Tuesday 13 March 2012 at 12.30 PM — Seminars

Le séminaire AOC recevra le 13 mars à 12h30 Sébastien Martin (docteur, Université Paris Dauphine) dans l’amphithéâtre Darwin.

Les systèmes algébro-différentiels permettent de modéliser des systèmes physiques complexes comme les circuits électriques et les mouvements dynamiques. Ils sont souvent de grande taille et difficiles à résoudre.

Dans un premier temps, nous étudions le problème de l’analyse structurelle des systèmes algébro-différentiels conditionnels. Ce problème permet de vérifier si un tel système ne pourra pas être résolu par des méthodes numériques. Nous montrons que ce problème est équivalent au problème du sous-graphe sans couplage parfait. Nous montrons que ce dernier est NP-difficile. Nous proposons une formulation en termes de graphes et une formulation en nombres entiers pour ce problème. Nous étudions le polyèdre associé et décrivons plusieurs classes de contraintes valides. Nous donnons des conditions nécessaires et suffisantes pour que ces contraintes définissent des facettes. Nous discutons également d’algorithmes de séparation pour ces contraintes et en utilisant ces résultats, nous développons un algorithme de coupes et branchements. Nous étudions aussi une extension de ce problème pour les systèmes algébro-différentiels conditionnels imbriqués. Nous étendons la plupart des résultats précédent à ce cas. Nous identifions de nouvelles contraintes valides pour cette variante du problème.

Dans une deuxième partie, nous nous intéressons au problème de parallélisation des systèmes algébro-différentiels. Ce problème se ramène au problème du séparateur. Nous proposons une formulation en nombres entiers et nous étudions le polyèdre associé. Nous proposons quelques résultats expérimentaux obtenus suite à cette étude.

Ce travail a été réalisé en collaboration avec M. Lacroix et R. Mahjoub.

Tuesday 14 February 2012

A Case in Serendipity: 1 Error = 5+ MINLP Papers

fr 

Tuesday 14 February 2012 at 12.30 PM — Seminars

Le séminaire AOC recevra le 14 février à 12h30 Antonio Frangioni (professeur, Université de Pise, Italie).

We report as an unintended reformulation of a MIQP with cost-separable semi-continuous variables led us to the accidental (re)discovery of a useful concept, that of Perspective Reformulation of a MINLP, and to subsequent unexpected developments. In particular we will report of extensions to non-cost-separable variables (prompted by the need to finding another application to publish the first paper), comparison of our Semi-Infinite MILP formulation and MI-Second Order Cone formulations (prompted by the need of fending off competing teams), applications (which originally motivated the discovery) that are successful mainly for wrong reasons, as well as some more recent developments about "projected" versions of the approach, with some fresh results presented for the first time. Apart from providing an overview on a recent and potentially interesting research field in MINLP, we hope that this talk can motivate the audience to making more errors and looking at them with more interest.

Tuesday 10 January 2012

Recouvrement d'un corps par des sphères

fr 

Tuesday 10 January 2012 at 12.30 PM — Seminars

Le séminaire AOC recevra le mardi 10 janvier à 12h30 Nelson Maculan (professeur, Universidade Federal do Rio de Janeiro, Brésil).

Étant donné un corps T à trois dimensions (de forme quelconque) et un lot de sphères de rayons différents, nous voudrions recouvrir ce corps T avec ces sphères en minimisant leur nombre selon certaines conditions.

Nous présentons

  • d’une part, deux modèles d’optimisation non linéaire mixte avec quelques résultats numériques,
  • d’autre part, une application associée à la radiation d’une tumeur par des rayons gamma (gamma-knife), dont les résultats numériques sont illustrés par un système graphique de l’aide à la décision.

    • Ce travail est une extension de

    L. Liberti, N. Maculan& Y. Zhang, Optimal configuration of gamma ray machine radiosurgery units: the sphere covering subproblem, Optimization Letters, vol. 3, pp. 109-121, (2009).

Monday 7 November 2011

Formulations and Exact Algorithms for the Asymmetric Traveling Salesman Problem

fr 

Monday 7 November 2011 at 12.30 PM — Seminars

Le séminaire AOC recevra le 7 novembre à 12h30 Paolo Toth (professeur, Université de Bologne, Italie).

Attention, horaire inhabituel le lundi !

The Traveling Salesman Problem (TSP) is one of the best-known combinatorial optimization and graph theory problems. In this talk, the “asymmetric” (i.e. defined on a directed graph) version of the problem, called ATSP in the following, is considered. ATSP can be defined as follows. Given a complete directed graph G, where each arc has an associated cost, a Hamiltonian circuit of G is a circuit passing through each vertex of G exactly once. The ATSP is to find a Hamiltonian circuit of G whose total cost (given by the sum of the costs of its arcs) is a minimum. Such a problem is known to be NP-hard in the strong sense, and finds many practical applications (e.g. in vehicle routing, scheduling, wiring, FMS, and sequencing problems).

The talk will review the main Integer Linear Programming formulations and the most effective exact algorithms proposed for ATSP.

Extensive computational results comparing the performance of the previously described algorithms on random and real-world instances from the literature will be reported.

Tuesday 11 October 2011

Don't break my orbits

fr 

Tuesday 11 October 2011 at 12.30 PM — Seminars

Le séminaire AOC recevra le 11 octobre à 12h30 Léo Liberti (professeur chargé de cours, École polytechnique).

Symmetries in ILP are routinely exploited in Branch-and-Bound (BB) solvers by breaking them, i.e. by pruning BB subtrees rooted at branching disjunctions on variables whose index is equivalent, by orbit symmetry, to other variable indices whose BB subtree was already explored. We propose here a reformulation technique based on linearizing orbits by means of added variables. By relaxing the defining constraints of each linearization, we obtain an ILP reformulation of the original ILP, which is, in certain instances, suprisingly effective as regards bound quality and solution efficiency.

Wednesday 4 May 2011

Une 3/2-approximation pour le problème de forêt couvrante contrainte

fr 

Wednesday 4 May 2011 at 12.00 PM — Seminars

Le séminaire AOC recevra le 4 mai Basile Couëtoux (post-doc, Dauphine), à 12h00 de façon exceptionnelle.

Attention, cette séance aura lieu le mercredi à midi au lieu de l’horaire habituel.

Nous nous intéressons à un problème de localisation qui consiste à couvrir un graphe avec des arbres contraints de poids minimal. Étant donné un graphe pondéré, le problème de la forêt couvrante contrainte consiste à trouver une forêt d’arbres contenant chacun au moins p sommets, couvrant le graphe, telle que la somme des poids des arêtes de cette forêt soit minimale. Nous notons ce problème Min WCF(p). Min WCF(p) pour p>3 a été montré NP-difficile par Imielinska et al.. Ces auteurs ont également établi un algorithme d’approximation à un facteur 2 près en utilisant une méthode gloutonne. Laszlo et Mukherjee proposent un algorithme plus raffiné, qui fournit une solution au moins aussi bonne que la solution fournie par l’algorithme précédent, mais qui reste cependant une approximation à 2 près. L’application de la méthode générale sur les forêts contraintes de Goemans et Williamson pour Min WCF(p) donne un algorithme d’approximation à un facteur 2-1/n près, où n est le nombre des sommets du graphe.

Nous avons déjà établit d’autres résultats de difficulté pour ce problème et nous allons présenter un algorithme qui est une 3/2-approximation.

Tuesday 3 May 2011

Systèmes interactifs pour la résolution de problèmes complexes

fr 

Tuesday 3 May 2011 at 12.00 PM — Seminars

Le séminaire AOC recevra le 3 mai Marin Bougeret (post-doc, ENS Lyon), à 12h00 de façon exceptionnelle.

Systèmes interactifs pour la résolution de problèmes complexes : application en optimisation combinatoire, planification et ordonnancement.

Cette présentation traite de l’utilisation de l’interaction avec un oracle pour la construction d’algorithmes ayant des performances garanties.

L’oracle est considéré comme pouvant répondre instantanément et correctement à n’importe quelle question. Informellement, on s’intéresse au compromis "performance de l’algorithme, coût de l’algorithme, quantité d’information donnée par l’oracle".

Bien que l’étude de tels compromis existe dans différents domaines, tels l’algorithmique distribuée, ou l’algorithmique online, nous nous restreindrons au cadre des problèmes d’optimisation offline (avec un accent sur les problèmes d’ordonnancement), et de la théorie de l’approximation.

On s’intéresse donc au compromis "ratio d’approximation, temps d’exécution, quantité d’information donnée par l’oracle".

On souhaite écrire un algorithme interactif Aint qui, étant donné une instance, pose une question à l’oracle, et fournit grâce à la réponse une solution garantie (à un facteur ρ de l’optimal). Un tel algorithme peut ensuite être transformé en un algorithme classique Aclq (sans oracle), soit en remplaçant l’oracle par un autre algorithme B, soit en re-exécutant Aint pour toutes les réponses possibles à la question posée. Il se trouve que ce formalisme interactif a des liens forts avec des techniques usuelles de conception de schémas d’approximation.

Le premier objectif de la présentation est donc de situer ce formalisme par rapport aux techniques existantes (en examinant les possibilités qu’il offre), et de comprendre quelles sont les "bonnes" questions à poser à l’oracle pour obtenir beaucoup d’information via une "petite" réponse. Le propos sera illustré sur des exemples simples venant du problème du Knapsack, ou de l’ordonnancement de tâches indépendantes sur des machines identiques.

Le second objectif est de donner un exemple complet d’application sur le problème du "Multiple Strip Packing" (MSP). Le MSP consiste à placer des rectangles dans un nombre fixé de boîtes (ayant des largeurs différentes et des hauteurs infinies), en minimisant la hauteur maximale atteinte. Ce problème est 2-innaproximable en temps polynomial, à moins que P=NP. Je présenterai un algorithme interactif ayant un ratio d’approximation de 5/2.

Thursday 28 April 2011

Extended formulations, non-negative factorizations and randomized communication protocols

fr 

Thursday 28 April 2011 at 12.00 PM — Seminars

Le séminaire AOC recevra le 28 avril Roland Grappe (post-doc, Padoue)

Attention, cette séance aura lieu le jeudi à midi au lieu de l’horaire habituel.

An extended formulation of a polyhedron P is a polyhedron in a higher dimensional space whose projection is P. In a seminal paper, Yannakakis (1991) proved that the minimum number of facets in an extended formulation of a given polytope is the non-negative rank of its slack matrix.

We show that the non-negative rank of a non-negative matrix is (up to small constants) determined by the minimum complexity of a randomized communication protocol computing the matrix on average.

We then use this connection to prove novel conditional lower bounds on the sizes of extended formulations, in particular, for perfect matching polytopes.

This is joint work with Michele Conforti, Yuri Faenza, Samuel Fiorini and Hans Raj Tiwary.

Tuesday 26 April 2011

Des problèmes d'optimisation combinatoire avec des applications en biologie et data-mining

fr 

Tuesday 26 April 2011 at 12.30 PM — Seminars

Le séminaire AOC recevra le 26 avril Antonio Mucherino (post-doc, CERFACS)

Dans ce séminaire, je vais discuter de problèmes qui sont importants dans les domaines de la biologie et du data-mining. Ces problèmes peuvent être formulés comme des problèmes d’optimisation combinatoire. Le premier problème que je vais considérer est l’identification de la conformation tridimensionnelle d’une molécule en utilisant certaines distances entre ses atomes. Ce problème est connu dans la littérature scientifique comme le problème de distance geometry. Il s’agit d’un problème de satisfaction de contraintes que nous avons reformulé comme un problème d’optimisation combinatoire. Cette reformulation est basée sur deux conditions, qui sont fortement liées à l’ordre dans lequel les atomes de la molécule sont triés. Dans ce contexte, alors, le problème d’identifier un ordre pour les atomes d’une molécule, qui nous permet de discrétiser le problème de distance geometry, est de grande importance. Il s’agit encore d’un problème d’optimisation combinatoire. Enfin, le dernier problème que je vais considérer est le problème de l’identification des biclusterings cohérents de matrices de données. Les solutions de ce problème combinatoire permettent d’effectuer des classifications de données en data mining. Des applications classiques pour ce problème sont l’analyse de gènes en biologie et l’analyse des fermentations du vin en agriculture.

Tuesday 22 March 2011

Détermination des éléments les plus vitaux pour des problèmes de graphes

fr 

Tuesday 22 March 2011 at 12.00 PM — Seminars

Le séminaire AOC recevra le 22 mars (à 12h exceptionnellement) Sonia Toubaline (Dauphine).

Nous considérons les versions des k arêtes (sommets) les plus vitales (vitaux) et de min arête (sommet)-bloqueur pour différents problèmes de graphes. Etant donné un problème d’optimisation P défini sur un graphe valué, le problème "k Most Vital Edges (Nodes) P" consiste à déterminer un sous-ensemble de k arêtes (sommets) dont la suppression du graphe dégrade au maximum la valeur optimale de P. Le problème complémentaire, "Min Edge (Node) Blocker P", consiste à supprimer un sous-ensemble d’arêtes (sommets) de cardinalité minimale tel que la valeur optimale de P est, selon la nature de P, inférieure ou égale ou supérieure ou égale à un seuil spécifique. Nous étudions la complexité, l’approximation et la résolution exacte de ces quatre versions pour les problèmes de graphes suivants : arbre couvrant de valeur minimale, affectation de valeur minimale, stable de valeur maximale, couverture de valeur minimale, 1-médian, 1-centre, flot de coût minimal et flot maximum. Ainsi, nous proposons des preuves de NP-difficulté au sens fort ou de polynomialité pour des classes particulières de graphes, des résultats d’approximation, des algorithmes d’énumération explicite ou implicite pour résoudre ces problèmes ou encore une formulation par programmation linéaire.

- page 1 of 2