Séminaire d'Optimisation Combinatoire

Lundi 14 janvier 2008 à 14h en salle A707

Title: Mixed hypergraphs and their generalizations

Title: Monotone Parametric Min Cut Revisited: Structures and Algorithms

Abstract: We consider the min cut problem when capacities depend on a parameter k. There are some classes of this parametric min cut problem that are known to have the nice structural property that min cuts are nested in k, and the nice algorithmic property that all min cuts can be computed in the same asymptotic time as one call to Push-Relabel. We extend these results in several directions: we find three more general classes of problems where these two nice properties still hold, and we extend to other results with the same flavor.

Lundi 4 février 2008 à 14h en salle A711

Title: An improved approximation algorithm for the Max-Controlled Set problem

Abstract: A vertex i of a graph G=(V,E) is said to be controlled by M \subseteq V if the majority of the elements of the neighborhood of i (including itself) belong to M. The set M is a monopoly in G if every vertex i \in V is controlled by M. Given a set M \subseteq V and two graphs G_1=(V,E_1) and G_2=(V,E_2) where E_1 \subseteq E_2, the monopoly verification problem (mvp) consists of deciding whether there exists a sandwich graph G=(V,E) (i.e., a graph where E_1 \subseteq E \subseteq E_2) such that M is a monopoly in G=(V,E). If the answer to the mvp is No, we then consider the max-controlled set problem (mcsp), whose objective is to find a sandwich graph G=(V,E) such that the number of vertices of G controlled by M is maximized. Th mvp can be solved in polynomial time; the mcsp, however, is NP-hard. In this work, we present a deterministic polynomial time approximation algorithm for the mcsp with ratio 1/2+ (1+\sqrt{n})/(2n-2), where n=|V|>4. The algoritm is obtained through the use of randomized rounding and derandomization techniques, namely the method of conditional expectations. Additionally, we show how to improve this ratio if good estimates of expectation are obtained in advance.

Lundi 11 février 2008 à 14h en salle A711

Titre : Sur la probabilité de satisfaisabilité des formules 2-XOR aléatoires

Résumé : Nous considérons le problème de satisfaisabilité des formules 2-XOR. Ces formules sont des conjonctions d'équations booléennes de la forme x \plus y = 0 (ou x \oplus y = 1). Une formule aléatoire de taille m sur n variables est générée en choisissant uniformément m équations parmi les n(n-1) possibles. La probabilité p(n, m) qu'une telle formule soit satisfaisable décroît en fonction de la taille m de la formule. Lorsque n tend vers l'infini, la transition de phase de la satisfaisabilité à l'insatisfaisabilité s'effectue pour les valeurs c \in (0,1/2) du paramètre d'ordre c=m/n.

Mardi 12 février 2008 à 14h en salle A707

Title: Hub location problems in cargo delivery

Abstract: Hub location problems are special location-allocation problems in which flows between origin/destination pairs are distributed via special centers called hubs. Hubs are consolidation and dissemination centers at which flows from the origin with different destinations are consolidated on their route at a hub node; and they are then combined with flows from different origins but same destinations. The hub location problem involves the location decisions of the hubs and the allocation decision of the demand centers to these hubs. Hub location models have applications in telecommunications, transportation and cargo delivery. In this talk we focus on specific objectives and constraints of hub location problems arising in cargo delivery. We model two problems that consider these specific requirements. In the first problem, we model the hub location problem with stopovers and delivery time objectives. In the second problem, we incorporate release time scheduling into hub location. For both problems, we derive valid inequalities and present computational results.

Lundi 17 mars 2008 à 14h en salle A707

Title: Weighted Timed Automata: Model-Checking and Games

Abstract: In this talk, I will present weighted/priced timed automata, an extension of timed automata with costs to represent natural quantitative aspects of embedded systems. I will then present several optimization problems on that model, I will show that some of those problems are very difficult, and finally present possible solutions to problems like the optimal reachability, the optimal mean-cost problem (optimal cost in the long-term), etc. This talk synthesizes joint works done in collaboration with Thomas Brihaye, Ed Brinksma, Véronique Bruyère, Franck Cassez, Emmanuel Fleury, Kim G. Larsen, Nicolas Markey, Jean-François Raskin, and Jacob Illum Rasmussen.

Lundi 31 mars 2008 à 14h en salle A707

Titre : Équilibres de Nash pour des jeux de Voronoi sur des graphes

Résumé : Les jeux de Voronoi ont été introduits pour étudier la séparation d'un espace par des agents visant à maximiser la surface attribuée. Nous étudions la version discrète qui se joue sur un graphe où la longueur du plus court chemin définit une métrique. Ceci peut être vu comme le jeu associé au problème de facility location. Il y a des graphes où le jeux converge vers un équilibre et des graphes où il n'y a pas de convergence. Nous montrons que distinguer ces deux cas est NP-complet. Pour finir nous étudions la différence du coût social entre les différents équilibres.

Mardi 20 mai 2008 à 14h en salle A707

Titre : Relaxations disjonctives pour problèmes d’optimisation pseudo-booléens

Résumé : L’utilisation d’inégalités valides déduites de la fermeture élémentaire des coupes de Lift-and-Project a permis le calcul efficace de bornes de très bonne qualité pour certaines classes de problèmes d’optimisation de fonctions quadratiques pseudo-booléennes, tels que le problème MAX-2-SAT (cf. Bonami & Minoux 2006). On commencera par rappeler comment la structure du problème d’optimisation sur la fermeture élémentaire des coupes de Lift-and- Project peut être exploitée pour générer des inégalités valides fortes. On discutera ensuite des liens avec d’autres types de relaxations (Sherali-Adams par exemple) ainsi que la possibilité d’extension de l’approche précédemment décrite à d’autres classes de relaxations disjonctives potentiellement plus fortes. Des résultats de calcul préliminaires illustreront l’intérêt potentiel et les difficultés de ce type d’extension.

Mardi 27 mai 2008 à 14h en salle A711

Eric Gourdin, Orange Lab

Titre : Optimisation des Reseaux IP/MPLS

Résumé : Dans les réseaux Internet, la façon dont le trafic est routé dépend du protocole de routage utilisé. Les protocoles de routage « classiques » routent le trafic sur des plus court chemins. Le méta-protocole MPLS (Multi-Protocole Label Switching) offre plus de flexibilité pour router le trafic. Le /Traffic Engineering/ (TE) consiste à chercher la meilleure façon d'utiliser les ressources d'un réseau donné pour satisfaire un ensemble de demandes. Dans cet exposé, plusieurs problèmes d'optimisation issus du TE seront présentés, ainsi que des modèles et/ou des techniques utilisés pour les résoudre.

Jeudi 12 juin 2008 à 14h en salle A405

Title: New Lower Bounds for the Split Delivery Vehicle Routing Problem (SDVRP)

Abstract: We present an algorithm combining column and cut generation for the SDVRP. We depart from an extended formulation over a large set of variables from which valid inequalities are derived. Columns are q-routes resulting a pseudo-polynomial pricing. We discuss branch-cut-and-price aspects, its ability to obtain good upper bounds and how fixing by reduced costs can be performed on the original variables. Up to now, best lower bounds were obtained to almost all instances tested (joint work with Lorenza Moreno and Eduardo Uchoa).

Lundi 16 juin 2008 à 13h en salle A711

Title: Finding total unimodularity in optimization problems solved by linear programs

Abstract: A popular approach in combinatorial optimization is to model problems as integer linear programs. Ideally, the relaxed linear program would have only integer solutions, which happens for instance when the constraint matrix is totally unimodular. Still, sometimes it is possible to build an integer solution with same cost from the fractional solution. Examples are two scheduling problems and the single disk prefetching/caching problem. We show that problems such as the three previously mentioned can be separated into two subproblems: (1) finding an optimal feasible set of slots, and (2) assigning the jobs or pages to the slots. It is straigthforward to show that the latter can be solved greedily. We are able to solve the former with a totally unimodular linear program, from which we obtain simple combinatorial algorithms with improved worst case running time.

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

Title: Modelling Hop-Constrained and Diameter-Constrained Minimum Spanning Tree Problems as Steiner Tree Problems over Layered Graphs

Abstract: The Hop-Constrained Minimum Spanning Tree Problem (HMSTP) is a NP-hard problem arising in the design of centralized telecommunication networks with quality of service constraints. We show that the HMSTP is equivalent to a Steiner Tree Problem (STP)in an adequate layered graph. We prove that the directed cut formulation for the STP defined in the layered graph, dominates the best previously known formulations for the HMSTP. We then show that the Steiner directed cuts in the extended layered graph space can be viewed as being the strengthening of some known cuts (including facets) in the original design space. Moreover, those strengthened cuts can be combined and projected into new families of cuts, including proven facets, in that original design space. We also adapt the proposed approach for the Diameter-Constrained Minimum Spanning Tree Problem (DMSTP). Computational results with a branch-and-cut algorithm show that the proposed method is significantly better than previously known methods on both problems. Joint work with Luis Gouveia and Luidi Simonetti.

Lundi 23 juin 2008 à 14h en salle A707

Mikhail Y. Kovalyov, Faculty of Economics Belarusian State University

Title: General ideas of FPTAS construction on the example of a production planning problem

Abstract: General ideas of FPTAS construction include formulation of a "rounded" problem, development of a dynamic programming algorithm for the latter, determination of appropriate lower and upper bounds, application of a bound improvement procedure. These ideas will be demonstrated on the example of a production planning problem, which is to determine production quantities of the same product over time such that production capacities are satisfied and total production and holding/backlogging costs are minimized. The problem is modelled as a knapsack type problem.

Lundi 6 octobre 2008 à 14h en salle A707

Titre : Algorithmes d'approximation pour minimiser le makespan sur une machine avec contrainte d'indisponibilité

Résumé : Nous nous intéressons au problème d'ordonnancement sur une seule machine avec des dates de début au plus tôt et des durées de latence. De plus, nous considérons que la machine est indisponible pendant une période fixe et connue à l'avance. Notre objectif est de minimiser le makespan (la date de livraison du dernier job). Nous étudions plusieurs cas de ce problème. A chaque cas, nous proposons des algorithmes avec des performances garanties.

Lundi 20 octobre 2008 à 14h en salle A711

Titre : Branch-and-Price-and-Cut pour couvrir par des bicliques

Résumé : Pour les graphes sans triangle, P.C. Fishburn et P.L. Hammer ont montré (1996) que le problème du recouvrement par bicliques se réduit au problème de la coloration dans un graphe au arête. Les algorithmes résolvant le problème de coloration peuvent donc être appliquées directement au recouvrement par bicliques, comme par exemple le Branch-and-Price (génération de colonnes) de Mehrotra et Trick (1995). Nous généraliseront le résultat de Fishburn et Hammer à tous les graphes. Au niveau algorithmique, nous obtenons un Branch-and-Price-and-Cut pour couvrir un graphe quelconque par des bicliques.

Lundi 3 novembre 2008 à 14h en salle A707

Titre : Formulations pour le problème de ramassage et livraison préemptif avec un véhicule

Résumé : Nous considérons le problème de ramassage et livraison (pickup and delivery) avec un véhicule dans lequel le transport de chaque demande peut être interrompu, c'est-à-dire que le véhicule peut temporairement décharger une demande sur un sommet différent de sa destination. Dans un premier temps nous donnons quelques résultats de complexité. Nous montrons en particulier que le problème du circuit Eulérien avec contraintes de précédence induites par des chemins est NP-difficile, sauf si les chemins sont arc-disjoints. En se basant sur ces resultats, nous déterminons tout d'abord l'information minimale nécessaire pour définir une solution du problème en fonction de la capacité du véhicule. Nous présentons ensuite une première formulation linéaire en nombres entiers valide dans le cas où le véhicule ne peut transporter qu'une demande en même temps (version unitaire). Nous étendons par la suite ce modèle dans le cas général. Nous terminons par une présentation de quelques résultats polyédraux pour le premier modèle.

Lundi 17 novembre 2008 à 14h en salle A707

Titre : d-bloqueurs et d-transversaux minimaux dans les graphes

Résumé : Etant donné un graphe G, on définit un d-bloqueur de G comme un ensemble d'arêtes E tel que nu(G-E) <= nu(G) - d (où, pour un graphe H, nu(H) est la cardinalité d'un couplage maximum de H), et un d-transversal de G comme un ensemble d'arêtes ayant au moins d arêtes en commun avec tout couplage maximum de G. On s'intéresse à la recherche de d-bloqueurs et de d-transversaux de taille minimum. Nous montrerons que ces deux problèmes sont NP-difficiles, et présenterons quelques résultats positifs concernant la résolution de ces problèmes dans des cas particuliers. (Travail en collaboration avec Marie-Christine Costa, Dominique de Werra, Christophe Picouleau, Bernard Ries et Rico Zenklusen.)

Lundi 1 décembre 2008 à 14h en salle A707

Titre : Relaxations et décompositions pour la programmation en nombres entiers

Résumé : Les liens entre les méthodes classiques de relaxation (lagrangienne et agrégée) et de décomposition (lagrangienne et de Dantzig-Wolfe (génération de colonnes)) seront rappelés et une nouvelle preuve, utilisant la décomposition de Dantzig-Wolfe, de la dominance de la décomposition lagrangienne sur la relaxation lagrangienne sera présentée. Ces différentes méthodes de relaxation, décomposition, ainsi qu'une convexification, seront ensuite évaluées pour la résolution du problème du sac-à-dos quadratique en variables 0-1 avec contrainte de cardinalité.

Lundi 8 décembre 2008 à 14h en salle A707

Titre : Well-quasi-order par sous graphes induits

Résumé : Robertson et Seymour montrent la conjecture de Wagner dans leur série de papiers des "Graph Minors", qui dit que toutes les classes de graphes fermées par mineurs sont caractérisées par un ensemble fini de mineurs interdits. Il en résulte l'existence d'algorithmes polynomiaux pour reconnaître ces classes. (Ceci peut être vu comme une généralisation du théorème de Kuratowski caractérisant les graphes planaires.) La conjecture de Wagner est en fait équivalente à dire que le pre-ordre "être mineur de" est "Well-quasi-ordered" (WQO) (i.e. pour toute séquence infinie (x_i) d'éléments, il existe i inférieur à j tels que x_i <= x_j). Il existe d'autres relations entre les graphes à explorer vis à vis du WQO. On s'intéresse dans l'exposé à la relation de sous graphe induit. La largeur NLC de Wanke est une généralisation de la largeur arborescente de Robertson et Seymour. On définit une restriction NLC' de la largeur NLC, et on montre que les classes de largeur NLC' bornée sont WQO par sous graphe induit. Il en résulte par exemple que l'on peut reconnaître en temps polynomial les graphes de largeur NLC' au plus k fixé. (Travail en commun avec J. Daligault et S. Thomassé.)