Integer and Combinatorial Optimization¶
Nemhauser, G., & Wolsey, L. (1988). Integer and Combinatorial Optimization. John Wiley & Sons.
Cited by¶
4 citations across 3 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Branch and Bound
- In operations research, branch-and-bound is the bridge between the theoretical study of combinatorial optimization and its practical realization (formalized in Nemhauser and Wolsey's (1988)
This sourcecanonical treatise on integer/combinatorial optimization; the standard reference for branch-and-bound theory, polyhedral methods, and relaxation-based bounds.
- 6
This sourcetreats the trade-off between bound tightness (stronger relaxations and cutting planes) and the cost of computing those bounds — source for the 'tighter relaxation does not always win' tension.
- In operations research, branch-and-bound is the bridge between the theoretical study of combinatorial optimization and its practical realization (formalized in Nemhauser and Wolsey's (1988)
- Integer Linear Programming (ILP)
- In polyhedral combinatorics, the study of the integer hull (the convex hull of integer points satisfying the constraints) connects directly to formulation strength; finding tight descriptions of integer hulls for specific problem classes has been a major research program, codified in Nemhauser and Wolsey's (1988) reference work on integer and combinatorial optimization.
This sourceCanonical comprehensive treatise on integer and combinatorial optimization; the standard reference for branch-and-bound theory, polyhedral methods, and relaxation-based bounds.
Supported in partVerified against the publisher's abstract
Publisher abstract supports the book as an encyclopedic reference on integer/combinatorial optimization and LP/IP formulation, but does not state the specific integer-hull research-program claim.
“A unifying approach to optimization problems is to formulate them like linear programming problems, while restricting some or all of the variables to the integers. This book is an encyclopedic resource for such f”
- In polyhedral combinatorics, the study of the integer hull (the convex hull of integer points satisfying the constraints) connects directly to formulation strength; finding tight descriptions of integer hulls for specific problem classes has been a major research program, codified in Nemhauser and Wolsey's (1988) reference work on integer and combinatorial optimization.
Mechanisms¶
- Algorithmic Relaxation
- The canonical device here is the LP relaxation: drop the integrality requirement, solve the easy continuous problem, and use its value as a bound on the hard one.
This sourceDefines linear-programming relaxation by replacing integrality with a continuous domain and using the relaxed optimum to bound the integer problem.
- The canonical device here is the LP relaxation: drop the integrality requirement, solve the easy continuous problem, and use its value as a bound on the hard one.
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? Read against the text for 1 of 4 citations: 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
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.
Links previously used in the corpus¶
Before the registry existed this work was also linked 1 other way.
Registry ID ref:f6c0fdb0f6c8 · see in the full table