Séminaire d'Optimisation Combinatoire

Lundi 11 janvier 2010 à 14h en salle A707

Title: On families of split cuts that can be generated efficiently

Abstract: Split cuts represent the most widely used class of cutting planes currently employed by state-of-the-art branch-and-cut solvers for mixed integer linear programming. Rank-1 cuts often have better numerical properties than higher rank cuts. With the aim of generating a good approximation of the first split closure (the intersection of all split cuts), we study several heuristics to generate new families of strong rank-1 split cuts, by considering integer linear combinations of the rows of the simplex tableau, and deriving the corresponding mixed-integer Gomory cuts. In particular, we propose several cut generation algorithms that share the following aims: reducing the number of nonzeroes, obtaining small coefficients, generating orthogonal cuts. A key idea is that of selecting a subset of the variables, and trying to generate a cut which cuts deeply on those variables. We show that variables with small reduced cost are good candidates for this purpose, yielding cuts that close a larger integrality gap. On a set of MILP test instances where standard split cut generators close on average 28.8% of the integrality gap in the first pass, we can close 35.3% by investing 10 times as much cut generation time. Incorporating our new split cuts into a branch-and-cut algorithm yields an improvement in the overall performance: except on very easy instances, where our procedure is too slow to bring advantage, on average we can save 23% computing time on instances which are solved, and close more integrality gap on unsolved instances in a fixed amount of time.

Lundi 25 janvier 2010 à 14h en salle A707

Title: Paths and trails in edge-colored graphs and digraphs

Abstract: Different algorithmic questions regarding properly edge-colored s-t paths/trails in edge-colored graphs and digraphs are addressed in this talk. Given a c-edge-colored graph $G^c$ with no properly edge-colored closed trails, we present a polynomial time procedure for the determination of properly edge-colored s-t trails visiting all vertices of $G^c$. As an immediate consequence, we polynomially solve the Hamiltonian path (resp., Eulerian trail) problem for this particular class of graphs. In addition, we prove that to check whether $G^c$ contains 2 properly edge-colored s-t paths/trails with length at most L > 0 is NP-complete in the strong sense. Besides, we also show that if $G^c$ is a general c-edge-colored graph, to find 2 monochromatic vertex disjoint s-t paths with different colors is NP-complete. Regarding c-edge-colored digraphs, we show that the determination of a directed properly edge-colored $s$-$t$ path is NP-complete. If the digraph is a c-edge-colored tournament, we show that deciding whether it contains a properly edge-colored circuit passing through a given vertex v (resp., directed s- t Hamiltonian path) is NP-complete. As a consequence, we solve a weak version of an open problem posed in [Gutin, Sudakov and Yeo, 1998]. In addition, we show that several problems are polynomial if we deal with directed properly edge-colored s-t trails instead of directed properly edge-colored s-t paths.

Lundi 8 février 2010 à 14h en salle A707

Titre : Comparaison et évaluation en moyenne de processus d'optimisation pour le problème du vertex cover

Résumé : Dans la littérature, on considère souvent qu'un algorithme d'approximation polynomial est plus performant qu'un autre lorsqu'il possède un meilleur rapport d'approximation en pire cas. Cependant, il faut être conscient que cette mesure, désormais "classique", ne prend pas en compte la réalité de toutes les exécutions possibles d'un algorithme (elle ne considère que les exécutions menant à la plus mauvaise solution). Dans les travaux que je vais vous présenter, nous nous sommes focalisés sur le problème du vertex cover et nous avons tenté de mieux "capturer" le comportement des ces algorithmes d’approximation en montrant que les performances moyennes d’un algorithme peuvent être décorélées des performances en pire cas, en évaluant les performances moyennes d’un algorithme et en comparant les performances de différents algorithmes (analytiquement et expérimentalement). Nous avons aussi proposé un algorithme de liste et nous avons prouvé analytiquement qu'il retourne toujours une meilleure solution que celle construite par un autre algorithme de liste récent [ORL 2006] quand ils traitent la même liste de sommets (dans certains graphes particuliers, la différence de taille peut être arbitrairement grande). On constate dans ces études que les algorithmes 2-approchés étudiés sont ceux qui obtiennent les plus mauvaises performances en moyenne et que ceux qui ont les meilleurs comportements moyens ont de mauvais rapports d'approximation.

Lundi 15 février 2010 à 14h en salle A707

Titre : Trois problèmes polynomiaux en optimisation combinatoire

Résumé : Nous présentons trois nouveaux problèmes d'optimisation combinatoire que l'on peut résoudre en temps polynomial. Le premier problème (traité avec Mateusz Zotkiecz et Michal Pioro) consiste à calculer une paire de chemins qui peuvent partager certains arcs fiables mais qui sont obligatoirement disjoints en termes d'arcs non fiables. Si un arc fiable est utilisé par deux chemins, son coût est comptabilisé une seule fois. Nous montrons que ce problème et certaines de ses généralisations sont faciles à résoudre. Le second problème (traité avec Mohamed Didi Biha) consiste à calculer une coupe séparatrice de deux sommets donnés. Etant donné un graphe non-orienté valué et deux sommets a et b, nous souhaitons trouver une coupe minimale telle que les deux sommets a et b sont du même coté de la coupe tout en étant dans deux composantes connexes différentes. Nous donnons un algorithme combinatoire, des formulations compactes et une description complète du dominant de ces coupes. Le troisième problème (traité avec Makhlouf Hadji) consiste à construire un réseau à composantes connexes unicycliques tout en respectant des contraintes de type Steiner : des sommets particuliers doivent appartenir aux cycles. Nous montrons que ce problème se résout en temps polynomial, nous donnons une description partielle du polytope et quelques algorithmes de séparation.

Lundi 22 février 2010 à 14h en salle A707

Titre : Acyclicité des hypergraphes : caractérisations et problèmes d'optimisation.

Résumé : Un graphe est acyclique s'il ne contient pas de cycle. Dans un hypergraphe, identifier une suite d'hyperarêtes et/ou de sommets à un cycle est plus arbitraire. Il existe justement plusieurs notions non équivalentes de la notion d'acyclicité pour les hypergraphes. Elles sont pour la plupart issues de la théorie des bases de données. Dans cet exposé, nous allons présenter les quatre notions suivantes (par ordre strictement croissant de généralité) : la Berge-acyclicité, la gamma-acyclicité, la beta-acyclicité et l'alpha-acyclicité. Pour chaque notion, nous verrons plusieurs façons de la caractériser. Puis nous nous intéresserons à des problèmes d'optimisation et de complexité autour de ces notions.

Lundi 15 mars 2010 à 14h en salle A711

Title: Optimizing Helicopter Transport of Oil Rig Crews at Petrobras

Abstract: This work presents the Helicopter Planning and Scheduling System implemented at Petrobras. Offshore platforms are responsible for most Brazilian oil production and require the air transportation of more than 68 thousand passengers per month in order to operate them. The main objective of the project was to reduce the number of offshore landings since this is the more dangerous phase of an helicopter flight. The optimization model in this complex system consists of a MIP that is solved (approximately) by column generation. The system was succesfully deployed in four airports. A reduction of 18% in landings was verified, which corresponds to approximately 15 thousand fewer landings per year. In addition, cost savings of 14%, representing more than 20 million USD per year, were observed.

Lundi 22 mars 2010 à 15h en salle B104bis

Title: Mechanism without Money is expensive

Abstract: In literature on algorithmic mechanism design, truthful approximation mechanisms are mostly relied on enforcing payment due to various social choice impossibility results. However, in many important environments, the money cannot be used as a medium of compensation because of ethical (political decisions) or legal (organ donations) considerations. We consider mechanism design without payment in which approximation can be used to obtain strategy-proofness (truthfulness) without resorting to payments. We consider the problem of Facility Locations in which each agent has a location at a node of a graph. Given the locations of all agents, a mechanism opens a facility that minimizes a social objective function and obtains simultaneously strategy-proofness. Our main results: we prove conjectures proposed by Alon et al. and settle the complete picture of the single facility - single location model. Joint work with Orestis Telelis.

Mardi 30 mars 2010 à 14h en salle A711

Titre : Représentation des graphes d'intervalles

Résumé : Nous abordons la question de la représentation des graphes d'intervalles à travers deux problèmes algorithmiques : le maintien dynamique d'un modèle d'intersection et la complétion d'un graphe quelconque en graphe d'intervalles. L'algorithme de maintien dynamique traite chacune des quatre opérations élémentaires, ajout ou retrait d'une arête ou d'un sommet (avec les arêtes définissant son voisinage), en temps O(n). Il détermine après chaque modification si le nouveau graphe est encore un graphe d'intervalles. Si la réponse est positive, un modèle d'intersection en est fourni, sinon l'algorithme s'arrête. Pour cela, nous utilisons la représentation classique par un PQ-arbre, introduite en 1976 par Booth et Lueker, dans sa version complétée par Korte et Möhring en 1985. Au passage, nous montrons une équivalence mathématique et algorithmique parfaite de cette dernière version avec la décomposition modulaire. Le problème de complétion est abordé par l'approche incrémentale et utilise la même représentation que l'algorithme dynamique. Chaque insertion de sommet étant traitée en temps O(n), la complexité totale de l'algorithme est O(n^2), ce qui améliore la précédente borne de O(nm) pour le problème et la place pour la première fois en deçà de la meilleure borne connue pour le problème plus général de la complétion en un graphe triangulé, résolu en temps O(nm) ou O(n^2.376).

Vendredi 7 mai 2010 à 14h en salle A711

Title: Exact and heuristic approaches for the multi-dimensional knapsack problem

Abstract: We first consider the general 0/1 multi-constraint knapsack problem and discuss the performances of a heuristic approach particularly suitable for a parallel computing environnment embedding core problem features and a strong branching scheme based on reduced costs of the corresponding LP relaxation solution value. The proposed approach is compared to the recent state of the art procedures available in the literature on the well known OR-Library multi-dimensional knapsack problem benchmarks instances improving several best known lower bounds. We focus then on the 2-constraint knapsack problem and focus on a pre-processing procedure aimed at reducing the size of the problem instance. The procedure mainly relies on the solution of a core problem and a state of the art ILP solver (CPLEX). The effectiveness of the reduction procedure is compared with the performances of the well known 2-KP algorithm by Martello and Toth (joint work with Andrea Grosso).

Vendredi 14 mai 2010 à 14h en salle A707

Titre : Coloration de graphes mixtes

Résumé : Un graphe mixte G=(V,E,U) est un graphe contenant à la fois des arêtes (ensemble E) et des arcs (ensemble U). Ces graphes permettent de modéliser des problèmes d'ordonnancement dans lesquels on a à la fois des contraintes de précédences et des contraintes de disjonction. Une coloration des sommets d'un graphe mixte est une fonction c qui associe à chaque sommet v du graphe un entier c(v) tel que (i) si (u,v) est dans E alors c(u) est differente de c(v) et (ii) si (u,w) est dans U alors c(u) est inferieur à c(w). Colorer les sommets d'un graphe mixte avec un nombre minimum de couleurs est un problème NP-difficile. Ici, nous allons analyser différentes classes de graphes mixtes et déterminer si le problème est polynomial ou NP-difficile dans ces classes. En particulier nous allons montrer que le problème est résoluble en temps polynomial dans les k-arbres partiels mixtes et que le problème reste NP-difficile même dans les graphes mixtes bipartis planaires 3-réguliers. Les résultats ont été obtenus en collaboration avec D. de Werra.

Vendredi 26 novembre 2010 à 14h en salle A711

Title: Algorithms on Dynamic Data

Abstract: I will present a new computational model for dynamic data. In this model, the input data change gradually (deterministically or stochastically) and the goal of an algorithm is to maintain the solution to some problem at each time step, under the constraint that it only has a limited access to the data each time. As the data is constantly changing and the algorithm might be unaware of these changes, it cannot be expected to always output the exact right solution; we are interested in algorithms that guarantee to output an approximate solution. After presenting the model, I will focus on the problems of sorting and of selecting an element of a given rank when the true ordering of the elements changes slowly and randomly. I will give lower bounds and algorithms achieving near-optimal performance in expectation and with high probability. Depending on the time, I will finish with the application of the model on some graph-related problems.

Lundi 6 décembre 2010 à 15h30 en salle A707

Title: Online maximum k-coverage

Abstract: We study an online model for the maximum k-coverage problem, where given a universe of elements E={e_1,e_2,…,e_m}, a collection of subsets of E, S={S_1,S_2,…,S_n}, and an integer k, we ask for a subcollection A of S, such that |A|=k and the number of elements of E covered by A is maximized. In our model, at each step i, a new set S_i is revealed, and we have to decide whether we will keep it or discard it. At any time of the process, only k sets can be kept in memory; if at some point the current solution already contains k sets, any inclusion of any new set in the solution must entail the irremediable deletion of one set of the current solution (a set not kept when revealed is irremediably deleted). We first propose an algorithm that improves upon former results for the same model. We next settle a graph-version of the problem, called maximum k-vertex coverage problem. Here also we propose non-trivial improvements of the competitive ratio for natural classes of graphs (mainly regular and bipartite).