# Combinatorial optimization

A combinatorial optimization problem consists in determining a best solution among a discrete set of solutions, called feasible solutions. In general, such a set is finite but huge, and is described implicitly, i.e., by means of a list of constraints that any feasible solution must satisfy. In order to formalize the notion of a best solution, some function, called the objective function, is considered. It associates a real value to each solution, and a best, or optimal, solution, is then a feasible solution minimizing or maximizing this objective function. In particular, combinatorial optimization deals with practical problems such as optimizing the design and operating of production systems, or, more generally, optimizing the decision making process of a company.

The research work carried out in the Combinatorial optimization (OC) team covers two main topics: Mathematical programming and applications and Graphs and optimization.

## « Mathematical programming and applications »

This topic is essentially about discrete optimization (either linear or non linear). This kind of very general models can be used to formulate almost every single combinatorial optimization problem. Such problems are generally hard to solve, and, in many cases, only small ones can be solved efficiently. The researchers of the OC team that work on this topic aim at acquiring a better understanding of these problems, in order to be able to solve them more efficiently. They are also interested in solving efficiently practical optimization problems related to different fields: telecommunications, transport, energy, environment, etc. Finally, another aspect of interest is the one of finding robust optimal solutions for such problems. Indeed, in an industrial setting, it is usually more relevant to look for a “robust” solution, which will perform rather well in any possible situation, instead of looking for an “optimal” one for a very specific case. The OC team has already worked on the problem of computing such solutions, as the notion of robustness is a very rich and useful one.

## « Graphs and optimization »

Graphs are mathematical tools which play a central role in Operational Research. They can be used to model various types of systems. Finding an optimal solution then generally consists in identifying an optimal structure in a graph. Because of the sizes of the associated real instances, even a powerful computer is not sufficient to provide an optimal solution within a reasonable amount of time. In order to make such a solution easier to find, one often needs to prove structural properties of optimal solutions, and then, whenever this is possible, use them to design efficient algorithms to solve the problem, either exactly, or approximately. The researchers of the OC team that work on this topic aim at applying this approach to some graph optimization problems, that are general enough to model many real-life situations. They are also interested in approximation algorithms, parameterized algorithms, and online algorithms.

• Directory
• Publications
• Former
• Projects

## 2021

### Articles de revue

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. In Discrete Applied Mathematics, 290: 36-59, 2021.
1. Bouquet, V.; Delbot, F. c. and Picouleau, C. On the vertices belonging to all, some, none minimum dominating set. In Discrete Applied Mathematics, 288: 9-19, 2021.
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, 298 (1-2): 183-206, 2021.

### Livres

1. Billionnet, A. Designing Protected Area Networks: A Mathematical Programming Approach. EDP Sciences - Current Natural Sciences (Open ebook), 2021.

### Non publié

1. Falq, A-E.; Fouilhoux, P. and Kedad-Sidhoum, S. Dominance inequalities for scheduling around an unrestrictive common due date. , working paper or preprint.

## 2020

### Articles de revue

1. Alès, Z. and Knippel, A. The K -partitioning problem: Formulations and branch-and-cut. In Networks, 76 (3): 323-349, 2020.
1. Costa, M.-C.; de Werra, D. and Picouleau, C. Minimal graphs for 2-factor extension. In Discrete Applied Mathematics, 2020.
1. Porumbel, D. C. Projective Cutting-Planes. In SIAM Journal on Optimization, 30 (1): 1007-1032, 2020.
1. Elloumi, S.; Lambert, A. and Lazare, A. Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation. In Journal of Global Optimization, 2020.
1. Picouleau, C. Minimal graphs for hamiltonian extension. In Open Journal of Discrete Applied Mathematics, 2020.
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.
1. Bucarey, V.; Elloumi, S.; Labbé, M. and Plein, F. Models and Algorithms for the Product Pricing with Single-Minded Customers Requesting Bundles. In Computers and Operations Research, 2020.
1. Bentz, C.; Costa, M-C. and Hertz, A. On the edge capacitated Steiner tree problem. In Discrete Optimization, 38: 100607, 2020.
1. Chen, Z.; Fampa, M.; Lambert, A. and Lee, J. Mixing convex-optimization bounds for maximum-entropy sampling. In Mathematical Programming B, 2020.
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.
1. Phouratsamay, S-L.; Kedad-Sidhoum, S. and Pascual, F. Coordination of a two-level supply chain with contracts. In 4OR: A Quarterly Journal of Operations Research, 2020.
1. Billionnet, A. La R.O. pour préserver la biodiversité. In Tangente, Hors Série Kiosque (75): 58-60, 2020.

### Chapitres d'ouvrage

1. Etheve, M.; Alès, Z.; Bissuel, C.; Kedad-Sidhoum, S. and Juan, O. Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR: International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 176-185, 2020.

### 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.
1. Silva, I. F.; Bouhtou, M.; Chardy, M.; Bentz, C. and Kedad-Sidhoum, S. Battery Energy Management of a Telecommunications Company to Participate in the Curtailment Market and Reduce the Total Energy Cost. In 2020 IEEE 8th International Conference on Smart Energy Grid Engineering (SEGE), pages 121-127, IEEE, Oshawa, France, 2020.
1. Silva, I. F.; Bentz, C.; Bouhtou, M.; Chardy, M. and Kedad-Sidhoum, S. Optimizing Battery Usage for a Telecommunications Company with Energy Curtailment Incentives. In ROADEF2020, Montpellier, France, 2020.
1. Bentz, C.; Costa, M-C.; Poirion, P-L.; Ridremont, T. and Zakour, C. Wind farm cable layout optimization with constraints of load flow and robustness. In ICREEE 2020: International Conference on Renewable Energy and Environment Engineering, Tokyo (on line), Japan, 2020.
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.

### Non publié

1. Bouquet, V. and Picouleau, C. The Minimum Dominating Set problem is polynomial for (claw, P8)-free graphs. , working paper or preprint.
1. Kim, E. J.; Milanic, M.; Monnot, J. and Picouleau, C. Complexity and algorithms for constant diameter augmentation problems. , working paper or preprint.
1. Frosini, A.; Picouleau, C. and Rinaldi, S. Characterization of the degree sequences of (quasi) regular uniform hypergraphs. , working paper or preprint.
1. Ridremont, T.; Watel, D.; Poirion, P-L. and Picouleau, C. Adaptive network flow with \$k\$-Arc Destruction. , working paper or preprint.
1. Bouquet, V. and Picouleau, C. The complexity of the Perfect Matching-Cut problem. , working paper or preprint.
1. Lambert, A. Valid inequalities and global solution algorithm for Quadratically Constrained Quadratic Programs. , preprint.
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.
1. Quezada, F.; Gicquel, C. and Kedad-Sidhoum, S. Combining polyhedral approaches and stochastic dual dynamic integer programming for solving the uncapacitated lot-sizing problem under uncertainty. , working paper or preprint.
1. Bouquet, V.; Delbot, F. c. and Picouleau, C. Partition of graphs with maximum degree ratio. , working paper or preprint.

## 2019

### Articles de revue

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.
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.
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.
1. Paulusma, D.; Picouleau, C. and Ries, B. Critical vertices and edges in H-free graphs. In Discrete Applied Mathematics, 257: 361-367, 2019.
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.
1. Bentz, C. An FPT Algorithm for Planar Multicuts with Sources and Sinks on the Outer Face. In Algorithmica, 81 (1): 224-237, 2019.

### Articles de conférence

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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.

## 2018

### Articles de revue

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.
1. Costa, M-C.; de Werra, D. and Picouleau, C. Minimal graphs for matching extension. In Discrete Applied Mathematics, 234: 47-55, 2018.
1. Porumbel, D. C. Prize-collecting set multicovering with submodular pricing. In International Transactions in Operational Research, 25 (4): 1221-1239, 2018.
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.
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.
1. Billionnet, A. Phylogenetic conservation prioritization with uncertainty. In Biodiversity and Conservation, 27 (12): 3137-3153, 2018.
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.
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.
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.
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.
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.
1. Phouratsamay, S-L.; Kedad-Sidhoum, S. and Pascual, F. Two-level lot-sizing with inventory bounds. In Discrete Optimization, 2018.
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.

### 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,, Lecture Notes in Computer Science 10856, 2018.

### Articles de conférence

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.
1. Lambert, A.; Elloumi, S. and Lazare, A. Unconstrained 0-1 polynomial optimization through convex quadratic reformulation. In ISMP 18, Bordeaux, France, 2018.
1. Lambert, A. Valid inequalities for QCQPs. In ISMP 18, Bordeaux, France, 2018.
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.
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.
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.
1. Kedad-Sidhoum, S. Problèmes de lot-sizing: résultats fondamentaux et applications émergentes. In ROADEF2018, Lorient, France, 2018.
1. Milliet de Faverges, M.; Russolillo, G.; Picouleau, C.; Merabet, B. and Houzel, B. Modelling passenger train arrival delays with Generalized Linear Models and its perspective for scheduling at main stations. In 8th International Conference on Railway Engineering (ICRE 2018), IET, London, United Kingdom, 2018.
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.
1. Costa, M-C.; De Werra, D and Picouleau, C. Extenseurs hamiltoniens minimaux. In ROADEF, Lorient, France, 2018.
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.
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.
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.
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.
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.
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.
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.
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.
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.

### 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.

## 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.
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.

### 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.

### Articles de conférence

1. Lambert, A. and Elloumi, S. Quadratic convex reformulation for partitioning problems. In EUROPT 17, Montreal, Canada, 2017.
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.
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.
1. Elloumi, S.; Lambert, A. and Lazare, A. Global optimisation of binary polynomial programs. In PGMO Days, Palaiseau, France, 2017.
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.
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.
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.

### Divers

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

### Non publié

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

## 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.
1. Billionnet, A.; Elloumi, S. and Lambert, A. Exact quadratic convex reformulations of mixed-integer quadratically constrained problems. In Mathematical Programming, 158 (1-2): 235-266, 2016.
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.
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.

### Articles de conférence

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.
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.
1. Elloumi, S. and Lambert, A. Reformulation quadratique convexe du problème d'affectation quadratique. In ROADEF 2016, Compiègne, France, 2016.
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.

## 2015

### Articles de revue

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.
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.
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.

### 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.
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.

## 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.

### Articles de conférence

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.
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.
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.
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.
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.
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.

## 2013

### Articles de revue

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.
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.

### Articles de conférence

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.
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.
1. Billionnet, A.; Elloumi, S. and Lambert, A. Convex reformulations of mixed-integer quadratically constrained programs. In EUROPT 2013, pages 24, Florence, Italy, 2013.
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.

### 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.
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.
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.

### 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.
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.
1. Billionnet, A.; Elloumi, S. and Lambert, A. A new Branch and Bound algorithm for MIQPs. In EURO 2012, pages 57, Vilnius, Liechtenstein, 2012.

## 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.

### Articles de conférence

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.

## 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.

### Articles de conférence

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.
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.

## 2009

### Articles de revue

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.
1. Bentz, C. Disjoint paths in sparse graphs. In Discrete Applied Mathematics, 157: 3558-3568, 2009.
1. Bentz, C. A simple algorithm for multicuts in planar graphs with outer terminals. In Discrete Applied Mathematics, 157: 1959-1964, 2009.
1. Bentz, C. and Picouleau, C. Locally bounded k -colorings of trees. In RAIRO - Operations Research, 43 (1): 27-33, 2009.
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.

### Articles de conférence

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.
1. Bentz, C. New results on planar and directed multicuts. In EUROCOMB 2009, pages 207-211, Bordeaux, France, ENDM 34, 2009.
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.
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.
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.
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.
1. Bentz, C. On Planar and Directed Multicuts with few Source-Sink Pairs. In CTW 2009, pages 313-316, Paris, France, 2009.

## 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.
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.
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.

### Articles de conférence

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.
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.

## 2007

### Articles de revue

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.
1. Bentz, C. The maximum integer multiterminal flow problem in directed graphs. In Operations Research Letters, 35: 195-200, 2007.
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.

## 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.
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.
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.
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.
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.

## 2005

### Articles de conférence

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.
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.

## 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).

## 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.

## Ongoing projects

• Full name: Orange Isaias FARIA: Orange Isaias FARIA - Funder: Orange
• Duration: December 2018 - December 2021
• Description:
• Full name: EDF Marc ETHEVE: EDF Marc ETHEVE - Funder: EDF ELECTRICITE DE FRANCE
• Duration: January 2019 - December 2021
• Description:
• Full name: Sté KARDINAL HYOSEOK Kim: KARDINAL HYOSEOK Kim - Funder: Kardinal
• Duration: October 2020 - September 2023
• Description:

## Past projects

• Full name: Optimisation combinatoire
• Duration: January 2020 - December 2020
• Description:

• Full name: France GALOP
• Duration: December 2016 - December 2019
• Description:

• Full name: DIM RFSI n°2018-06
• Duration: May 2019 - October 2019
• Description:

• Full name: DIM RFSI n°2018-15
• Duration: February 2019 - December 2019
• Description:

• Full name: RTE GODARD
• Duration: January 2017 - December 2019
• Description:

• Full name: SPIROPS COLOMBIER
• Duration: February 2017 - January 2020
• Description:

• Full name: CNCF RESEAU Marie MILLIET
• Duration: February 2017 - January 2020
• Description:

• Full name: FRANCE GALOP HOUDAYER
• Duration: January 2018 - January 2021
• Description:

Top