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.

Peer-reviewed conferences and journals

Communications

2022

Articles de conférence

  1. Mencarelli, L. An Outer Approximation Algorithm for 0-1 Polynomial Programming. In HUGO 2022 - XV. Workshop on Global Optimization, Szeged, Hungary, 2022. www 
  1. Quezada, F.; Gicquel, C. and Kedad-Sidhoum, S. A partial decomposition approach for solving the stochastic uncapacitated lot-sizing problem. In 32nd European Conference on Operations Research (EURO2022), Espoo, Finland, 2022. www 
  1. Alès, Z.; Huré, V. and Lambert, A. New optimization models for optimal classification trees. In 32nd European Conference on Operational Research (EURO 2022), Espoo, Finland, 2022. www 
  1. Dur'an Mateluna, C.; Jorquera-Bravo, N.; Alès, Z. and Elloumi, S. Robust MILP formulations for the two-stage p-Center Problem. In PGMO Days 2022, Palaiseau, France, 2022. www 
  1. Picouleau, C. and Bouquet, V. The Perfect Matching-Cut problem in bipartite graphs with diameter three. In ICGT 2022, Montpellier, France, 2022. www 
  1. Lambert, A. Exact solution of the OPF problem based on compact quadratically constrained convex relaxation. In 32nd European Conference on Operational Research (EURO 2022), Espoo, Finland, 2022. www 
  1. Elloumi, S.; Lambert, A.; Neveu, B. and Trombettoni, G. Global Solution of Quadratic Problems by Interval Methods and Convex Reformulation. In HUGO 2022 - 15th Workshop on Global Optimization, Szeged, Hungary, 2022. www 
  1. Mencarelli, L.; Floquet, J.; Georges, F.; Guillaud, B. and Mellouki, W. The Satellite Constellation Design Problem via MI(N)LP Boosted with a Genetic Algorithm. In PGMO Days 2022, Palaiseau, France, 2022. www 
  1. Alès, Z.; Elloumi, S. and Pass-Lanneau, A. Algorithmes de placement optimisé de drones pour la conception de réseaux de communication. In Conference on Artificial Intelligence for Defense (CAID) 2022, Rennes, France, Actes de la 4ème Conference on Artificial Intelligence for Defense (CAID 2022) , 2022. www 
  1. Quezada, F.; Gicquel, C. and Kedad-Sidhoum, S. A partial decomposition approach to solve the stochastic uncapacitated lot-sizing problem. In European Conference on Stochastic Optimization - Computational Management Science (ECSO-CMS 2022), Venice, Italy, 2022. www 
  1. Porumbel, D. C. Projective Cutting Planes with multiple cuts per iteration for robust linear programming. In PGMO Days 2022, Palaiseau (91), France, 2022. www 

Divers

  1. Yuehgoh, F.; Travers, N. and Djebali, S. A Technology Intelligence Recommendation System based on Multiplex Networks. , Poster. www 
  1. Yuehgoh, F.; Travers, N. and Djebali, S. A Technology Intelligence Recommendation System based on Multiplex Networks. , Poster. www 

2021

Livres

Articles de conférence

  1. Quezada, F.; Gicquel, C. and Kedad-Sidhoum, S. A partial nested decomposition approach for remanufacturing planning under uncertainty. In Advances in Production Management Systems - APMS 2021, pages 663-672, Springer, Nantes, France, IFIP Advances in Information and Communication Technology 631, 2021. doi  www 
  1. Quezada, F.; Gicquel, C. and Kedad-Sidhoum, S. New valid inequalities for a multi-item multi-echelon lot-sizing problem with returns and lost sales. In International Workshop on Lot-Sizing - IWLS 2021, online streaming, France, 2021. www 
  1. Charles, M.; Dauzere-Peres, S.; Kedad-Sidhoum, S. and Mazhoud, I. Capacitated lot-sizing problem with inventory constraints within periods. In 2021 IEEE 17th International Conference on Automation Science and Engineering (CASE), pages 1021-1026, IEEE, Lyon, France, 2021. doi  www 
  1. Mencarelli, L.; Floquet, J. and Georges, F. Mixed Integer Nonlinear Approaches for the Satellite Constellation Design Problem. In PGMO DAYS 2021, Palaiseau, France, 2021. www 

Rapports

  1. Guillemin, F.; Navas, R.; Aimi, A.; Aubonnet, T.; Kerdoncuff, T-. G.; Secci, S.; Hadjadj-Aoul, Y.; Rovedakis, S. and Boubendir, A. Reference architecture for slicing in LoRAWAN networks. Technical Report, Consortium INTELLIGENTSIA, 2021.

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

Articles de conférence

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

2019

Articles de conférence

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

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

Articles de conférence

  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. Lambert, A.; Elloumi, S. and Lazare, A. Unconstrained 0-1 polynomial optimization through convex quadratic reformulation. In ISMP 18, Bordeaux, France, 2018. www 
  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. doi  www 
  1. Lambert, A. Valid inequalities for QCQPs. In ISMP 18, Bordeaux, 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. 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. 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. Lucas, R.; Alès, Z. and Elloumi, S. A MILP Formulation for Adaptive Solutions in Railway Scheduling. In PGMO Days 2018, Palaiseau, France, 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. 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. 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. 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. 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 

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

Articles de conférence

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

PhD & HDR

2022

2021

2020

2019

2018

2017

Thèses et habilitations

Ongoing projects

KARDINAL HYOSEOK Kim
  • Full name: Sté KARDINAL HYOSEOK Kim: KARDINAL HYOSEOK Kim - Funder: Kardinal
  • Duration: October 2020 - September 2023
  • Description:
Saint Gobain Medvedev
  • Full name: Collaboration cifre Saint Gobian Anton Medvedev: Saint Gobain Medvedev - Funder: Saint Gobain
  • Duration: April 2022 - March 2025
  • Description:
Dotation OC 2023
  • Full name: Dotation OC 2023: Dotation OC 2023 - Funder: Laboratoire Cédric
  • Duration: January 2023 - December 2023
  • Description:
PEX ORION 2023
  • Full name: PEX ORION 2023: PEX ORION 2023 - Funder: Laboratoire Cédric
  • Duration: January 2023 - December 2023
  • Description:

Past projects

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

    • Full name: EDF Marc ETHEVE
    • Duration: January 2019 - December 2022
    • Description:

    • Full name: Orange Isaias FARIA
    • Duration: December 2018 - December 2021
    • Description:

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

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

    • Full name: RTE GODARD
    • Duration: January 2017 - December 2019
    • Description: Ce projet traite de la résolution exacte du problème de l’Optimal Power Flow (OPF). Sa modélisation comme un problème quadratique non convexe sous contraintes quadratiques non convexes place l’OPF dans la catégorie des problèmes d’optimisation difficiles. Des techniques de reformula- tion quadratique convexe en perturbant l’objectif à l’aide d’une matrice SDP ont été récemment développées et appliquées à des problèmes non convexes. Cette refor- mulation quadratique convexe est ici appliquée et spécialisée à la résolution globale de l’OPF à l’aide d’un Spatial Branch and Bound.

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

    • Full name: Soutien équipe OC 2022
    • Duration: January 2022 - December 2022
    • Description:

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

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

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

Top