IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v67y2021i9p5349-5363.html
   My bibliography  Save this article

Optimization: From Its Inception

Author

Listed:
  • Thomas L. Magnanti

    (Department of Electrical Engineering and Computer Science and Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

Abstract

Optimization has been one of the most fundamental and extensive contributions of management science/operations research, with an enormous number of contributions and subfields developed by many researchers and practitioners. When the journal Management Science launched in 1954, little was known about optimization, including some results in nonlinear optimization and the simplex method and duality developed for linear programming. However, linear programming computations were limited to problems with at most 101 linear constraints. Then some early contributions by seminal researchers began to develop foundations for the field. I will review a few of these early contributions, focusing on the traveling sales problem and integer programming, decomposition, and column generation. I will summarize some research and applied contributions since then, including the enormous development of computations. I will focus on linear and integer programs with some material on combinatorial optimization.

Suggested Citation

  • Thomas L. Magnanti, 2021. "Optimization: From Its Inception," Management Science, INFORMS, vol. 67(9), pages 5349-5363, September.
    • Handle: RePEc:inm:ormnsc:v:67:y:2021:i:9:p:5349-5363
    DOI: 10.1287/mnsc.2021.3955
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.2021.3955
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.2021.3955?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Marshall L. Fisher, 2004. "The Lagrangian Relaxation Method for Solving Integer Programming Problems," Management Science, INFORMS, vol. 50(12_supple), pages 1861-1871, December.
    2. M. L. Balinski, 1965. "Integer Programming: Methods, Uses, Computations," Management Science, INFORMS, vol. 12(3), pages 253-313, November.
    3. Egon Balas, 1971. "Intersection Cuts—A New Type of Cutting Planes for Integer Programming," Operations Research, INFORMS, vol. 19(1), pages 19-39, February.
    4. Frank M. Bass, 1969. "A New Product Growth for Model Consumer Durables," Management Science, INFORMS, vol. 15(5), pages 215-227, January.
    5. A. Charnes & W. W. Cooper, 1954. "The Stepping Stone Method of Explaining Linear Programming Calculations in Transportation Problems," Management Science, INFORMS, vol. 1(1), pages 49-69, October.
    6. Andrew J. Clark & Herbert Scarf, 2004. "Optimal Policies for a Multi-Echelon Inventory Problem," Management Science, INFORMS, vol. 50(12_supple), pages 1782-1790, December.
    7. Wallace J. Hopp (Editor-in-Chief), 2004. "Ten Most Influential Papers of Management Science's First Fifty Years," Management Science, INFORMS, vol. 50(12_supple), pages 1763-1763, December.
    8. Ali Emrouznejad & Marianna Marra, 2017. "The state of the art development of AHP (1979–2017): a literature review with a social network analysis," International Journal of Production Research, Taylor & Francis Journals, vol. 55(22), pages 6653-6675, November.
    9. Harvey M. Wagner & Thomson M. Whitin, 1958. "Dynamic Version of the Economic Lot Size Model," Management Science, INFORMS, vol. 5(1), pages 89-96, October.
    10. P. C. Gilmore & R. E. Gomory, 1961. "A Linear Programming Approach to the Cutting-Stock Problem," Operations Research, INFORMS, vol. 9(6), pages 849-859, December.
    11. Richard M. Karp, 1977. "Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane," Mathematics of Operations Research, INFORMS, vol. 2(3), pages 209-224, August.
    12. Richard Bellman, 1954. "On some applications of the theory of dynamic programming to logistics," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 1(2), pages 141-153, June.
    13. George B. Dantzig, 1955. "Linear Programming under Uncertainty," Management Science, INFORMS, vol. 1(3-4), pages 197-206, 04-07.
    14. P. C. Gilmore & R. E. Gomory, 1963. "A Linear Programming Approach to the Cutting Stock Problem---Part II," Operations Research, INFORMS, vol. 11(6), pages 863-888, December.
    15. Hugh Everett, 1963. "Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources," Operations Research, INFORMS, vol. 11(3), pages 399-417, June.
    16. C. E. Lemke, 1954. "The dual method of solving the linear programming problem," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 1(1), pages 36-47, March.
    17. H. W. Kuhn, 1955. "The Hungarian method for the assignment problem," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 2(1‐2), pages 83-97, March.
    18. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    19. VAN ROY, Tony J. & WOLSEY, Laurence A., 1987. "Solving mixed integer programming problems using automatic reformulation," LIDAM Reprints CORE 782, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    20. Michael Held & Richard M. Karp, 1970. "The Traveling-Salesman Problem and Minimum Spanning Trees," Operations Research, INFORMS, vol. 18(6), pages 1138-1162, December.
    21. Richard Bellman, 1954. "Some Applications of the Theory of Dynamic Programming---A Review," Operations Research, INFORMS, vol. 2(3), pages 275-288, August.
    22. A. M. Geoffrion, 1969. "An Improved Implicit Enumeration Approach for Integer Programming," Operations Research, INFORMS, vol. 17(3), pages 437-454, June.
    23. Tony J. Van Roy & Laurence A. Wolsey, 1987. "Solving Mixed Integer Programming Problems Using Automatic Reformulation," Operations Research, INFORMS, vol. 35(1), pages 45-57, February.
    24. George B. Dantzig, 1957. "Discrete-Variable Extremum Problems," Operations Research, INFORMS, vol. 5(2), pages 266-288, April.
    25. Kurt Spielberg & Monique Guignard-Spielberg, 2007. "Preface: History of integer programming: distinguished personal notes and reminiscences," Annals of Operations Research, Springer, vol. 149(1), pages 3-4, February.
    26. John C. Harsanyi, 1967. "Games with Incomplete Information Played by "Bayesian" Players, I-III Part I. The Basic Model," Management Science, INFORMS, vol. 14(3), pages 159-182, November.
    27. Hau L. Lee & V. Padmanabhan & Seungjin Whang, 1997. "Information Distortion in a Supply Chain: The Bullwhip Effect," Management Science, INFORMS, vol. 43(4), pages 546-558, April.
    28. Gale, David, 1989. "The Theory of Linear Economic Models," University of Chicago Press Economics Books, University of Chicago Press, edition 1, number 9780226278841, September.
    29. William Orchard-Hays, 1990. "History of the Development of LP Solvers," Interfaces, INFORMS, vol. 20(4), pages 61-73, August.
    30. Harvey J. Greenberg & William P. Pierskalla, 1970. "Surrogate Mathematical Programming," Operations Research, INFORMS, vol. 18(5), pages 924-939, October.
    31. Ellis L. Johnson & George L. Nemhauser & Martin W.P. Savelsbergh, 2000. "Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition," INFORMS Journal on Computing, INFORMS, vol. 12(1), pages 2-23, February.
    32. Egon Balas, 1965. "An Additive Algorithm for Solving Linear Programs with Zero-One Variables," Operations Research, INFORMS, vol. 13(4), pages 517-546, August.
    33. Marshall L. Fisher, 2004. "Comments on ÜThe Lagrangian Relaxation Method for Solving Integer Programming ProblemsÝ," Management Science, INFORMS, vol. 50(12_supple), pages 1872-1874, December.
    34. M. Seetharama Gowda & Jong-Shi Pang, 1992. "On Solution Stability of the Linear Complementarity Problem," Mathematics of Operations Research, INFORMS, vol. 17(1), pages 77-83, February.
    35. T. L. Magnanti & J. F. Shapiro & M. H. Wagner, 1976. "Generalized Linear Programming Solves the Dual," Management Science, INFORMS, vol. 22(11), pages 1195-1203, July.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Gregorio Rius-Sorolla & Julien Maheut & Sofia Estelles-Miguel & Jose P. Garcia-Sabater, 2021. "Collaborative Distributed Planning with Asymmetric Information. A Technological Driver for Sustainable Development," Sustainability, MDPI, vol. 13(12), pages 1-23, June.
    2. Timo Gschwind & Stefan Irnich, 2014. "Dual Inequalities for Stabilized Column Generation Revisited," Working Papers 1407, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz, revised 23 Jul 2014.
    3. Patriksson, Michael, 2008. "A survey on the continuous nonlinear resource allocation problem," European Journal of Operational Research, Elsevier, vol. 185(1), pages 1-46, February.
    4. Aardal, K.I. & van Hoesel, S., 1995. "Polyhedral Techniques in Combinatorial Optimization," Other publications TiSEM ed028a07-eb6a-4c8d-8f21-d, Tilburg University, School of Economics and Management.
    5. Freville, Arnaud, 2004. "The multidimensional 0-1 knapsack problem: An overview," European Journal of Operational Research, Elsevier, vol. 155(1), pages 1-21, May.
    6. Ioannis Fragkos & Zeger Degraeve & Bert De Reyck, 2016. "A Horizon Decomposition Approach for the Capacitated Lot-Sizing Problem with Setup Times," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 465-482, August.
    7. Wallace J. Hopp & David Simchi-Levi, 2021. "Management Science : The Legacy of the Past and Challenge of the Future," Management Science, INFORMS, vol. 67(9), pages 5306-5316, September.
    8. Syam Menon & Ali Amiri, 2004. "Scheduling Banner Advertisements on the Web," INFORMS Journal on Computing, INFORMS, vol. 16(1), pages 95-105, February.
    9. Aardal, K.I. & van Hoesel, S., 1995. "Polyhedral Techniques in Combinatorial Optimization," Discussion Paper 1995-57, Tilburg University, Center for Economic Research.
    10. Sinuany-Stern, Zilla, 2023. "Foundations of operations research: From linear programming to data envelopment analysis," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1069-1080.
    11. Timo Gschwind & Stefan Irnich, 2016. "Dual Inequalities for Stabilized Column Generation Revisited," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 175-194, February.
    12. François Clautiaux & Cláudio Alves & José Valério de Carvalho & Jürgen Rietz, 2011. "New Stabilization Procedures for the Cutting Stock Problem," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 530-545, November.
    13. Yanling Chu & Xiaoju Zhang & Zhongzhen Yang, 2017. "Multiple quay cranes scheduling for double cycling in container terminals," PLOS ONE, Public Library of Science, vol. 12(7), pages 1-19, July.
    14. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    15. Ibrahim Muter & Tevfik Aytekin, 2017. "Incorporating Aggregate Diversity in Recommender Systems Using Scalable Optimization Approaches," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 405-421, August.
    16. Melega, Gislaine Mara & de Araujo, Silvio Alexandre & Jans, Raf, 2018. "Classification and literature review of integrated lot-sizing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 271(1), pages 1-19.
    17. Herbert Meyr & Mirko Kiel, 2022. "Minimizing setups and waste when printing labels of consumer goods," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(3), pages 733-761, September.
    18. Bian, Zheyong & Bai, Yun & Douglas, W. Scott & Maher, Ali & Liu, Xiang, 2022. "Multi-year planning for optimal navigation channel dredging and dredged material management," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 159(C).
    19. G. Rius-Sorolla & J. Maheut & Jairo R. Coronado-Hernandez & J. P. Garcia-Sabater, 2020. "Lagrangian relaxation of the generic materials and operations planning model," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 28(1), pages 105-123, March.
    20. Syam Menon & Rakesh Gupta, 2008. "Optimal Broadcast Scheduling in Packet Radio Networks via Branch and Price," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 391-399, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:67:y:2021:i:9:p:5349-5363. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.