Local Minima in Quadratic-Penalty Relaxations of Binary Linear Programs

Many combinatorial optimization problems admit quadratic unconstrained binary formulations (QUBO) which can often be relaxed to the box $[0,1]^n$ and optimized using scalable gradient-based methods. However, the resulting non-convex landscape can often contain local optima that are spurious or infeasible. In this paper, we establish sufficient structural conditions on quadratic penalties that rule out these failures, guaranteeing that every local minimizer of the relax problem is both binary and feasible. For each problem we study, we examine existing QUBO formulations when available, identify why they fail when they do, and propose alternative relaxed QUBOs that satisfy our conditions. We show for several common combinatorial problems, including open-pit mining, knapsack, and traveling salesman formulations, that these constructions allow gradient-based methods such as projected gradient descent and Adam to be safely applied to obtain valid binary solutions. Our results clarify when differentiable optimization is a reliable local solver for quadratic combinatorial objectives.

A common way to handle hard discrete optimization problems is to convert them into quadratic unconstrained binary optimization problems, or QUBOs. These QUBOs are often easier to implement and can be optimized using modern gradient-based methods on GPUs. However, this relaxation can introduce serious failures: the optimizer may get stuck at a solution that is fractional or violates the original constraints, even when constraint penalties are made very large. This paper studies when such failures can be ruled out. We identify structural conditions on the penalty terms that guarantee every local minimum of the relaxed problem corresponds to a valid binary and feasible solution of the original combinatorial problem. The results provide a theoretical guide for designing QUBO formulations that are safe optimize with continuous, gradient-based methods.