A Gradient-Based Primal Heuristic for Multidimensional Knapsack

The Multidimensional Knapsack (MKP) is a canonical combinatorial optimization problem underlying many problems such as resource-allocation and selection tasks. At large scale, obtaining strong feasible solutions under limited computational budgets remains practically important at which mature exact solvers and specialized heuristics struggle. A central goal of this paper is to obtain high-quality feasible solutions quickly, motivating primal heuristics. Towards that goal, we introduce a continuous relaxation for MKP, combined with a GPU-parallelizable primal-search approach. Our formulation penalizes the maximum normalized constraint ReLU-based violation rather than an aggregate penalty, so that each first-order update is driven by a maximally violated constraint. Hence, we term our method as MAX-ReLU. Building on that, the resulting algorithm applies straight-through estimator rounding and gradient updates to a large batch of trajectories, evaluates binary candidates throughout optimization, and retains the best feasible incumbent found so far. We theoretically analyze feasibility and near-binarity properties of the relaxation, with key arguments extending beyond nonnegative constraint matrices. Experiments on small- and large-scale multidimensional-knapsack instances (synthesized by a well-known MKP generator) show that MAX-ReLU, as compared to GPU- and CPU-based exact and greedy solvers, rapidly finds high-quality feasible solutions, with particularly strong early-time performance in regimes with large number of constraints.