Equipe Optimisation Combinatoire 
Séminaires 2007 - 2008
- 03 juillet 2008 :
Sulamita Klein
(Rio de Janeiro) : 2K2 vertex-set partition into nonempty parts
A graph is 2K2-partitionable if its vertex set can be partitioned into four nonempty parts A, B, C, D such that each vertex of A is adjacent to each vertex of B, and each vertex of C is adjacent to each vertex of D. Determining whether an arbitrary graph is 2K2-partitionable is the only vertex-set partition problem into four nonempty parts according to external constraints whose computational complexity is open. We show that for C4-free graphs, circular-arc graphs, spiders, P4-sparse graphs, and bipartite graphs the 2K2 partition problem can be solved in polynomial time.
- 18 mars 2008 :
Michele Conforti
(Padoue) : Simple mixed integer sets
An Integer Program is Mixed whenever some of the variables are allowed to be continuous. MIP's arise e.g. in Production Planning, when some integer variables model decisions (in which period to produce) and some continuous variables model production levels.
As in (pure) IP, it is important to represent the set of feasible solutions as vertices of a polyhedron, described by linear inequalities. However, in the mixed case, this seem to be quite challenging and some of the tools that have been used are different from the ones that have been so successful, for instance, in polyhedral combinatorics.
We will survey some results in this area obtained jointly with M. DiSumma, F. Eisenbrand, B. Gerards, L. Wolsey and G. Zambelli.
- 04 février 2008 :
Vincent Jost
(Ecole Polytechnique) : Relaxation Lagrangienne pour la combinatoire.
La relaxation Lagrangienne permet de donner un cadre conceptuel théorique simple pour quelques techniques classiques utilisées autour de la programmation linéaire en nombres entier.
J'expliquerai en détail la définition et la versatilité de la relaxation lagrangienne. J'insisterai sur le fait que la relaxation lagrangienne n'a pas une nature algorithmique, et qu'elle nécessite l'emploi d'un algorithme de minimisation de fonction convexe pour être utilisée numériquement.
Je montrerai le lien entre relaxation lagrangienne et génération de colonne et des pistes étudiées pour améliorer cette dernière dans le cadre de l'analyse convexe.
Je montrerai que certaines relaxations semi-définies positives (SDP) peuvent être décrites par la relaxation lagrangienne de contraintes quadratiques (exprimant la nature booléenne de variables par l'équation x*(x-1) = 0).
- 06 décembre 2007 :
Olivier Briant
(Grenoble) : An Heuristic Solution Method of a Quadratical Model of Aircraft
Rotation Problem Based on Dantzig-Wolfe Decomposition.
Each aircraft of an airlines company has to undergo maintenance checks at the end of a certain amount of flight hours to ensure the security conditions. An aircraft which undergoes a maintenance check before the end of the legal remaining flight time, looses its flight potential. As a consequence of this fact, over maintained aircrafts cost very expensive to the airlines company. Given a flight schedule for a specific aircraft fleet, our objective is to maximize the aircraft utilization and to smooth the flight load. We propose, a mixed integer programming model with quadratic objective function, for a one week aircraft rotation problem and give its Dantzig-Wolfe decomposition. The master problem assigns the flight strings to the aircrafts and insures covering of all the flights, and the sub-problems find the optimum flight string for each aircraft. As there are two different objectives, there are also two different sub-problems : one for maximization of aircraft utilization and one for minimization of the difference between aircraft utilization and aircraft mean-load. Both sub-problems are known to be NP-hard and solved by a dynamic program.
Finally we propose an heuristic method which exploits the dual values calculated by simplex. Our column generation based heuristic method gives either a feasible solution or a solution with minimum arc violation.
- 29 novembre 2007 : Mikhail Y.
Kovalyov
(Minsk) : Multi-Product Lot-sizing and Sequencing on an Imperfect Single
Machine.
A problem of lot-sizing and sequencing several discrete products on a single machine will be considered. A sequence dependent setup time is required between lots of different products. The machine is imperfect in the sense that it can produce defective items, and furthermore, it can break down. The number of defective items of each product is given as an integer valued non-decreasing function of the total number of produced items of this product, and the total machine breakdown time is given as a real valued non-decreasing function of the manufactured quantities of all products. Two problem settings are considered. In the first setting, the objective is to minimize the completion time of the last item, provided that all the product demands for good quality items are satisfied. In the second setting, the objective is to minimize the total cost of demand dissatisfaction, subject to satisfying a given upper bound on the completion time of the last item. Properties of optimal solutions, NP-hardness proofs for general cases, and polynomial exact and approximation algorithms for the case, in which the number of defective items is given by rounding down a linear function of the number of produced items, will be discussed. The latter case is known as the "fraction defective" case in the quality control literature.
- 29 novembre 2007 : Anton Eremeev
(Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch of Russian
Academy of Sciences) : The Supply Management Problem: A Survey of Results.
This talk contains a survey of theoretical and experimental results obtained for a number of modifications of the supply management problem. The problem consists in optimization of product delivery from a set of suppliers to a set of customers minimizing the total cost, given the admissible intervals for the shipment sizes, so that the demands of the customers are satisfied. The modifications of this problem differ in the assumptions concerning the delivery cost functions (linearity, concavity, continuity), in admission or violation for a delivery to exceed the demand and in the number of admissible intervals a supplier may have. The problem complexity and provable performance guarantees of exact and approximation algorithms for the case of single customer will be discussed. Two hybrid genetic heuristics for the case of multiple customers will be briefly described and the results of experiments with these heuristics and CPLEX branch-and-cut solver will be presented.
- 22 novembre 2007 : Myriam Preissmann
(G-SCOP, Grenoble) : Maximum directed cuts in digraphs with degree
restriction
For integers m, k ≥ 1, we investigate the maximum size of a directed cut in directed graphs in which there are m edges and each vertex has either indegree at most k or outdegree at most k.
Reference : Jenö Lehel, Frédéric Maffray, Myriam Preissmann, "Maximum directed cuts in digraphs with degree restriction", Cahier Leibniz-IMAG, n° 158, décembre 2006.
- 15 novembre 2007 : Gennady Shmonin
(Grenoble) : Parametric Integer Programming in Fixed Dimension
An integer programming problem is stated as follows: Given a system of linear inequalities A x <= b, find an integral vector x satisfying all the inequalities, or assert that no such vector exists. Lenstra (1983) showed that if the number of variables is fixed, the problem is solvable in polyomial time. Kannan (1990) and Kannan (1992) considered a generalization of this problem, in which the right-hand side b of the inequalities is allowed to vary over some given polyhedron Q, and the question to decide is: Is there a right-hand side b in Q such that the system A x <= b has no integral solution? This is indeed a generalization, since the input polyhedron Q of the right-hand sides can be chosen to contain a single vector only. Kannan established an algorithm to solve this problem that runs in polynomial time if the number of variables x, as well as the affine dimension of Q, is fixed.
The main purpose of the talk is to describe an algorithm for solving the problem in polynomial time, assuming only the number of variables x to be fixed. The general framework is very similar to that of Kannan, while the latter can be viewed as a generalisation of Lenstra's algorithm. Due to this relations, we give some brief (and incomplete) description of Lenstra's algorithm, too.
Reference: F. Eisenbrand and G. Shmonin, "Integer Points in a Parameterised Polyhedron" (currently, being extensively revised)
http://www.optimization-online.org/DB_HTML/2007/04/1651.html
- 08 novembre 2007 : Eric Tannier
(INRIA, Grenoble) : Reconstitution de scénarios évolutifs et contraintes de
parcimonie
L'organisation d'un génome peut être modélisée par une permutation signée, et une mutation dans cette organisation par une transformation sur les permutations. Transformer une permutation en une autre en utilisant un nombre minimum de mutations est l'énoncé général du problème des réarrangements génomiques. Mais les scénarios issus des solutions optimales ne respectent pas toujours un principe de conservation qui voudrait que si plusieurs permutations ont un segment qui contient les mêmes éléments, alors ces éléments ne sont probablement pas séparés au cours de l'évolution. Dans ce séminaire, je développerai quelques principes algorithmiques qui permettent de construire des scénarios qui respectent cette contrainte de conservation.
- 29 octobre 2007 : Bertrand Guenin
(Université de Waterloo) : Les cycles impairs dans les graphes.
Un résultat classique de Whitney caractérise lorsque deux graphes ont la même famille de cycles (ou les cycles sont interprétés comme des ensembles d'arètes). Ce théorème dit que deux graphes ont les mêmes cycles si l'on peut obtenir un graphe à partir de l'autre en réarrangeant le graphe sur des coupes qui consistent en un ou deux sommets. Nous sommes intéressés à caractériser quand est ce que deux graphes ont le même ensemble de cycles pair (un cycle est pair si il contient un nombre pair d'arètes). Nous présentons un théorème du type de Whitney pour le cas où les graphes ont une connectivité élevée et pour le cas ou les graphes ont suffisamment de circuits impairs disjoints.
- 18 octobre 2007 : Satoru Iwata
(Kyoto) : Algorithms for Orientations and Detachments of Graphs.
This talk presents two efficient algorithms concerning orientations and detachments of graphs. Both algorithms are closely related to the works of C.~St.~J.~A.~Nash-Williams.
Given a 2k-edge-connected undirected graph, we consider to find a minimum cost orientation that yields a k-arc-connected directed graph. This minimum cost k-arc-connected orientation problem is a special case of the submodular flow problem. Frank (1982) devised a combinatorial algorithm that solves the problem in O(k2n3m) time, where n and m are the numbers of vertices and edges, respectively. Gabow (1995) improved Frank's algorithm to run in O(kn2m) time by introducing a new sophisticated data structure. We describe an algorithm that runs in O(k3n3 + kn2m) time without using sophisticated data structures. In addition, we present an application of the algorithm to find a shortest dijoin in O(n2m) time, which matches the current best bound. This is a joint work with Yusuke Kobayashi.
We also investigate a necessary and sufficient condition for a graph to have an orientation that has k edge-disjoint arborescences rooted at a fixed vertex s subject to lower and upper bounds on the indegree at each vertex. The result is used to derive a characterization of graphs having a detachment that contains k edge-disjoint spanning trees. The proof yields an efficient algorithms for finding those orientations and detachments. In particular, we present an algorithm for finding a connected (loopless) detachment in O(nm) time, where n and m denote the numbers of vertices and edges, respectively. This is a joint work with Tibor Jordan.
- 12 octobre 2007 : Kristine Vuskovic
(Leeds) : The use of decomposition in the study of even-hole-free graphs.
We consider finite and simple graphs. We say that a graph G contains a graph X, if X is isomorphic to an induced subgraph of G. A graph G is X-free if it does not contain X. Let F be a (possibly infinite) family of graphs. A graph G is F-free if it is X-free, for every X in F.
Many interesting classes of graphs can be characterized as being F-free for some family F. Most famous such example is the class of perfect graphs. A graph G is perfect if for every induced subgraph H of G, chi (H) = omega (H), where chi (H) denotes the chromatic number of H and omega (H) denotes the size of a largest clique in H. The famous Strong Perfect Graph Theorem states that a graph is perfect if and only if it does not contain an odd hole nor an odd antihole (where a hole is a chordless cycle of length at least four). In the last 15 years a number of other classes of graphs defined by excluding a family of induced subgraphs have been studied, perhaps originally motivated by the study of perfect graphs. The kinds of questions this line of research was focused on were whether excluding induced subgraphs affects the global structure of the particular class in a way that can be exploited for putting bounds on parameters such as chi and omega, constructing optimization algorithms (problems such as finding the size of a largest clique or a minimum coloring), recognition algorithms and explicit construction of all graphs belonging to the particular class. A number of these questions were answered by obtaining a structural characterization of a class through their decomposition (as was the case with the proof of the Strong Perfect Graph Theorem).
In this talk we survey some of the most reacent uses of the decomposition theory in the study of classes of even-hole-free graphs. Even-hole-free graphs are related to beta-perfect graphs in a similar way in which odd-hole-free graphs are related to perfect graphs. beta-Perfect graphs are a particular class of graphs that can be polynomialy colored, by coloring greedily on a particular, easily constructable, ordering of vertices.