Source-linked AI summary
Quantum Computing based Hybrid Solution Strategies for Large-scale Discrete-Continuous Optimization Problems
Akshay Ajagekar, Travis Humble, Fengqi You
TL;DR
Large-scale mixed-integer optimization is computationally challenging for classical deterministic methods, while current quantum systems are limited in large-scale optimization. The paper proposes hybrid QC-based strategies that combine exact classical techniques with quantum approaches and demonstrates them across four applications. The authors report that these hybrid algorithms outperformed general-purpose state-of-the-art exact solvers on large-scale mixed-integer optimization problems, with a clear quantum advantage perceived relative to small-scale cases.
Problem
Large-scale mixed-integer optimization is computationally challenging because classical methods face combinatorial growth, while current quantum hardware and algorithms remain inadequate for large-scale problems.
Method
The paper develops hybrid QC-based solution strategies that combine exact classical techniques with quantum methods across molecular conformation, job-shop scheduling, manufacturing cell formation, and vehicle routing.
Results
The proposed hybrid QC-based algorithms clearly outperformed general-purpose state-of-the-art exact solvers on large-scale mixed-integer optimization problems, while a clear quantum advantage was perceived over small-scale cases.
Takeaways & Limitations
Hybrid QC-based strategies demonstrated applicability across large-scale mixed-integer optimization applications spanning molecular design, scheduling, manufacturing, and routing.
Takeaways & Limitations
Increasing allotted physical memory can be disproportionate to expected improvement for the manufacturing cell formation problem, and its best solution remained more than 34% from optimal after 24 hours.
Abstract
from arXiv · showhide
Quantum computing (QC) has gained popularity due to its unique capabilities that are quite different from that of classical computers in terms of speed and methods of operations. This paper proposes hybrid models and methods that effectively leverage the complementary strengths of deterministic algorithms and QC techniques to overcome combinatorial complexity for solving large-scale mixed-integer programming problems. Four applications, namely the molecular conformation problem, job-shop scheduling problem, manufacturing cell formation problem, and the vehicle routing problem, are specifically addressed. Large-scale instances of these application problems across multiple scales ranging from molecular design to logistics optimization are computationally challenging for deterministic optimization algorithms on classical computers. To address the computational challenges, hybrid QC-based algorithms are proposed and extensive computational experimental results are presented to demonstrate their applicability and efficiency. The proposed QC-based solution strategies enjoy high computational efficiency in terms of solution quality and computation time, by utilizing the unique features of both classical and quantum computers.
2 Quantum Computing Institute, Oak Ridge National Laboratory, Oak Ridge, Tennessee 37831, USA
The paper concerns quantum computing and hybrid techniques for optimization, including molecular design, scheduling, supply chain, and logistics optimization.
- The paper focuses on quantum computing and hybrid techniques for optimization.
- Applications include molecular design and scheduling.
- The scope also includes supply chain and logistics optimization.
1. Introduction
Large-scale mixed-integer and discrete-continuous optimization remains difficult because classical methods face growing subproblems, search spaces, and computational demands. The paper develops hybrid quantum-classical strategies that combine exact techniques with quantum search across four application domains.
- Problem and motivation: Large-scale nonconvex MINLP problems remain computationally expensive for state-of-the-art deterministic global optimization algorithms.
- Problem and motivation: Deterministic methods face growing subproblems and exponential branch-and-bound trees, requiring enumeration of more feasible alternatives.
- Problem and motivation: Combinatorial optimization becomes more time-consuming as complexity and search spaces grow, while Moore’s-law saturation limits expected classical processing-speed gains.
- Quantum-computing constraints: Current quantum hardware and algorithms are inadequate for large-scale optimization because available machines have limited qubits, connectivity, and quantum memory.
- Proposed approach: The paper develops hybrid QC-based models combining complementary quantum and exact-solution strengths to address large-scale discrete-continuous combinatorial complexity.
- Applications and contributions: Applicability is demonstrated across molecular design, process scheduling, manufacturing operations, and vehicle routing using BQP, MILP, MIQP, and IQFP formulations.
2. Background on Quantum Computing for Optimization
Quantum computing uses qubits, superposition, and entanglement, with gate-model and annealing-based architectures offering different operating principles. The paper focuses on annealing-based optimization while addressing current hardware and embedding constraints.
- Quantum computing foundations: Qubits can occupy superposition states and form entangled states, distinguishing quantum computers from classical-bit computation.
- Quantum architectures: Gate-model computers sequentially apply quantum gates to evolve qubit states, whereas annealing-based computers intrinsically implement quantum annealing.
- Quantum annealing: Quantum annealing uses tunneling to explore low-cost solutions and drives the system toward the ground state of a problem Hamiltonian.
- Hardware limitations: Commercial quantum computers remain rudimentary, with limited qubit counts, poor error correction, decoherence, and limited quantum control.
- Quantum architectures: Annealing-based devices are designed explicitly for optimization and are described as more reliable for optimization problems than gate-model devices.
- Quantum annealing implementation: D-Wave optimization problems must be formulated as Ising or QUBO models and mapped onto hardware through minor-embedding.
- Quantum annealing implementation: The probability of recovering a global optimum depends strongly on the graph embedding and annealing schedule.
3. Overview of Quantum Optimization Application Domains
The paper applies hybrid quantum-classical optimization strategies to four domains spanning molecular design, manufacturing, scheduling, and logistics. These applications increase in complexity and are evaluated through computational experiments using classical and quantum resources.
- Application scope: Four applications are studied: molecular conformation, job-shop scheduling, manufacturing cell formation, and vehicle routing.
- Application scope: The applications span molecular design, process operations, and supply-chain and logistics optimization, with complexity arranged to increase successively.
- Molecular conformation: Molecular conformation supports molecular design and has implications for drug design and product design.
- Scheduling and manufacturing: Job-shop scheduling is a notoriously difficult combinatorial optimization problem underlying practical production-scheduling problems.
- Scheduling and manufacturing: Cell formation is an important component of cellular manufacturing and is relevant to manufacturing industries and engineering management.
- Vehicle routing: The vehicle routing problem is a well-studied logistics problem with many real-world applications and is treated here in a nonlinear formulation.
- Scope of hybrid methods: The proposed hybrid algorithms are not limited to the listed examples and can extend to other practically relevant real-world problems.
- Computational evaluation: Experiments combine a classical backend with a D-Wave 2000Q processor using 2,048 qubits and 5,600 couplers.
4. QC for Molecular Conformations in Molecular/Product Design
The molecular conformation problem is modeled on a discrete cubic lattice and solved with hybrid QC techniques to obtain efficient approximate solutions and starting points for continuous optimization. Results show strong performance on larger instances, while discretization and heuristic search limit guarantees of global optimality.
- Motivation: Molecular conformation supports molecular design applications, including determining folded states from amino-acid sequences, but larger molecules challenge existing methods.Heuristics can be computationally expensive, parameter-sensitive, and lack global-optimum guarantees; exact methods may perform poorly as molecule size increases.
- Hybrid QC Method: The hybrid QC partitioning approach solves the discretized molecular problem efficiently and searches for configurations near the global minimum.Quantum annealing addresses QUBO subproblems within a hybrid strategy, while the discretized solution can initialize continuous-domain global minimization.
- Model Formulation: The model places B bead atoms on a 3-dimensional cubic lattice with N sites, where N ≥ B, and assigns each bead to a lattice location.Binary variables encode bead-to-site assignments, while bond lengths, pairwise potentials, and placement penalties define the optimization model.
- Computational Results: For butane, the discretized model obtains a gauche global optimum, whereas the anti conformation is the global optimum of the continuous nonlinear problem.The discrepancy results from simplifying assumptions in the discretized model; the gauche conformer remains more stable than other eclipsed configurations.
- Computational Results: The hybrid QC approach is competitive in numerical results and superior in computation time for the reported molecular conformation experiments.Its solutions lie within a local neighborhood of the global minimum and can provide an upper bound and starting point for continuous optimization.
- Limitations and Use: Because the hybrid partitioning approach is heuristic, it does not always guarantee the lowest-energy solution.Its supported role is therefore as a good-quality approximate solution, upper bound, or initialization when short computation times are preferred.
5. QC for Job-shop Scheduling
Job-shop scheduling is a difficult large-scale MILP problem whose combinatorial structure challenges classical solvers. The proposed hybrid QC-MILP decomposition combines deterministic optimization with quantum global optimization to obtain optimal solutions for large instances.
- Large and complex search spaces make job-shop scheduling computationally challenging, while heuristics may fail to find high-quality solutions at large scales.
- Job-shop scheduling assigns jobs to machines under operational, scheduling, and logic constraints while minimizing total processing cost.
- The MILP model uses start-time, machine-assignment, and sequencing variables, with constraints enforcing release dates, due dates, assignments, and machine order.
- The hybrid QC-MILP decomposition combines deterministic decomposition with QC-based global optimization for large-scale MILP scheduling.
- The method converges to an optimal solution or proves infeasibility in a finite number of iterations.
- For 150 jobs and 150 machines, the MILP contains 150 continuous variables, 44,850 binary variables, and 126,579,825 constraints.
- The hybrid method produces optimal schedules competitively with Gurobi and handles larger problems without physical memory augmentation, but with reasonably longer runtimes.
- Gurobi returns no solution beyond 70-job, 70-machine instances because its branch-and-bound tree exceeds physical memory, whereas the hybrid method solves each within reasonable time.
6. QC for Manufacturing Cell Formation
Manufacturing cell formation is a large-scale MIQP problem involving part-machine grouping and nonlinear costs. The proposed QC-MIQP stepwise decomposition combines a dual LP with quantum optimization and improves scalability relative to Gurobi.
- 6. QC for Manufacturing Cell Formation: Manufacturing cell formation assigns parts and machines to cells to improve internal interactions and minimize costs associated with intracellular movement and resource underutilization.
- 6. QC for Manufacturing Cell Formation: The problem is NP-hard, and exact methods can require considerable time to obtain global optima for large instances.
- 6.1. Model Formulation: The formulation assumes known operational requirements, permits any machine-cell assignment, omits cell capacity limits, and allows empty cells.
- 6.1. Model Formulation: The MIQP assigns continuous part-to-cell variables and binary machine-to-cell variables while allowing alternate routings.
- 6.2. Hybrid QC-MIQP Stepwise Decomposition Method: The QC-MIQP stepwise decomposition uses Benders decomposition, replaces quadratic terms through a dual LP, and iteratively generates upper and lower bounds from smaller subproblems.
- 6.2. Hybrid QC-MIQP Stepwise Decomposition Method: The hybrid method combines the deterministic dual LP with a quantum step and yields an optimal solution for manufacturing cell formation.
- 6.3. Computational Results: The hybrid method outperforms Gurobi in solution quality and computation time for medium- to large-size instances.
- 6.3. Computational Results: Beyond 500 binary variables, Gurobi performance deteriorates, while the hybrid method obtains optimal or near-optimal solutions with almost half the time on larger instances.
7. QC for Vehicle Routing
Vehicle routing is an NP-hard logistics optimization problem with fractional, quadratic objectives and operational constraints. The proposed QC-IQFP parametric method combines inexact deterministic optimization with quantum computing to obtain competitive large-scale solutions.
- Vehicle routing determines routes for vehicles serving customers while minimizing transportation cost and satisfying operational constraints.
- Vehicle routing is NP-hard and can require sophisticated solution strategies because of its challenging formulation.
- Real-world routing often involves hundreds of locations, motivating approximate methods that deliver high-quality solutions within reasonable computation times.
- The quadratic vehicle-flow formulation reduces the number of constraints and models travel cost separately from working time in a fractional objective.
- The model requires each customer to be visited exactly once and enforces route continuity, while assuming no vehicle capacity restrictions.
- The QC-IQFP parametric method exploits inexact deterministic optimization and converges to a global optimum within a finite number of iterations.
- The method obtains high-quality solutions within reasonable times and uses less computation than Bonmin and BARON.
- For larger instances, Bonmin and BARON fail to find optimal solutions after 24 hours, while the hybrid method obtains a near-optimal solution within 10 hours.
8. Conclusions
The paper proposes hybrid quantum-computing strategies for large-scale mixed-integer optimization and demonstrates them across four practical application problems. These strategies outperformed general-purpose exact solvers on large-scale problems, while exact solvers remained efficient for small-scale instances.
- Hybrid QC-based solution strategies were proposed for large-scale mixed-integer optimization problems.
- The applicability of the strategies was demonstrated on molecular conformation, job-shop scheduling, manufacturing cell formation, and vehicle routing problems.
- The molecular conformation problem was reformulated as QUBO and solved using hybrid QC partitioning, while job-shop scheduling used hybrid QC-MILP decomposition.
- Manufacturing cell formation used hybrid QC-MIQP stepwise decomposition, and vehicle routing used a hybrid QC-IQFP parametric method.
- The proposed hybrid QC-based algorithms clearly outperformed general-purpose state-of-the-art exact solvers on large-scale mixed-integer optimization problems.
- Exact solvers were efficient for small-scale problems, whereas hybrid QC techniques showed a clear quantum advantage for large-scale optimization problems.
- Performance was independent of the annealing-based QC device used and may improve as such devices become more scalable.
Nomenclature
The nomenclature defines variables, parameters, and sets for molecular conformation, job-shop scheduling, manufacturing cell formation, and vehicle routing formulations.
- Molecular conformation: Molecular conformation notation includes potential-energy terms, bond length, interatomic distances, and binary atom-location variables.
- Molecular conformation: The molecular conformation binary variable xij indicates whether atom i is placed at location j.
- Job-shop scheduling: Job-shop scheduling notation includes jobs, processing costs and times, due and release dates, machine assignments, job order, and start times.
- Job-shop scheduling: The job-shop scheduling variable yij denotes whether job j is processed after job i on the same machine, while tsi denotes job i's start time.
- Manufacturing cell formation: Manufacturing cell formation notation covers cells, part-machine requirements, movement and nonutilization costs, operations, production volume, and assignments.
- Manufacturing cell formation: Manufacturing cell assignments use yjk for machine-to-cell placement and xik for part-to-cell processing.
- Vehicle routing: Vehicle routing notation defines vehicles, route steps, locations, travel costs, working time, and vehicle-location-step visit variables.