Abstract
Over the last 20 years, the combination of faster computers, more reliable data, and improved algorithms has resulted in the near-routine solution of many integer programs of practical interest. Integer programming models are used in a wide variety of applications, including scheduling, resource assignment, planning, supply chain design, auction design, and many, many others. In this tutorial, we outline some of the major themes involved in creating and solving integer programming models.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Applegate, D., Bixby, R., Chvatal, V. and Cook, W., 1998, On the solution of traveling salesman problems, in: Proc. Int. Congress of Mathematicians, Doc. Math. J. DMV, Vol. 645.
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P. and Vance, P. H., 1998, Branch-and-price: column generation for huge integer programs, Oper. Res. 46:316.
Bixby, R. E., Fenelon, M., Gu, Z., Rothberg, E. and Wunderling, R., 1999, MIP: Theory and Practice—Closing the Gap, Proc. 19th IFIP TC7 Conf. on System Modelling, Kluwer, Dordrecht, pp. 19–50.
Common Optimization INterface for Operations Research (COIN), 2004, at http://www.coin-or.org
Cordier, C., Marchand, H., Laundy, R. and Wolsey, L. A., 1999, bc-opt: a branch-and-cut code for mixed integer programs, Math. Program. 86:335.
Crowder, H., Johnson, E. L. and Padberg, M. W., 1983, Solving large scale zero-one linear programming problems, Oper. Res. 31:803–834.
Gomory, R. E., 1958, Outline of an algorithm for integer solutions to linear programs, Bulletin AMS 64:275–278.
Gueret, C, Prins, C. and Sevaux, M., 2002, Applications of Optimization with Xpress-MP, S. Heipcke, transl., Dash Optimization, Blisworth, UK.
Hillier, F. S. and Lieberman, G. J., 2002, Introduction to Operations Research, McGraw-Hill, New York.
ILOG CPLEX 9.0 Reference Manual, 2004, ILOG.
Juenger, M., Reinelt, G. and Thienel, S., 1995, Practical Problem Solving with Cutting Plane Algorithms in Combinatorial Optimization, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 111, American Mathematical Society, Providence, RI.
Land, A. H. and Doig, A. G., 1960, An Automatic Method for Solving Discrete Programming Problems, Econometrica 28:83–97.
Nemhauser, G. L. and Wolsey, L. A., 1998, Integer and Combinatorial Optimization, Wiley, New York.
Ralphs, T. K. and Ladanyi, L., 1999, SYMPHONY: A Parallel Framework for Branch and Cut, White paper, Rice University.
Schrijver, A., 1998, Theory of Linear and Integer Programming, Wiley, New York.
Taha, H. A., 2002, Operations Research: An Introduction, Prentice-Hall, New York.
Williams, H. P., 1999, Model Building in Mathematical Programming, Wiley, New York.
Winston, W., 1997, Operations Research: Applications and Algorithms, Thomson, New York.
Wolsey, L. A., 1998, Integer Programming, Wiley, New York.
XPRESS-MP Extended Modeling and Optimisation Subroutine Library, Reference Manual, 2004, Dash Optimization, Blisworth, UK.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer Science+Business Media, LLC
About this chapter
Cite this chapter
Bosch, R., Trick, M. (2005). Integer Programming. In: Burke, E.K., Kendall, G. (eds) Search Methodologies. Springer, Boston, MA. https://doi.org/10.1007/0-387-28356-0_3
Download citation
DOI: https://doi.org/10.1007/0-387-28356-0_3
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-23460-1
Online ISBN: 978-0-387-28356-2
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)