2025 AIChE Annual Meeting

(392bh) Quadratic Knapsack Problem: A Qubo-Based Approach for Optimal Sensor Placement in Water Distribution Networks

Authors

The Quadratic Knapsack Problem (QKP) arises in various combinatorial optimization applications, including optimal sensor placement in water distribution networks (WDNs) for real-time monitoring and anomaly detection, network interdiction problems, and VLSI design [1]. Traditional mixed-integer programming (MIP) approaches effectively solve these problems but often struggle with scalability [2]. To address this, we explore the formulations of quadratic unconstrained binary optimization (QUBO), utilizing recent advances in quantum and classical optimization algorithms [3, 4]. For instance, network interdiction problems naturally result in a QKP, where interdiction decisions exhibit nonlinear interactions—removing multiple network components can have a synergistic effect on disruption. These interactions are captured in the quadratic terms of the optimization model, making QKP a suitable framework for formulating interdiction as a QUBO problem.

We formulate the WDN sensor placement problem as an MIP (refer eq. 1), where the objective function minimizes the placement cost and accounts for network coverage constraints. In eq. 1, xᵢ is a binary variable that takes values in the set {0, 1}ⁿ, cᵢ refers to the cost of placing a sensor at a node i of the WDN, wᵢⱼ is the weight matrix and refers to the cost of not placing a sensor adjacent to the edge connecting two nodes i and j and is given by eq. 2 . The predefined s determines the total number of sensors.

To reformulate the MIP into a QUBO, the constraint is penalized and incorporated into the objective function. In eq. 3, λ refers to a positive scalar penalty constant. QUBO is particularly important because quantum annealers, such as those developed by D-Wave [5] and variational quantum algorithms (VQA) in gate-based quantum computers [6], naturally solve optimization problems formulated as Ising spin models [3]. Using the QUBO formulation, we can directly map combinatorial optimization problems onto quantum hardware.

To evaluate the performance of our QUBO-based approach, we benchmark different classical and quantum optimization solvers, comparing the best objective solution and time to target (TT) for feasible (TT_Feasible) and optimal (TT_Best) solutions. TT integrates the probability of finding a solution and the required time, making it a relevant metric for sampling-based algorithms like simulated and quantum annealing. Table 1 summarizes the results obtained for different WDNs, highlighting the limitations of the QUBO-based approach, particularly in quantum annealing and hybrid quantum-classical methods. To address this, we derive an analytical lower bound for λ. Specifically, for any λ ≥ max{max{|cᵢ|}, max{2|wᵢⱼ|} : i, j ∈ [n]}, eq. 1 can be reformulated as the QUBO problem in eq. 2 [7]. This approach enhances the performance of the QUBO reformulation when using quantum annealers and hybrid quantum-classical solvers.
Recent advancements in VQA (QAOA [6]) show promising results for solving QKP on gate-based quantum devices. The use of GPUs and decomposition methods, especially through optimized frameworks such as NVIDIA CUDA-Quantum, enhances scalability for solving QUBOs, enabling solutions to larger, more complex QKP instances.References
[1] Valentina Cacchiani, Manuel Iori, et al. Knapsack problems — an overview of recent advances. part
ii: Multiple, multidimensional, and quadratic knapsack problems. Computers Operations Research,
143:105693, 2022.
[2] F. Hooshmand, F. Amerehi, et al. Logic-based benders decomposition algorithm for contamination
detection problem in water networks. Computers and Operations Research, 115, March 2020.
[3] Naeimeh Mohseni, Peter L. McMahon, et al. Ising machines as hardware solvers of combinatorial opti-
mization problems, 2022.
[4] David E. Bernal Neira, Carl D. Laird, et al. Utilizing modern computer architectures to solve mathe-
matical optimization problems: A survey. Computers Chemical Engineering, 184:108627, 2024.
[5] D-Wave Systems Inc. D-Wave Leap Quantum Cloud Service, 2024.
[6] Edward Farhi, Jeffrey Goldstone, et al. A quantum approximate optimization algorithm, 2014.
[7] Rodolfo A Quintero and Luis F Zuluaga. Characterizing and Benchmarking QUBO Reformulations of
the Knapsack Problem, 2021.
[8] Kentucky Water Resources Research Institute, University of Kentucky. Water Distribution System
Research Database, 2016.