- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper proposes MAX-ReLU, a GPU-parallel primal heuristic for multidimensional knapsack. Its continuous objective combines normalized profit, the maximum normalized constraint violation, and a concave binarity penalty. The algorithm evaluates update directions at rounded binary states, applies Adam updates to continuous states, and retains the best feasible solution across parallel trajectories. The paper also establishes sufficient conditions under which continuous local minima are feasible vertices of the LP relaxation.
Critical strengths
-
The formulation combines a maximum normalized violation penalty with a concave binarity term and provides an explicit sufficient penalty threshold for feasibility of continuous local minima. The accompanying vertex characterization connects the relaxation to the geometry of the feasible polytope.
-
The algorithm maintains continuous states while using rounded candidates to determine update directions. The separate analysis of rounded-state changes is valuable: under its sufficient condition, an infeasible binary state cannot remain unchanged indefinitely, without claiming convergence or optimality.
Critical weaknesses
The specified initialization and update rule permanently exclude some items, potentially making optimal solutions unreachable. All coordinates start below the rounding threshold, with zero Adam moments. For an unselected item, Equation (5) and imply . Consequently, any item with , equivalently , can never cross the threshold into selection. Increasing runtime or batch size does not remove this restriction. This is consequential because low-profit items may have excellent resource efficiency. For example, consider capacities , 100 unit-profit items consuming each, and two groups of 50 profit-50 items consuming and , respectively. At , all unit-profit items are permanently excluded: the optimum is 100, whereas any reachable feasible solution has value at most 50. The paper should characterize this restriction and evaluate heterogeneous-profit instances with appropriate initialization and binarity-parameter controls.
The contribution of the max-violation design is not isolated from the rest of the search framework. The radial-scaling feasibility argument and the feasible-polytope vertex argument can also be applied to an unaveraged sum of ReLU violations under the same sufficient condition; these properties therefore do not establish a distinctive advantage of the maximum penalty. Meanwhile, the reported ablations vary the binarity coefficient, penalty weight, learning rate, and batch size, but do not directly compare max against sum or mean penalties under an otherwise matched implementation. A controlled comparison with separately tuned penalty weights is needed to distinguish the contribution of max-violation handling from STE updates, Adam, and parallel search.
Questions for authors
-
How many items satisfy in the evaluated instances? Can the authors characterize the resulting permanently excluded variables and test heterogeneous-profit instances using both the default method and controls such as and alternative initializations?
-
How does MAX-ReLU compare with sum-ReLU and mean-ReLU variants when initialization, STE updates, optimizer, batch size, and time budget are matched, with penalty weights tuned separately? Which measured advantage can then be attributed specifically to the maximum-violation choice?
Response to Reviewer YuNi
We thank the reviewer for the precise questions and for the counterexample.
Q1: Permanently excluded items. The reviewer is correct that the default initialization can permanently exclude some items. We now characterize exactly when this happens and add a simple guard that removes the issue. Importantly, none of the 180 original benchmark instances trigger this exclusion. We turned the example into a result (C.8.1).
Q2: Max versus sum and mean. We agree that feasibility alone does not single out the max. Natural extension to Top-k. The maximum and sum penalties are two endpoints of a natural family: the sum of the k largest positive constraint violations, with k=1 recovering the maximum and k=m recovering the sum. We show that this Top-k family preserves the same feasibility guarantee, so the reviewer’s max-vs-sum question naturally leads to studying intermediate aggregation levels as well.
We therefore also include Top-k results. On the uniformly dense instances, the maximum performs best, whereas on block-structured instances, aggregating several highly violated rows is more effective: Top-4, Top-15, and the positive-only mean outperform both solvers on all 8 held-out comparisons. This suggests that the appropriate aggregation level depends on constraint structure: following one maximally violated row is effective when each row already couples many variables, while combining several violated rows provides complementary update directions when constraints have different supports.
The revision proves the guarantee for every ℓp aggregation, and for every top-k aggregation (the sum of the k largest violations). λ≥λ0 suffices for the max, the sum and every top-k, and λ≥mλ0 for the mean (C.4.1). Three results then show what the max adds.