An algorithm for the optimal solution of variable knockout problems

J.E. Beasley

REVIEW 3 major objections 5 minor 18 references

An algorithm for the optimal solution of variable knockout problems

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 1908.02031 v5 pith:TNYP7R7T submitted 2019-08-06 math.OC

J.E. Beasley This is my paper · ORCID

classification math.OC MSC 90C1090C2790C35

keywords variableknockoutzero-oneintegerprogrammingbileveloptimizationshortestpathinterdictionsetcoveringcardinalityconstraintnetwork

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

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

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

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

Referee Report

3 major / 5 minor

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.

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 (3)

[§2.1, Algorithm 1] 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).
[§2.1, blocking property] 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.
[§2.1, feasibility of the final knockout set] 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.

minor comments (5)

[Abstract and Section 1] 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.
[Algorithm 1 pseudocode] 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 2.2] 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 3, Tables 1 and 2] 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.
[References] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the knockout algorithm is constructive and its only self-citations are benchmark or solver infrastructure, not the knockout answer.

full rationale

I find no circular step in this paper. Algorithm 1 does not fit a parameter to the target result and then relabel it as a prediction; instead, it iteratively adds knockout constraints to exclude previously found feasible solutions and finally solves a set-covering problem over the recorded supports. The claim that this gives an optimal knockout set is an unproved correctness claim, not a circular derivation: the set-cover objective and constraints are not constructed from the final knockout set, and no quantity is defined in terms of the answer it is supposed to produce. The self-citations are limited to OR-Library test instances [5,6], set-covering algorithms [4,7,8], and the SCIP solver [1,17]; these are external tools or benchmark sources and do not encode the number or identity of arcs knocked out in the computational results. The passage 'It is trivial to show by means of an example that our knockout algorithm does not involve complete enumeration' is a completeness/efficiency assertion, not a reduction of the derivation to its inputs. Even if the algorithm has a correctness bug, such as the skeptic's concern about the terminal recorded solution being included in the final set cover, that would be a correctness issue, not circularity. Therefore the paper is not circular, and the appropriate score is 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The algorithm introduces no new physical or mathematical entities and fits no parameters. The thresholds, costs, and cardinality levels are user-specified inputs. The main load-bearing assumption is the unproved blocking property of the generated supports.

assumptions (3)

domain assumption Each integer program solved inside Algorithm 1 and Algorithm 2 is solved to proven global optimality by SCIP.
The claimed optimality of the knockout set inherits from exactness of every subproblem solve; Section 3 states SCIP 4.0.0 is used.
ad hoc to paper The stopping condition of Algorithm 1 implies the recorded supports form a blocking family for all deficient feasible solutions.
This is the unproved correctness step. The paper only gives an example after Algorithm 1 in Section 2.1, not a proof, and the final set-covering step relies on it.
domain assumption The underlying problem is formulated as a zero-one integer program, and setting a variable to zero corresponds to a meaningful knockout such as deleting an arc.
The knockout model in Section 1 equates variable knockout with forcing xi=0 via xi + alpha_i <= 1; the shortest path illustration uses the standard path-flow IP.

how reviews work

0 comments

Cite this review

Pith. "Pith review of An algorithm for the optimal solution of variable knockout problems." pith.science (2026). https://pith.science/paper/TNYP7R7T

@misc{pith2026190802031,
  author       = {Pith},
  title        = {Pith review of: An algorithm for the optimal solution of variable knockout problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TNYP7R7T}},
  note         = {Machine review of arXiv:1908.02031}
}

read the original abstract

We consider a class of problems related to variable knockout, where knockout means set a variable to zero. Given an optimisation problem formulated as a zero-one integer program the question we consider in this paper is what might be an appropriate set of variables to knockout of the problem, in order that the optimal solution to the problem that remains after variable knockout has a desired property. This property might be related to the optimal solution value after knockout, or require the problem after knockout to be infeasible. We present an algorithm for the optimal solution of this knockout problem. Computational results are given for an illustrative example based upon shortest path interdiction using publicly available shortest path test problems.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[1]

SCIP: Solving constraint integer program s

Achterberg T. SCIP: Solving constraint integer program s. Mathematical Programming Computation 2009;1(1):1–41

work page 2009
[2]

An improved hybrid al gorithm for the set covering problem

Al-Shihabi S, Arafeh M, Barghash M. An improved hybrid al gorithm for the set covering problem. Computers & Industrial Engineering 2015;85:328– 334

work page 2015
[3]

Shortest path network interdiction with asymmetric information

Bayrak H, Bailey MD. Shortest path network interdiction with asymmetric information. Networks 2008;52(3):133–140

work page 2008
[4]

An algorithm for set covering problem

Beasley JE. An algorithm for set covering problem. Europ ean Journal of Operational Re- search 1987;31(1):85–93

work page 1987
[5]

OR-Library: distributing test problems by e lectronic mail

Beasley JE. OR-Library: distributing test problems by e lectronic mail. Journal of the Op- erational Research Society 1990;41(11):1069–1072

work page 1990
[6]

An algorithm for the resource constrained shortest path prob- lem

Beasley JE, Christoﬁdes N. An algorithm for the resource constrained shortest path prob- lem. Networks 1989;19(4):379–394

work page 1989
[7]

A genetic algorithm for the set coveri ng problem

Beasley JE, Chu PC. A genetic algorithm for the set coveri ng problem. European Journal of Operational Research 1996;94(2):392–404

work page 1996
[8]

Enhancing an algorithm for set co vering problems

Beasley JE, Jornsten K. Enhancing an algorithm for set co vering problems. European Jour- nal of Operational Research 1992;58(2):293–300

work page 1992

Show all 18 references

[9]

A heuristic method for the set covering problem

Caprara A, Fischetti M, Toth P. A heuristic method for the set covering problem. Operations Research 1999;47(5):730–743

1999
[10]

Algorithms for the set co vering problem

Caprara A, Toth P, Fischetti M. Algorithms for the set co vering problem. Annals of Oper- ations Research 2000;98:353–371

2000
[11]

An overview of bilevel op timization

Colson B, Marcotte P, Savard G. An overview of bilevel op timization. Annals of Operations Research 2007;153(1):235–256

2007
[12]

Annotated bibliography on bilevel programmin g and mathematical programs with equilibrium constraints

Dempe S. Annotated bibliography on bilevel programmin g and mathematical programs with equilibrium constraints. Optimization 2003;52(3):3 33–359

2003
[13]

Shortest-path network interdictio n

Israeli E, Wood RK. Shortest-path network interdictio n. Networks 2002;40(2):97–111

2002
[14]

Bilevel programming and applications

Kalashnikov VV, Dempe S, Perez-Valdes GA, Kalashnykov a NI, Camacho-Vallejo JF. Bilevel programming and applications. Mathematical Probl ems in Engineering 2015;Article ID 310301. Available from http://dx.doi.org/10.1155/201 5/310301 Last accessed February 16 2020

2015 doi
[15]

An eﬀective and simple he uristic for the set covering problem

Lan GH, DePuy GW, Whitehouse GE. An eﬀective and simple he uristic for the set covering problem. European Journal of Operational Research 2007;17 6(3):1387–1403

2007
[16]

A bi-objective approach for shortest-path network inter- diction

Rocco CM, Ramirez-Marquez JE. A bi-objective approach for shortest-path network inter- diction. Computers & Industrial Engineering 2010;59(2):2 32–240

2010
[17]

Available from http://scip.zib.de/ Last accessed February 16 2020

SCIP: Solving constraint integer programs. Available from http://scip.zib.de/ Last accessed February 16 2020

2020
[18]

Bilevel and multilevel program ming: a bibliography review

Vicente LN, Calamai PH. Bilevel and multilevel program ming: a bibliography review. Jour- nal of Global Optimization 1994;5(3):291–306

1994

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

SCIP: Solving constraint integer program s

Achterberg T. SCIP: Solving constraint integer program s. Mathematical Programming Computation 2009;1(1):1–41

work page 2009

[2] [2]

An improved hybrid al gorithm for the set covering problem

Al-Shihabi S, Arafeh M, Barghash M. An improved hybrid al gorithm for the set covering problem. Computers & Industrial Engineering 2015;85:328– 334

work page 2015

[3] [3]

Shortest path network interdiction with asymmetric information

Bayrak H, Bailey MD. Shortest path network interdiction with asymmetric information. Networks 2008;52(3):133–140

work page 2008

[4] [4]

An algorithm for set covering problem

Beasley JE. An algorithm for set covering problem. Europ ean Journal of Operational Re- search 1987;31(1):85–93

work page 1987

[5] [5]

OR-Library: distributing test problems by e lectronic mail

Beasley JE. OR-Library: distributing test problems by e lectronic mail. Journal of the Op- erational Research Society 1990;41(11):1069–1072

work page 1990

[6] [6]

An algorithm for the resource constrained shortest path prob- lem

Beasley JE, Christoﬁdes N. An algorithm for the resource constrained shortest path prob- lem. Networks 1989;19(4):379–394

work page 1989

[7] [7]

A genetic algorithm for the set coveri ng problem

Beasley JE, Chu PC. A genetic algorithm for the set coveri ng problem. European Journal of Operational Research 1996;94(2):392–404

work page 1996

[8] [8]

Enhancing an algorithm for set co vering problems

Beasley JE, Jornsten K. Enhancing an algorithm for set co vering problems. European Jour- nal of Operational Research 1992;58(2):293–300

work page 1992