The DOI matches its Crossref record; 10 of the 10 references it cites were found in a registry or an index.
Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria
Abstract
This paper proposes methodology for improving the performance of Benders decomposition when applied to mixed integer programs. It introduces a new technique for accelerating the convergence of the algorithm and theory for distinguishing “good” model formulations of a problem that has distinct but equivalent mixed integer programming representations. The acceleration technique is based upon selecting judiciously from the alternate optima of the Benders subproblem to generate strong or pareto-optimal cuts. This methodology also applies to a much broader class of optimization algorithms that includes Dantzig-Wolfe decomposition for linear and nonlinear programs and related “cutting plane” type algorithms that arise in resource directive and price decomposition. When specialized to network location problems, this cut generation technique leads to very efficient algorithms that exploit the underlying structure of these models. In discussing the “proper” formulation of mixed integer programs, we suggest criteria for comparing various mixed integer formulations of a problem and for choosing formulations that can provide stronger cuts for Benders decomposition. From this discussion intimate connections between the previously disparate viewpoints of strong Benders cuts and tight linear programming relaxations of integer programs emerge.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Linear Programming and Extensions
Dantzig, G. (1963) · RAND Corporation eBooks · doi:10.7249/r366 · Cited by 5,755
Partitioning procedures for solving mixed-variables programming problems
Benders, J. F. (1962) · Numerische Mathematik · doi:10.1007/bf01386316 · Cited by 3,855
Nemhauser, G. L., & Wolsey, L. A. (1972) · Cited by 3,371
Optimization Theory of Large Systems
Lasdon, L. S., & Tabak, D. (1971) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/tsmc.1971.4308301 · Cited by 1,677
Multicommodity Distribution System Design by Benders Decomposition * † ‡
Geoffrion, A. M., & Graves§, G. W. (2010) · International Series in Operations Research & Management Science · doi:10.1007/978-1-4419-6810-4_4 · Cited by 978
A Dual-Based Procedure for Uncapacitated Facility Location
Erlenkotter, D. (1978) · Operations Research · doi:10.1287/opre.26.6.992 · Cited by 912
Cornuéjols, G., Fisher, M. L., & Nemhauser, G. L. (1979) · Management Science · doi:10.1287/mnsc.25.8.808 · Cited by 430
Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
Nemhauser, G. L., & Wolsey, L. A. (1981) · North-Holland mathematics studies · doi:10.1016/s0304-0208(08)73471-6 · Cited by 138
Enumerative Methods in Integer Programming
Spielberg, K. (1979) · Annals of discrete mathematics · doi:10.1016/s0167-5060(08)70347-9 · Cited by 29
A Generalized Approach to Dantzig-Wolfe Decomposition for Concave Programs
Holloway, C. A. (1973) · Operations Research · doi:10.1287/opre.21.1.210 · Cited by 21
Cited by
Routing and scheduling of vehicles and crews
Raff, S. (1983) · Computers & Operations Research · doi:10.1016/0305-0548(83)90030-8 · Cited by 867
Biegler, L. T., & Grossmann, I. E. (2004) · Computers & Chemical Engineering · doi:10.1016/j.compchemeng.2003.11.003 · Cited by 593
A survey of variants and extensions of the location-routing problem
Drexl, M., & Schneider, M. (2015) · European Journal of Operational Research · doi:10.1016/j.ejor.2014.08.030 · Cited by 465
Aldrighetti, R., Battini, D., Ivanov, D., & Zennaro, I. (2021) · International Journal of Production Economics · doi:10.1016/j.ijpe.2021.108103 · Cited by 377
Optimal solutions to a real-world integrated airline scheduling problem
Cacchiani, V., & Salazar-González, J.-J. (2017) · Transportation Science · doi:10.1287/trsc.2015.0655 · Cited by 64
Metadata
- Authors
- Magnanti, T. L., & Wong, R. T.
- Venue
- Operations Research
- Published
- 1981-06
- Volume
- 29
- Issue
- 3
- Pages
- 464-484
- ISSN
- 0030-364X (ISSN-L)
- 1526-5463
- OpenAlex
- W2086522200
- Cited by
- 731
- References
- 10
- FWCI
- 4.92
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria. https://app.cochat.ai/papers/10.1287/opre.29.3.464
- The paper
- Magnanti, T. L., & Wong, R. T. (1981). Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria. Operations Research. https://doi.org/10.1287/opre.29.3.464
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.