Search-based software engineering (SBSE) tackles critical optimization problems in software engineering, including the next release problem (NRP) and feature selection problem (FSP). Traditional heuristic approaches and integer linear programming (ILP) methods work well for small- to medium-scale problems but face growing computational cost as instances scale up. We investigate quantum annealing (QA) as an optimization subroutine for multi-objective SBSE problems. We propose two QA-based algorithms tailored to different problem scales. For small-scale problems, we reformulate multi-objective optimization (MOO) as single-objective optimization (SOO) using penalty-based mappings for quantum processing. For large-scale problems that exceed current hardware capacity, we employ a decomposition strategy guided by maximum energy impact (MEI) that partitions the problem into smaller sub-QUBOs, integrating QA with a steepest-descent method for local search. Applied to NRP and FSP, our approaches are benchmarked against the heuristic NSGA-II, IBEA, and MOEA/D, as well as the ILP-based ϵ-constraint method. The experimental results reveal that while our methods produce fewer non-dominated solutions than ϵ-constraint, they achieve substantial reductions in execution time. Compared to the evolutionary baselines, our methods achieve competitive solution quality with lower runtime on the instances that they can encode. The penalty-based QUBO formulation fails to reach feasible regions on constraint-dense FSP instances, limiting the current applicability of the approach. QA is a promising but still hardware-limited component for multi-objective SBSE workflows, rather than a wholesale replacement for classical solvers.
Search-based software engineering (SBSE) tackles critical optimization problems in software engineering, including the next release problem (NRP) and feature selection problem (FSP). Traditional heuristic approaches and integer linear programming (ILP) methods work well for small- to medium-scale problems but face growing computational cost as instances scale up. We investigate quantum annealing (QA) as an optimization subroutine for multi-objective SBSE problems. We propose two QA-based algorithms tailored to different problem scales. For small-scale problems, we reformulate multi-objective optimization (MOO) as single-objective optimization (SOO) using penalty-based mappings for quantum processing. For large-scale problems that exceed current hardware capacity, we employ a decomposition strategy guided by maximum energy impact (MEI) that partitions the problem into smaller sub-QUBOs, integrating QA with a steepest-descent method for local search. Applied to NRP and FSP, our approaches are benchmarked against the heuristic NSGA-II, IBEA, and MOEA/D, as well as the ILP-based ϵ-constraint method. The experimental results reveal that while our methods produce fewer non-dominated solutions than ϵ-constraint, they achieve substantial reductions in execution time. Compared to the evolutionary baselines, our methods achieve competitive solution quality with lower runtime on the instances that they can encode. The penalty-based QUBO formulation fails to reach feasible regions on constraint-dense FSP instances, limiting the current applicability of the approach. QA is a promising but still hardware-limited component for multi-objective SBSE workflows, rather than a wholesale replacement for classical solvers.
Search-based software engineering (SBSE) addresses critical optimization challenges in software engineering, including the next release problem (NRP) and feature selection problem (FSP). While traditional heuristic approaches and integer linear programming (ILP) methods have demonstrated efficacy for small to medium-scale problems, their scalability to large-scale instances remains unknown. Here, we introduce quantum annealing (QA) as a subroutine to tackling multi-objective SBSE problems, leveraging the computational potential of quantum systems. We propose two QA-based algorithms tailored to different problem scales. For small-scale problems, we reformulate multi-objective optimization (MOO) as single-objective optimization (SOO) using penalty-based mappings for quantum processing. For large-scale problems, we employ a decomposition strategy guided by maximum energy impact (MEI), integrating QA with a steepest descent method to enhance local search efficiency. Applied to NRP and FSP, our approaches are benchmarked against the heuristic NSGA-II and the ILP-based ε-constraint method. Experimental results reveal that while our methods produce fewer non-dominated solutions than ε-constraint, they achieve significant reductions in execution time. Moreover, compared to NSGA-II, our methods deliver more non-dominated solutions with superior computational efficiency. These findings underscore the potential of QA in advancing scalable and efficient solutions for SBSE challenges.
This paper explores the applications of quantum annealing (QA) and classical simulated annealing (SA) to a suite of combinatorial optimization problems in machine learning, namely feature selection, instance selection, and clustering. We formulate each task as a Quadratic Unconstrained Binary Optimization (QUBO) problem and implement both quantum and classical solvers to compare their effectiveness. For feature selection, we propose several QUBO configurations that balance feature importance and redundancy, showing that quantum annealing (QA) produces solutions that are computationally more efficient. In instance selection, we propose a few novel heuristics for instance-level importance measures that extend existing methods. For clustering, we embed a classical-to-quantum pipeline, using classical clustering followed by QUBO-based medoid refinement, and demonstrate consistent improvements in cluster compactness and retrieval metrics. Our results suggest that QA can be a competitive and efficient tool for discrete machine learning optimization, even within the constraints of current quantum hardware.
We investigate the use of quantum computing algorithms on real quantum hardware to tackle the computationally intensive task of feature selection for light-weight medical image datasets.Feature selection is often formulated as a k of n selection problem, where the complexity grows binomially with increasing k and n.Quantum computers, particularly quantum annealers, are well-suited for such problems, which may offer advantages under certain problem formulations.We present a method to solve larger feature selection instances than previously demonstrated on commercial quantum annealers.Our approach combines a linear Ising penalty mechanism with subsampling and thresholding techniques to enhance scalability.The method is tested in a toy problem where feature selection identifies pixel masks used to reconstruct small-scale medical images.We compare our approach against a range of feature selection strategies, including randomized baselines, classical supervised and unsupervised methods, combinatorial optimization via classical and quantum solvers, and learning-based feature representations.The results indicate that quantum annealing-based feature selection is effective for this simplified use case, demonstrating its potential in high-dimensional optimization tasks.However, its applicability to broader, real-world problems remains uncertain, given the current limitations of quantum computing hardware.While learned feature representations such as autoencoders achieve superior reconstruction performance, they do not offer the same level of interpretability or direct control over input feature selection as our approach.
Industrial optimization challenges, such as the pooling and blending problem (PBP), require advanced computational methods to address non-convexity and scalability limitations in classical solvers. This work introduces a novel methodological framework for solving PBPs using quantum annealing (QA) that transforms the PBP into quadratic unconstrained binary optimization (QUBO) formulations at two resolution levels, enabling direct deployment on quantum annealers. Key innovations include a discretization technique tailored for PBP’s bilinear constraints and an embedding method optimized for current quantum hardware. Benchmarking against classical solvers focuses on Haverly’s classical three-stream PBP, enabling transparent comparison and development of quantum embedding and solution techniques. The proposed framework offers a scalable template for adapting similar engineering systems to quantum annealing architectures. Addressing genuine industrial-scale instances will require future advances in quantum hardware and embedding algorithms. The results demonstrate that QA exhibits the best performance among the examined alternatives, provide foundational insights towards leveraging QA in Process Systems Engineering.
We investigate the use of quantum computing algorithms on real quantum hardware to tackle the computationally intensive task of feature selection for light-weight medical image datasets. Feature selection is often formulated as a k of n selection problem, where the complexity grows binomially with increasing k and n. Quantum computers, particularly quantum annealers, are well-suited for such problems, which may offer advantages under certain problem formulations. We present a method to solve larger feature selection instances than previously demonstrated on commercial quantum annealers. Our approach combines a linear Ising penalty mechanism with subsampling and thresholding techniques to enhance scalability. The method is tested in a toy problem where feature selection identifies pixel masks used to reconstruct small-scale medical images. We compare our approach against a range of feature selection strategies, including randomized baselines, classical supervised and unsupervised methods, combinatorial optimization via classical and quantum solvers, and learning-based feature representations. The results indicate that quantum annealing-based feature selection is effective for this simplified use case, demonstrating its potential in high-dimensional optimization tasks. However, its applicability to broader, real-world problems remains uncertain, given the current limitations of quantum computing hardware. While learned feature representations such as autoencoders achieve superior reconstruction performance, they do not offer the same level of interpretability or direct control over input feature selection as our approach.
Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic solutions for Ising models, which are equivalent to quadratic unconstrained binary optimization (QUBO). Constraints on solutions feasibility need to be properly encoded. We experiment on different ways of performing such an encoding. As benchmark we consider the cardinality constrained quadratic knapsack problem (CQKP), a minimal extension of QUBO with one inequality and one equality constraint. We consider different strategies of constraints penalization and variables encoding. We compare three QUBO solvers: quantum annealing on quantum hardware (D-Wave Advantage), probabilistic algorithms on digital hardware and mathematical programming solvers. We analyze their QUBO resolution quality and time, and the persistence values extracted in the quantum annealing sampling process. Our results show that a linear penalization of CQKP inequality improves current best practice. Furthermore, using such a linear penalization, persistence values produced by quantum hardware in a generic way allow to match a specific CQKP metric from literature. They are therefore suitable for general purpose variable fixing in core algorithms for combinatorial optimization.