Optimisation combinatoire

Un problème d’optimisation combinatoire consiste à trouver la meilleure solution dans un ensemble discret de solutions appelé ensemble des solutions réalisables. En général, cet ensemble est fini mais de cardinalité très grande et il est décrit de manière implicite, c’est-à-dire par une liste de contraintes que doivent satisfaire les solutions réalisables. Pour définir la notion de meilleure solution, une fonction, dite fonction objectif, est introduite. Pour chaque solution, elle renvoie un réel, et la meilleure solution ou solution optimale est celle qui minimise ou maximise la fonction objectif. L’optimisation combinatoire s’applique ainsi à l’optimisation de l’architecture et du fonctionnement des systèmes de production, à l’optimisation des choix techniques ou technico-économiques concernant les produits (coûts, performances, fiabilité) et de façon générale, à l’optimisation des décisions prises dans l’Entreprise.

Les recherches de l’équipe OC se répartissent sur deux axes : Programmation mathématique et applications et Graphes et optimisation.

Axe « Programmation mathématique et applications »

Cet axe concerne essentiellement l’optimisation discrète (linéaire et non linéaire). Cette modélisation, extrêmement générale, permet de formuler de très nombreux problèmes d’optimisation combinatoire. Ces problèmes sont généralement difficiles et, dans beaucoup de cas, les problèmes de grande taille ne peuvent actuellement être résolus. Les travaux de l’équipe visent à une meilleure compréhension de ces problèmes dans le but d’améliorer leur résolution. Nous nous sommes également beaucoup intéressés à la résolution de problèmes d’optimisation industriels dans différents domaines : télécommunications, transports, énergies, environnement. Nous développons également des travaux concernant la recherche de solutions optimales robustes. Il est en effet souvent plus pertinent dans les applications industrielles de considérer une solution « robuste » qui se comportera bien dans toutes les situations susceptibles de se produire plutôt qu’une solution « optimale » pour une situation précise. L’équipe OC a déjà initié des travaux sur ce thème et la robustesse est source de très nombreuses problématiques.

Axe « Graphes et optimisation »

Les graphes constituent un outil mathématique fondamental de la Recherche Opérationnelle. Ils permettent la modélisation de systèmes extrêmement variés. L’obtention de solutions aux problèmes posés consiste généralement en la détection de structures optimales. De par la taille des problèmes posés la seule « puissance » des ordinateurs n’est pas suffisante pour mener à bien les calculs permettant d’obtenir une solution. Pour essayer de mener à bien cette résolution il est nécessaire de dégager des propriétés structurelles des solutions optimales pour développer, lorsque cela est possible, des algorithmes capables d’effectuer les calculs aboutissant à la résolution exacte ou approchée du problème considéré. L’axe Graphes et Optimisation a pour objectif de suivre cette démarche pour certains problèmes de graphes suffisamment généraux pour modéliser de nombreuses situations concrètes. Des travaux ont également été menés sur l’approximation polynomiale, les algorithmes paramétrés, et l’algorithmique online.

Publications

2020

Articles de revue

  1. Costa, M.-C.; de Werra, D. and Picouleau, C. Minimal graphs for 2-factor extension. In Discrete Applied Mathematics, 2020. doi  www 
  1. Bentz, C. and Le Bodic, P. Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth. In Theoretical Computer Science, 809: 239-249, 2020. doi  www 
  1. Picouleau, C. Minimal graphs for hamiltonian extension. In Open Journal of Discrete Applied Mathematics, 2020. doi  www 
  1. Porumbel, D. C. Projective Cutting-Planes. In SIAM Journal on Optimization, 30 (1): 1007-1032, 2020. doi  www 
  1. Quezada, F.; Gicquel, C.; Kedad-Sidhoum, S. and Vu, D. Q. A multi-stage stochastic integer programming approach for a multi-echelon lot-sizing problem with returns and lost sales. In Computers and Operations Research, 116: 104865, 2020. doi  www 

Articles de conférence

  1. Bentz, C.; Costa, M-C.; Poirion, P-L.; Ridremont, T. and Zakhour, C. Optimisation robuste du câblage d'un parc éolien sous contraintes de load flow. In ROADEF 2019, Montpellier, France, 2020. www 
  1. Falq, A-E.; Fouilhoux, P. and Kedad-Sidhoum, S. Linear inequalities for neighborhood based dominance properties for the common due-date scheduling problem. In 21ème congrès annuel de la Société franc caise de recherche opérationnelle et d'aide `a la décision (ROADEF 2020), Montpellier, France, 2020. www 

Non publié

  1. Elloumi, S.; Lambert, A. and Lazare, A. Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation. , working paper or preprint. www 
  1. Bouquet, V.; Delbot, F. c.; Picouleau, C. and Rovedakis, S. On Minimum Dominating Sets in cubic and (claw,H)-free graphs. , working paper or preprint. www 
  1. Ridremont, T.; Watel, D.; Poirion, P-L. and Picouleau, C. Adaptive network flow with $k$-Arc Destruction. , working paper or preprint. www 
  1. Bouquet, V. and Picouleau, C. The Minimum Dominating Set problem is polynomial for (claw, P8)-free graphs. , working paper or preprint. www 
  1. Bouquet, V.; Delbot, F. c. and Picouleau, C. On the vertices belonging to all, some, none minimum dominating set. , 11 figures. www 

2019

Articles de revue

  1. Paulusma, D.; Picouleau, C. and Ries, B. Critical vertices and edges in H-free graphs. In Discrete Applied Mathematics, 257: 361-367, 2019. doi  www 
  1. Bentz, C. Weighted and locally bounded list-colorings in split graphs, cographs, and partial k-trees. In Theoretical Computer Science, 782: 11-29, 2019. doi  www 
  1. Hertz, A. and Picouleau, C. On graceful difference labelings of disjoint unions of circuits. In Open Journal of Discrete Applied Mathematics, 2 (3): 38-55, 2019. doi  www 
  1. Bentz, C. An FPT Algorithm for Planar Multicuts with Sources and Sinks on the Outer Face. In Algorithmica, 81 (1): 224-237, 2019. doi  www 
  1. Elloumi, S. and Lambert, A. Global solution of non-convex quadratically constrained quadratic programs. In Optimization Methods and Software, 34 (1): 98-114, 2019. doi  www 
  1. Elloumi, S.; Hudry, O.; Marie, E.; Martin, A.; Plateau, A. and Rovedakis, S. Optimization of wireless sensor networks deployment with coverage and connectivity constraints. In Annals of Operations Research: 1-24, 2019. doi  www 
  1. B"ulb"ul, K.; Kedad-Sidhoum, S. and c Sen, H. Single-machine common due date total earliness/tardiness scheduling with machine unavailability. In Journal of Scheduling, 22 (5): 543-565, 2019. doi  www 

Articles de conférence

  1. Elloumi, S.; Lambert, A. and Lazare, A. Quadratisation et reformulation convexe pour les polyn^omes de variables binaires. In ROADEF 2019, Le Havre, France, 2019. www 
  1. Houdayer, A.; Plateau, A. and SOUTIL, E. Planification des courses de galop. In ROADEF2019. 20ème congrès annuel de la société Franc caise de Recherche Opérationnelle et d'Aide `a la Décision, Le Havre, France, 2019. www 
  1. Silva, I. F.; Bentz, C.; Bouhtou, M.; Chardy, M. and Kedad-Sidhoum, S. Optimizing Battery Usage for a Telecommunications Company Participating in a Curtailing Market. In PGMODays 2019, Paris, France, 2019. www 
  1. Falq, A-E.; Fouilhoux, P. and Kedad-Sidhoum, S. MIP formulations for just-in-time scheduling around a common due-date. In 14th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2019), Renesse, Netherlands, 2019. www 
  1. Ethève, M.; Alès, Z.; Bissuel, C.; Juan, O. and Kedad-Sidhoum, S. A Graph-based Heuristic for Variable Selection in Mixed Integer Linear Programming. In PGMO Days, Paris, France, 2019. www 
  1. Elloumi, S.; Lambert, A. and Lazare, A. Semidefinite programming relaxations through quadratic reformulation for box-constrained polynomial optimization problems. In 2019 6th International Conference on Control, Decision and Information Technologies (CoDIT), pages 1498-1503, IEEE, Paris, France, 2019. doi  www 
  1. Absi, N.; Artigues, C.; Kedad-Sidhoum, S.; Ngueveu, S. U. and Goupil, F. Bornes pour un problème d'ordonnancement avec allocation et stockage d'énergie et co^uts linéaires par morceaux. In 20ème congrès annuel de la société Franc caise de Recherche Opérationnelle et d'Aide `a la Décision (ROADEF 2019), Le Havre, France, 2019. www 
  1. Charles, M.; Dauzère-Pérès, S. and Kedad-Sidhoum, S. More realistic test instances for the Capacitated Lot-Sizing Problem. In 30th European Conference On Oparational Research, EURO2019, Dublin, Ireland, 2019. www 
  1. Silva, I. F.; Bentz, C.; Bouhtou, M.; Chardy, M. and Kedad-Sidhoum, S. Energy storage management with energy curtailing incentives in a telecommunications context. In 10th International Workshop on Lot sizing - IWLS 2019, Paris, France, 2019. www 
  1. Godard, H.; Elloumi, S.; Lambert, A.; Maeght, J. and Ruiz, M. Novel Approach Towards Global Optimality of Optimal Power Flow Using Quadratic Convex Optimization. In 6th International Conference on Control, Decision and Information Technologies (CoDIT), Paris, France, 2019. doi  www 
  1. Lucas, R.; Alès, Z.; Ramond, F. c. and Elloumi, S. Reducing the Adaptation Costs of a Rolling Stock Schedule with Adaptive Solution: the Case of Demand Changes. In RailNorrk"oping 2019. 8th International Conference on Railway Operations Modelling and Analysis (ICROMA), pages 857-876, Norrk"oping, Sweden, Link"oping Electronic Conference Proceedings 69, 2019. www 
  1. Lambert, A.; Elloumi, S.; Godard, H.; Maeght, J. and Ruiz, M. Solving Alternative Current Optimal Power Flow to Global Optimality with Quadratic Reformulation Using Semi-Definite Programming and Branch-and-Bound. In PGMO days, Palaiseau, France, 2019. www 
  1. Lambert, A.; Elloumi, S.; Lazare, A. and Rodriguez-heck, e. The Impact of Quadratization in Convexification-Based Resolution of Polynomial Binary Optimization. In PGMO days, Palaiseau, France, 2019. www 
  1. Falq, A-E.; Fouilhoux, P. and Kedad-Sidhoum, S. Inégalités linéaires de dominance pour l'ordonnancement juste-`a-temps avec date d'échéance commune non restrictive. In JPOC11 : Journées Polyèdres et Optimisation Combinatoire, Metz, France, 2019. www 
  1. Quezada, F.; Gicquel, C. and Kedad-Sidhoum, S. A Stochastic Dual Dynamic Integer Programming for the Uncapacitated Lot-Sizing Problem with Uncertain Demand and Costs. In 29th International Conference on Automated Planning and Scheduling ICAPS2019, pages 353-361, AAAI Press, Berkeley, United States, 2019. www 
  1. Quezada, F.; Gicquel, C. and Kedad-Sidhoum, S. Stochastic dual dynamic integer programming for a multi-echelon lot-sizing problem with remanufacturing and lost sales. In IEEE International Conference on Control, Decision and Information Technologies CODIT 2019, pages 1254-1259, IEEE, Paris, France, 2019. doi  www 
  1. Quezada, F.; Gicquel, C. and Kedad-Sidhoum, S. Stochastic lot-sizing problem with remanufacturing: a dual dynamic decomposition approach. In PGMO Days, Paris, France, 2019. www 
  1. Quezada, F.; Gicquel, C. and Kedad-Sidhoum, S. A dynamic programming based decomposition approach for the stochastic uncapacitated single-item lot-sizing problem. In 10th International Workshop on Lot sizing - IWLS 2019, pages 73-77, Paris, France, 2019. www 
  1. Quezada, F.; Gicquel, C. and Kedad-Sidhoum, S. Stochastic uncapacitated single-item lot-sizing problem: a dual dynamic decomposition approach. In Congrès de la société franc caise de Recherche Opérationnelle et d'Aide `a la décision ROADEF2019, Le Havre, France, 2019. www 
  1. Charles, M.; Dauzère-Pérès, S.; Kedad-Sidhoum, S. and Mazhoud, I. Parallelized approaches to solve the capacitated lot-sizing problem with lost sales and setup times. In 10th International Workshop on Lot sizing - IWLS 2019, Paris, France, 2019. www 

Non publié

  1. Falq, A-E.; Fouilhoux, P. and Kedad-Sidhoum, S. Mixed integer formulations using natural variables for single machine scheduling around a common due date. , 34 pages, 10 figures. www 
  1. Bucarey, V.; Elloumi, S.; Labbé, M. and Plein, F. Models and Algorithms for the Product Pricing with Single-Minded Customers Requesting Bundles. , working paper or preprint. www 

2018

Articles de revue

  1. Costa, M-C.; de Werra, D. and Picouleau, C. Minimal graphs for matching extension. In Discrete Applied Mathematics, 234: 47-55, 2018. doi  www 
  1. Phouratsamay, S-L.; Kedad-Sidhoum, S. and Pascual, F. Two-level lot-sizing with inventory bounds. In Discrete Optimization, 2018. doi  www 
  1. Porumbel, D. C. From the separation to the intersection sub-problem in Benders decomposition models with prohibitively-many constraints. In Discrete Optimization, 29: 148-173, 2018. doi  www 
  1. Watel, D. and Faye, A. Taxi-Sharing: Parameterized Complexity and Approximability of the Dial-a-ride problem with money as an incentive. In Theoretical Computer Science, 745: 202-223, 2018. doi  www 
  1. Diner, ". Y. s.; Paulusma, D.; Picouleau, C. and Ries, B. Contraction and deletion blockers for perfect graphs and H-free graphs. In Theoretical Computer Science, 746: 49-72, 2018. doi  www 
  1. Kedad-Sidhoum, S.; Monna, F.; Mounié, G. and Trystram, D. A Family of Scheduling Algorithms for Hybrid Parallel Platforms. In International Journal of Foundations of Computer Science, 29 (1): 63-90, 2018. doi  www 
  1. Artigues, C.; Bourreau, E.; Jost, V.; Kedad-Sidhoum, S. and Ramond, F. c. Trains do not vanish: the ROADEF/EURO challenge 2014. In Annals of Operations Research, 271 (2): 1091-1105, 2018. doi  www 
  1. Helal, N.; Pichon, F.; Porumbel, D. C.; Mercier, D. and Lefevre, E. The capacitated vehicle routing problem with evidential demands. In International Journal of Approximate Reasoning, 95: 124-151, 2018. doi  www 
  1. Bendotti, P.; Fouilhoux, P. and Kedad-Sidhoum, S. The Unit-capacity Constrained Permutation Problem. In European Journal of Operational Research, 268 (2): 463-472, 2018. doi  www 
  1. Porumbel, D. C. Prize-collecting set multicovering with submodular pricing. In International Transactions in Operational Research, 25 (4): 1221-1239, 2018. doi  www 
  1. Billionnet, A. Quantifying extinction probabilities of endangered species for phylogenetic conservation prioritization may not be as sensitive as might be feared. In Biodiversity and Conservation, 27 (5): 1189-1200, 2018. doi  www 
  1. Billionnet, A. Phylogenetic conservation prioritization with uncertainty. In Biodiversity and Conservation, 27 (12): 3137-3153, 2018. doi  www 
  1. Bentz, C.; Costa, M-C.; Poirion, P-L. and Ridremont, T. Formulations for designing robust networks. An application to wind power collection. In Electronic Notes in Discrete Mathematics, 64: 365-374, 2018. doi  www 

Chapitres d'ouvrage

  1. Alès, Z. and Elloumi, S. Compact MILP formulations for the p-center problem. In Combinatorial Optimization, pages 14-25, Springer, Cham, Lecture Notes in Computer Science 10856, 2018. doi  www 

Articles de conférence

  1. Lambert, A.; Elloumi, S. and Lazare, A. Résolution du problème de suites binaires avec faible autocorrélation `a l'aide d'une reformulation quadratique convexe. In ROADEF 2018, Lorient, France, 2018. www 
  1. Bentz, C.; Costa, M-C. and Hertz, A. Minimum length disjoint paths and Capacitated (rooted) Steiner Tree. In Euro-Alio International Conference on Applied Combinatorial Optimization Aims and Objectives, Bologna, Italy, 2018. www 
  1. Dauzère-Pérès, S.; Absi, N.; Kedad-Sidhoum, S.; Penz, B. and Rapine, C. The single-item green lot-sizing problem with fixed carbon emissions. In European Conference on Operational Reasearch, Valencia, Spain, 2018. www 
  1. Kedad-Sidhoum, S. Problèmes de lot-sizing: résultats fondamentaux et applications émergentes. In ROADEF2018, Lorient, France, 2018. www 
  1. Costa, M-C.; De Werra, D and Picouleau, C. Extenseurs hamiltoniens minimaux. In ROADEF, Lorient, France, 2018. www 
  1. Falq, A-E.; Fouilhoux, P. and Kedad-Sidhoum, S. Formulations PLNE et dominances pour l'ordonnancement juste-`a-temps avec date d'échéance commune. In ROADEF - 19ème congrès annuel de la Société franc caise de recherche opérationnelle et d'aide `a la décision, Lorient, France, 2018. www 
  1. Lambert, A. Valid inequalities for QCQPs. In ISMP 18, Bordeaux, France, 2018. www 
  1. Lambert, A.; Elloumi, S.; Godard, H.; Maeght, J. and Ruiz, M. Solve Alternative Current Optimal Power Flow to global optimality. In ISMP 18, bordeaux, France, 2018. www 
  1. Ngueveu, S. U.; Absi, N.; Artigues, C.; Kedad-Sidhoum, S. and Goupil, F. Decomposition method in a scheduling problem with energy storage and costs. In International Symposium on Mathematical Programming - ISMP 2018, Bordeaux, France, 2018. www 
  1. Absi, N.; Artigues, C.; Kedad-Sidhoum, S.; Ngueveu, S. U. and Goupil, F. Upper and lower bounds for an energy scheduling problem with piecewise-linear costs and storageresources. In PGMO Days, Paris, France, 2018. www 
  1. Absi, N.; Artigues, C.; Kedad-Sidhoum, S.; Ngueveu, S. U.; Rannou, J. and Saadi, O. Scheduling energy-consuming jobs on parallel machines with piecewise-linear costs and storage resources: A lot-sizing and scheduling perspective. In 16th International Conference on Project Management and Scheduling - PMS 2018, pages 1-4, TexMat, Rome, Italy, 2018. www 
  1. Falq, A-E.; Fouilhoux, P. and Kedad-Sidhoum, S. MIP Formulations for Just-in-Time Scheduling with Common Due-Date. In International Symposium on Combinatorial Optimization (ISCO 2018), Marrakesh, Morocco, 2018. www 
  1. Falq, A-E.; Fouilhoux, P. and Kedad-Sidhoum, S. Extreme points for scheduling around a common due date. In ISMP International Conference on Mathematical Programming (ISMP 2018), Bordeaux, France, 2018. www 
  1. Lambert, A.; Elloumi, S. and Lazare, A. Unconstrained 0-1 polynomial optimization through convex quadratic reformulation. In ISMP 18, Bordeaux, France, 2018. www 
  1. Quezada, F.; Gicquel, C. and Kedad-Sidhoum, S. Stochastic lot-sizing for remanufacturing planning with lost sales and returns. In IWLS 2018 - 9th International Workshop on Lot sizing, Ubatuba, Brazil, 2018. www 
  1. Quezada, F.; Gicquel, C. and Kedad-Sidhoum, S. Lot-sizing for remanufacturing under uncertainty: a stochastic multi-stage mixed-integer programming approach. In ROADEF 2018 - 19e congrès de la société franc caise de Recherche Opérationnelle et d'Aide `a la Décision, Lorient, France, 2018. www 
  1. Quezada, F.; Gicquel, C. and Kedad-Sidhoum, S. Valid inequalities for solving a stochastic lot-sizing problem with returns. In 23rs Symposium on Mathematical Programming - ISMP 2018, Bordeaux, France, 2018. www 
  1. Absi, N.; Artigues, C.; Kedad-Sidhoum, S.; Ngueveu, S. U.; Rannou, J. and Saadi, O. Ordonnancement sous contraintes d'énergie avec stockage et couts linéaires par morceaux. In ROADEF 2018 - 19e congrès de la société franc caise de Recherche Opérationnelle et d'Aide `a la Décision, Lorient, France, 2018. www 

Non publié

  1. Bentz, C.; Costa, M-C.; Poirion, P-L. and Ridremont, T. Robust capacitated trees and networks with uniform demands *. , working paper or preprint. www 

2017

Articles de revue

  1. Billionnet, A.; Elloumi, S.; Lambert, A. and Wiegele, A. Using a Conic Bundle Method to Accelerate Both Phases of a Quadratic Convex Reformulation. In INFORMS Journal on Computing, 29 (2): 318-331, 2017. doi  www 
  1. Porumbel, D. C.; Goncalves, G.; Allaoui, H. and Hsu, T. Iterated Local Search and Column Generation to solve Arc-Routing as a permutation set-covering problem. In European Journal of Operational Research, 256 (2): 349-367, 2017. doi  www 

Livres

  1. Delacroix, J.; Barthélemy, F. c.; Fournier, R.; Gil-Michalon, I.; Lambert, A.; Plateau, A.; Rovedakis, S.; Simonot, M.; Thion, V. and Waymel, E. Informatique. Dunod, Fluoresciences , 2017. www 

Articles de conférence

  1. Godard, H.; Elloumi, S.; Lambert, A.; Maeght, J. and Ruiz, M. Reformulation Quadratique Convexe Pour l'Optimisation des Flux de Puissance. In ROADEF 17, Metz, France, 2017. www 
  1. D'Ambrosio, C.; Elloumi, S.; Lambert, A. and Lazare, A. Global solution of unconstrained binary polynomial optimization problems. In ROADEF 17, Metz, France, 2017. www 
  1. Elloumi, S.; Lambert, A. and Lazare, A. Global optimisation of binary polynomial programs. In PGMO Days, Palaiseau, France, 2017. www 
  1. Elloumi, S.; Godard, H.; Lambert, A.; Maeght, J. and Ruiz, M. Solving Optimal Power Flow through reformulation. In 15th EUROPT Workshop on Advances in Continuous Optimization, montréal, Canada, 2017. www 
  1. Lambert, A. and Elloumi, S. Quadratic convex reformulation for partitioning problems. In EUROPT 17, Montreal, Canada, 2017. www 
  1. Cotté, G.; Costa, M-C. and Picouleau, C. d-extensibles de stables dans les graphes bipartis. In ROADEF2017. 18ème congrès annuel de la Société Franc caise de Recherche Opérationnelle et d'Aide `a la Décision, Metz, France, 2017. www 
  1. Gladkikh, E.; Lambert, A.; Faye, A.; Watel, D. and Costa, M-C. Optimisation du maillage électrique du parc éoliennes off-shore -- projet Stationis. In ROADEF 17, Metz, France, 2017. www 

Divers

  1. Costa, M-C. Entretien avec... , Entretien personnel invité sur la recherche opérationnelle. www 
  1. Billionnet, A. Puzzle Game about Connectivity and Biological Corridors. , Biodiversity puzzle game. www 

Non publié

  1. Bentz, C.; Costa, M-C. and Hertz, A. On the edge capacitated Steiner tree problem. , working paper or preprint. www 

2016

Articles de revue

  1. Watel, D.; Weisser, M-A.; Bentz, C. and Barth, D. Directed Steiner trees with diffusion costs. In Journal of Combinatorial Optimization, 32 (4): 1089-1106, 2016. doi  www 
  1. Billionnet, A.; Costa, M-C. and Poirion, P-L. Robust optimal sizing of a hybrid energy stand-alone system. In European Journal of Operational Research, 254: 565-575, 2016. doi  www 
  1. Porumbel, D. C. Ray projection for optimizing polytopes with prohibitively many constraints in set-covering column generation. In Mathematical Programming, 155 (1-2): 147-197, 2016. doi  www 

Articles de conférence

  1. Elloumi, S. and Lambert, A. Reformulation quadratique convexe du problème d'affectation quadratique. In ROADEF 2016, Compiègne, France, 2016. www 
  1. Elloumi, S. and Lambert, A. Comparison of Quadratic Convex Reformulations to Solve the Quadratic Assignment Problem. In cocoa 2016, pages 726-734, Hong Kong, China, Lecture Notes in Computer Science, Combinatorial Optimization and Applications. COCOA 2016 10043, 2016. doi  www 
  1. Lambert, A.; Elloumi, S.; D'Ambrosio, C. and Lazare, A. Global solution of mixed-integer polynomial optimization problems through quadratic reformulation. In PGMO days, Palaiseau, France, 2016. www 
  1. Bentz, C.; Costa, M-C.; Porumbel, D. and Ridremont, T. Conception de câblages robustes dans les parcs éoliens : recherche d'une Arborescence de Steiner ''robuste''. In 17ème congrès ROADEF, Compiègne, France, 2016. www 

2015

Articles de revue

  1. Bazgan, C.; Bentz, C.; Picouleau, C. and Ries, B. Blockers for the stability number and the chromatic number. In Graphs and Combinatorics, 31 (1), 2015. doi  www 
  1. Porumbel, D. C. and Goncalves, G. Using dual feasible functions to construct fast lower bounds for routing and location problems. In Discrete Applied Mathematics, 196: 83-99, 2015. doi  www 
  1. Watel, D.; Weisser, M-A.; Bentz, C. and Barth, D. An FPT algorithm in polynomial space for the Directed Steiner Tree problem with Limited number of Diffusing nodes. In Information Processing Letters, 115 (2): 275-279, 2015. doi  www 

Articles de conférence

  1. Lambert, A.; Elloumi, S. and Billionnet, A. Global Solution of General Quadratic Programs. In ISMP 15, Pittsburg, United States, 2015. www 
  1. Bentz, C.; Elloumi, S.; GOURDIN, E. and Lefebvre, T. Flot maximum robuste avec incertitudes sur les chemins. In 16?me congr?s annuel de la ROADEF, pages 1, Marseille, France, 2015. www 

2014

Articles de revue

  1. Billionnet, A.; Elloumi, S. and Lambert, A. A Branch and Bound algorithm for general mixed-integer quadratic programs based on quadratic convex relaxation. In Journal of Combinatorial Optimization, 28: 376-399, 2014. www 

Articles de conférence

  1. Bentz, C.; Costa, M-C. and Hertz, A. A Steiner tree problem with capacity constraints. In GO IX, Ninth international colloquium on Graphs and Optimization, pages 12, Sirmione, Italy, 2014. www 
  1. Bentz, C.; Elloumi, S.; GOURDIN, E. and Lefebvre, T. Network coding for survivable multicast video streaming networks. In Reliable Networks Design and Modeling (RNDM), 2014 6th International Workshop on, pages 138-144, X, France, 2014. www 
  1. Elloumi, S. and Lambert, A. Recent advances in solving some optimization problems in graphs by quadratic programming. In Ninth International Colloquium on Graphs and Optimization. GO IX, pages 1, X, Italy, 2014. www 
  1. Bentz, C.; Costa, M-C.; Hertz, A. and Poirion, P-L. Cabling optimization of a windfarm and capacitated K-Steiner tree. In PGMO-COPI'14 Gaspard Monge Program for Optimization - Conference on Optimization Practices in Industry, pages 4 pages, Palaiseau (91), France, 2014. www 
  1. Watel, D.; Weisser, M-A.; Bentz, C. and Barth, D. Directed Steiner Tree with Branching Constraint. In 20th International Computing and Combinatorics Conference - COCOON, pages 263-275, Springer, Atlanta, United States, 2014. doi  www 
  1. Lefebvre, T.; Bentz, C.; Elloumi, S. and Gourdin, E. Survivable Network Coding. In ROADEF - 15ème congrès annuel de la Société franc caise de recherche opérationnelle et d'aide `a la décision, Bordeaux, France, 2014. www 

2013

Articles de revue

  1. Billionnet, A.; Elloumi, S. and Lambert, A. An efficient compact quadratic convex reformulation for general integer quadratic programs. In Computational Optimization and Applications, 54: 141-162, 2013. www 
  1. Bentz, C.; Cornaz, D. and Ries, B. Packing and covering with linear programming: A survey. In European Journal of Operational Research, 227: 409-422, 2013. www 

Articles de conférence

  1. Watel, D.; Weisser, M-A.; Bentz, C. and Barth, D. Steiner Problems with Limited Number of Branching Nodes. In SIROCCO 2013, pages nc, Ischia, Italy, 2013. www 
  1. Billionnet, A.; Elloumi, S. and Lambert, A. Convex reformulations of mixed-integer quadratically constrained programs. In EUROPT 2013, pages 24, Florence, Italy, 2013. www 
  1. Elloumi, S.; Billionnet, A. and Lambert, A. Global solution of mixed-integer quadratic programs through quadratic convex reformulation. In EURO XXVI, pages 91, ROME, Italy, 2013. www 
  1. Elloumi, S. and Lambert, A. Quadratic convex reformulation for graph partitionning problems. In IFIP TC 7 / 2013 System Modelling and Optimization, pages 1, Klagenfurt, Austria, 2013. www 

Rapports

  1. Watel, D.; Weisser, M-A. and Bentz, C. Inapproximability proof of DSTLB and USTLB in planar graphs. Technical Report, Supélec, 2013.

2012

Articles de revue

  1. Jarray, F. and Picouleau, C. Minimum decomposition into convex binary matrices. In Discrete Applied Mathematics, 160 (7-8): 1164-1175, 2012. doi  www 
  1. Billionnet, A.; Elloumi, S. and Lambert, A. Extending the QCR method to the case of general mixed integer programs. In Mathematical Programming Computation, 131: 381-401, 2012. www 
  1. Bentz, C.; Costa, M-C.; Picouleau, C.; Ries, B. and De Werra, D. d-Transversals of Stable Sets and Vertex Covers in Weighted Bipartite Graphs. In Journal of Discrete Algorithms, 17: 95-102, 2012. doi  www 

Articles de conférence

  1. Billionnet, A.; Elloumi, S. and Lambert, A. Convex reformulations of Integer Quadratically Constrained Problems. In ISMP (21th International Symposium of Mathematical programming), pages 1 page, Berlin, Germany, 2012. www 
  1. Bentz, C. A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs. In IPEC 2012, pages 109-119, Ljubljana, Slovenia, LNCS 7535, 2012. www 
  1. Billionnet, A.; Elloumi, S. and Lambert, A. A new Branch and Bound algorithm for MIQPs. In EURO 2012, pages 57, Vilnius, Liechtenstein, 2012. www 

2011

Articles de revue

  1. Bentz, C. On the hardness of finding near-optimal multicuts in directed acyclic graphs. In Theoretical Computer Science, 412: 5325-5332, 2011. www 

Articles de conférence

  1. Costa, M-C.; de Werra, D.; Picouleau, C.; Ries, B. and Bentz, C. Minimum d-Transversals of Maximum-Weight Stable Sets in Trees. In European conference on combinatorics, graph theory and applications EuroComb'11, Electronics Notes in Discrete Mathematics, pages 129-134, Bupapest, Hungary, 2011. www 
  1. Billionnet, A.; Elloumi, S. and Lambert, A. A solution method for quadratically constrained integer problems. In Optimization 2011, Lisbon, Portugal., pages 64, X, France, 2011. www 

2010

Articles de revue

  1. Ries, B.; Bentz, C.; De Werra, D.; Costa, M-C.; Zenklusen, R. and Picouleau, C. Blockers and Transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid. In Discrete Mathematics, 310: 132-146, 2010. doi  www 

Articles de conférence

  1. Billionnet, A.; Elloumi, S. and Lambert, A. Solving a general mixed-integer quadratic problem through convex reformulation : a computational study. In EWMINLP, Marseille, France, 2010. www 
  1. Billionnet, A.; Elloumi, S. and Lambert, A. Reformulation convexe des programmes quadratiques entiers : un algorithme de Branch and Bound fondé sur la structure du problème reformulé. In ROADEF 10, 11?me congr?s annuel de la Soci?t? fran?aise de Recherche Op?rationnelle et d?Aide ? la D?cision, pages 2 pages, Toulouse, France, 2010. www 

2009

Articles de revue

  1. Bentz, C. Disjoint paths in sparse graphs. In Discrete Applied Mathematics, 157: 3558-3568, 2009. www 
  1. Bentz, C. A simple algorithm for multicuts in planar graphs with outer terminals. In Discrete Applied Mathematics, 157: 1959-1964, 2009. www 
  1. Bentz, C. and Picouleau, C. Locally bounded k -colorings of trees. In RAIRO - Operations Research, 43 (1): 27-33, 2009. doi  www 
  1. Bentz, C.; Costa, M-C.; Derhy, N. and Roupin, F. Cardinality constrained and multicriteria (multi)cut problems. In Journal of Discrete Algorithms, 7 (1): 102-111, 2009. www 
  1. Bentz, C.; Costa, M-C.; Létocart, L. and Roupin, F. Multicut and integral multiflow in rings. In European Journal of Operational Research, 196 (3): 1251-1254, 2009. www 

Articles de conférence

  1. Bentz, C. New results on planar and directed multicuts. In EUROCOMB 2009, pages 207-211, Bordeaux, France, ENDM 34, 2009. www 
  1. Bentz, C. On Planar and Directed Multicuts with few Source-Sink Pairs. In CTW 2009, pages 313-316, Paris, France, 2009. www 
  1. Bentz, C.; Costa, M-C.; de Werra, D.; Picouleau, C.; Ries, B. and Zenklusen, R. d-bloqueurs et d-transversaux. In Recherche op?rationnelle et aide ? la d?cision. ROADEF'09 Nancy, pages 316-317, X, France, 2009. www 
  1. Billionnet, A.; Elloumi, S. and Lambert, A. Convex reformulations for integer quadratic programs. In 20th International Symposium of Mathematical programming (ISMP), pages 115, Chicago, United States, 2009. www 
  1. Aponte, M-V.; Levieux, G. and Natkin, S. Scaling the Level of Difficulty in Single Player Video Games. In Proceedings of the 8th International Conference on Entertainment Computing, pages 24-35, Paris, France, 2009. www 
  1. Billionnet, A.; Elloumi, S. and Lambert, A. Convex reformulations for binary quadratic programs. In EURO 2009, 23rd European Conference on Operational Research, pages 47, Bonn, Germany, 2009. www 
  1. Billionnet, A.; Elloumi, S. and Lambert, A. Résolution de programmes quadratiques en nombres entiers par reformulation convexe. In JPOC 6 (Journ?es Poly?dres et Optimisation Combinatoire), pages 15-18, Bordeaux, France, 2009. www 

Thèses

2008

Articles de revue

  1. Bentz, C. On the complexity of the multicut problem in bounded tree-width graphs and digraphs. In Discrete Applied Mathematics, 156: 1908-1917, 2008. www 
  1. Bentz, C. Exact and approximate resolution of integral multiflow and multicut problems: algorithms and complexity. In 4OR: A Quarterly Journal of Operations Research, 6: 89-92, 2008. www 
  1. Costa, M-C.; de Werra, D.; Picouleau, C. and Ries, B. Addendum to ``Bicolored Matchings in Some Classes of Graphs''. In Graphs and Combinatorics, 24 (2): 127-128, 2008. doi  www 

Articles de conférence

  1. Billionnet, A.; Elloumi, S. and Lambert, A. Comparaison de reformulations linéaires de programmes quadratiques en nombres entiers. In ROADEF'08, 9?me Congr?s de la Soci?t? Fran?aise de Recherche Op?rationnelle et d?Aide ? la D?cision, pages 71-72, Clermont-Ferrand, France, 2008. www 
  1. Billionnet, A.; Elloumi, S. and Lambert, A. Linear Reformulations of Integer Quadratic Programs. In MCO'08, 2nd international conference on Modelling, Computation and Optimization in Information Systems and Management Sciences, pages 43-51, Metz, France, LNCS , 2008. www 

2007

Articles de revue

  1. Bentz, C. The maximum integer multiterminal flow problem in directed graphs. In Operations Research Letters, 35: 195-200, 2007. www 
  1. Bentz, C.; Costa, M-C. and Roupin, F. Maximum integer multiflow and minimum multicut problems in uniform grid graphs. In Journal of Discrete Algorithms, 5 (1): 36-54, 2007. doi  www 
  1. Bentz, C.; Costa, M-C.; Picouleau, C. and Zrikem, M. The shortest multipaths problem in a capacitated dense channel. In European Journal of Operational Research, 178: 926-931, 2007. www 

2006

Articles de conférence

  1. Bentz, C.; Costa, M-C.; Picouleau, C.; Ries, B. and de Werra, D. Reconstruction de la coloration d’un graphe `a partir de projections de cha^ines. In ROADEF'06 7ème congrès ROADEF - Février, pages 51, Lille, France, 2006. www 
  1. Costa, M-C.; Roupin, F.; Bentz, C. and Derhy, N. Etude du problème de la multicoupe minimale `a cardinalité contrainte. In ROADEF'06 7ème congrès, février, pages 54, Lille, France, 2006. www 
  1. Bentz, C. Multicoupe dans les graphes planaires et de largeur d'arbre bornée. In ROADEF'06 7ème congrès, février, pages 54, Lille, France, 2006. www 
  1. Bentz, C. The Maximum Integer Multiterminal Flow Problem. In OTA'06 Int. Workshop of ICCSA 2006, Glasgow, pages 738-747, X, France, LNCS 3982, 2006. www 
  1. Bentz, C. Approximation du problème de flot multiterminal entier maximum dans les graphes orientés. In ROADEF'06 7ème congrès, février, pages 48, Lille, France, 2006. www 

2005

Articles de conférence

  1. Bentz, C. Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs. In ICGT'05 7th Int. Colloquium on Graph Theory, Hyeres, pages 55-60, X, France, ENDM 22, 2005. www 
  1. Costa, M-C.; Roupin, F. and Bentz, C. Résoudre en temps linéaire le problème de la multicoupe minimum dans des grilles rectangulaires. In ROADEF'05 6ème congrès, février, pages 105-106, Tours, France, 2005. www 

2004

Divers

  1. Létocart, L.; Bentz, C.; Costa, M-C. and Roupin, F. A bibliography on multicut and integer multiflow problems. , Rapport scientifique CEDRIC (ref. CEDRIC 654). www 

2001

Articles de revue

  1. Picouleau, C. Reconstruction of domino tiling from its two orthogonal projections. In Theoretical Computer Science, 255 (1-2): 437-447, 2001. doi  www 
Haut