Eric Bourreau
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Eric Bourreau has a total of 27 co-authors. Here are the top co-authors by number of shared publications:
- Camille Grange
LIRMM, University of Montpellier, CNRS, Montpellier, France
3 shared publications - Gérard Fleury
UMR 6158 LIMOS, Université Clermont Auvergne, Clermont Auvergne INP, Aubière, France
3 shared publications - Michael Poss
LIRMM University of Montpellier CNRS Montpellier France
3 shared publications - Philippe Lacomme
UMR 6158 LIMOS, Université Clermont Auvergne, Clermont Auvergne INP, Aubière, France
3 shared publications - Camille Grange
LITIS Normandie Univ UNIHAVRE 25 rue Philippe Lebon Le Havre France
2 shared publications - Marion Lavignac
Innovation and Group Projects Department SNCF, Technology 1 avenue François Mitterand Saint-Denis France
2 shared publications
Latest Publications
- 18 May 2026
- Published by Springer Nature in Journal of Heuristics
- Vol. 32 (2) , 22
Indirect job-shop coding using rank: application to QAOA (IQAOA)
- 18 May 2026
- Published by Springer Nature in Journal of Heuristics
- Vol. 32 (2) , 22
Indirect job-shop coding using rank: application to QAOA (IQAOA)
- Open Access
- 1 January 2025
- Published by Wiley in Quantum Engineering
- Vol. 2025 (1)
A Hybrid Quantum‐Assisted Column Generation Algorithm for the Fleet Conversion Problem
The problem of fleet conversion aims to reduce the carbon emissions and cost of operating a fleet of vehicles for a given set of tours. It can be modeled as a column generation scheme with the maximum weighted independent set (MWIS) problem as the sub‐problem or worker problem. Quantum variational algorithms have gained significant interest in the past several years. Recently, a method to represent quadratic unconstrained binary optimization (QUBO) problems using logarithmically fewer qubits was proposed. Here we use this method to solve the MWIS Workers and demonstrate how quantum and classical solvers can be used together to approach an industrial‐sized use case (up to 64 tours).
- 1 January 2025
- Published by Wiley in Quantum Engineering
- Vol. 2025 (1)
Open AccessA Hybrid Quantum‐Assisted Column Generation Algorithm for the Fleet Conversion Problem
The problem of fleet conversion aims to reduce the carbon emissions and cost of operating a fleet of vehicles for a given set of tours. It can be modeled as a column generation scheme with the maximum weighted independent set (MWIS) problem as the sub‐problem or worker problem. Quantum variational algorithms have gained significant interest in the past several years. Recently, a method to represent quadratic unconstrained binary optimization (QUBO) problems using logarithmically fewer qubits was proposed. Here we use this method to solve the MWIS Workers and demonstrate how quantum and classical solvers can be used together to approach an industrial‐sized use case (up to 64 tours).
- Open Access
Quadratic versus Polynomial Unconstrained Binary Models for Quantum Optimization illustrated on Railway Timetabling
Quantum Approximate Optimization Algorithm (QAOA) is one of the most short-term promising quantum-classical algorithm to solve unconstrained combinatorial optimization problems. It alternates between the execution of a parametrized quantum circuit and a classical optimization. There are numerous levers for enhancing QAOA performances, such as the choice of quantum circuit meta-parameters or the choice of the classical optimizer. In this paper, we stress on the importance of the input problem formulation by illustrating it with the resolution of an industrial railway timetabling problem. Specifically, we present a generic method to reformulate any polynomial problem into a Polynomial Unconstrained Binary Optimization (PUBO) problem, with a specific formulation imposing penalty terms to take binary values when the constraints are linear. We also provide a generic reformulation into a Quadratic Unconstrained Binary Optimization (QUBO) problem. We then conduct a numerical comparison between the PUBO with binary penalty terms and the QUBO formulations proposed on a railway timetabling problem solved with QAOA. Our results illustrate that the PUBO reformulation outperforms the QUBO one for the problem at hand.
Open AccessQuadratic versus Polynomial Unconstrained Binary Models for Quantum Optimization illustrated on Railway Timetabling
Quantum Approximate Optimization Algorithm (QAOA) is one of the most short-term promising quantum-classical algorithm to solve unconstrained combinatorial optimization problems. It alternates between the execution of a parametrized quantum circuit and a classical optimization. There are numerous levers for enhancing QAOA performances, such as the choice of quantum circuit meta-parameters or the choice of the classical optimizer. In this paper, we stress on the importance of the input problem formulation by illustrating it with the resolution of an industrial railway timetabling problem. Specifically, we present a generic method to reformulate any polynomial problem into a Polynomial Unconstrained Binary Optimization (PUBO) problem, with a specific formulation imposing penalty terms to take binary values when the constraints are linear. We also provide a generic reformulation into a Quadratic Unconstrained Binary Optimization (QUBO) problem. We then conduct a numerical comparison between the PUBO with binary penalty terms and the QUBO formulations proposed on a railway timetabling problem solved with QAOA. Our results illustrate that the PUBO reformulation outperforms the QUBO one for the problem at hand.
- Open Access
Quadratic versus Polynomial Unconstrained Binary Models for Quantum Optimization illustrated on Railway Timetabling
Quantum Approximate Optimization Algorithm (QAOA) is one of the most short-term promising quantum-classical algorithm to solve unconstrained combinatorial optimization problems. It alternates between the execution of a parametrized quantum circuit and a classical optimization. There are numerous levers for enhancing QAOA performances, such as the choice of quantum circuit meta-parameters or the choice of the classical optimizer. In this paper, we stress on the importance of the input problem formulation by illustrating it with the resolution of an industrial railway timetabling problem. Specifically, we present a generic method to reformulate any polynomial problem into a Polynomial Unconstrained Binary Optimization (PUBO) problem, with a specific formulation imposing penalty terms to take binary values when the constraints are linear. We also provide a generic reformulation into a Quadratic Unconstrained Binary Optimization (QUBO) problem. We then conduct a numerical comparison between the PUBO with binary penalty terms and the QUBO formulations proposed on a railway timetabling problem solved with QAOA. Our results illustrate that the PUBO reformulation outperforms the QUBO one for the problem at hand.
Open AccessQuadratic versus Polynomial Unconstrained Binary Models for Quantum Optimization illustrated on Railway Timetabling
Quantum Approximate Optimization Algorithm (QAOA) is one of the most short-term promising quantum-classical algorithm to solve unconstrained combinatorial optimization problems. It alternates between the execution of a parametrized quantum circuit and a classical optimization. There are numerous levers for enhancing QAOA performances, such as the choice of quantum circuit meta-parameters or the choice of the classical optimizer. In this paper, we stress on the importance of the input problem formulation by illustrating it with the resolution of an industrial railway timetabling problem. Specifically, we present a generic method to reformulate any polynomial problem into a Polynomial Unconstrained Binary Optimization (PUBO) problem, with a specific formulation imposing penalty terms to take binary values when the constraints are linear. We also provide a generic reformulation into a Quadratic Unconstrained Binary Optimization (QUBO) problem. We then conduct a numerical comparison between the PUBO with binary penalty terms and the QUBO formulations proposed on a railway timetabling problem solved with QAOA. Our results illustrate that the PUBO reformulation outperforms the QUBO one for the problem at hand.
- 6 September 2024
- Published by Elsevier in European Journal of Operational Research
- Vol. 320 (3) , 516-526
Moderate exponential-time quantum dynamic programming across the subsets for scheduling problems
- 6 September 2024
- Published by Elsevier in European Journal of Operational Research
- Vol. 320 (3) , 516-526
Moderate exponential-time quantum dynamic programming across the subsets for scheduling problems
- Top Cited Papers
- 30 May 2024
- Published by American Physical Society (APS) in Physical Review A
- Vol. 109 (5) , 052441
Solving various NP-hard problems using exponentially fewer qubits on a quantum computer
NP-hard problems are not believed to be exactly solvable through general polynomial time algorithms. Hybrid quantum-classical algorithms to address such combinatorial problems have been of great interest in the past few years. Such algorithms are heuristic in nature and aim to obtain an approximate solution. Significant improvements in computational time and/or the ability to treat large problems are some of the principal promises of quantum computing in this regard. The hardware, however, is still in its infancy and the current noisy intermediate-scale quantum (NISQ) computers are not able to optimize industrially relevant problems. Moreover, the storage of qubits and introduction of entanglement require extreme physical conditions. An issue with quantum optimization algorithms such as the quantum approximate optimization algorithm is that they scale linearly with problem size. In this paper, we build upon a proprietary methodology which scales logarithmically with problem size—opening an avenue for treating optimization problems of unprecedented scale on gate-based quantum computers. To test the performance of the algorithm, we first find a way to apply it to a handful of NP-hard problems: Maximum Cut, Minimum Partition, Maximum Clique, Maximum Weighted Independent Set. Subsequently, these algorithms are tested on a quantum simulator with graph sizes of over a hundred nodes and on a real quantum computer up to graph sizes of 256. To our knowledge, these constitute the largest realistic combinatorial optimization problems ever run on a NISQ device, overcoming previous problem sizes by almost tenfold.
- 30 May 2024
- Published by American Physical Society (APS) in Physical Review A
- Vol. 109 (5) , 052441
Top Cited PapersSolving various NP-hard problems using exponentially fewer qubits on a quantum computer
NP-hard problems are not believed to be exactly solvable through general polynomial time algorithms. Hybrid quantum-classical algorithms to address such combinatorial problems have been of great interest in the past few years. Such algorithms are heuristic in nature and aim to obtain an approximate solution. Significant improvements in computational time and/or the ability to treat large problems are some of the principal promises of quantum computing in this regard. The hardware, however, is still in its infancy and the current noisy intermediate-scale quantum (NISQ) computers are not able to optimize industrially relevant problems. Moreover, the storage of qubits and introduction of entanglement require extreme physical conditions. An issue with quantum optimization algorithms such as the quantum approximate optimization algorithm is that they scale linearly with problem size. In this paper, we build upon a proprietary methodology which scales logarithmically with problem size—opening an avenue for treating optimization problems of unprecedented scale on gate-based quantum computers. To test the performance of the algorithm, we first find a way to apply it to a handful of NP-hard problems: Maximum Cut, Minimum Partition, Maximum Clique, Maximum Weighted Independent Set. Subsequently, these algorithms are tested on a quantum simulator with graph sizes of over a hundred nodes and on a real quantum computer up to graph sizes of 256. To our knowledge, these constitute the largest realistic combinatorial optimization problems ever run on a NISQ device, overcoming previous problem sizes by almost tenfold.
- Open Access
Indirect Job-Shop coding using rank: application to QAOA (IQAOA)
The Job-Shop Scheduling Problem (JSSP) stands as one of the most renowned challenges in scheduling. It is characterized as a disjunctive problem, wherein a solution is fully depicted through an oriented disjunctive graph, with earliest starting times computed using a longest path algorithm. The complexity of solving this problem arises in part from the requirement that disjunctive graphs representing solutions must be acyclic. Consequently, enumerating these graphs is feasible for small-scale instances only. A significant advancement in this field, credited to (Bierwith, 1995), is the introduction of the 'vector by repetition' (commonly known as Bierwith's vector). Notably, this vector possesses the property that it can be mapped to an acyclic disjunctive graph, thereby enabling the mapping of a vector to a solution. This property has facilitated the development of highly efficient resolution schemes, as it allows the enumeration of solutions only i.e. acyclic disjunctive graphs. Our objective is to demonstrate how Bierwith's vector can be integrated into a Quantum Approximate Optimization Algorithm (QAOA) to tackle the job-shop problem using a novel quantum approach.
Open AccessIndirect Job-Shop coding using rank: application to QAOA (IQAOA)
The Job-Shop Scheduling Problem (JSSP) stands as one of the most renowned challenges in scheduling. It is characterized as a disjunctive problem, wherein a solution is fully depicted through an oriented disjunctive graph, with earliest starting times computed using a longest path algorithm. The complexity of solving this problem arises in part from the requirement that disjunctive graphs representing solutions must be acyclic. Consequently, enumerating these graphs is feasible for small-scale instances only. A significant advancement in this field, credited to (Bierwith, 1995), is the introduction of the 'vector by repetition' (commonly known as Bierwith's vector). Notably, this vector possesses the property that it can be mapped to an acyclic disjunctive graph, thereby enabling the mapping of a vector to a solution. This property has facilitated the development of highly efficient resolution schemes, as it allows the enumeration of solutions only i.e. acyclic disjunctive graphs. Our objective is to demonstrate how Bierwith's vector can be integrated into a Quantum Approximate Optimization Algorithm (QAOA) to tackle the job-shop problem using a novel quantum approach.
- Open Access
Solving various NP-Hard problems using exponentially fewer qubits on a Quantum Computer
NP-hard problems are not believed to be exactly solvable through general polynomial time algorithms. Hybrid quantum-classical algorithms to address such combinatorial problems have been of great interest in the past few years. Such algorithms are heuristic in nature and aim to obtain an approximate solution. Significant improvements in computational time and/or the ability to treat large problems are some of the principal promises of quantum computing in this regard. The hardware, however, is still in its infancy and the current Noisy Intermediate Scale Quantum (NISQ) computers are not able to optimize industrially relevant problems. Moreover, the storage of qubits and introduction of entanglement require extreme physical conditions. An issue with quantum optimization algorithms such as QAOA is that they scale linearly with problem size. In this paper, we build upon a proprietary methodology which scales logarithmically with problem size - opening an avenue for treating optimization problems of unprecedented scale on gate-based quantum computers. In order to test the performance of the algorithm, we first find a way to apply it to a handful of NP-hard problems: Maximum Cut, Minimum Partition, Maximum Clique, Maximum Weighted Independent Set. Subsequently, these algorithms are tested on a quantum simulator with graph sizes of over a hundred nodes and on a real quantum computer up to graph sizes of 256. To our knowledge, these constitute the largest realistic combinatorial optimization problems ever run on a NISQ device, overcoming previous problem sizes by almost tenfold.
Open AccessSolving various NP-Hard problems using exponentially fewer qubits on a Quantum Computer
NP-hard problems are not believed to be exactly solvable through general polynomial time algorithms. Hybrid quantum-classical algorithms to address such combinatorial problems have been of great interest in the past few years. Such algorithms are heuristic in nature and aim to obtain an approximate solution. Significant improvements in computational time and/or the ability to treat large problems are some of the principal promises of quantum computing in this regard. The hardware, however, is still in its infancy and the current Noisy Intermediate Scale Quantum (NISQ) computers are not able to optimize industrially relevant problems. Moreover, the storage of qubits and introduction of entanglement require extreme physical conditions. An issue with quantum optimization algorithms such as QAOA is that they scale linearly with problem size. In this paper, we build upon a proprietary methodology which scales logarithmically with problem size - opening an avenue for treating optimization problems of unprecedented scale on gate-based quantum computers. In order to test the performance of the algorithm, we first find a way to apply it to a handful of NP-hard problems: Maximum Cut, Minimum Partition, Maximum Clique, Maximum Weighted Independent Set. Subsequently, these algorithms are tested on a quantum simulator with graph sizes of over a hundred nodes and on a real quantum computer up to graph sizes of 256. To our knowledge, these constitute the largest realistic combinatorial optimization problems ever run on a NISQ device, overcoming previous problem sizes by almost tenfold.
- Open Access
Indirect Quantum Approximate Optimization Algorithms: application to the TSP
We propose an Indirect Quantum Approximate Optimization Algorithm (referred to as IQAOA) where the Quantum Alternating Operator Ansatz takes into consideration a general parameterized family of unitary operators to efficiently model the Hamiltonian describing the set of string vectors. This algorithm creates an efficient alternative to QAOA, where: 1) a Quantum parametrized circuit executed on a quantum machine models the set of string vectors; 2) a Classical meta-optimization loop executed on a classical machine; 3) an estimation of the average cost of each string vector computing, using a well know algorithm coming from the OR community that is problem dependent. The indirect encoding defined by dimensional string vector is mapped into a solution by an efficient coding/decoding mechanism. The main advantage is to obtain a quantum circuit with a strongly limited number of gates that could be executed on the noisy current quantum machines. The numerical experiments achieved with IQAOA permits to solve 8-customer instances TSP using the IBM simulator which are to the best of our knowledge the largest TSP ever solved using a QAOA based approach.
Open AccessIndirect Quantum Approximate Optimization Algorithms: application to the TSP
We propose an Indirect Quantum Approximate Optimization Algorithm (referred to as IQAOA) where the Quantum Alternating Operator Ansatz takes into consideration a general parameterized family of unitary operators to efficiently model the Hamiltonian describing the set of string vectors. This algorithm creates an efficient alternative to QAOA, where: 1) a Quantum parametrized circuit executed on a quantum machine models the set of string vectors; 2) a Classical meta-optimization loop executed on a classical machine; 3) an estimation of the average cost of each string vector computing, using a well know algorithm coming from the OR community that is problem dependent. The indirect encoding defined by dimensional string vector is mapped into a solution by an efficient coding/decoding mechanism. The main advantage is to obtain a quantum circuit with a strongly limited number of gates that could be executed on the noisy current quantum machines. The numerical experiments achieved with IQAOA permits to solve 8-customer instances TSP using the IBM simulator which are to the best of our knowledge the largest TSP ever solved using a QAOA based approach.
- 31 July 2023
- Published by Springer Nature in 4OR
- Vol. 21 (3) , 363-403
An introduction to variational quantum algorithms for combinatorial optimization problems
- 31 July 2023
- Published by Springer Nature in 4OR
- Vol. 21 (3) , 363-403
An introduction to variational quantum algorithms for combinatorial optimization problems