Persistency in quadratic 0–1 optimization

Tongli Zhang, Yong Xia

Georg Hahn, Hristo N. Djidjev

Recent advances in the development of commercial quantum annealers such as the D-Wave 2X allow solving NP-hard optimization problems that can be expressed as quadratic unconstrained binary programs. However, the relatively small number of available qubits (around 1000 for the D-Wave 2X quantum annealer) poses a severe limitation to the range of problems that can be solved. This paper explores the suitability of preprocessing methods for reducing the sizes of the input programs and thereby the number of qubits required for their solution on quantum computers. Such methods allow us to determine the value of certain variables that hold in either any optimal solution (called strong persistencies) or in at least one optimal solution (weak persistencies). We investigate preprocessing methods for two important NP-hard graph problems, the computation of a maximum clique and a maximum cut in a graph. We show that the identification of strong and weak persistencies for those two optimization problems is very instance-specific,but can lead to substantial reductions in the number of variables.

Gintaras Palubeckis

Serigne Guèye, Philippe Yves Paul Michelon

To solve combinatorial optimization problems more easily, it can be valuable to identify a set of necessary or sufficient conditions that an optimal solution of the problem must satisfy. For instance, weak and strong duality conditions in linear programming support the development of the well-known optimization algorithms for these problems. Similarly, the Karush–Kuhn–Tucker conditions give necessary and sufficient conditions for optimality in convex quadratic programming that underlie the development of optimization algorithms in this domain. Although such continuous conditions do not exist for integer programming, some necessary conditions can be derived from Karush–Kuhn–Tucker conditions for the Quadratic Unconstrained Binary Optimization (QUBO) problem. We present these conditions and show how they lead to a derivation of well-known criteria for fixing the values of single variables in the QUBO problem. From this, we show how to generalize these criteria to fix a product of any number of p (integer) literals, which also may be viewed as a generalization of the persistency notion, consisting of clauses of a Constraint Satisfaction Problem that the optimal solution must satisfy. We then couple our list of persistencies with state-of-the-art rules not covered by our approach. The resulting integrated set of conditions for fixing values of variables is tested in computational experiments on instances from standard databases available in the literature, showing that we can fix more variables and reduce problems more fully than previous approaches.

Kim Allemand, Komei Fukuda, Thomas M. Liebling +1 more

Shunta Ide, Kikuchi, Shuta, Shu Tanaka

Constrained combinatorial optimization problems (CCOPs) are challenging to solve due to the exponential growth of the solution space. When tackled with Ising machines, constraints are typically enforced by the penalty function method, whose coefficients must be carefully tuned to balance feasibility and objective quality. Variable-reduction techniques such as sample persistence variable reduction (SPVAR) can mitigate hardware limitations of Ising machines, yet their behavior on CCOPs remains insufficiently understood. Building on our prior proposal, we extend and comprehensively evaluate multi-penalty SPVAR (MP-SPVAR), which fixes variables using solution persistence aggregated across multiple penalty coefficients. Experiments on benchmark problems, including the quadratic assignment problem and the quadratic knapsack problem, demonstrate that MP-SPVAR attains higher feasible-solution ratios while matching or improving approximation ratios relative to the conventional SPVAR algorithm. An examination of low-energy states under small penalties clarifies when feasibility degrades and how encoding choices affect the trade-off between solution quality and feasibility. These results position MP-SPVAR as a practical variable-reduction strategy for CCOPs and lay a foundation for systematic penalty tuning, broader problem classes, and integration with quantum-inspired optimization hardware as well as quantum algorithms.