Séminaire d'Optimisation Combinatoire

Lundi 4 février 2013 à 14h15 en salle A707

Title: Packing rectangles in a rectangle

Abstract: We address the problem of packing rectangles into a bigger rectangle, also called the two-dimensional Orthogonal Packing Problem (OPP-2). The goal is to decide whether a set V of rectangles can be packed in a rectangular container C without overlapping and without exceeding the borders of C. In the classical version the rotation of items is not allowed. If the set V can be packed in C then V is called a feasible set. This problem is NP-complete and can be seen as a sub-problem of the two-dimensional Orthogonal Knapsack Problem (each item has an associated profit and the goal is to choose a subset of items maximizing the total profit). In 1997 Fekete and Schepers introduced an interesting characterization of feasible solutions based on interval graphs. Using this characterization they designed an efficient algorithm to solve OPP by enumerating the interval graphs with a certain number of constraints. In this work, we present a new algorithm for solving OPP-2 based on a more compact representation of interval graphs using the so-called MPQ-trees. One of the main advantages is having a reduced number of "symmetrical" solutions. Similar to Fekete and Schepers' approach, our algorithm can be generalized to a multidimensional case. I will finish the talk by showing the comparison with other algorithms from the literature using classical benchmarks. This is a joint work with C. Joncour and A. Pêcher.

Lundi 25 février 2013 à 14h15 en salle A707

Title: Finding a Sparse k-Subgraph in Restricted Graph Classes

Abstract: Given a simple undirected graph and two integers k and C, the Sparsest k-Subgraph problem asks for a set of k vertices inducing at most C edges. As a generalization of the classical Independent Set problem, Sparsest k-Subgraph is NP-hard as well as inapproximable and fixed-parameter intractable in general graphs. In this talk we present new complexity results and open questions in some restricted graph classes, such as subclasses of perfect graphs. In particular we will prove the NP-hardness in chordal graphs, and present a dynamic programming in interval graphs, leading to an FPT algorithm. This is a joint work with Marin Bougeret and Rodolphe Giroudeau.

Lundi 18 mars 2013 à 14h15 en salle A707

Title: On cutting planes for mixed integer linear programming

Abstract: This talk gives an introduction to a recently established link between the geometry of numbers and mixed integer linear optimization. The main focus is to provide a review of families of lattice-free polyhedra and their use in a disjunctive programming approach. The use of lattice-free polyhedra in the context of deriving and explaining cutting planes for mixed integer programs is not only mathematically interesting, but it leads to some fundamental new discoveries, such as an understanding under which conditions cutting planes algorithms converge finitely. These theoretical results suggest the possibility that cutting planes from special families of lattice-free polyhedra could give rise to numerically efficient novel algorithms.

Mardi 19 mars 2013 à 14h15 en salle A301

Title: On Efficient Domination and Efficient Edge Domination Problems in Graphs and Hypergraphs

Abstract: Packing and covering problems in graphs and hypergraphs and their relationships belong to the most fundamental topics in combinatorics and graph algorithms and have a wide spectrum of applications in computer science, operations research and many other fields. Recently, there has been an increasing interest in graph and hypergraph problems combining packing and covering properties, and the NP-complete Exact Cover problem on hypergraphs (asking for a collection of hyperedges covering each vertex exactly once) is a good example for this. Closely related graph problems are the Efficient Domination (ED) and Efficient Edge Domination (EED) problems; the ED problem corresponds to the exact cover problem for the closed neighborhoods of a graph, and the EED problem on a graph G is the ED problem on its line graph L(G). We give a survey on previous results, describe some connections to other problems such as Maximum Weight Independent Set and Minimum Weight Dominating Set, consider some new cases where the problems are efficiently solvable by using structural properties of graph classes and using closure properties under the square operation, and we also extend the graph problems to hypergraphs.

Lundi 25 mars 2013 à 14h15 en salle A707

Title: Approximated Perspective Relaxations: a Project & Lift Approach

Abstract: The Perspective Reformulation (PR) of a Mixed-Integer NonLinear Program with semi-continuous variables is obtained by replacing each term in the (separable) objective function with its convex envelope. Solving the corresponding Perspective Relaxation requires appropriate techniques. Under some rather restrictive assumptions, the Projected PR can be defined where the integer variables are eliminated by projecting the solution set on the space of the continuous variables only. This approach produces a simple piecewise-convex problem with the same structure as the original one; however, this prevents the use of general-purpose solvers, in that some variables are then only implicitly represented in the formulation. We show how to construct an Approximated Projected PR whereby the projected formulation is ``lifted'' back to the original variable space, with the integer variables expressing one piece of the obtained piecewise-convex function; in some cases, this produces a reformulation of the original problem with exactly the same size and structure as the standard continuous relaxation but with a substantially improved bound. While the bound can be weaker than that of the PR, this approach can be applied in many more cases and allows direct use of off-the-shelf MIQP software; this is shown to be beneficial in different applications. In the process we also relax some of the other restrictive assumptions of the original development, such as the need for the objective function to be quadratic and the need for the left endpoint of the domain of the variables to be non-negative.

Mardi 26 mars 2013 à 14h15 en salle A301

Titre : Le sous-graphe k-balancé maximal d'un graphe signé: applications et méthodes de résolution

Résumé : Un graphe signé G = (V,E,s) est dit k-balancé si V peut être partitionné en au plus k ensembles de sorte que chaque arrête positive appartient à l'un de ces ensembles tandis que chaque arrête négatives lie deux ensembles différents. Nous étudions le problème qui consiste à chercher le sous-graphe de G qui soit k-balancé et de cardinalité maximale. Le cas particulier k = 2 (2-MBSP) revient à chercher un sous-graphe balancé de cardinalité maximale. Ce problème a des applications dans la recherche d'une sous-matrice de réseaux de taille maximale. Nous discutons des applications du k-MBSP dans l'analyse de portefeuilles financiers en gestion de risque et dans les structures communautaires. Nous sommes intéressés par la résolution du problème de façon exacte ou heuristiques. Dans le cas du 2-MBSP, nous présentons un algorithme de coupes et branchements efficace et des heuristiques primales. Nous montrons un large ensemble de résultats numériques réalisés sur les applications susmentionnées. Pour le cas général, nous décrivons une formulation en variables 0-1, présentons une description polyédrale partielle ainsi qu'un algorithme de coupes et branchements préliminaire.

Mardi 2 avril 2013 à 15h15 en salle A303

Title: Graph colouring problems and polyhera

Abstract: We consider two graph colouring problems. A classic result states that for a hereditary class of graphs (set of graphs closed under taking induced subgraphs), if for every graph G in the class the chromatic number chi(G) is equal to the size of the largest clique omega(G), then these values are also equal in the complement of every graph in the class. This is proved by first showing the stable set polytope of G is integral. The first question I will discuss was raised by Gyárfás in order to generalize this result: for which functions f is there a function f* such that all hereditary classes of graphs where chi(G) <= f(omega(G)) for every graph G also have chi(H) <= f*(omega(H) for every complement H? And if f* exists, what is the smallest such function? We improve on long standing bounds of Gyárfás on f for the existence of f*. We obtain the exact function f* when f(x)=3 (also improving on earlier bounds of Gyárfás). This is joint work with A. Gyárfás, R. Machado, A. Sebo, S. Thomassé and N. Trotignon. The second problem I will discuss is a conjecture of Steinberg: are all planar graphs with no length 4 and 5 cycles 3-colourable? We introduce a method to automatically search for a proof based (the solutions of) linear programs. We discuss results and challenges of our approach and explore how it extends to other problems. This includes joint work with B. Guenin and ongoing work with M. Rao.

Lundi 8 avril 2013 à 14h en salle A306

Title: The matching structure behind the composition of strips

Abstract: A strip is a triple (G,A,B), where G is a simple, undirected graph and A,B are cliques of G. The composition of strips takes as input a set of strips, and outputs a graph. Chudnovsky and Seymour showed that strips from a suitable family form the building blocks of a wide class of claw-free graphs, meaning that every graph in this class can be expressed as the composition of strips from the family, and conversely a composition of those strips always produces a claw-free graph from this class. One of the reasons why claw-free graphs attracted the interest of many researchers is that they generalize line graphs, thus the Maximum (Weighted) Stable Set problem on claw-free graphs generalizes the maximum (weighted) matching problem. In this talk we show that, in fact, MWSS problems on graphs that are the composition of strips share a common matching-like structure, both from an algorithmic and from a polyhedral point of view. We also address a number of applications of these results, mainly back in the context of claw-free graphs, including decomposition algorithms, extended formulations and a polytime separation routine for the stable set polytope of claw-free graphs, and a fast combinatorial algorithm for the MWSS on claw-free graphs. Joint work with G.Oriolo and G. Stauffer.

Lundi 17 juin 2013 à 14h15 en salle A707

Title: The complexity of signed graph homomorphisms

Abstract: Signed graphs are graphs with signed edges (i.e. positive and negative) with an equivalence relation based on a re-signing operation. They have been used, for example, as a way of extending classical results in graph colouring (in relation with graph minors) or in the theory of flows. Recently, the notion of homomorphisms of signed graphs has been introduced by Bertrand Guenin and further developed by Reza Naserasr, Edita Rollova and Eric Sopena. It naturally extends the notion of homomorphisms for classical graphs to the case of signed graphs. We study the computational complexity of the $H$-signed colouring problem, i.e. the question of deciding whether a given signed graph admits a homomorphism to a fixed signed graph $H$. We settle all cases where $H$ is a cycle, and discuss the restriction where the input graph is planar. We relate these questions to the state of the art for classical graph homomorphisms. This is joint work with Reza Naserasr.

Lundi 1 juillet 2013 à 14h15 en salle A707

Title: Model Checking Lower Bounds for Simple Graphs

Abstract: Courcelle's theorem states that MSO properties can be decided in linear time on bounded treewidth graphs, but the hidden constant is a tower of exponentials. Unfortunately, a well-known result by Frick and Grohe shows that deciding even FO logic on trees (a much more restricted problem) requires such a non-elementary parameter dependence. In this talk we will extend the results of Frick and Grohe to even simpler classes of graphs. In particular, we will show that the non-elementary parameter dependence is still necessary even for uncolored paths, and then discuss some implications of this result. Furthermore, we will show a (d+1)-fold exponential lower bound for the parameter dependence of MSO model checking on colored trees of height d. This matches the recent (d+1)-fold exponential algorithm for this problem recently given by Gajarsky and Hlineny.

Lundi 16 septembre 2013 à 13h45 en salle A711

Title: Structural Parameterizations of Common Induced Subgraph Isomorphism

Abstract: The Maximum Common Induced Subgraph problem (MCIS) takes a pair of graphs as input and asks for a graph of maximum order that is isomorphic to an induced subgraph of each of the input graphs. When parameterized by the solution size, the problem is at least W[1]-hard in general and remains W[1]-hard when parameterized by the treewidth of input graphs. We discuss various parameterizations of MCIS and prove that it is fixed-parameter tractable when parameterized by vertex cover and when restricted to graphs of bounded genus. A number of related open problems are presented.

Lundi 23 septembre 2013 à 14h15 en salle A707

Titre : Une approche basée sur les graphs pour le problème de linéarisation de génome

Résumé : En génomique comparative, le problème de linéarisation consiste à déterminer l'ordre des gènes dans un chromosome à partir d'un ordre partiel (représenté par un graphe orienté acyclique), en utilisant des données disponibles pour des espèces proches. Le plus intéressant consiste à obtenir un ordre total compatible avec l'ordre partiel qui minimise une distance d'évolution donnée avec un génome de référence. Dans le cas de la distance de breakpoints, on cherche à minimiser le nombre de paires de gènes consécutifs dans l'ordre créé et séparés dans le génome de référence. Le problème consistant à construire un ordre total optimal pour cette distance, MBL (pour Minimum Breakpoint Linearization), est NP-complet et APX-difficile, et n'admet aucun algorithme efficace. Dans cet exposé, nous proposons une représentation en graphs de ce problème afin de le réduire à une variante de Feedback Vertex Set. Cette approche nous permet, outre l'utilisation directe d'algorithmes d'approximation ou paramétrés de la littérature, de produire un algorithme d'approximation pour ce problème.

Lundi 7 octobre 2013 à 14h15 en salle A707

Title: Konig's edge-colouring theorem for all graphs

Abstract: We show that the maximum degree of a graph G is equal to the minimum number of ocm sets covering G, where an ocm set is the vertex-disjoint union of elementary odd cycles and one matching, and a collection of ocm sets covers G if every edge is in the matching of an ocm set or in some odd cycle of at least two ocm sets. This min-max relation gives a linear description of the star polytope with a minimal TDI-system. Joint work with V. H. Nguyen from LIP6.

Lundi 14 octobre 2013 à 14h15 en salle A707

Title: Energy-aware scheduling algorithms

Abstract: Due to the increasing need for dealing with the energy consumption in computer systems, new low energy architectures have been developed that support several low power features such as multiple power states of memory banks, bank/row specific activation, and the dynamic voltage scaling of processors. These features force to take appropriate decisions at higher design levels. Thus, new technologies generate new algorithmic questions, as by answering them is likely to have a significant impact in reducing the energy consumption in computer systems. In this context it appeals very interesting to address these problems as scheduling problems, with the objective of minimizing the energy consumption. In this talk, we consider the energy minimization problem of scheduling a set of n jobs on m parallel speed-scalable processors. This model captures the intuitive idea that the faster a processor works the more energy it consumes. We present different algorithmic approaches that lead to optimal or approximate solutions for several machine environments.

Lundi 4 novembre 2013 à 14h15 en salle A707

Titre : Au carrefour polyédral du voyageur et du postier

Résumé : Je vais montrer quelques idées simples et efficaces qui ont conduit à l'amélioration de la garantie d'approximation pour le problème du voyageur commerce avec des métriques de graphe (1.4, résultat 2012 commun avec Jens Vygen), et de la 'version chemin' avec des métriques quelconques (1.6, 2013). Partant du résultat classique de Christofides, les nouvelles méthodes utilisent une combinaison de résultats polyédraux et combinatoires classiques et nouveaux concernant le problème du postier, simplifié par un language de probas élémentaires.

Lundi 18 novembre 2013 à 14h15 en salle A707

Fouad Ben Abdelaziz, NEOMA Business School Rouen

Title: Dominance and efficiency in multicriteria decision under uncertainty

Abstract: We propose several concepts of efficient solutions for multi-criteria decision problems under uncertainty. We show how alternative notions of efficiency may be grounded on different decision ‘contexts’, depending on what is known about the Decision Maker’s (DM) preference structure and probabilistic anticipations. We define efficient sets arising naturally from polar decision contexts. We investigate these sets from the points of view of their relative inclusions and point out some particular subsets which may be especially relevant to some decision situations. We also emphasise relations between some optimization concepts and voting theory.

Lundi 9 decembre 2013 à 14h45 en salle A711

Title: Tight Hardness Results for Exact Algorithms

Abstract: In this talk, we will discuss the Strong Exponential Time Hypothesis (SETH) and its implications for Exact Algorithms. Loosely speaking, the SETH claims that there is no algorithm that can determine the satisfiability of CNF-formulas with n variables with a worst-case running time of O(1.99999^n), that is, SETH claims that the brute-force 2^n-time algorithm has the best possible growth rate (namely 2). Using this assumption, we are able to derive similar tight hardness results for problems such as Hitting Set, and we obtain some evidence for the tight hardness of Set Cover as well. The belief about the validity of SETH is quite divided, and we will raise some open problems and challenges surrounding this topic. The talk is based on the paper from CCC 2012 that has 9 authors.