Advanced Quantum Annealing for the Bi-Objective Traveling Thief Problem: An $\varepsilon$-Constraint-based Approach

• URL: http://arxiv.org/abs/2603.18038v1
• Date: Fri, 13 Mar 2026 05:26:25 GMT
• Title: Advanced Quantum Annealing for the Bi-Objective Traveling Thief Problem: An $\varepsilon$-Constraint-based Approach
• Abstract summary: Bi-Objective Traveling Thief Problem (BI-TTP) requires the simultaneous optimization of travel cost and item profit.<n> Conventional methods for the BI-TTP often face severe scalability issues due to the complex interdependence between routing and packing decisions.<n>We propose an advanced hybrid approach that combines quantum annealing (QA) with the $varepsilon$-constraint method.
• Score: 7.06690496634166
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper addresses the Bi-Objective Traveling Thief Problem (BI-TTP), a challenging multi-objective optimization problem that requires the simultaneous optimization of travel cost and item profit. Conventional methods for the BI-TTP often face severe scalability issues due to the complex interdependence between routing and packing decisions, as well as the inherent complexity and large problem size. These difficulties render classical computing approaches increasingly inapplicable. To tackle this, we propose an advanced hybrid approach that combines quantum annealing (QA) with the $\varepsilon$-constraint method. Specifically, we reformulate the bi-objective problem into a single-objective formulation by restricting the second objective through adjustable $\varepsilon$-levels, determined within established upper and lower bounds. The resulting subproblem involves a sum of fractional terms, which is reformulated with auxiliary variables into an equivalent form. Subsequently, the equivalent formulation is transformed into a Quadratic Unconstrained Binary Optimization (QUBO) model, enabling direct solution via a quantum annealing (QA) solver. The solutions obtained from the quantum annealer are subsequently refined using a tailored heuristic procedure to further enhance overall performance. By leveraging the flexibility in selecting $\varepsilon$ parameters, our approach effectively captures a broad Pareto front, enhancing solution diversity. Experimental results on benchmark instances demonstrate that the proposed method effectively balances two objectives and outperforms baseline approaches in time efficiency.

Related papers

• Quantum Preconditioning For Constrained Optimization Problems [0.0]
  We study the effect of quantum preconditioning on constrained optimization problems.<n>The proposed approach uses two-point correlations between decision variables to construct a modified objective function.<n>Experiments on dense, weighted complete-graph instances show that the preconditioned problem instances reach near-optimal solutions faster.
  arXiv  Detail & Related papers  (2026-08-28T20:23:37Z)
• A Hybrid Classical-Quantum Approach for Multi-Constrained Location Optimization Problem [0.19573380763700712]
  The Maximal Covering Location Problem (MCLP) aims to determine the optimal facility placements that maximize total coverage.<n>It is characterized by both equality and inequality constraints, which ensure correct coverage but significantly increase the complexity of exploring the solution space as instance size grows.<n>In this work, the MCLP is formulated as a Quadratic Unconstrained Binary Optimization model, where constraint embedding plays a critical role in solution quality.
  arXiv  Detail & Related papers  (2026-07-08T19:44:55Z)
• Pure and mixed Dicke state ansatz for equality and inequality constraints in variational quantum eigensolver [0.0]
  Combinatorial optimization can be addressed with quantum computing through variational quantum algorithms.<n>A central challenge is to design an ansatz expressive enough to explore the feasible subspace of the Hilbert space where the optimal solution lies.<n>We propose the first feasibility-preserving mixed Dicke state ansatz for Hamming weight constrained optimization.
  arXiv  Detail & Related papers  (2026-06-07T08:10:09Z)
• CVaR-Assisted Custom Penalty Function for Constrained Optimization [3.652509571098291]
  Constrained optimization problems are frequently reformulated as quadratic unconstrained binary optimization (QUBO) models.<n>Standard QUBO formulations enforce inequality constraints through slack variables and quadratic penalties.<n>We propose a slack-free penalty formulation for constrained binary optimization that eliminates auxiliary slack variables.
  arXiv  Detail & Related papers  (2026-04-22T01:08:38Z)
• A Framework for Combining Optimization-Based and Analytic Inverse Kinematics [53.66628333687382]
  Twolytic and optimization methods for inverse kinematics (IK) problems have been deeply studied in the history of robotics.<n>We present a new formulation for IK avoidance that uses an IK solution that is fundamentally easier for ours to solve.
  arXiv  Detail & Related papers  (2026-02-04T22:23:32Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex.<n>Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs.<n>We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• Two-Step QAOA: Enhancing Quantum Optimization by Decomposing K-hot Constraints in QUBO Formulations [0.0]
  Two-Step QAOA aims to improve the effectiveness of QAOA by decomposing problems with k-hot encoding QUBO formulations.<n>We transform soft constraints into hard constraints, simplifying the generation of initial conditions.
  arXiv  Detail & Related papers  (2024-08-09T23:38:28Z)
• Optimized QUBO formulation methods for quantum computing [0.4999814847776097]
  We show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario. We follow by submitting instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios.
  arXiv  Detail & Related papers  (2024-06-11T19:59:05Z)
• Lagrangian Duality in Quantum Optimization: Overcoming QUBO Limitations for Constrained Problems [0.0]
  We propose an approach to solving constrained optimization problems based on embedding the concept of Lagrangian duality into the framework of adiabatic quantum computation. Within the setting of circuit-model fault-tolerant quantum computation, we demonstrate that this approach achieves a quadratic improvement in circuit depth and maintains a constraint-independent circuit width.
  arXiv  Detail & Related papers  (2023-10-06T19:09:55Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  We present an alternative method that does not require extra slack variables. We evaluate our approach on the traveling salesman problem, the bin packing problem, and the knapsack problem. This new approach can be used to solve problems with inequality constraints with a reduced number of resources.
  arXiv  Detail & Related papers  (2022-11-25T06:05:18Z)
• A Study of Scalarisation Techniques for Multi-Objective QUBO Solving [0.0]
  Quantum and quantum-inspired optimisation algorithms have shown promising performance when applied to academic benchmarks as well as real-world problems. However, QUBO solvers are single objective solvers. To make them more efficient at solving problems with multiple objectives, a decision on how to convert such multi-objective problems to single-objective problems need to be made.
  arXiv  Detail & Related papers  (2022-10-20T14:54:37Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs. A new dual approach is proposed with the integration of two ingredients: entropy regularized policy and Vaidya's dual. The proposed approach is shown to converge (with linear rate) to the global optimum.
  arXiv  Detail & Related papers  (2022-06-03T16:26:38Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  We study optimization of areas under precision-recall curves (AUPRC), which is widely used for imbalanced tasks. We develop novel momentum methods with a better iteration of $O (1/epsilon4)$ for finding an $epsilon$stationary solution. We also design a novel family of adaptive methods with the same complexity of $O (1/epsilon4)$, which enjoy faster convergence in practice.
  arXiv  Detail & Related papers  (2021-07-02T16:21:52Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.