{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T15:08:40Z","timestamp":1742396920560},"reference-count":81,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["INFORMS Journal on Computing"],"published-print":{"date-parts":[[2000,2]]},"abstract":" This paper is about modeling and solving mixed integer programming (MIP) problems. In the last decade, the use of mixed integer programming models has increased dramatically. Fifteen years ago, mainframe computers were required to solve problems with a hundred integer variables. Now it is possible to solve problems with thousands of integer variables on a personal computer and obtain provably good approximate solutions to problems such as set partitioning with millions of binary variables. These advances have been made possible by developments in modeling, algorithms, software, and hardware. This paper focuses on effective modeling, preprocessing, and the methodologies of branch-and-cut and branch-and-price, which are the techniques that make it possible to treat problems with either a very large number of constraints or a very large number of variables. We show how these techniques are useful in important application areas such as network design and crew scheduling. Finally, we discuss the relatively new research areas of parallel integer programming and stochastic integer programming. <\/jats:p>","DOI":"10.1287\/ijoc.12.1.2.11900","type":"journal-article","created":{"date-parts":[[2003,4,22]],"date-time":"2003-04-22T15:12:40Z","timestamp":1051024360000},"page":"2-23","source":"Crossref","is-referenced-by-count":115,"title":["Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition"],"prefix":"10.1287","volume":"12","author":[{"given":"Ellis L.","family":"Johnson","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, School of Industrial and Systems Engineering, Atlanta, GA 30332-0205"}]},{"given":"George L.","family":"Nemhauser","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, School of Industrial and Systems Engineering, Atlanta, GA 30332-0205"}]},{"given":"Martin W.P.","family":"Savelsbergh","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, School of Industrial and Systems Engineering, Atlanta, GA 30332-0205"}]}],"member":"109","reference":[{"key":"B1","first-page":"677","author":"Anbil R.","year":"1998","journal-title":"Documenta Mathematica"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1147\/sj.311.0071"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1287\/inte.25.1.69"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581273"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(96)00007-7"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.26.1.86"},{"key":"B9","first-page":"7","volume-title":"Optimization in Industry II","author":"Barnhart C.","year":"1994"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1287\/opre.46.3.316"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-5203-1_14"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70351-0"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584074"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1287\/inte.29.1.49"},{"key":"B15","volume-title":"Introduction to Stochastic Programming","author":"Birge J.","year":"1997"},{"key":"B16","volume-title":"AIMMS The Modeling System","author":"Bisschop J.","year":"1993"},{"key":"B17","unstructured":"Bixby R.E., Boyd E.A., Dadmehr S.S., Indovina R.R. The MIPLIB Mixed Integer Programming Library, Technical Report R92-36. (1992) (Rice University, Houston, Texas)"},{"key":"B18","first-page":"12","volume":"58","author":"Bixby R.E.","year":"1998","journal-title":"Optima"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(88)90160-9"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1287\/inte.27.1.7"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580428"},{"key":"B23","volume-title":"GAMS, A User's Guide","author":"Brooke A.","year":"1988"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1287\/inte.27.1.128"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1007\/BF02023053"},{"key":"B26","first-page":"45","volume-title":"Annotated Bibliographies in Combinatorial Optimization","author":"Caprara A.","year":"1997"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90167-2"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580109"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-69346-7_22"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1287\/opre.31.5.803"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2.4.393"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1287\/opre.7.1.58"},{"key":"B35","first-page":"35","volume-title":"Handbooks in Operations Research and Management Science, Volume 8: Network Routing","author":"Desrosiers J.","year":"1995"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(93)90044-O"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.12.7.576"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1137\/0804046"},{"key":"B39","first-page":"110","volume-title":"Proceedings of the 4th International IPCO Conference","author":"Escudero L.F.","year":"1996"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.20.5.736"},{"key":"B41","volume-title":"AMPL: A Modeling Language for Mathematical Programming","author":"Fourer R.","year":"1993"},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1287\/opre.42.6.1042"},{"key":"B44","first-page":"591","volume-title":"Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms","author":"Goemans M.X.","year":"1997"},{"key":"B45","unstructured":"Gomory R. An Algorithm for the Mixed Integer Problem. (1960) (The Rand Corporation, Santa Monica, CA) . Technical Report RM-2597"},{"key":"B46","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1958-10224-4"},{"key":"B47","first-page":"1195","volume":"32","author":"Gr\u00f6tschel M.","year":"1984","journal-title":"Research"},{"key":"B48","doi-asserted-by":"publisher","DOI":"10.1287\/opre.40.2.309"},{"key":"B49","first-page":"617","volume-title":"Handbooks in Operations Research and Management Science, Volume 7: Network Models","author":"Gr\u00f6tschel M.","year":"1995"},{"key":"B50","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582117"},{"key":"B51","doi-asserted-by":"publisher","DOI":"10.1287\/moor.11.4.537"},{"key":"B52","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.10.4.427"},{"key":"B53","doi-asserted-by":"publisher","DOI":"10.1080\/07408179708966344"},{"key":"B54","doi-asserted-by":"publisher","DOI":"10.1287\/opre.29.1.49"},{"key":"B55","doi-asserted-by":"publisher","DOI":"10.1287\/moor.22.3.513"},{"key":"B56","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585938"},{"key":"B57","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.3.2.121"},{"key":"B58","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.39.6.657"},{"key":"B59","doi-asserted-by":"publisher","DOI":"10.1287\/inte.28.1.75"},{"key":"B61","volume-title":"Planning Under Uncertainty","author":"Infanger G.","year":"1994"},{"key":"B62","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-83724-1_1"},{"key":"B63","first-page":"169","volume":"16","author":"Johnson E.L.","year":"1982","journal-title":"Annals of Discrete Mathematics"},{"key":"B64","first-page":"225","volume-title":"Handbooks in Operations Research and Management Science, Volume 7: Network Models","author":"J\u00fcnger M.","year":"1995"},{"key":"B66","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(98)00013-3"},{"key":"B67","volume-title":"Stochastic programming","author":"Kall P.","year":"1994"},{"key":"B69","doi-asserted-by":"publisher","DOI":"10.2307\/1910129"},{"key":"B70","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(93)90002-X"},{"key":"B71","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"B72","unstructured":"Linderoth J.Topics in Parallel Integer Programming (1998) (Georgia Institute of Technology, Atlanta, GA) . Ph.D. Thesis"},{"key":"B73","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.11.2.173"},{"key":"B74","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050044"},{"key":"B75","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(92)90028-2"},{"key":"B76","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.44.8.1100"},{"key":"B77","doi-asserted-by":"publisher","DOI":"10.1287\/opre.37.4.531"},{"key":"B78","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(94)90013-2"},{"key":"B79","doi-asserted-by":"publisher","DOI":"10.1002\/9781118627372"},{"key":"B80","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(87)90002-2"},{"key":"B81","doi-asserted-by":"publisher","DOI":"10.1287\/opre.33.4.842"},{"key":"B82","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.6.4.445"},{"key":"B83","first-page":"453","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Savelsbergh M.W.P.","year":"1998"},{"key":"B84","volume-title":"Theory of Linear and Integer Programming","author":"Schrijver A.","year":"1986"},{"key":"B85","doi-asserted-by":"publisher","DOI":"10.1287\/inte.25.1.6"},{"key":"B86","doi-asserted-by":"publisher","DOI":"10.1287\/opre.19.4.1070"},{"key":"B88","doi-asserted-by":"publisher","DOI":"10.1287\/opre.45.2.188"},{"key":"B89","volume-title":"Model Building in Mathematical Programming","author":"Williams H.P.","year":"1978"},{"key":"B90","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.10.3.261"},{"key":"B91","volume-title":"Integer Programming","author":"Wolsey L.A.","year":"1998"}],"container-title":["INFORMS Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/ijoc.12.1.2.11900","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T11:45:20Z","timestamp":1680435920000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/ijoc.12.1.2.11900"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,2]]},"references-count":81,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2000,2]]}},"alternative-id":["10.1287\/ijoc.12.1.2.11900"],"URL":"https:\/\/doi.org\/10.1287\/ijoc.12.1.2.11900","relation":{},"ISSN":["1091-9856","1526-5528"],"issn-type":[{"value":"1091-9856","type":"print"},{"value":"1526-5528","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,2]]}}}