Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IISE Transactions

Routing and wavelength assignment with protection: A quadratic unconstrained binary optimization approach enabled by Digital Annealer technology

Oylum Şeker, Merve Bodur, Hamed Pouya

Published Mar 24, 2023• 3 citations
Publisher

Abstract

Routing and wavelength assignment with protection is an important problem in telecommunications. Given an optical network and incoming connection requests, a commonly studied variant of the problem aims to grant a maximum number of requests by assigning lightpaths with minimum network resource usage, while ensuring the provided services remain functional in the case of a single-link failure through dedicated protection paths. We consider a version where alternative lightpaths for requests are assumed to be given as a precomputed set and show that it is NP-hard. We formulate the problem as an Integer Programming (IP) model and also use it as a foundation to develop a Quadratic Unconstrained Binary Optimization (QUBO) model. We present necessary and sufficient conditions on objective function parameters to prioritize request granting objective over wavelength-link usage for both models, and a sufficient condition ensuring the exactness of the QUBO model. Moreover, we implement a problem-specific branch-and-cut algorithm for the IP model and employ a new quantum-inspired technology, Digital Annealer (DA), for the QUBO model. We conduct computational experiments on a large suite of nontrivial instances to assess the efficiency and efficacy of all of these approaches as well as two problem-specific heuristics. Although the objective penalty coefficient values that guarantee the exactness of the QUBO model were outside the acceptable range for DA, it always yielded feasible solutions even with smaller values in practice. The results show that the emerging technology DA outperforms the considered techniques coupled with GUROBI in finding mostly significantly better or as good solutions in two minutes compared to two-hour run time, whereas problem-specific heuristics fail to be competitive.

DOI
10.1080/24725854.2023.2193835

Related papers

Quantum-inspired optimization for wavelength assignment

Aleksey S. Boev, Sergey R. Usmanov, Alexander M. Semenov +5 more

Problems related to wavelength assignment (WA) in optical communications networks involve allocating transmission wavelengths for known transmission paths between nodes that minimize a certain objective function, for example, the total number of wavelengths. Playing a central role in modern telecommunications, this problem belongs to NP-complete class for a general case so that obtaining optimal solutions for industry-relevant cases is exponentially hard. In this work, we propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem. We propose an advanced embedding procedure to transform this problem into the quadratic unconstrained binary optimization (QUBO) form, having a improvement in the number of iterations with price-to-pay being a slight increase in the number of variables (“spins”). Then, we compare a quantum-inspired technique for solving the corresponding QUBO form against classical heuristic and industrial combinatorial solvers. The obtained numerical results indicate on an advantage of the quantum-inspired approach in a substantial number of test cases against the industrial combinatorial solver that works in the standard setting. Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications and open a perspective for further analysis of the use of quantum computing devices.

arXiv:2211.00317•Frontiers in Physics•Jan 18, 2023•9 citations

Multi-objective QUBO Solver: Bi-objective Quadratic Assignment Problem

Mayowa Ayodele, Richard Allmendinger, Manuel López‐Ibáñez +1 more

Quantum and quantum-inspired optimisation algorithms are designed to solve problems represented in binary, quadratic and unconstrained form. Combinatorial optimisation problems are therefore often formulated as Quadratic Unconstrained Binary Optimisation Problems (QUBO) to solve them with these algorithms. Moreover, these QUBO solvers are often implemented using specialised hardware to achieve enormous speedups, e.g. Fujitsu’s Digital Annealer (DA) and D-Wave’s Quantum Annealer. However, these are single-objective solvers, while many real-world problems feature multiple conflicting objectives. Thus, a common practice when using these QUBO solvers is to scalarise such multi-objective problems into a sequence of single-objective problems. Due to design trade-offs of these solvers, formulating each scalarisation may require more time than finding a local optimum.We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver that is not based on scalarisation. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem. We observe that algorithm performance significantly depends on the archiving strategy adopted, and that combining DA with non-scalarisation methods to optimise multiple objectives outperforms the current scalarised version of the DA in terms of final solution quality.

•Mar 25, 2022•0 citations

Routing and wavelength assignment problems in optical networks—comparing formulations for solution by quantum annealing

Ethan Davies, Darren Banfield, Ben Weaver +2 more

We develop four different quadratic unconstrained binary optimization formulations of routing problems relevant to the optical transport layers in telecommunications networks. Our formulations handle joint routing and wavelength assignment, unicast, multicast trees, and shared risk avoidance. We show that this approach is viable, even for multicast, and we test and compare the effectiveness of each formulation at solving these problems using the DWave hybrid solver. We describe expedients we applied to ensure valid solutions, along with challenges of the QUBO approach.

Journal of Optical Communications and Networking•Nov 14, 2025•3 citations

Segment Routing with Digital Annealing

Sebastian Engel, Christian Munch, Fritz Schinkel +3 more

The growing demand in broadband and data networks is a tremendous driver for innovation and investment. Efficient usage of resources and reliable operations are key objectives for network management. Optimization plays a pivotal role to make the best decisions in limited time. To tackle such difficult and elaborate (typically NP-hard) computational problems the latest developments in Quantum Computing are coming into focus. Successes with models for road traffic, logistics or financial industry have already demonstrated the applicability of these new methods to real-world problems. In this paper we formulate a model for resource assignment for transporting data over networks. For applicability in existing network management environments the model was designed on top of Segment Routing (SR) concepts. The validity of the model is proven for different cost and reliability targets. Based on a Digital Annealer (DA) as quantum-inspired hardware and an appropriate decomposition approach realistic data sets of a tier-1 provider can be processed. The quality of the results is comparable to classical optimization methods while the new approaches outperform those in computation time and have potential for a higher number of demands. An end-to-end comparison of quadratic model creation and solving on large data sets versus a processing as linear integer problem is presented. This shows that quantum approaches and algorithms are not only a preparation for a more distant future of fully functional quantum computers but can generate business advantages even today.

IEEE/IFIP Network Operations and Management Symposium (NOMS)•Apr 25, 2022•4 citations

Quantum computing approach for multi-objective routing and spectrum assignment optimization

Oumayma Bouchmal, Bruno Cimoli, Ripalta Stabile +5 more

Optimization problems are fundamental in a wide range of fields, including telecommunications, where efficient resource allocation is critical to ensure good network performance and high scalability. In the context of elastic optical networks (EONs), the multi-objective routing and spectrum assignment (MO-RSA) problem represents a key challenge, as it involves selecting a valid path and assigning frequency slots while fulfilling continuity and contiguity constraints and optimizing multiple conflicting objectives. This paper presents a novel, to the best of our knowledge, quantum-based approach to solving the MO-RSA problem. We first formulate the MO-RSA problem as a quadratic unconstrained binary optimization (QUBO) problem and then solve it using the quantum approximate optimization algorithm (QAOA). Our method accounts for both minimizing the total number of used links (or any non-negative additive metric) and maximizing the optical signal-to-noise ratio. For our simulations, we employed the Qiskit framework and IBM’s sampler-based quantum backend to implement and test the proposed approach. Our results demonstrate that by encoding the MO-RSA problem into a QUBO model and optimizing it with QAOA, we achieved an approximation ratio of 88% and a computational complexity of O ( n 2 ) , which represents a significant improvement over the exponential complexity of traditional integer linear programming methods.

Journal of Optical Communications and Networking•Mar 17, 2025•7 citations

Efficient Migration to the Next Generation of Networks Based on Digital Annealing

Mohammad Javad-Kalbasi, Shahrokh Valaee

Networks are frequently changing due to new technologies. The growing demand for bandwidth is forcing many carriers to migrate their existing network to a network with a new technology in order to increase network performance. Telecommunication companies are looking for optimization algorithms to efficiently manage their network migration. In this paper, the network migration problem is considered as a set of circuit migration problems in which two technicians simultaneously migrate the two ends of a circuit in order to minimize the total accumulated sites in-service and total technician travels. While total accumulated sites in-service indicates how fast the sites can be upgraded during the migration process, total technician travels estimates the required cost. We first formulate our target problem as a constrained binary quadratic program which is NP-hard in general. Our approach for solving the derived optimization problem is based on converting it to a quadratic unconstrained binary optimization problem (QUBO) using the penalty method. Subsequently, we exploit Digital Annealer which is a massively parallel hardware architecture to minimize the derived QUBO. To evaluate our proposed method, we study extensive network migration instances on the 75-node CONUS network topology.

IEEE International Conference on Acoustics Speech and Signal Processing•May 13, 2021•3 citations
Routing and wavelength assignment with protection is an important problem in telecommunications. Given an optical network and incoming connection requests, a commonly studied variant of the problem aims to grant a maximum number of requests by assigning lightpaths with minimum network resource usage, while ensuring the provided services remain functional in the case of a single-link failure through dedicated protection paths. We consider a version where alternative lightpaths for requests are assumed to be given as a precomputed set and show that it is NP-hard. We formulate the problem as an Integer Programming (IP) model and also use it as a foundation to develop a Quadratic Unconstrained Binary Optimization (QUBO) model. We present necessary and sufficient conditions on objective function parameters to prioritize request granting objective over wavelength-link usage for both models, and a sufficient condition ensuring the exactness of the QUBO model. Moreover, we implement a problem-specific branch-and-cut algorithm for the IP model and employ a new quantum-inspired technology, Digital Annealer (DA), for the QUBO model. We conduct computational experiments on a large suite of nontrivial instances to assess the efficiency and efficacy of all of these approaches as well as two problem-specific heuristics. Although the objective penalty coefficient values that guarantee the exactness of the QUBO model were outside the acceptable range for DA, it always yielded feasible solutions even with smaller values in practice. The results show that the emerging technology DA outperforms the considered techniques coupled with GUROBI in finding mostly significantly better or as good solutions in two minutes compared to two-hour run time, whereas problem-specific heuristics fail to be competitive.
Problems related to wavelength assignment (WA) in optical communications networks involve allocating transmission wavelengths for known transmission paths between nodes that minimize a certain objective function, for example, the total number of wavelengths. Playing a central role in modern telecommunications, this problem belongs to NP-complete class for a general case so that obtaining optimal solutions for industry-relevant cases is exponentially hard. In this work, we propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem. We propose an advanced embedding procedure to transform this problem into the quadratic unconstrained binary optimization (QUBO) form, having a improvement in the number of iterations with price-to-pay being a slight increase in the number of variables (“spins”). Then, we compare a quantum-inspired technique for solving the corresponding QUBO form against classical heuristic and industrial combinatorial solvers. The obtained numerical results indicate on an advantage of the quantum-inspired approach in a substantial number of test cases against the industrial combinatorial solver that works in the standard setting. Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications and open a perspective for further analysis of the use of quantum computing devices.
Quantum and quantum-inspired optimisation algorithms are designed to solve problems represented in binary, quadratic and unconstrained form. Combinatorial optimisation problems are therefore often formulated as Quadratic Unconstrained Binary Optimisation Problems (QUBO) to solve them with these algorithms. Moreover, these QUBO solvers are often implemented using specialised hardware to achieve enormous speedups, e.g. Fujitsu’s Digital Annealer (DA) and D-Wave’s Quantum Annealer. However, these are single-objective solvers, while many real-world problems feature multiple conflicting objectives. Thus, a common practice when using these QUBO solvers is to scalarise such multi-objective problems into a sequence of single-objective problems. Due to design trade-offs of these solvers, formulating each scalarisation may require more time than finding a local optimum.We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver that is not based on scalarisation. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem. We observe that algorithm performance significantly depends on the archiving strategy adopted, and that combining DA with non-scalarisation methods to optimise multiple objectives outperforms the current scalarised version of the DA in terms of final solution quality.
We develop four different quadratic unconstrained binary optimization formulations of routing problems relevant to the optical transport layers in telecommunications networks. Our formulations handle joint routing and wavelength assignment, unicast, multicast trees, and shared risk avoidance. We show that this approach is viable, even for multicast, and we test and compare the effectiveness of each formulation at solving these problems using the DWave hybrid solver. We describe expedients we applied to ensure valid solutions, along with challenges of the QUBO approach.
The growing demand in broadband and data networks is a tremendous driver for innovation and investment. Efficient usage of resources and reliable operations are key objectives for network management. Optimization plays a pivotal role to make the best decisions in limited time. To tackle such difficult and elaborate (typically NP-hard) computational problems the latest developments in Quantum Computing are coming into focus. Successes with models for road traffic, logistics or financial industry have already demonstrated the applicability of these new methods to real-world problems. In this paper we formulate a model for resource assignment for transporting data over networks. For applicability in existing network management environments the model was designed on top of Segment Routing (SR) concepts. The validity of the model is proven for different cost and reliability targets. Based on a Digital Annealer (DA) as quantum-inspired hardware and an appropriate decomposition approach realistic data sets of a tier-1 provider can be processed. The quality of the results is comparable to classical optimization methods while the new approaches outperform those in computation time and have potential for a higher number of demands. An end-to-end comparison of quadratic model creation and solving on large data sets versus a processing as linear integer problem is presented. This shows that quantum approaches and algorithms are not only a preparation for a more distant future of fully functional quantum computers but can generate business advantages even today.
Optimization problems are fundamental in a wide range of fields, including telecommunications, where efficient resource allocation is critical to ensure good network performance and high scalability. In the context of elastic optical networks (EONs), the multi-objective routing and spectrum assignment (MO-RSA) problem represents a key challenge, as it involves selecting a valid path and assigning frequency slots while fulfilling continuity and contiguity constraints and optimizing multiple conflicting objectives. This paper presents a novel, to the best of our knowledge, quantum-based approach to solving the MO-RSA problem. We first formulate the MO-RSA problem as a quadratic unconstrained binary optimization (QUBO) problem and then solve it using the quantum approximate optimization algorithm (QAOA). Our method accounts for both minimizing the total number of used links (or any non-negative additive metric) and maximizing the optical signal-to-noise ratio. For our simulations, we employed the Qiskit framework and IBM’s sampler-based quantum backend to implement and test the proposed approach. Our results demonstrate that by encoding the MO-RSA problem into a QUBO model and optimizing it with QAOA, we achieved an approximation ratio of 88% and a computational complexity of O ( n 2 ) , which represents a significant improvement over the exponential complexity of traditional integer linear programming methods.
Networks are frequently changing due to new technologies. The growing demand for bandwidth is forcing many carriers to migrate their existing network to a network with a new technology in order to increase network performance. Telecommunication companies are looking for optimization algorithms to efficiently manage their network migration. In this paper, the network migration problem is considered as a set of circuit migration problems in which two technicians simultaneously migrate the two ends of a circuit in order to minimize the total accumulated sites in-service and total technician travels. While total accumulated sites in-service indicates how fast the sites can be upgraded during the migration process, total technician travels estimates the required cost. We first formulate our target problem as a constrained binary quadratic program which is NP-hard in general. Our approach for solving the derived optimization problem is based on converting it to a quadratic unconstrained binary optimization problem (QUBO) using the penalty method. Subsequently, we exploit Digital Annealer which is a massively parallel hardware architecture to minimize the derived QUBO. To evaluate our proposed method, we study extensive network migration instances on the 75-node CONUS network topology.