An Automatic Method of Solving Discrete Programming Problems.

Land, A. H., & Doig, A. G. (1960). An Automatic Method of Solving Discrete Programming Problems. Econometrica, 28(3), 497-520.

Type

Journal article

Intellectual base

Primary research

Year

1960

Volume

28

Issue

3

Pages

497-520

DOI

10.2307/1910129

DOI registrant

JSTOR

Link

https://doi.org/10.2307/1910129

Cited from

cognitive_science, computer_science, operations_research

Cited by

7 citations across 7 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Backtracking
  • Branch-and-bound is backtracking plus bounding.
• Branch and Bound
  • Branch and bound originates with

    This sourcethe original branch-and-bound paper, formalizing implicit enumeration via partition-and-bound for (mixed-)integer linear programming.

• Integer Linear Programming (ILP)
  • Land and Doig (1960) formalized branch-and-bound.

    This sourceFoundational branch-and-bound paper formalizing implicit enumeration through partition-and-bound for integer linear programming; widely credited as the original B&B publication in operations research.

• Navigation
  • And decision-tree pruning, the reasoning behind branch-and-bound, transferred to focused literature review, where the cost-of-traversal calculation becomes a reading-time budget over which citations to follow.

    This sourceIntroduces branch-and-bound — the cost-of-traversal pruning of a decision tree — the reasoning that transfers to focused, budget-bounded exploration.

Mechanisms

• Branch and Bound
  • The classic misuse is swapping the real bound for a heuristic estimate that is not guaranteed optimistic, to make it run faster; the moment the bound stops being admissible, the method can silently discard the region containing the best solution and still report a confident "optimum."

    This sourceExplains that a non-admissible bound can discard the region containing the best solution while still reporting an optimum.

• Integer Programming Solver
  • Branch and prune. Systematically split the feasible space on fractional variables, discarding whole branches that cannot improve on the incumbent — branch-and-bound, sharpened with cutting planes and heuristics.

    This sourceIntroduces a tree method that branches on nonintegral variables and prunes subproblems whose bounds cannot improve the incumbent.

• Search-Branch Pruning Test
  • This is the reasoning behind branch-and-bound and alpha-beta pruning — a provable dead end lets you discard a whole subtree without visiting it.

    This sourceDevelops branch-and-bound pruning, in which a bound proves that an entire branch cannot improve the incumbent and can be discarded without exhaustive search.

Verification

Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Not recorded. Neither this nor any other of the 7 citations of this work carries a recorded support check.

Was it audited? Yes. A second, independent pass read the citation against the article text and recorded a verdict.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

Registry ID ref:b94e7984e933 · see in the full table