💻 computer science

Residual-Guided Simulated Annealing for Multi-Dimensional Subset Sum

This paper introduces Residual-Guided Simulated Annealing (RGSA), a novel cardinality-preserving heuristic that consistently generates low-residual, near-feasible solutions for the multi-dimensional subset sum problem on QOBLIB instances with $m \ge 12$ , outperforming blind simulated annealing and QUBO samplers while providing a reproducible classical baseline where exact solvers remain impractical.

Original authors: Sreekuttan L S

Published 2026-10-01

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Sreekuttan L S

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of computer science, there is a class of puzzles known as the subset sum problem. Imagine you have a large collection of items, each with a specific weight, and you are asked to find a group of them that adds up to a precise target number. This task seems simple when there is only one target to hit, but the difficulty explodes when you must satisfy several different targets at the same time. This harder version is called the multi-dimensional subset sum problem, or in the research community, the "Market Split" problem. It asks a computer to divide a set of items into two groups so that the total weight of each group matches a specific set of goals across multiple categories simultaneously. These puzzles are not just academic exercises; they represent a fundamental challenge in optimization, testing the limits of how well computers can navigate complex landscapes of possibilities to find a perfect fit. For decades, researchers have struggled with these problems because the number of possible combinations grows so fast that even the most powerful supercomputers can get lost, unable to find the single perfect solution among billions of wrong turns.

A researcher named Sreekuttan L. S. from Bloq Quantum in India has recently tackled this challenge with a new approach designed not to find the perfect answer, but to get remarkably close to it when a perfect answer is out of reach. The study focuses on a specific set of difficult puzzles from a standard library used to test optimization methods. Instead of trying to solve the problem by checking every possibility, which is impossible for large sets, the researcher developed a method called Residual-Guided Simulated Annealing. To understand how this works, imagine you are trying to balance a scale with several different weights on it. If the scale is tipped to one side, you know exactly how much weight you are missing. This method uses that "missing amount," or the error, to guide its next move. When the computer decides to swap one item in its current group for another, it does not pick randomly. Instead, it calculates exactly what the new item needs to be to cancel out the error and then searches for the available item that comes closest to that ideal replacement. It is a smart, directional search that constantly corrects its course based on how far it is from the goal.

The researcher tested this new method against older, more random approaches and against several other powerful computer programs. The experiments were run on eight different versions of the Market Split puzzle, ranging from smaller, manageable sizes to a flagship version that is considered extremely difficult. In the first round of testing, the new method was pitted against a version that made random swaps without using the error to guide its choices. The results showed a clear advantage for the guided approach. On the most difficult test case, the random method left an average error of about 104 units, while the new guided method reduced that error to about 100 units. While this difference might seem small, in the context of these puzzles, it represents a significant improvement in finding a solution that is much closer to being perfect. The study also tested a full pipeline that included this guided method along with a few other supporting steps, which further lowered the error to about 100.37 units on average. Crucially, none of the runs in this initial phase found a perfect solution, but the guided method consistently produced results that were much closer to the target than the random attempts.

To see how this method held up in a broader competition, the researcher expanded the study to include a wider range of time limits and compared the new method against six other established solvers, including some that are designed to find exact answers. The tests were run with a strict time limit of 25 seconds. In this race, the new guided method proved to be highly reliable. While several of the other powerful solvers failed to return any usable answer within the time limit, the guided method consistently produced a result. When the time limit was extended to 300 seconds, the guided method continued to improve, reaching a median error of 36.54 units. In comparison, a method based on a different type of random search produced an error of 263.46 units, and another popular genetic algorithm settled at 72.27 units. The guided method was able to find a solution that was significantly closer to the target than its competitors, even though it did not claim to have found the perfect, exact answer.

The study makes a clear distinction between finding a perfect solution and finding a very good one. The researcher explicitly states that this method does not prove that a perfect solution exists or does not exist; it simply finds a solution that is very close to perfect. In the world of these puzzles, a "perfect" solution means the numbers match exactly, while a "near-feasible" solution means they are very close. The new method is excellent at finding these near-perfect solutions quickly. It acts as a powerful tool for getting a computer to a point where it is very close to the answer, which can then be used as a starting point for other methods that might eventually find the exact solution. The research highlights that for the most difficult versions of these puzzles, where exact solvers often run out of time or memory, this guided approach offers a reliable way to get very close to the goal in a matter of seconds.

The findings suggest that using the error in the calculation to guide the search is a highly effective strategy. By looking at what is missing and searching for the item that best fills that gap, the computer avoids the aimless wandering that characterizes older random methods. This approach does not replace the need for exact solvers when a perfect answer is required, but it provides a robust and transparent way to handle the hardest cases where exact methods struggle. The study concludes that for these specific types of difficult puzzles, the guided method consistently produces low-error results that are verified and reproducible. It offers a new baseline for how these problems can be approached, showing that even when a perfect solution is out of reach, a smart, guided search can get remarkably close, providing a valuable tool for researchers and engineers working with complex optimization challenges.

Technical Summary: Residual-Guided Simulated Annealing for Multi-Dimensional Subset Sum

Problem Definition
The paper addresses the Multi-Dimensional Subset Sum Problem, also known as the Market Split problem. Formally, given a matrix $A \in \mathbb{Z}_{\ge 0}^{m \times N}$ of attribute vectors and a target vector $b \in \mathbb{Z}_{\ge 0}^m$ , the goal is to find a binary vector $x \in \{0, 1\}^N$ such that $Ax = b$ . The problem is NP-complete even for $m=1$ . The specific instances evaluated are from the Quantum Optimization Benchmarking Library (QOBLIB), which features "deliberately small, hard" systems designed to expose weaknesses in general-purpose integer programming. These instances are characterized by dense positive coefficients and equality targets that leave little tolerance for locally plausible but globally inconsistent choices. The study focuses on the fixed-cardinality slice where the number of selected items is $q \approx N/2$ .

Methodology: Residual-Guided Simulated Annealing (RGSA)
The core contribution is Residual-Guided Simulated Annealing (RGSA), a cardinality-preserving local search heuristic. Unlike standard simulated annealing (SA) which often relies on blind random swaps, RGSA incorporates the current residual vector $\Delta = Ax - b$ to guide the search.

Geometric Swap Proposal: When an item $i$ is removed from the current set $S$ , the method calculates an "ideal compensator" vector $w^* = w_i - \Delta$ . It then searches the set of unselected items $\bar{S}$ for the vector $w_j$ that is geometrically nearest to $w^*$ in the $m$ -dimensional attribute space.
Hybrid Neighborhood: The algorithm mixes this guided proposal with a probability $p_g$ (set to 0.65 in experiments) and a uniform random swap with probability $1-p_g$ . This ensures exploration of the solution space even when the ideal compensator lies outside the observed point cloud.
Acceptance Rule: The method uses a Metropolis acceptance criterion based on the Euclidean residual norm $R(x) = \|Ax - b\|_2$ rather than its square, keeping temperature magnitudes interpretable.
Supporting Components:
- Lagrangian Warm Start: An optional initialization step using Lagrangian dual projection to generate a feasible cardinality partition before annealing begins.
- Deterministic Polishing: A post-processing phase involving exhaustive one-for-one and two-for-two exchanges to reach a local optimum within the examined neighborhoods.
- Full Pipeline: The combination of Lagrangian warm start, RGSA, and deterministic polishing is termed the "Full RGSA pipeline."

Experimental Setup
The study evaluates RGSA on 8 QOBLIB Market Split instances with dimensions $m \in \{9, \dots, 15\}$ and coefficient ranges $D \in \{50, 200\}$ . The evaluation is conducted in three stages:

Controlled Benchmark: 160 runs (8 instances $\times$ 4 configurations $\times$ 5 seeds) comparing RGSA variants against a "Blind SA" baseline.
25-Second Budget: A comparison involving 1,554 runs across 8 methods (RGSA variants, Blind SA, and 6 external solvers including SCIP, CP-SAT, pymoo GA, and a QUBO sampler) under a strict 25-second wall-clock limit.
300-Second Budget: A longer-duration experiment with intermediate checkpoints (25, 60, 120, 300s) to analyze convergence and availability.

Key Results

Residual Reduction: RGSA consistently lowers the Euclidean residual compared to Blind SA. On the flagship instance $(m=15, D=200)$ , the Full RGSA pipeline achieves a mean residual of 100.37, compared to 104.06 for RGSA alone and significantly higher values for Blind SA.
Comparison with External Solvers:
- Exact Solvers: Exact solvers (SCIP, CP-SAT) and linear programming surrogates (HiGHS) failed to return any feasible vector within the 25-second and 300-second budgets for these specific instances, resulting in 0% availability for valid incumbents in the 25-second window.
- Heuristics: At the 300-second mark, the Full RGSA pipeline achieved the lowest median residual of 36.54, outperforming the Champion RGSA configuration (guided SA without full polishing) at 38.00, and Blind SA at 42.25. The Champion configuration provided a stable anytime trajectory, while the Full pipeline reached a slightly lower endpoint residual.
- QUBO Sampler: A standard QUBO simulated-annealing sampler (Neal) performed poorly, with a median residual of 263.46, highlighting the benefit of the specific residual-guided geometry of RGSA.
Feasibility: No configuration in the study achieved exact feasibility ( $Ax=b$ ) on the tested instances within the time budgets. The study explicitly notes that 0/160 runs in the primary benchmark found exact solutions.

Significance and Claims
The paper positions RGSA not as a replacement for exact solvers, but as a transparent classical baseline and a candidate incumbent generator for hybrid search methods.

First Controlled Study: To the author's knowledge, this is the first controlled, multi-seed heuristic scaling study on QOBLIB Market Split classes with $m \ge 12$ .
Methodological Contribution: It introduces a specific, cardinality-preserving geometric swap heuristic that uses the residual equation itself to define the nearest-vector proposal, differing from previous penalty-based or single-variable jump methods.
Practical Utility: RGSA produces low-residual, near-feasible assignments in seconds at the $m=15$ frontier, where exact solvers are currently impractical. These results provide a "reproducible classical baseline" and a starting point for exact or hybrid search, rather than proving infeasibility.
Modesty: The author emphasizes that the results are descriptive. A nonzero residual does not prove infeasibility, and the study does not claim universal dominance over other methods. The primary value lies in the rigorous reporting of residual quality, availability, and runtime together.

Technical Summary: Residual-Guided Simulated Annealing for Multi-Dimensional Subset Sum

More like this