{"id":"d1a55aae-7939-4e83-966f-bc52735c8fb6","arxiv_id":"1908.02031","paper_version":5,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An iterative generate-and-cover algorithm computes optimal variable knockout sets for integer programs, demonstrated on shortest path interdiction instances.","lead":"This paper presents a two-phase algorithm for choosing which variables to set to zero in an integer program so that the remaining problem's optimal value meets a target, or becomes infeasible. It illustrates the method on shortest path arc deletion problems using public test networks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1's final set cover includes the terminal solution that already satisfies the target, forcing unnecessary knockouts; it is not optimal as written.","rationale":"The reader's weakest assumption is the blocking property. That property is actually a consequence of the while-loop stopping rule: if a feasible solution with value below C* survived at termination, it would be feasible for the last MIP, forcing an objective below C*. Thus every deficient solution contains at least one recorded support, and hitting all deficient recorded supports hits all deficient solutions. The real problem is that Algorithm 1 does not restrict the final set cover to deficient supports. Because S is incremented before the while condition is retested, the terminal good solution is included in the set cover. The counterexample shows the algorithm can force an extra knockout and return cost 2 instead of 1. This invalidates the stated optimality of Algorithm 1 as written, but the flaw is localized and repairable: use only recorded supports corresponding to solutions with value below C* (or, if the loop never runs, return the empty set), and optionally add feasibility constraints to the final optimization as the paper already suggests. Therefore the manuscript needs a revision, not a categorical rejection; the verdict should remain CONDITIONAL. The reader's concern about the blocking property is real as a rigor gap, but it is not the decisive issue, hence partial agreement.","tokens_in":6168,"tokens_out":16149,"duration_ms":183436,"concrete_test":"Run Algorithm 1 exactly as written on the two-point IP above: feasible supports {1,2} with objective 1 and {3} with objective 5, C* = 5, unit knockout costs. Record the returned knockout cost; it will be 2. Then recompute the same instance with the final set cover restricted to recorded supports whose solution value is below C* (here only {1,2}); the minimum cost is 1. The difference is direct evidence that including the terminating good solution causes the suboptimality.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In §2.1 the final set-covering step of Algorithm 1 minimizes sum_i d_i alpha_i subject to sum_{i in F(s)} alpha_i >= 1 for every recorded solution s = 1,...,S. The pseudocode increments S and records the new solution before testing the while condition, so F(S) is the solution that caused termination because it already has the desired property. That solution should not need to be knocked out; requiring a hit in it can only increase the knockout cost. This is not a missing proof but a concrete failure of optimality. Example: let the zero-one IP have exactly two feasible points, A = (1,1,0) with support F(A) = {1,2} and objective value 1, and B = (0,0,1) with support F(B) = {3} and objective value 5. (This feasible set is expressible as an IP by adding no-good constraints excluding the other six binary points.) Let C* = 5 and all knockout costs be 1. Algorithm 1 records F(1) = {1,2}; since 1 < 5, it solves with alpha_1 + alpha_2 >= 1. The only remaining feasible solution is B, so it records F(2) = {3} and exits. The final set cover must satisfy alpha_1 + alpha_2 >= 1 and alpha_3 >= 1, so its minimal cost is 2. But the true optimal knockout set is {1} (or {2}), cost 1: after knocking out variable 1, A is infeasible and B remains, so the remaining optimum is 5. Hence the algorithm returns a suboptimal answer on an instance the paper claims to solve optimally. The blocking property flagged in the reader's verdict can in fact be proved once the set cover is restricted to recorded supports with value below C*; the real defect is the inclusion of F(S) and the analogous empty-set case when the original optimum already meets C*.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper considers the variable knockout problem for zero-one integer programs: choose a minimum-cost set of variables to force to zero so that the remaining problem has a desired property, typically an optimal value at least C* or infeasibility. The author proposes Algorithm 1, which repeatedly solves the original problem with added knockout constraints that exclude previously found supports, records the nonzero variables of each solution, and once a solution with the desired property is found, solves a set-covering problem over the recorded supports to determine the optimal knockout set. A cardinality-constrained variant, Algorithm 2, is also given. Computational experiments apply the method to shortest path interdiction instances from OR-Library, reporting minimal numbers of arcs to remove to raise the shortest path length to 1.5 or 2 times its original value, plus results for K-arc cardinality-constrained knockout. The paper claims optimality of Algorithm 1 but provides no formal proof of the key stopping property.","tokens_in":6541,"tokens_out":7802,"duration_ms":138336,"significance":"If correct, the proposed algorithm is attractive because it is problem-generic, requires no problem-specific structure, and connects variable knockout to set covering, with publicly available test instances and reproducible SCIP-based experiments. The computational results are clearly reported and the idea of generating supports by iterated solves is natural. However, the central optimality claim is currently not supported: Algorithm 1 as written can return a provably suboptimal knockout set, and the blocking property that justifies the final set cover is asserted rather than proved. With a corrected set-covering step and a rigorous proof, the framework could be a useful contribution to bilevel-style optimization where the lower-level optimal value is constrained. As it stands, the main algorithmic claim is not established.","major_comments":[{"comment":"The final set-covering step includes the terminal solution F(S), but this is the first solution that already has the desired property and therefore should not be knocked out. Since S is incremented after recording the solution that causes the while loop to terminate, F(S) is exactly the solution that satisfied the threshold condition. Requiring a hit in F(S) can only increase the knockout cost and may render the final optimization infeasible when feasibility-preserving constraints are added. Concretely, let the feasible set be exactly A=(1,1,0) with objective value 2 and B=(0,0,1) with objective value 5, let C*=5, and let all knockout costs be 1. Algorithm 1 records F(1)={1,2}, solves with alpha_1+alpha_2>=1, then records F(2)={3} and terminates. The final cover alpha_1+alpha_2>=1, alpha_3>=1 has optimal cost 2, while the true optimal knockout is {1} with cost 1: after setting x1=0, A is infeasible, B remains feasible, and the remaining optimal value is 5. Thus Algorithm 1 returns a suboptimal answer on an instance within the stated problem class. The set cover should be formed only over the deficient recorded supports F(1),...,F(S-1).","section":"§2.1, Algorithm 1"},{"comment":"The paper does not prove that, when the while loop stops, every unrecorded feasible solution with value below C* contains at least one of the recorded supports F(s). This is the load-bearing property that justifies the final set-covering formulation. The sentence 'It is trivial to show by means of an example...' is not a proof. A rigorous argument is needed: after the final solve, if a deficient solution were feasible for all knockout constraints for s=1,...,S-1, then because it has lower objective value than the terminal solution, the last solve would have selected it, a contradiction. This blocking property is true for the corrected set cover, but it must be stated and proved explicitly, including the case where multiple optimal solutions exist in the lower-level solves.","section":"§2.1, blocking property"},{"comment":"The final optimization in Algorithm 1 is described as finding a set that 'eliminate[s] all solutions' F(1),...,F(S). For the threshold property 'optimal value at least C*', the terminal solution F(S) should be preserved, not eliminated. If the final set cover is allowed to remove all feasible solutions, the resulting problem is infeasible and the threshold property is not satisfied in the sense defined in Section 1, unless infeasibility is explicitly accepted as a separate desired property. The technical note about adding Equations (2),(3),(5) addresses preservation but is not integrated into the pseudocode and still does not fix the unnecessary terminal constraint. The pseudocode and the surrounding text should be revised so the final set cover is explicitly restricted to deficient solutions and preserves at least one feasible solution attaining the threshold.","section":"§2.1, feasibility of the final knockout set"}],"minor_comments":[{"comment":"The term 'optimal solution' is used for both the knockout set and the lower-level optimization; this is understandable in context, but the paper would benefit from a formal problem statement with a named theorem stating the claimed optimality of Algorithm 1.","section":"Abstract and Section 1"},{"comment":"The pseudocode does not specify how to handle the case where the optimization becomes infeasible: the line 'F(S) <- non-zero variables in the current solution' has no meaning if no solution exists. The infeasibility property is discussed in the text but not reflected in the pseudocode.","section":"Algorithm 1 pseudocode"},{"comment":"Algorithm 2 relies on the same unproved blocking property as Algorithm 1, and the statement 'repeat the solution process until the problem is infeasible' should clarify that the final solve is performed with knockout constraints for the feasible solutions found before the infeasible run, and that the reduction S <- S-1 achieves this.","section":"Section 2.2"},{"comment":"The computational tables would be more informative if each row reported whether the knockout set was proven optimal by the integer solver and whether the reported time is for the whole process including the final set-covering solve. Also, a sentence describing the construction of the directed network instances in [6] would improve reproducibility.","section":"Section 3, Tables 1 and 2"},{"comment":"Reference [5] is listed as 'OR-Library: distributing test problems by electronic mail'; the URL for OR-Library would be a useful addition. Reference [17] already includes a URL, so consistency in format is desirable.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The concrete counterexample in §2.1 is decisive: Algorithm 1 as written is not optimal. The fix is local—exclude the terminal solution from the set cover and add a proof of the blocking property—so the paper is not beyond repair. I recommend major revision rather than rejection because the central idea is sound and the computational study is useful, but the optimality claim must be corrected and rigorously supported before publication. I also suggest the author check whether the same terminal-solution issue affects Algorithm 2 in edge cases where the infeasibility condition is reached with recorded solutions that all have high value."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper gives a generic formulation for variable knockout in zero-one IPs and an iterative algorithm that looks like a specialization of well-known row-generation ideas in network interdiction. The writing is clear, the OR-Library instances are public, and the cardinality-constrained variant is a useful addition. The reader's conditional verdict is roughly right, but the stress-test note found a concrete bug that is more serious than a missing proof: Algorithm 1, as written, is not optimal.\n\nThe pseudocode initializes S=1 with the optimal solution F(1). Inside the while loop, after each optimization it increments S and records the new solution before re-checking the while condition. So when the solved problem first returns a solution with the desired property, that solution is recorded as F(S) and then included in the final set cover. The final cover thus contains a constraint that at least one variable from a 'good' solution must be knocked out. That is unnecessary and can only increase the knockout cost. The stress-test example is correct: two feasible solutions, supports {1,2} and {3}, C*=5, unit costs; Algorithm 1 gives cost 2, while knocking out variable 1 alone costs 1 and achieves the property. I checked the pseudocode step-by-step and the flaw is real. The computational results in Section 3 are affected because the reported 'minimal' knockout counts may be overestimates.\n\nThe good news is that the fix is tiny: exclude F(S) from the final set-covering step, or restructure the loop so the terminal solution is not recorded. Once that is done, the blocking property can be proved in a few lines: any unrecorded deficient solution would have been feasible for the last constrained IP and would contradict its optimal value. The paper should have included that proof instead of the 'it is trivial' remark. The feasibility edge case mentioned in Section 2.1 is also under-specified, but it is not the main problem.\n\nI would not cite this version, and the experimental claims need to be redone after the fix. But the core idea is sound and the paper is a reasonable draft for a specialized OR venue. It deserves a referee, not a desk reject, because the defect is identifiable and fixable, and the generic formulation may be worth recording. Give it to someone familiar with the shortest-path interdiction literature—it should also cite and compare against Israeli and Wood (2002).","headline":"Algorithm 1 has a real off-by-one: it records the first feasible solution that already satisfies the target property and then forces the set cover to hit it, inflating knockout costs; the paper is otherwise a plausible generic interdiction method needing a small fix.","tokens_in":7022,"tokens_out":5401,"would_cite":false,"duration_ms":58346,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C10","90C27","90C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims an iterative knockout loop plus a final set covering step finds a minimum-cost set of variables to delete so that the remaining zero-one integer program attains a target optimal value.","keywords":["variable knockout","zero-one integer programming","bilevel optimization","shortest path interdiction","set covering","cardinality constraint","network interdiction"],"falsifier":"Take a small zero-one integer program with few enough variables to enumerate all feasible solutions, run Algorithm 1, and check whether the returned knockout set leaves any feasible solution with value below the target; a single unrecorded surviving solution would falsify the optimality claim.","tokens_in":1491,"feed_emoji":"🎯","tokens_out":1772,"duration_ms":84092,"temperature":0.7,"pith_summary":"The paper considers the variable knockout problem: given a zero-one integer program, choose a minimum-cost set of variables to force to zero so that the program that remains has an optimal value at least a target C*, or becomes infeasible. It claims that a simple iterative procedure solves this problem optimally. The procedure repeatedly solves the underlying program with added constraints requiring every recorded solution support to be hit, records the support of each new solution, and stops once the current solution satisfies the target. The recorded supports are then fed into a set covering problem whose solution is the optimal knockout set. This target-optimal-value constraint is what separates the problem from ordinary bilevel optimization: adding an explicit constraint that the objective exceed C* would not preclude all low-value solutions.","feed_headline":"Knockout loop plus set cover finds minimum-cost deletions","feed_subtitle":"For any binary integer program, the same loop finds the smallest deletion set that blocks all solutions below a target value.","key_machinery":"The load-bearing object is the support F(s) of a feasible solution, defined as the set of variables equal to one in that solution. Each recorded support generates a knockout constraint that at least one variable from F(s) must be knocked out, expressed as a sum over the support of the knockout indicators being at least one. The iterative solve-and-record loop is the mechanism that collects supports until the desired property holds, and the set covering optimization over those recorded supports is the mechanism that produces the minimum-cost knockout set. The coupling constraint x_i + alpha_i <= 1 connects each knockout decision to the underlying variable, ensuring that a knocked-out variable is forced to zero.","core_discovery":"The central claim is that Algorithm 1 finds an optimal knockout set for any zero-one integer program. The algorithm starts from an optimal solution F(1) of the original problem and imposes the knockout constraint that at least one variable from F(1) must be knocked out. It keeps solving the restricted problem, each time recording the support F(s) of the new solution and adding a constraint that every recorded support must be hit; the loop stops when the solution found has value at least C* (or is infeasible). The final optimization, minimizing the cost of the chosen knockout variables subject to a set covering constraint for each recorded F(s), then selects the minimum-cost knockout set. The paper also gives a cardinality version, Algorithm 2, which repeats the loop until the restricted problem is infeasible and returns the best feasible value achievable with exactly K knockouts. Computational results on shortest-path instances illustrate the claim; for one 100-node network with an 80-unit shortest path, the algorithm reports that two arcs must be knocked out to raise the path to at least 120.","pith_inferences":["Beyond the paper's example-based argument, a formal proof of Algorithm 1's optimality would require showing that the loop's stopping condition implies every unrecorded feasible solution below the target contains at least one recorded support; the paper does not supply that proof.","A natural computational check, not reported in the paper, is to run Algorithm 1 on small random zero-one programs where complete enumeration is possible and verify that the returned knockout set eliminates every feasible solution below the target.","The paper's suggested replacement of x_i + alpha_i <= 1 with x_i + M_i alpha_i <= M_i extends the loop to integer and continuous variables, opening the method to knapsack, assignment, and network design models where supports may be denser."],"forward_implications":["Any zero-one integer program with a target optimal value can in principle be handled by the same loop, with no problem-specific structure required.","For shortest-path interdiction, the minimum number of arcs whose deletion forces the origin-destination path length to reach a multiple of the original length is computed by treating each arc as a zero-one variable and solving a sequence of integer programs.","The cardinality variant yields, for each K, the largest shortest-path length achievable by knocking out exactly K arcs.","If the desired property is infeasibility, the same recorded-support loop applies and the final set cover gives the minimum knockout set that leaves no feasible solution.","The final optimization is a set covering problem, so existing exact or heuristic set covering methods can be used for very large knockout instances."],"supporting_citations":[{"why":"Supplies the integer programming solver used for every lower-level optimisation in the computational tests.","marker":"[1]"},{"why":"Provides an algorithm for the set covering problem that forms the final knockout optimisation step.","marker":"[4]"},{"why":"Makes the computational test instances publicly available for future knockout studies.","marker":"[5]"},{"why":"Supplies the directed network instances used in the shortest-path knockout experiments.","marker":"[6]"},{"why":"Defines the shortest-path network interdiction problem whose knockout version this paper solves optimally.","marker":"[13]"}],"fun_headline_variants":["Loop plus set cover finds optimal knockout sets","Minimum-cost deletions via hitting-set loop","Optimal variable knockout by iterative set cover","Set cover trick solves zero-one knockout problems"],"cache_read_input_tokens":9088,"weakest_assumption_plain":"The algorithm's optimality rests on the unproved blocking property that every feasible solution with value below the target contains at least one of the recorded supports, so that hitting the recorded supports necessarily kills every deficient solution.","fun_headline_variants_meta":{"raw":{"variants":["Loop plus set cover finds optimal knockout sets","Minimum-cost deletions via hitting-set loop","Optimal variable knockout by iterative set cover","Set cover trick solves zero-one knockout problems"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000175,"raw_usage":{"total_tokens":1242,"prompt_tokens":860,"completion_tokens":382,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":476,"completion_tokens_details":{"reasoning_tokens":328}},"tokens_in":476,"tokens_out":382,"duration_ms":5015,"temperature":1.0,"reasoning_tokens":328,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:56:16.285441+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small zero-one integer program with few enough variables to enumerate all feasible solutions, run Algorithm 1, and check whether the returned knockout set leaves any feasible solution with value below the target; a single unrecorded surviving solution would falsify the optimality claim.","supporting_citations":[{"cited_title":"SCIP: Solving constraint integer program s","cited_arxiv_id":null,"evidence_quote":"Supplies the integer programming solver used for every lower-level optimisation in the computational tests."},{"cited_title":"An algorithm for set covering problem","cited_arxiv_id":null,"evidence_quote":"Provides an algorithm for the set covering problem that forms the final knockout optimisation step."},{"cited_title":"OR-Library: distributing test problems by e lectronic mail","cited_arxiv_id":null,"evidence_quote":"Makes the computational test instances publicly available for future knockout studies."},{"cited_title":"An algorithm for the resource constrained shortest path prob- lem","cited_arxiv_id":null,"evidence_quote":"Supplies the directed network instances used in the shortest-path knockout experiments."},{"cited_title":"Shortest-path network interdictio n","cited_arxiv_id":null,"evidence_quote":"Defines the shortest-path network interdiction problem whose knockout version this paper solves optimally."}],"review_version":1}