acceptodds
Under review as a conference paper at ICLR 2027

A Gradient-Based Primal Heuristic for Multidimensional Knapsack

Abstract

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.

Primary area:
optimization
Keywords:
Binary Optimization, Nonconvex Optimization, Primal Heuristics, GPU Acceleration, Continuous Relaxation

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_YuNiOpenReview ↗
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
  1. 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.

  2. 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 A≥0A\geq0 imply gj(z)≥−qj+β/ng_j(z)\geq-q_j+\beta/n. Consequently, any item with qj≤β/nq_j\leq\beta/n, equivalently cj≤βcˉc_j\leq\beta\bar c, 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,100)(100,100), 100 unit-profit items consuming (1,1)(1,1) each, and two groups of 50 profit-50 items consuming (100,1)(100,1) and (1,100)(1,100), respectively. At β=0.05\beta=0.05, 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
  1. How many items satisfy cj≤βcˉc_j\leq\beta\bar c 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 β=0\beta=0 and alternative initializations?

  2. 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?

1 comment
AuthorsOpenReview ↗

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).

  • Characterization. Let Eβ={j:cj≤βcˉ}E_\beta=\{j: c_j\le\beta\bar c\}. Under A≥0A\ge0 and the zero rounded start, every item in EβE_\beta stays unselected for every λ\lambda, batch size and run time. Every item outside EβE_\beta is pushed toward selection at every feasible state. The loss is at most ∑j∈Eβcj≤∣Eβ∣ βcˉ\sum_{j\in E_\beta}c_j\le|E_\beta|\,\beta\bar c. A feasible rounded state is a rest state exactly when all its unselected items are in EβE_\beta (C.1.5), so EβE_\beta marks exactly where the non-stalling result ends.
  • Guard. EβE_\beta is computed in O(n)O(n) time before the search. If it is nonempty, we set β=0\beta=0, so no item is ever excluded, and the feasibility part of Theorem 1 still holds. On the example instance, the guard reaches the optimum 100 in every run, within 3 s.
  • Weighted form. The exclusion comes from giving every item the same binarization weight. Item weights 0<ωj<qj0<\omega_j<q_j remove the exclusion mechanism and keep both parts of Theorem 1, with threshold λ0(ω)=max⁡y∈P(q+ω)⊤y\lambda_0(\omega)=\max_{y\in P}(q+\omega)^\top y.
  • Submitted instances. No item is excluded in any of the 180 submitted instances; the smallest profit is 10.06 βcˉ10.06\,\beta\bar c (C.8.2).
  • It costs little when it happens. In 12 heterogeneous-profit instances, the excluded items carry at most 0.5%0.5\% of the profit. Lifting the exclusion in three ways improves the objective by at most 0.002%0.002\%. On the public robust class, the guard is active on all 8 held-out instances, and MAX-ReLU beats cuOPT on 8/8 (C.2.5).
  • Why β>0\beta>0 by default. On the submitted instances, β=0.05\beta=0.05 beats β=0\beta=0: the bound gap is 0.468%0.468\% vs. 0.762%0.762\%, and the 1%1\% target is reached in 0.60 s vs. 1.85 s. A scan over β∈{0,0.05,0.2}\beta\in\{0,0.05,0.2\} selects 0.050.05 on all three families (C.8.2).

Q2: Max versus sum and mean. We agree that feasibility alone does not single out the max. Natural extension to Top-kk. The maximum and sum penalties are two endpoints of a natural family: the sum of the kk largest positive constraint violations, with k=1k=1 recovering the maximum and k=mk=m recovering the sum. We show that this Top-kk 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-kk 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\ell_p aggregation, and for every top-kk aggregation (the sum of the kk largest violations). λ≥λ0\lambda\ge\lambda_0 suffices for the max, the sum and every top-kk, and λ≥mλ0\lambda\ge m\lambda_0 for the mean (C.4.1). Three results then show what the max adds.

  • Structure (C.4.2). On the box, V(y)=max⁡{0,γP(y)−1}V(y)=\max\{0,\gamma_P(y)-1\}, where γP\gamma_P is the gauge of the feasible polytope. So VV, and the MAX-ReLU iterates, do not change when redundant valid rows are added. The sum and the mean lack this property: duplicating one row changes them.
  • Matched experiment (C.4.3). Both penalties use the same code, start, STE rule, Adam settings, β\beta, step size, batch size and time limit. λ\lambda is tuned separately for each penalty, and the mean is the sum with λ/m\lambda/m. On 27 held-out instances, MAX beats tuned SUM on 27/27 at every checkpoint from 5 to 120 s, and a second GPU gives 27/27 again. The gain is up to 1.05%1.05\% at 5 s.
  • Block structure (C.4.4). When rows have different supports, averaging several violated rows is best. Top-4, Top-15 and the mean over violated rows win 8/8 against both solvers. Following one row is weaker (the maximum wins 0/8 against Gurobi), and so is summing without averaging (the sum wins 2/8). On uniformly dense rows, the maximum is best (above). So the aggregation adapts to the row structure, and every top-kk sum keeps the threshold λ0\lambda_0.
Reviewer_1RTyOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes a continuous relaxation for the Multidimensional Knapsack problem and a search approach (MAX-ReLU) that is parallelizable on GPUs. MAX-ReLU is compared to GPU- and CPU-based exact and greedy solvers on problems generated from a single generator using multiple evaluation setups.

Critical strengths
  • (S1) The introduction of the non-standard penalty term V in Equation (2) enables a sound and theoretical analyis of the relaxed solution landscape in Theorem 1. Theorem 1 connects well the continuous and discrete optimization.
  • (S2) The max-ReLU relaxation in equations (1) and (5) motivates the corresponding solver in Algorithm 1, which is parallelizable using established parallel batching frameworks on GPUs.
Critical weaknesses

Critical weaknesses:

  • (W1) The experiments are conducted only on synthetic datasets from a single generator, which makes the generalization of the results to other datasets unclear. Validation on additional independent (synthetic or real-world) datasets would significantly strengthen the paper's contribution.
  • (W2) The experimental comparison mixes algorithmic novelty with parallelization on hardware. The paper compares MAX-ReLU on a GPU with state-of-the-art CPU solvers under time limits. It remains unclear if the proposed algorithm enables faster search independent of hardware.

Minor weaknesses:

  • (MW1) The availability of code would facilitate the reproducibility of the results.
  • (MW2) Citations in the main text are inconsitently formated: sometimes "author (year)" (for example in the Introduction, although it is not a gramatical object of the sentence), sometimes "(author, year)" (see Related Work). If it is not a is not a gramatical object of the sentence, it should be (author, year).
  • (MW3) Table 2 presents numbers with 6 significant figures, which suggests a spurious precision. Based on the experimental setup, 2-3 significant figures are reasonable.
  • (MW4) Please use the thousands separator consistently.
Questions for authors
  • (Q1) As pointed out in Remark 2, the condition λ≥λ0\lambda \geq \lambda_0 is sufficient, but not necessary, for the statement in Theorem 1. Moreover, as mentioned in Section 3, λ0\lambda_0 is not used by the solver and the previous condition is also violated in the experimental setting. Therefore, how does Theorem 1 relate to, influence, or motivate the design of the MAX-ReLU algorithm?
  • (Q2) A time budget to evaluate the solvers (Table 1) is necessary. But the specific choice of 60 seconds is unclear. How does an evaluation for different time budgets, such as 30 and 120 seconds, change the results?
  • (Q3) The algorithm is evaluated for a single initialization choice (Algorithm 1, step 1). How does the initialization interval choice affect MAX-ReLU performance? Is the algorithm better by design or just because of a well-chosen initialization?
2 comments
AuthorsOpenReview ↗

Response to Reviewer 1RTy

We thank the reviewer for the positive assessment and the thoughtful questions. All new material is in Appendix C.

W1: Instance diversity. We added six groups of instances (C.2):

  • Fresh instances at three capacity ratios (27; two ratios are new). MAX-ReLU beats cuOPT and Gurobi on 27/27 at 120 s (C.2.1).
  • Heterogeneous profits (12). It beats cuOPT on 11 (one tie) and is level with Gurobi (median difference below 0.001%0.001\%).
  • Public OR-Library CB set (72). These instances have few rows (m/n≤0.06m/n\le0.06). At m=30m=30, MAX-ReLU beats cuOPT on 20/24 and is level with Gurobi. Its standing rises with mm, as in the m/nm/n trend of Sec. 5.4. At 5 s, it beats cuOPT on 48/72.
  • Six larger structured families with public CB coefficients, the CB recipe and correlated rows (n≤4,000n\le4{,}000, m/n≤2.16m/n\le2.16). With the untuned rule, it beats cuOPT on 24/24 and Gurobi on 22/24 (C.2.2). At half density, it still beats cuOPT on 23/24 and leads Gurobi early (C.2.3).
  • Block-structured MKPs (20; n=5,000n=5{,}000, local and global rows). With a top-kk penalty, it beats Gurobi in 39/40 runs and cuOPT in 40/40 (C.2.4).
  • Public robust scenario data (8 held-out). It beats cuOPT on 8/8 and is within 0.01%0.01\% of Gurobi in median (C.2.5).

C.2.5 also shows when MAX-ReLU gains over Gurobi: the share of fractional entries at an LP vertex predicts the outcome with ROC AUC 0.99.

W2: Algorithm versus hardware.

  • Same CPU, no GPU (C.7). On the eight CPU threads that Gurobi uses, MAX-ReLU (B=64B=64) reaches 1%1\% of the bound in a median of 0.93 s, versus 1.56 s and 1.54 s for Gurobi's two settings. It is first on 18/21 instances, which are all those with m/n≥0.12m/n\ge0.12. So the advantage does not come from the GPU alone.
  • Same GPU, different method. cuOPT is itself a GPU solver. On the same GPU, MAX-ReLU beats it on 27/27 fresh instances at every checkpoint from 5 to 120 s (C.2.1), and it beats a separately tuned sum penalty on 27/27 (C.4.3). GFORS, PQQA (B.4) and GPU ADMM (C.3) give further same-GPU comparisons.

Q1: How Theorem 1 guides the design. It sets the scale of λ\lambda (C.1.6). Write λ=κU\lambda=\kappa U, where UU is an upper bound on λ0\lambda_0. Every tested κ∈{1.05,1.5,3}\kappa\in\{1.05,1.5,3\} is within 0.062%0.062\% of the best in nine regimes. At κ≤0.9\kappa\le0.9 the search often finds no positive solution, consistent with the rest-state result (C.1.5). The choice of lambda in the additional experiments now defualts to λ=1.05U\lambda=1.05U, and the bound takes one pass over AA (C.1.2). This rule ran untuned on all new structured families and on the public-data class. On the public CB set, settings chosen in units of λ0\lambda_0, jointly with β\beta and step size, beat the fixed setting on 48/48 held-out instances by a median of 13.4%13.4\%.

Q2: Time budgets. We chose 60 s to measure early primal progress, and it does not favor MAX-ReLU: at 60 s, its mean already exceeds the 20-minute Gurobi reference in 16 of 21 regimes (Table 1). C.5 reports 5 to 120 s.

  • Fresh instances: MAX-ReLU leads cuOPT at every checkpoint, and its 60-s value beats Gurobi's 120-s value on 27/27.
  • Structured families: the median gain over Gurobi is above 1%1\% at 10 s.
  • Block structure: at 30 s, it already beats the 60-s baselines in 38/40 runs (Gurobi) and 40/40 (cuOPT).
  • Public robust data: with setup counted for both, it leads cuOPT at 5 s by a median of 5–6% (C.2.5).

Q3: Initialization.

  • The start carries no instance information. From the zero rounded state, the gradient is constant until items enter. So the position of the interval only delays the first selection, and its width spreads the first selections (C.6.1).
  • On 21 instances (C.6.2), wider starts cost 0.20.2–0.3%0.3\% at 5 s and about 0.02%0.02\% at 120 s. Moving the narrow interval toward 1/2 matters little after the first second. An LP start plus noise is level at 120 s (median +0.010%+0.010\%).
  • So the simple start stays competitive without solving an LP: from 5 s on, its median difference to the LP start is at most 0.012%0.012\%, and it is ahead at 10 s and 30 s.

Minor weaknesses. The revision uses consistent author–year citations, reports Table 2 with three significant figures, and uses thousands separators throughout. We will release the code with the final version.

I thank the authors for their revision. Due to the limited time left in the discussion period, I only verified the parts of it relevant for my initial review. Overall, the revision addresses my main concerns and questions.

My remaining concerns are about framing:

Please state the limits of the added evidence in the main text. Table 20 shows that at half density MAX-ReLU loses to Gurobi on 15/16 (MIPFocus=0) and 16/16 (MIPFocus=1) of the 16 instances where Gurobi moves beyond its greedy start, at 120 s. Table 22 shows it losing 0/0/8 to Gurobi (MIPGap = 0). Table 27 also shows configurations where Gurobi clearly wins. These are legitimate results, but the current summary mainly presents the results as uniform wins. A short "where the method does not help (and why?)" paragraph would strengthen the paper.

Theorem 1 versus the λ actually used. The main grid runs at λ = 0.3 while the thresholds are λ₀ ∈ [0.3151, 0.3244], so the sufficient condition is violated in the main experiments. The rule λ = 1.05U is used only in the appendix. Please say explicitly that Theorem 1 is motivational for the main results and give the empirical support for the new rule in the main text, or explain why the main grid was not rerun with it.

Code (minor): an anonymized repository during review would be more useful than a release with the final version, given that the contribution is largely empirical.

I will raise my score to 3 on the assumption that the above points are addressed in the camera-ready version.

Reviewer_jheYOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes a large-scale approximate solver for MKP, which is an ILP in the form min⁡cTx∣Ax≤b,x∈0,1n\min\\{c^T x \mid Ax\le b, x\in\\{0,1\\}^n \\} where A,cA,c have nonnegative and bb positive entries. The solver is highly parallel and uses existing infrastructure (GPUs, Adam, etc) for training AI models. The ILP is relaxed to a non-convex quadratic minimization problem over the box [0,1]n[0,1]^n, which is a nonnegative combination of three terms: the original (negative) objective, a piecewise-affine convex term (ReLU) encouraging feasibility (ie, Ax≤bAx\le b), and a concave quadratic term encouraging integrality. This function is approximately minimized by a version of subgradient descent with a straight-thru trick, which means that subgradients are actually computed in points rounded to integrality. During the updates, rounded solutions are examined for objective values and best-so-far ones are remembered. Several such trajectories o updates are developed at ones in parallel, starting from different initial points. Though for general ILPs it is intractable to find a feasible solution, for the MKP any z=0 is feasible.

The method is compared with other large-scale ILP solvers on synthetically generated dense MKP instances, with the entries of A being iid from a uniform distribution. The solvers were Gurobi (with three sets of parameters), NVidia's cuOPT, and a primal heursitic that won CP 2024 competition. In a limited time budget, the proposed heuristic almost always found a better feasible suboptimum than the other methods.

Critical strengths

The method is relatively simple and on the given type of MKP instances, it yields good suboptima quickly.

The proposed primal heuristic is interesting and, to my knowledge, some of its parts are novel.

Critical weaknesses

I see several major problems.

Theorem 1 (the main theoretical result) can be naturally split into independent parts: (a) for big enough λ\lambda, every local minimizer is a vertex of PP; (b) every vertex of PP has at most rank(A) fractional coordinates. Here, (a) is not very surprising and (b) is a well-known classical argument, repeated in the literature (eg, [https://courses.grainger.illinois.edu/cs583/sp2016/LectureNotes/rank-lemma.pdf], cf. also Theorem 1 in the paper (Puchinger et al, 2010)). This limits the novelty of the theoretical analysis significantly.

Moreover, this theoretical result is rather disconnected from the used algorithm, where (as the authors also emphasize) λ\lambda is often much smaller than in Theorem 1.

Using a concave term to encourage integrality is well-known, decsribed many times in the optimization literature.

When speaking about subgradient of a non-convex function F(y)F(y), it would be useful to specify what kind of subgradient it is (Clarke?).

Does the heuristic search have any provable convergence properties at all? Can it (or its simplified version without rounding and straight-thru) be proven to converge to a local minimizer?

The experiments are on a single type of synthetically generated MKP instances, which have rather simple structure: the entries of AA are iid from a uniform distribution. Such a type of MKP can be very easy compared to more structured (possibly sparse) instances. Note, the MKP definition includes some very hard combinatorial problems, such as max-weight independent set which is APX-hard (I expect there are public benchmarks for this problem but I am not sure). Min-weight set-cover can also be reduced to MKP, by substitution yk=1−xky_k=1-x_k (though this does not preserve approximation ratios).

It can be objected that what is called "MKP" is defined not by the signs of the entries of A,b,cA,b,c but also by a distribution of its instances: MKP tend to be dense and tend to have independent entries of AA. If this is the motivation of the authors, then it should be said much more clearly in the intro (MKP should be specified in a narrower and softer way than just by (1) and the paragraph below).

I also believe there comparing to more baseline solvers would be helpful. MKP is studied for decades and there are many types of solvers (based on LP relaxation, primal-dual, nonlinear ADMM, ...). In particular, why to restrict to primal heursitics only (except Gurobi)?

Questions for authors

Do you have any evidence/opinion how the method would behave on more structured MKPs, both dense and sparse (such as max independent set)?

1 comment
AuthorsOpenReview ↗

Response to Reviewer jheY

We thank the reviewer for the careful review. All new material is in Appendix C, and its first table maps each point to a section.

1. Novelty of Theorem 1. The vertex bound in (b) (Puchinger et al., 2010) is now credited in the revision. Our contribution is (a), and the combined use of (a) and (b) to guide the algorithm design. In particular:

  • An upper bound on λ0\lambda_0 needs no LP, only one pass over AA and a sort (C.1.2).
  • The threshold is tight: with one row, an infeasible local minimizer exists for every λ<λ0\lambda<\lambda_0 (C.1.3).
  • The feasibility conclusion extends to near-stationary points and to the rest states of the rounded search (C.1.4–C.1.5).
  • It holds for every ℓp\ell_p and top-kk aggregation of the violations, and the maximum is the one that is invariant to redundant valid rows (C.4.1–C.4.2).

2. Theory and the choice of λ\lambda. λ0\lambda_0 is the working scale of the search. On the submitted instances, λ=0.3\lambda=0.3 is (0.92–0.95)λ0(0.92\text{–}0.95)\lambda_0. Write λ=κU\lambda=\kappa U, where UU is an upper bound on λ0\lambda_0. Every tested κ∈{1.05,1.5,3}\kappa\in\{1.05,1.5,3\} is within 0.062%0.062\% of the best in all nine regimes, while at κ≤0.9\kappa\le0.9 the search might find no positive solution (C.1.6). The revision now defaults to λ=1.05U\lambda=1.05U, and this rule ran without tuning on all new structured families and on the public-data class (C.2.2–C.2.5).

3. Subgradient and convergence. FF is a C1C^1 function plus a finite convex function, so it is Clarke regular. Its Clarke, Fréchet and limiting subdifferentials coincide, and Eq. (5) selects an element of this set at the rounded point (C.1.1). Without rounding, FF is weakly convex, so projected subgradient methods reach near-stationary points. For λ>λ0\lambda>\lambda_0, these points are feasible (C.1.4). With rounding, the method is a search procedure like the feasibility pump, and we characterize where it can stop. For λ>λ0\lambda>\lambda_0, every rest state is feasible, and a strict rest state is a local minimizer of FF. When no item is excluded, there is no rest state at all, so the search leaves every rounded state in finite time (C.1.5). Algorithm 1 checks every candidate, so every returned solution is feasible.

4. Structure and sparsity. We thank the reviewer for this suggestion. The method targets dense resource constraints, and we tested it beyond the paper's generator (C.2):

  • Larger dense families. Six families with nn up to 4,000 and m/nm/n up to 2.16, from public CB coefficients, the CB recipe and correlated rows. With the untuned rule, MAX-ReLU beats cuOPT on 24/24 and greedy-warm-started Gurobi on 22/24 at 120 s. It leads Gurobi on 21/24 at 10 s (C.2.2).
  • Half density. MAX-ReLU still beats cuOPT on 23/24, and it leads Gurobi at 5 s on 12/16 (median +3.06%+3.06\%). On eight instances, Gurobi makes no progress in 120 s, and MAX-ReLU is ahead by 2.3–3.6% (C.2.3).
  • Block structure. Practical sparse MKPs are often block-structured: local rows cover one group of items, and global rows couple all groups. Following the kk most violated rows instead of one, MAX-ReLU beats Gurobi in 39/40 runs and cuOPT in 40/40 on 20 held-out instances with n=5,000n=5{,}000. Its setup is charged to its clock (C.2.4). The top-kk penalty keeps the threshold λ0\lambda_0 (C.4.1).
  • Public data. On robust scenario knapsacks built from public data, MAX-ReLU beats cuOPT on 8/8 held-out instances and stays within 0.01%0.01\% of Gurobi in median (C.2.5).
  • Where MAX-ReLU gains. The share of fractional entries at an LP vertex predicts the outcome against Gurobi, with ROC AUC 0.99 over 96 dense comparisons (C.2.5). When the LP is nearly integral, LP-based search is near optimal early. Otherwise, MAX-ReLU gains.

In the edge formulation of MIS, every violated edge has the same normalized violation, so the maximum is only a tie-break, and graph methods are the natural baselines. Complementing set-cover variables gives rows that only forbid selecting all items of one set. Both are far from the resource constraints we target, and the introduction now states this scope.

5. Baselines. cuOPT and Gurobi are full MIP solvers. cuOPT runs a first-order primal–dual LP method inside a feasibility pump, and GFORS is a primal–dual first-order method (63 cases, B.4). We added LP round-and-repair (HiGHS) and GPU ℓ2\ell_2-box ADMM (Wu & Ghanem, 2019) on 138 instances (C.3). On every instance where they return a solution (115/115 and 138/138), their final value is below MAX-ReLU's value after 5 s of search.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.