Séminaire d'Optimisation Combinatoire

Lundi 2 février 2009 à 14h en salle A707

Eduardo Uchoa Barboza, Université Fédérale Rio de Janeiro, Bresil

Title: A Polyhedral Study of the Time Dependent Traveling Salesman Problem

Abstract: The Time-Dependent Traveling Salesman Problem (TDTSP) is a generalization of the Traveling Salesman Problem (TSP), where arc costs depend on their position in the tour with respect to a chosen source node. We study a polytope associated with this problem, computing its dimension and identifying several classes of facet-defining inequalities. It is interesting to know that classical TSP facets correspond to disappointingly low dimensional faces of the TDTSP polytope. The new inequalities are also shown to be effective in a branch-cut-and-price algorithm, not only for the TDTSP itself, but also for several vehicle routing and scheduling problems. (Joint work with H. Abeledo, A. Pessoa and R. Fukasawa)

Lundi 9 février 2009 à 14h en salle A707

Titre : Ordonnancement de tâches on-line avec pénalités

Résumé : Nous nous intéressons au problème d'ordonnancement suivant. Soit un ensemble de tâches révélées une par une (on-line). Chaque tâche représente la requête d'un client et est définie par un triplet (r,d,p), où r est sa date d'arrivée, d sa date d'échéance et p son temps d'exécution et son poids. Lorsqu'une tâche est révélée, l'opérateur choisit de la rejeter ou de l'ordonnancer sur une des k machines identiques du système. Pour cela, il peut interrompre une tâche déjà ordonnancée s'il paie à celle-ci une pénalité proportionnelle à son poids. Étant données ces contraintes, le but de l'opérateur est de maximiser la somme des poids des tâches ordonnancées moins le total des pénalités accumulées. Pour résoudre ce problème, nous proposons un algorithme on-line dont le rapport de compétitivité est constant.

Lundi 2 mars 2009 à 14h en salle A707

Title: Convex relaxations in Branch and Bound global optimization methods: quadrilinear terms

Abstract: Mathematical programming problems involving nonconvex terms are usually solved using the spatial Branch and Bound (sBB) global optimization algorithm. Central to the sBB algorithm is the concept of convex relaxation of the original nonconvex problem, whose solution provides a bound on the optimal value of the objective function for every node in the search-space tree. We focus on quadrilinear terms, that occur often in the nonlinear programming formulation of known problems. We present four different ways to compute a convex (linear) relaxation of the graph of a quadrilinear monomial on a box, and we computationally analyze these relaxations in order to estabilish which is the tightest. We also apply the results to derive good convex relaxations for some instances of known problems, namely the Molecular Distance Geometry Problem and the Hartree-Fock Problem.

Lundi 23 mars 2009 à 14h en salle A707

Title: A Combinatorial Reformulation for the Molecular Distance Geometry Problem

Abstract: Many real life problems can be formulated as global optimization problems. Such problems are usually difficult to solve, because of the complexity of the objective function and constraints, and because of the large number of involved variables. The Molecular Distance Geometry Problem (MDGP) is the problem of finding the Cartesian coordinates of the atoms of a given molecule when some of the relative distances between pairs of atoms are known. This problem is usually formulated as a global continuous optimization problem. However, if some assumptions are satisfied, the continuous optimization problem can be reformulated as a combinatorial problem. This allows to reduce drastically the search domain of the optimization problem, and to improve the quality of the obtained solutions. A Branch and Prune (BP) algorithm is employed for solving the combinatorial problem.

Title: Separation, Dimension, and Facet Algorithms for Node Flow Polyhedra

Abstract: Given a directed acyclic graph with sources and sinks, consider the set of flows induced by putting non-negative flows on all source-sink paths. The flow through a node is the sum of the flows on all paths containing it. When the number of paths is much larger than the number of nodes, it is more convenient to consider the set of node flows in place of that of path flows. In a make-to-order production planning problem considered by Ball et al. (2003), nodes represent components and paths represent product configurations. The linear inequalities defining the set of node flows can then be used to model material compatibility constraints. Ball et al. found characterizations of the set of node flows for some special cases. We extend this work in various directions: we allow arbitrary directed networks, we allow both upper and lower bounds on flows, we characterize which valid inequalities are facets, we give fast algorithms for separation, validity, and dimension, and we put all the pieces together into an algorithm for separating to a facet. All algorithms are very efficient, as they are based on max flow and min-cost flow subroutines (Joint work with Maren Martens and Maurice Queyranne).

Lundi 6 avril 2009 à 14h en salle A707

Titre : Méthodes de résolution exacte des problèmes quadratiques en variables 0-1, basées sur des reformulations

Résumé : On s'intéresse à la résolution exacte de problèmes d'optimisation en variables 0-1 comportant une fonction objectif quadratique soumise à des contraintes linéaires. Ces problèmes sont généralement non convexes. Plus précisément, leur relaxation continue n'est pas un problème convexe. Pour pallier cette difficulté, l'approche principale développée consiste en une reformulation quadratique convexe du problème initial dans le but d'utiliser les méthodes générales de résolution des programmes quadratiques convexes en variables entières. Une nouvelle méthode et plusieurs variantes, basées principalement sur la programmation semidéfinie, seront détaillées dans cet exposé. De plus, on présentera une nouvelle reformulation linéaire, basée sur la résolution de la relaxation RLT. De nombreuses expérimentations sur des problèmes de graphe et un problème de gestion de portefeuille viennent valider les approches quadratiques.

Lundi 29 juin 2009 à 14h, salle A711

Titre : Optimisation de l'utilité espérée dépendant du rang dans les modèles graphiques pour la décision séquentielle

Résumé : Cet exposé sera consacré à la décision séquentielle automatique en IA. Plus précisément, nous nous intéresserons au modèle de l'utilité espérée dépendant du rang (RDEU). Ce modèle permet en effet de rendre compte de comportements décisionnels que l'utilité espérée ne peut expliquer. Néanmoins, la non-linéarité de RDEU complique singulièrement la tâche d'optimisation dans les problèmes de décision séquentielle. Lors de cet exposé, nous présenterons des résultats de complexité et proposeront des algorithmes exacts pour déterminer une stratégie optimale au sens de RDEU dans deux types de modèles graphiques: les arbres de décision et les diagrammes d'influence.

Lundi 26 octobre 2009 à 14h en salle A707

Titre : Coloration généralisée des sommets avec somme minimale dans certains sous-classes de graphes bloc

Résumé : Dans cet exposé, on introduit le problème de la coloration généralisée des sommets avec somme minimale (que l'on appellera " problème CGSM ") lequel consiste en affecter un ensemble d'entiers positifs de taille w(v) à chaque sommet v d'un graphe de sorte que l'intersection des ensembles affectés à toute couple des sommets adjacents soit vide et tel que la somme des entiers affectés aux sommets du graphe soit minimisée. Ce problème généralise celui classique sur la coloration des sommets avec somme minimum, lequel peut être résolu en temps polynomial pour les graphes bloc. On analysera deux versions du problème CGSM (avec préemption et sans préemption) dans deux sous-classes des graphes bloc : les arbres et les graphes représentatifs des arêtes des arbres. On montrera que les deux versions de ce problème sont NP-complets dans les graphes bloc. On montrera aussi l'existence d'algorithmes (pseudo)polynomiaux pour ce problème dans les graphes bloc si l'on fixe certains paramètres du graphe. Travail en collaboration avec Flavia Bonomo et Guillermo Duran (Univesité de Buenos Aires, Argentine) et Javier Marenco (Université Nationale de General Sarmiento, Argentine).

Lundi 2 novembre 2009 à 14h en salle A707

Titre : Augmentation de l'arête-connexité d'un hypergraphe sous contraintes de partition

Résumé : Un (hyper)graphe est k-arête-connexe si entre toutes paires de sommets il existe k chaînes (hyper)arête-disjointes. L'augmentation de l'arête-connexité d'un graphe consiste à, étant donnés un graphe G et un entier k, ajouter un nombre minimal d'arêtes à G pour le rendre k-arête-connexe. Grâce à l'algorithme de Frank, qui résout ce problème, de nombreuses extensions ont vu le jour : par exemple pour les hypergraphes, ou encore avec des contraintes supplémentaires sur les arêtes à ajouter. Nous proposons de résoudre la généralisation suivante: Soit H=(V,E) un hypergraphe, P une partition de V, et k un entier. Ajouter à H un nombre minimal d'hyperarêtes de taille 2 reliant différents membres de P pour le rendre k-arête-connexe. Nous exhibons deux bornes inférieures pour ce problème, et caractérisons les hypergraphes et les partitions pour lesquels ces bornes ne peuvent pas être atteintes. Un théorème min-max résolvant le problème en découle, accompagné d'une preuve constructive et polynomiale. Travail commun avec A. Bernath et Z. Szigeti.

Lundi 16 novembre 2009 à 14h en salle A707

Titre : Minorité stochastique sur les graphes de partition

Résumé : Nous considérons un graphe où les cellules sont caractérisées par un état qui est soit noir, soit blanc. À chaque pas de temps, une cellule, choisie aléatoirement, se met à jour et passe dans l'état minoritaire dans son voisinage. L'évolution globale de ce processus ne semble pas dépendre de la topologie du graphe: dans un premier temps des régions, pavées par des motifs dépendant de la topologie du graphe, se forment rapidement. Puis dans un deuxième temps, les frontières entre ces régions évoluent jusqu'à devenir relativement stables. Nous étudions ce processus sous différentes topologies: arbres, anneaux, grilles, cliques. Ceci nous permet de montrer que même si ce processus se comporte à priori globalement de la même manière sur n'importe quel graphe, modifier la topologie influence la façon dont les régions sont pavées (rayures, damiers), la structure et les mouvements des frontières entre les régions, l'ensemble limite, le temps de relaxation (le temps nécessaire pour que le processus atteigne une configuration de l'ensemble limite). Ainsi, Minorité entraîne des comportements riches et variés qui se révèlent difficile à analyser. Comprendre cette règle simple est néanmoins nécessaire avant de considérer des règles plus compliquées.

Lundi 14 décembre 2009 à 14h en salle A707

Titre : Chemins disjoints dans les graphes planaires

Résumé : Nous nous intéressons aux problèmes d'existence de flots entiers multicommodités dans les graphes. Une commodité est une paire de sommets (origine, destination), et pour chacune de ces paires, nous voulons trouver un flot d'un débit donné, de telle sorte que la somme des flots respectent la capacité des arêtes du graphe. Après un introduction à ce problème, nous rappelerons les principaux résultats du domaine, en particulier les derniers développement, puis montrerons la difficulté du problème de trouver un multiflot entier avec seulement deux commodités dans les graphes planaires. Enfin nous donnerons un algorithme pour router un nombre fixé de commodités dans un graphe planaire acyclique, lorsque la fonction de capacité (en tenant compte de la demande) est une circulation.