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.
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.
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.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. How- ever, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transfor- mations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated An- nealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total num- ber of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
The cardinality constrained index-tracking problem seeks to find a combination of financial assets to replicate the return of a broad market index while using only a small subset of the asset universe. However, finding this combination of assets is NP-hard. In this thesis, we show the computational efficacy of solving a quadratic unconstrained binary optimization (QUBO) problem using purpose-built hardware Digital Annealer. We express an intra-cluster distance minimization problem as a QUBO problem and examine the computational performance between Digital Annealer and a commercial solver Gurobi running on conventional hardware. Moreover, we develop a new framework to solve the cardinality constrained index-tracking problem using the quadratic k-medoids clustering method on a market graph. To circumvent the nature of NP-hardness, we use the penalty method to formulate the problem as a QUBO problem, allowing us to utilize purpose-built hardware to solve the problem.
Recent advances in quantum computing have shown great potential for solving combinatorial optimization problems. A notable example is the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum-inspired algorithms require Quadratic Unconstrained Binary Optimization (QUBO) formulations. Transforming constrained optimization into QUBO impacts the algorithms' speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess them by using Simulated Annealing (SA), and find that three of our approaches outperform existing methods in terms of execution time as well as quality and quantity of feasible solutions found. Also, we tested these transformations on a quantum annealer, which was unable to solve even small instances, due to limitations in connectivity and error rates. In general, our results highlight the advantages of the new approaches, which reduce the number of variables in the QUBO representation.