A Survey of Linear and Mixed-Integer Optimization Tutorials

References

• Ahmed S, Shapiro A (2008) Solving chance-constrained stochastic programs via sampling and integer programming. Chen Z, Raghavan S, eds. Tutorials in Operations Research (INFORMS, Hanover, MD), 261–269.Link, Google Scholar
• Ahuja R, Magnanti T, Orlin J (1993) Network Flows: Theory, Algorithms, and Applications (Prentice Hall, Englewood Cliffs, NJ).Google Scholar
• AMPL (2009) AMPL—A Mathematical Programming Language (AMPL Optimization LLC, Albuquerque, NM).Google Scholar
• Bazaraa M, Jarvis J, Sherali H (2005) Linear Programming and Network Flows (John Wiley & Sons, Inc., New York).Google Scholar
• Bazaraa M, Sherali H, Shetty C (2006) Nonlinear Programming: Theory and Algorithms (John Wiley & Sons, Inc., Hoboken, NJ).Crossref, Google Scholar
• Beale EML (1955) On minimizing a convex function subject to linear inequalities. J. Roy. Statist. Soc. 17(2):173–184.Google Scholar
• Benders J (1962) Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4(3):238–252.Crossref, Google Scholar
• Bertsimas D, Stock Patterson S (1998) The air traffic flow management problem with enroute capacities. Oper. Res. 46(3):406–422.Link, Google Scholar
• Bertsimas D, Tsitsiklis J (1997) Introduction to Linear Optimization (Athena Scientific, Belmont, MA).Google Scholar
• Bertsimas D, Weismantel R (2005) Optimization Over Integers (Dynamic Ideas, Belmont, MA).Google Scholar
• Bertsimas D, Brown D, Caramanis C (2011) Theory and applications of robust optimization. SIAM Rev. 53(3):464–501.Crossref, Google Scholar
• Birge J, Louveaux F (1997) Introduction to Stochastic Programming (Springer, New York).Google Scholar
• Bixby R (2012) A brief history of linear and mixed-integer programming. Grötschel M, ed. Documenta Mathematica—Optim. Stories, 21st Internat. Sympos. Math. Programming (Journal der Deutschen Mathematiker-Vereinigung, Berlin), 107–121.Google Scholar
• Bixby R, Rothberg E (2007) Progress in computational mixed integer programming—A look back from the other side of the tipping point. Ann. Oper. Res. 149(1):37–41.Crossref, Google Scholar
• Bixby R, Fenelon M, Gu Z, Rothberg E, Wunderling R (2000) MIP: Theory and Practice: Closing the gap. System Modeling and Optimization: Methods, Theory and Applications (Kluwer, The Netherlands), 19–50.Crossref, Google Scholar
• Brailsford S, Potts C, Smith B (1999) Constraint satisfaction problems: Algorithms and applications. Eur. J. Oper. Res. 119(3):557–581.Crossref, Google Scholar
• Brown G, Carlyle M, Salmerón J, Wood K (2006) Defending critical infrastructure. Interfaces 36(6):530–544.Link, Google Scholar
• Brown G, Rosenthal R (2008) Optimization tradecraft: Hard-won insights from real-world decision support. Interfaces 38(5):356–366.Link, Google Scholar
• Brown G, Dell R (2007) Formulating integer linear programs: A rogues' gallery. INFORMS Trans. Ed. 7(2):1–13.Google Scholar
• Brown G, Dell R, Wood RK (1997) Optimization and persistence. Interfaces 27(5):15–37.Link, Google Scholar
• Camm J, Raturi A, Tsubakitani S (1990) Cutting big M down to size. Interfaces 20(5):61–66.Link, Google Scholar
• Chen C-H, Fu M, Shi L (2008) Simulation and optimization. Chen Z, Raghavan S, eds. Tutorials in Operations Research (INFORMS, Hanover, MD), 247–260.Link, Google Scholar
• Cohen A, Parhi K (2011) Architecture optimizations for the RSA public key cryptosystem: A tutorial. IEEE Circuits and Systems Magazine 11(4):24–34.Crossref, Google Scholar
• Cook W (2012) Markowitz and Manne + Eastman + Land and Doig = branch and bound. Grötschel M, ed. Documenta Mathematica—Optim. Stories, 21st Internat. Sympos. Math. Programming, (Journal der Deutschen Mathematiker-Vereinigung, Berlin), 227–238.Google Scholar
• Cornuéjols G (2008) Valid inequalities for mixed integer linear programs. Math. Programming 112(1):3–44.Crossref, Google Scholar
• Cornuéjols G (2012) The ongoing story of Gomory cuts. Grötschel M, ed. Documenta Mathematica—Optim. Stories. 21st Internat. Sympos. Math. Programming (Journal der Deutschen Mathematiker-Vereinigung, Berlin), 221–226.Google Scholar
• Danna E (2008) Performance variability in mixed integer programming. MIP 2008 Workshop, Columbia University, New York, http://www.iro.umontreal.ca/∼gendron/IFT6551/LECTURES/Computation.pdf.Google Scholar
• Dantzig G (1955) Linear programming under uncertainty. Management Sci. 1(3–4):197–206.Link, Google Scholar
• Dantzig G (1963) Linear Programming and Extensions (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Dantzig G, Thapa M (1997) Linear Programming 1: Introduction (Springer, New York).Google Scholar
• Dantzig G, Thapa M (2003) Linear Programming 2: Theory and Extensions (Springer, New York).Google Scholar
• Dantzig G, Wolfe P (1960) Decomposition principle for linear programs. Oper. Res. 8(1):101–111.Link, Google Scholar
• Dantzig G, Orden A, Wolfe P (1955) A generalized simplex method for minimizing a linear form under linear inequality restraints. Pacific J. Math. 5(2):183–195.Crossref, Google Scholar
• Feillet D (2010) A tutorial on column generation and branch-and-price for vehicle routing problems. 4OR: Quart. J. Oper. Res. 8(4):407–424.Crossref, Google Scholar
• FICO (2008) Xpress-MP Optimization Suite. http://www.fico.com/en/Products/OMTools/Pages/FICO-Xpress-Optimization-Suite.aspx, Minneapolis.Google Scholar
• Fisher M (1981) The Lagrangian relaxation method for solving integer programming problems. Management Sci. 27(1):1–18.Link, Google Scholar
• Fourer R (2012) On the evolution of optimization modeling systems. Grötschel M, ed. Documenta Mathematica—Optim. Stories, 21st Internat. Sympos. Math. Programming (Journal der Deutschen Mathematiker-Vereinigung, Berlin), 377–388.Google Scholar
• Fourer R, Gay D, Kernighan B (2003) AMPL—A Modelling Language for Mathematical Programming (Thomson Brooks/Cole, Pacific Grove, CA).Google Scholar
• GAMS (2012) GAMS Distribution 23.9.1. Washington, DC.Google Scholar
• Gass S, Assad A (2011) History of operations research. Geunes J, ed. Tutorials in Operations Research (INFORMS, Hanover, MD), 1–14.Link, Google Scholar
• Geoffrion A (1972) Generalized Benders decomposition. J. Optim. Theory Appl. 10(4):237–260.Crossref, Google Scholar
• Gill P, Murray W, Saunders M, Tomlin J, Wright M (1986) On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method. Math. Programming 36(2):183–209.Crossref, Google Scholar
• Glover F (1990) Tabu research: A tutorial. Interfaces 20(4):74–94.Link, Google Scholar
• Grötschel M (2012) Documenta Mathematica—Optim. Stories, 21st Internat. Sympos. Math. Programming (Journal der Deutschen Mathematiker-Vereinigung, Berlin).Google Scholar
• GuRoBi (2009) GuRoBi Optimizer (GuRoBi Optimization Inc., Houston).Google Scholar
• Higle J (2005) Stochastic programming: Optimization when uncertainty matters. Smith JC, ed. Tutorials in Operations Research (INFORMS, Hanover, MD), 30–53.Link, Google Scholar
• Hoffman K (2000) Combinatorial optimization: History and future challenge. J. Appl. Comput. Math. 124(1–2):341–360.Crossref, Google Scholar
• Hooker J (1994) Logic-based methods for optimization. Borning A, ed. Principles and Practice of Constraint Programming, Vol. 874, Lecture Notes in Computer Science (Springer, Berlin, Heidelberg), 336–349.Crossref, Google Scholar
• IBM (2009) ILOG CPLEX IBM—International Business Machines Corporation, Incline Village, NV.Google Scholar
• Johnson D (2012) A brief history of NP-completeness, 1954–2012. Grötschel M, ed. Documenta Mathematica—Optim. Stories. 21st Internat. Sympos. Math. Programming (Journal der Deutschen Mathematiker-Vereinigung, Berlin), 359–376.Google Scholar
• Kallrath J (2011) Polylithic modeling and solution approaches using algebraic modeling systems. Optim. Lett. 5(3):453–466.Crossref, Google Scholar
• Kallrath J (2012) Algebraic Modeling Systems—Modeling and Solving Real World Optimization Problems (Springer-Verlag, Heidelberg, Germany).Crossref, Google Scholar
• Kallrath J, Wilson JM (1997) Business Optimisation Using Mathematical Programming (Macmillan Press, London).Google Scholar
• Karmarkar N (1984) A new polynomial-time algorithm for linear programming. Combinatorica 4(4):373–395.Crossref, Google Scholar
• Khachian L (1979) A polynomial algorithm in linear programming. Soviet Math. Doklady 20:191–194.Google Scholar
• King A, Wallace S (2012) Modeling with Stochastic Programming (Springer Series in Operations Research and Financial Engineering, New York).Crossref, Google Scholar
• Klee V, Minty G (1972) How good is the simplex algorithm? Shisha O, ed. Inequalities III (Academic Press, New York), 159–175.Google Scholar
• Klotz E, Newman A (2013a) Practical guidelines for solving difficult linear programs. Surveys Oper. Res. Management Sci. 18(1–2):1–17.Crossref, Google Scholar
• Klotz E, Newman A (2013b) Practical guidelines for solving difficult mixed integer programs. Surveys Oper. Res. Management Sci. 18(1–2):18–32.Crossref, Google Scholar
• Lambert W, Brickey A, Eurek K, Newman A (2013) Open pit block sequencing formulations: A tutorial. Interfaces. Forthcoming.Google Scholar
• Lee J, Leyffer S (2012) Mixed Integer Nonlinear Programming, the IMA Volumes in Mathematics and Its Applications, Vol. 154 (Springer, New York).Crossref, Google Scholar
• Lemke C (1954) The dual method of solving the linear programming problem. Naval Res. Logist. Quart. 1(1):36–47.Crossref, Google Scholar
• Lübbecke M, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Lustig I, Puget J-F (2001) Program does not equal program: Constraint programming and its relationship to mathematical programming. Interfaces 31(6):29–53.Link, Google Scholar
• Lustig I, Marsten R, Shanno D (1994) Interior-point methods for linear programming: Computational state of the art. ORSA J. Comput. 6(1):1–14.Link, Google Scholar
• Marsten R, Subramanian R, Saltzman M, Lustig I, Shanno D (1990) Interior point methods for linear programming: Just call Newton, Lagrange, and Fiacco and McCormick! Interfaces 20(4):105–116.Link, Google Scholar
• Martin K (1999) Large Scale Linear and Integer Optimization: A Unified Approach (Kluwer Academic Publishers, Boston).Crossref, Google Scholar
• Martin K (2010) Tutorial: COIN-OR: Software for the OR community. Interfaces 40(6):465–476.Link, Google Scholar
• Murty K (2009) New sphere methods for linear programs. Oskoorouchi M, ed. Tutorials in Operations Research (INFORMS, Hanover, MD), 62–80.Link, Google Scholar
• Něsetřil J, Něsetřilová H (2012) The origins of minimal spanning tree algorithms—Borůvka and Jarník. Grötschel M, ed. Documenta Mathematica—Optim. Stories. 21st Internat. Sympos. Math. Programming (Journal der Deutschen Mathematiker-Vereinigung, Berlin), 127–141.Google Scholar
• Powell W (2009) What you should know about approximate dynamic programming. Naval Res. Logist. 56(3):239–249.Crossref, Google Scholar
• Prekopa A (1995) Stochastic Programming (Kluwer Academic Publishers, Norwell, MA).Crossref, Google Scholar
• Rardin R (1998) Optimization in Operations Research (Prentice Hall, Upper Saddle River, NJ).Google Scholar
• Rebennack S, Reinelt G, Pardalos P (2012) A tutorial on branch and cut algorithms for the maximum stable set problem. Internat. Trans. Oper. Res. 19(1–2):161–199.Crossref, Google Scholar
• Rockafellar R (2007) Coherent approaches to risk in optimization under uncertainty. Klastorin T, ed. Tutorials in Operations Research (INFORMS, Hanover, MD), 38–61.Link, Google Scholar
• Rosenthal R (2012) GAMS: A User's Guide, http://www.gams.com/dd/docs/bigdocs/GAMSUsersGuide.pdf, Washington, DC.Google Scholar
• Savelsbergh M (1994) Preprocessing and probing techniques for mixed integer programming problems. ORSA J. Comput. 6(4):445–454.Link, Google Scholar
• Schneider U (2011) A tabu search tutorial based on a real-world scheduling problem. Central Eur. J. Oper. Res. 19(4):467–493.Crossref, Google Scholar
• Schrijver A (2012a) On the history of the shortest path problem. Grötschel M, ed. Documenta Mathematica—Optim. Stories, 21st Internat. Sympos. Math. Programming (Journal der Deutschen Mathematiker-Vereinigung, Berlin), 155–167.Google Scholar
• Schrijver A (2012b) On the history of the transportation and maximum flow problems. Grötschel M, ed. Documenta Mathematica—Optim. Stories, 21st Internat. Sympos. Math. Programming (Journal der Deutschen Mathematiker-Vereinigung, Berlin), 169–180.Google Scholar
• Sen S, Higle J (1999) An introductory tutorial on stochastic linear programming models. Interfaces 29(2):33–61.Link, Google Scholar
• Shapiro A, Dentcheva D, Ruszczynski A (2009) Lectures on Stochastic Programming: Modeling and Theory (Society for Industrial and Applied Mathematics and the Mathematical Programming Society, Philadelphia).Crossref, Google Scholar
• Sheldon B, Yost K (2011) Military operations research society (MORS): Oral history project interview of Dr. Gerald G. Brown. Military Oper. Res. 16(4):57–82.Crossref, Google Scholar
• Sherali D, Smith J (2001) Improving discrete model representations via symmetry considerations. Management Sci. 47(10):1396–1407.Link, Google Scholar
• Smith BM (1995) A tutorial on constraint programming. Report 95.14. University of Leeds. http://www.dcs.gla.ac.uk/~pat/cp4/papers/95_14.pdf.Google Scholar
• Terlaky T (2009) Twenty-five years of interior point methods. Oskoorouchi M, ed. Tutorials in Operations Research (INFORMS, Hanover, MD), 1–33.Link, Google Scholar
• Tovey C (2002) Tutorial on computational complexity. Interfaces 32(3):30–61.Link, Google Scholar
• Trick M (1997) A tutorial on integer programming. Carnegie Melon University, http://mat.gsia.cmu.edu/orclass/integer/integer.html.Google Scholar
• Trick M (2005) Formulations and reformulations in integer programming. Carnegie Melon University, http://mat.gsia.cmu.edu/trick/formul04.pdf.Google Scholar
• Wallace S (2010) Stochastic programming and the option of doing it differently. Ann. Oper. Res. 177(1):3–8.Crossref, Google Scholar
• Winston W, Goldberg J (2004) Operations Research: Applications and Algorithms (Duxbury Press, Belmont, CA).Google Scholar
• Wolsey L (1998) Integer Programming (John Wiley & Sons, New York).Google Scholar
• Worden K, Staszewski W, Hensman J (2011) Natural computing for mechanical systems research: A tutorial overview. Mech. Systems and Signal Processing 25(1):4–111.Crossref, Google Scholar