{"id":"70ce246f-cddb-46c7-bab9-4c1559873f96","arxiv_id":"2501.16826","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"A branch-and-cut method minimizes the pessimistic IEO regret loss directly for 0-1 combinatorial decision-focused learning, avoiding the need for a convex hull.","lead":"This paper treats decision-focused learning as a pessimistic bilevel optimization problem and proposes cut-generation algorithms to minimize the true regret loss for combinatorial downstream problems. Tests on 0-1 knapsack show lower out-of-sample regret than estimate-then-optimize and SPO+ in several settings, though not consistently.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claim of exact pessimistic-IEO minimization rests on an unspecified epsilon in (14c); positive margins below epsilon are misclassified, so the method is an epsilon-approximation, not exact.","rationale":"The reader identified the epsilon threshold in (14c) as the weakest assumption; my read agrees. The paper's own abstract admits an epsilon-approximation, which already conflicts with the contribution claiming no approximations. The missing epsilon specification is not a minor numerical detail: because w is a decision variable, the set of positive margins is learned, so no fixed epsilon can be certified below all of them. This makes the master problem solve a perturbed objective, invalidating the central exactness claim. The empirical overstatements in Section 5 and the post hoc exclusion of n = 500 for ny = 20 are additional concerns, but the epsilon issue is load-bearing for the paper's main theoretical contribution. The algorithmic machinery and experiments may still be salvageable if the claims are revised to present the method as an epsilon-approximation with a controlled relaxation error; hence the conditional verdict stands.","tokens_in":18297,"tokens_out":7921,"duration_ms":73632,"concrete_test":"Take a 0-1 knapsack instance with ny = 5 and n = 20, enumerate F(Z), and solve the proposed branch-and-cut formulation for epsilon = 10^-2, 10^-4, 10^-6, 10^-8 under otherwise identical settings, recording the fitted W and out-of-sample %ell_IEO. In parallel, compute the exact pessimistic IEO objective for any candidate W by evaluating all cells of the arrangement of hyperplanes f_w(x_i)^T(z_e - zbar_i) = 0 in W-space and identifying the true follower-optimal sets via strict inequalities in exact arithmetic. Determine the global minimizer of this exact piecewise-constant loss. If the optimal W or objective value differs across epsilon values, or differs from the exact global minimizer, then (14c) is an approximation and the exactness claim fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Contribution 1 claims minimization of the true pessimistic IEO loss without relying on approximations or surrogate functions. The construction in Section 3.2 does not deliver this. Constraint (13) encodes the strict disjunction f_w(x_i)^T(z_e - zbar_i) > 0 with an indicator. Constraint (14c) relaxes it to f_w(x_i)^T(z_e - zbar_i) >= epsilon - M lambda_ie, with no rule for choosing epsilon. For any z_e with margin in (0, epsilon), lambda_ie = 0 is infeasible, so the only feasible value is lambda_ie = 1, which forces theta_i >= ybar_i^T z_e and treats a provably suboptimal decision as a follower optimum. Because w is continuous and is itself optimized, positive margins can be arbitrarily small; no a priori epsilon can separate all of them from zero. Moreover, the paper allows M = epsilon, in which case (14c) also rejects negative margins under lambda_ie = 1, so even points genuinely in the optimal set cannot be represented. Thus the master problem is at best an epsilon-perturbation of the pessimistic loss; the convergence result in Lemma 2 is about convergence to this epsilon-perturbed problem, not to the exact pessimistic IEO solution. The computational experiments therefore benchmark an approximate objective, and the no-approximations contribution is not supported as stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a pessimistic bilevel optimization formulation for decision-focused learning in combinatorial optimization. The training problem minimizes an empirical normalized pessimistic IEO loss, where the lower level is a 0-1 linear optimization problem. The authors derive a single-level MILP using a big-M disjunction, then propose a column-and-constraint generation algorithm and a branch-and-cut algorithm, and test them on 0-1 knapsack instances against linear regression and SPO+. The central claimed contributions are exact minimization of the true pessimistic IEO loss without surrogate functions or convex hull descriptions, and superior out-of-sample performance on moderate- and large-size instances.","tokens_in":18551,"tokens_out":6604,"duration_ms":58010,"significance":"If the main claims were fully established, the paper would fill a genuine gap: an exact (or rigorously controlled) method for minimizing the pessimistic IEO loss for combinatorial downstream problems without a convex hull. The proposed branch-and-cut scheme is a plausible practical enhancement over column-and-constraint generation and the experiments provide useful evidence about the behavior of decision-focused training on knapsack problems. However, the exactness claim is not supported because the disjunctive reformulation uses an unspecified epsilon threshold, and the out-of-sample conclusions are contradicted by the paper's own tables. The algorithms and framework are a reasonable starting point, but the current manuscript overstates what is proven and what the experiments show.","major_comments":[{"comment":"The reformulation of the strict disjunction f_w(x_i)^T(z_e - \\bar{z}_i) > 0 as f_w(x_i)^T(z_e - \\bar{z}_i) >= \\epsilon - M \\lambda_{ie} is not equivalent to the exact pessimistic IEO loss. For any point whose positive margin is in (0, \\epsilon), the constraint with \\lambda=0 is infeasible, so the only feasible choice is \\lambda=1, which incorrectly treats a provably suboptimal decision as a follower optimum. Because w is continuous and optimized, positive margins can be arbitrarily small, so no a priori choice of \\epsilon can separate all of them from zero. Moreover, the text states that M can be set equal to \\epsilon or larger; if M=\\epsilon, then a point with a negative margin cannot be represented by either \\lambda=0 or \\lambda=1, making the master problem infeasible for valid lower-level optimal points. The paper itself calls formulation (14) an \\epsilon-approximation, but Contribution 1 claims minimization of 'the true pessimistic IEO loss without relying on approximations or surrogate functions.' As stated, the claim is not supported: the method solves an \\epsilon-perturbed problem, and the experiments benchmark that perturbed objective. The value of \\epsilon used in the experiments is also never reported, so the results are not reproducible in this respect.","section":"Section 3.2, Eq. (14c)"},{"comment":"Lemma 2 states that Algorithm 1 converges to a pessimistic IEO solution whose gap from the optimal is at most \\Delta. The proof shows that if no new subproblem points are added, then LB \\geq UB, where LB comes from P^{(k)}_\\epsilon. However, because \\(P^{(k)}_\\epsilon\\) is an \\epsilon-approximation and not a valid lower-bound relaxation of the original problem (as discussed above), LB is not guaranteed to be a valid lower bound on the true pessimistic objective. Consequently, the stopping criterion UB - LB \\leq \\Delta does not certify \\Delta-optimality for the original pessimistic bilevel problem; it certifies only distance to the \\epsilon-perturbed master problem. The lemma therefore needs to be restated with explicit dependence on \\epsilon, and a correct error bound must account for the misclassification of margins in (0,\\epsilon).","section":"Section 3.2, Lemma 2"},{"comment":"The conclusion claims that 'the proposed IEO method outperforms both LR and SPO+ in terms of out-of-sample IEO loss,' but the data in Tables 2 and 3 do not support a consistent outperformance. For example, in Table 2 with n=100, \\delta=1, instance 0, IEO has out-of-sample %\\bar{\\ell}_{IEO}=1.056 while LR achieves 0.954; in the same table, n=100, \\delta=7, \\delta=1, IEO has 1.960 versus LR's 0.726. The text in Section 4.3 explicitly acknowledges that 'no method consistently outperforms the others.' The Conclusion and Contribution 3 therefore overstate the experimental evidence. The claims should be qualified to specific regimes (e.g., \\delta=3 or \\delta=5, or after regularization with LHS), or the tables and conclusion should be aligned with the observed results.","section":"Section 4.3, Tables 2 and 3, and Section 5"},{"comment":"The n=500 results for the ny=20 instances are excluded because 'these were the cases where IEO successfully improved the warm-start solutions provided to the solver within a time limit of 1800 seconds.' This exclusion removes the cases where the proposed method may not have improved over its warmstart, which are exactly the unfavorable cases for the claim of consistent outperformance. The exclusion should either be reported as a limitation in the main claim, or the n=500 results should be included (even if they show IEO not improving). As presented, the selective exclusion weakens the conclusion that IEO outperforms LR and SPO+ for larger instances.","section":"Section 4.4, Figure 2"}],"minor_comments":[{"comment":"The abstract says the method 'solves an \\epsilon-approximation' of the pessimistic bilevel problem, while Contribution 1 says the method minimizes 'the true pessimistic IEO loss without relying on approximations.' These statements are inconsistent; even if the \\epsilon issue were resolved, the wording should be aligned.","section":"Abstract and Section 1"},{"comment":"The bounds fmin and fmax in the linearization (16) are never specified or discussed in the experiments. Their choice can affect the validity of the linearization, and the paper should report how they are set and whether they are data-dependent.","section":"Section 3.4.1"},{"comment":"The symbol \\gamma is used both for the lasso regularization coefficient (Section 4.3, set to 0.005) and for the perturbation scalar in (w = w_j + \\gamma\\epsilon\\epsilon\\epsilon). This overloading is confusing; different notation should be used for the two parameters.","section":"Section 3.4.4"},{"comment":"The algorithm parameters ninit, nrep, and nEP are introduced but no values are reported in the computational experiments, except indirectly. Without these values, the experiments are not fully reproducible.","section":"Sections 3.4.2 and 3.4.3"},{"comment":"In Table 1, the 'gap' columns report solver gaps for the branch-and-cut and CCG methods. For Instance 1 with n=500, the branch-and-cut gap is 0.347, which is quite large; the text should be careful when claiming that the branch-and-cut 'solves the problem to optimality' without noting that this only occurs for Instance 10.","section":"Section 4.2, Table 1"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses an interesting and relevant problem, and the algorithmic framework (CCG and branch-and-cut) appears to have merit. However, the central exactness claim is not currently justified due to the epsilon perturbation in (14c), and the out-of-sample claims are stronger than the reported experiments warrant. I believe these issues are fixable by rewriting the contributions in terms of epsilon-approximation, providing a rigorous error analysis, reporting the omitted parameters, and aligning the conclusions with the tables. The exclusion of n=500 results in Section 4.4 also needs to be handled transparently. I recommend major revision rather than rejection, as the core idea could become a valid contribution after these corrections."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things. First, the core algorithm is a genuine extension: the authors adapt Zeng's pessimistic-bilevel relaxation and column-and-constraint scheme to the case where the follower's objective depends on the leader's variables, and they add a branch-and-cut variant that clearly beats the CCG in their tests. Second, the paper's central claim does not hold as stated. It repeatedly says it minimizes the true pessimistic IEO loss without relying on approximations, but the abstract itself says \"solves an \\varepsilon-approximation\", and the master problem (14c) hinges on an epsilon threshold with no rule for choosing it. Since w is continuous and optimized, margins can be arbitrarily small, so no fixed epsilon can separate all positive margins from zero. They even allow M = epsilon, in which case lambda = 1 forces f_w(x_i)^T(z_e - zbar_i) >= 0 and negative margins cannot be represented at all. Lemma 2 shows convergence to the epsilon-perturbed problem, not to the exact pessimistic solution. That is load-bearing, not a nit. What the paper does well: the linearization of the bilinear term is sensible, the branch-and-cut with lazy cuts is a legitimate algorithmic contribution, and the computational comparison on 0-1 knapsack is useful, including the honest reporting of overfitting at n = 100 and the SPO+(CH) comparison. The normalization of the IEO loss is a nice detail. The relaxation in Section 3.1 is clearly explained, and the proof of Lemma 1 is fine. The soft spots beyond the epsilon issue: the conclusions overstate the experiments. Tables 2 and 3 show IEO is often worse than LR or SPO+(CH), especially for delta = 1 and small n. Section 4.3 says no method consistently outperforms the others; the conclusion says IEO outperforms both LR and SPO+. The n = 500 exclusion for ny = 20 is post hoc, as the authors admit. No code or data is shipped, so the branch-and-cut details are hard to reproduce. Who is this for: researchers in decision-focused learning and contextual optimization who want a method for combinatorial DOPs without a convex hull description. It deserves a serious referee, but the referee should insist on either dropping the exact no-approximation claim or specifying how epsilon is chosen and showing that the reported results are robust to it. The n = 500 results should also be reported, or the exclusion justified as a computational limit rather than a performance filter. With those revisions the paper could be a solid contribution to the OR/MS literature.","headline":"A real algorithmic extension for pessimistic IEO on binary DOPs, undermined by an epsilon gap in the master problem and by conclusions that overstate the experiments.","tokens_in":740,"tokens_out":1040,"would_cite":true,"duration_ms":31944,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C11","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"A pessimistic bilevel cut-generation method minimizes the true IEO loss for 0-1 combinatorial problems without surrogate losses or convex hulls.","keywords":["contextual optimization","decision-focused learning","pessimistic bilevel optimization","integrated estimation-optimization","SPO+","0-1 knapsack","branch-and-cut","column-and-constraint generation"],"falsifier":"Take a small 0-1 knapsack instance, enumerate all feasible points, and train the method with a specific $\\varepsilon$; after fitting $w$, look for a training point and feasible $z_e$ with $0 < f_w(x_i)^T(z_e - \\bar z_i) < \\varepsilon$. If one exists, compare the true pessimistic loss obtained by full enumeration with the loss reported by the master problem; a mismatch on any such instance shows the $\\varepsilon$-approximation is not the exact pessimistic IEO loss.","tokens_in":18023,"feed_emoji":"🎯","tokens_out":11145,"duration_ms":91729,"temperature":0.7,"pith_summary":"This paper tries to establish that the empirical risk minimization of the pessimistic integrated estimation-optimization (IEO) loss can be tackled directly for combinatorial downstream optimization problems with binary variables, without a surrogate loss or a convex-hull description. It models the learning task as a pessimistic bilevel program in which the leader chooses predictor weights and the follower, for each training sample, selects a decision that minimizes the predicted cost and maximizes the true cost, so the loss is the worst-case regret. The proposed algorithms, a column-and-constraint generation scheme and a branch-and-cut scheme, solve an $\\varepsilon$-approximation of the pessimistic bilevel problem, and the branch-and-cut variant is faster and reaches optimality on tested 0-1 knapsack instances. Out-of-sample experiments on the 0-1 knapsack problem show lower regret than linear regression and SPO+ and match SPO+ when a convex hull is available, which matters because convex hulls are rarely computable for larger integer problems. If correct, this gives practitioners a direct decision-focused training procedure for combinatorial problems that previously required approximations.","feed_headline":"Trains predictors on worst-case decision regret, not a proxy","feed_subtitle":"For 0-1 knapsack, the method beats estimate-then-optimize and SPO+ on out-of-sample regret, with no convex hull.","key_machinery":"The central object is the pessimistic bilevel reformulation of the IEO loss: the leader minimizes the average worst-case regret over the training set, while each follower, given predicted costs $f_w(x_i)$, chooses a minimizer of the downstream problem that is worst for the true cost vector $y_i$. The mechanism that makes the problem tractable is the finite relaxation of the follower's optimality condition: since the feasible set $Z$ of a 0-1 combinatorial problem is finite, the condition that a point $z_e$ is a follower optimum is represented by an inequality on the predicted-cost gap, which the algorithm writes as an $\\varepsilon$-separation constraint with a binary variable $\\lambda_{ie}$. Cuts add new feasible points found by solving the subproblem, tightening the relaxation; the branch-and-cut variant adds these cuts lazily inside one master MILP, which is what makes the approach practical.","core_discovery":"The paper's central claim is that the pessimistic IEO loss for 0-1 combinatorial optimization problems can be minimized directly, rather than through the SPO+ surrogate or through primal-dual approximations. The mathematical move is to write the empirical risk minimization as a pessimistic bilevel problem and to replace the follower's optimality condition with a finite-enumeration relaxation: because the feasible set $Z$ is finite, the statement that a point $z_e$ is a follower optimum can be expressed with binary variables and big-M constraints, and the relaxation is tightened by adding violated feasible points as cuts. The paper proves that this cut-generation procedure converges in finitely many iterations to a solution whose distance from a pessimistic optimum is at most a tolerance, and its 0-1 knapsack experiments show that the resulting predictors achieve lower out-of-sample normalized regret than linear regression and SPO+, without requiring the convex hull that SPO+ needs.","pith_inferences":["Beyond the paper: the method's exactness claim stands on the fixed $\\varepsilon$ in constraint (14c) being smaller than every nonzero predicted-cost gap, so a margin-separation check after training would either confirm or repair the claim.","Beyond the paper: the cut-generation template is not knapsack-specific; any 0-1 linear downstream problem with a finite feasible set could use the same relaxation, so the approach plausibly carries over to assignment, matching, and shortest-path decision-focused learning.","Beyond the paper: the observed small-sample overfitting suggests that direct minimization of worst-case regret amplifies noise, so a decision-aware regularizer tailored to the downstream problem, rather than generic lasso, is a natural next step.","Beyond the paper: the warm-start mechanism already used in the implementation could be developed into a hybrid training scheme that first fits a cheap surrogate such as SPO+ and then polishes with the exact pessimistic loss."],"forward_implications":["For 0-1 combinatorial downstream problems, predictor fitting can target true decision regret directly, so decision-focused learning does not need a convex hull or a continuous relaxation of the feasible set.","On the tested 0-1 knapsack instances, the branch-and-cut variant is the practical solver: it reaches lower in-sample IEO loss than column-and-constraint generation within the same time limit and sometimes closes the optimality gap below $10^{-4}$.","Out of sample, the direct IEO method is competitive with or better than linear regression and SPO+: it outperforms both on more nonlinear data and matches SPO+ with convex hull when that baseline is computable.","The method inherits a meaningful overfitting risk at small sample sizes, mirroring SPO+ with convex hull, which the paper mitigates with LHS sampling and lasso regularization but does not eliminate."],"supporting_citations":[{"why":"Supplies the SPO+ surrogate loss and its convex-hull treatment, which are the main baselines for the new method.","marker":"[13]"},{"why":"Supplies the column-and-constraint generation scheme for pessimistic bilevel problems that the paper adapts to IEO.","marker":"[25]"},{"why":"Establishes the difficulty of pessimistic bilevel problems and motivates the epsilon-approximation and iterative scheme.","marker":"[18]"},{"why":"Provides the risk-guarantee setting and the 0-1 knapsack instance-generation procedure used in the experiments.","marker":"[15]"},{"why":"Provides the optimistic bilevel IEO formulation and the degeneracy problem that the pessimistic variant avoids.","marker":"[11]"},{"why":"Provides the prior pessimistic-bilevel study of decision-focused predictions that the paper extends and compares with.","marker":"[14]"},{"why":"Supplies the contextual-optimization framework and the estimate-then-optimize baseline the paper targets.","marker":"[7]"}],"fun_headline_variants":["Cut through decision regret: bilevel learning for combinatorial optimization","Pessimistic bilevel cuts beat SPO+ on knapsack","Worst-case regret training via bilevel cuts","Direct regret minimization for decision-focused learning","Bilevel cut generation reduces out-of-sample regret"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method assumes that a fixed positive constant $\\varepsilon$ is smaller than every nonzero predicted-cost gap $f_w(x_i)^T(z_e - \\bar z_i)$ that can arise, but the paper gives no rule for choosing or verifying $\\varepsilon$; if some gap falls in $(0, \\varepsilon)$, the reformulation treats a non-optimal point as optimal and the computed loss and predictor are not the true pessimistic IEO solution.","fun_headline_variants_meta":{"raw":{"variants":["Cut through decision regret: bilevel learning for combinatorial optimization","Pessimistic bilevel cuts beat SPO+ on knapsack","Worst-case regret training via bilevel cuts","Direct regret minimization for decision-focused learning","Bilevel cut generation reduces out-of-sample regret"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000832,"raw_usage":{"total_tokens":3598,"prompt_tokens":874,"completion_tokens":2724,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":490,"completion_tokens_details":{"reasoning_tokens":2647}},"tokens_in":490,"tokens_out":2724,"duration_ms":16721,"temperature":1.0,"reasoning_tokens":2647,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T10:21:52.896478+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small 0-1 knapsack instance, enumerate all feasible points, and train the method with a specific $\\varepsilon$; after fitting $w$, look for a training point and feasible $z_e$ with $0 < f_w(x_i)^T(z_e - \\bar z_i) < \\varepsilon$. If one exists, compare the true pessimistic loss obtained by full enumeration with the loss reported by the master problem; a mismatch on any such instance shows the $\\varepsilon$-approximation is not the exact pessimistic IEO loss.","supporting_citations":[{"cited_title":"Smart “predict, then optimize","cited_arxiv_id":null,"evidence_quote":"Supplies the SPO+ surrogate loss and its convex-hull treatment, which are the main baselines for the new method."},{"cited_title":"A practical scheme to compute the pessimistic bilevel optimization problem,","cited_arxiv_id":null,"evidence_quote":"Supplies the column-and-constraint generation scheme for pessimistic bilevel problems that the paper adapts to IEO."},{"cited_title":"Pessimistic bilevel op- timization,","cited_arxiv_id":null,"evidence_quote":"Establishes the difficulty of pessimistic bilevel problems and motivates the epsilon-approximation and iterative scheme."},{"cited_title":"Risk guarantees for end-to-end prediction and optimization processes,","cited_arxiv_id":null,"evidence_quote":"Provides the risk-guarantee setting and the 0-1 knapsack instance-generation procedure used in the experiments."},{"cited_title":"A bilevel framework for decision-making under uncertainty with contextual information,","cited_arxiv_id":null,"evidence_quote":"Provides the optimistic bilevel IEO formulation and the degeneracy problem that the pessimistic variant avoids."},{"cited_title":"Decision-focused predictions via pessimistic bilevel optimization: A computational study,","cited_arxiv_id":null,"evidence_quote":"Provides the prior pessimistic-bilevel study of decision-focused predictions that the paper extends and compares with."}],"review_version":1}