User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Mixed Integer Programming

Primary tabs

Wolsey, Laurence [UCL]

A linear mixed integer program is an optimization problem in which a nonempty subset of integer variables (unknowns) and a subset of real-valued (continuous) variables exist, the constraints are all linear equations or inequalities, and the objective is a linear function to be minimized (or maximized). After presenting several practical applications of mixed integer programming, we describe the main classes of algorithms, branch-and-bound and branch-and-cut, that are used to solve this hard class of problems. Considerable attention is paid to ways to improve solution times, involving preprocessing, reformulation with cuts and/or new variables, and heuristics.

Document type Contribution à ouvrage collectif (Book Chapter) – Chapitre
Publication date 2008
Language Anglais
Host document "Wiley Encyclopedia of Computer Science and Engineering"- 1883-1892 (ISBN : 9780470050118)
Publisher Wiley-Interscience (USA)
Publication status Publié
Affiliation Louvain School of Management - Operations and Information
Keywords mixed integer programs; linear programs; branch-and-bound; branch-and-cut; preprocessing; cutting planes; extended formulations; heuristics
Links
  1. Balas, Discrete Applied Mathematics, 89, 1 (1998)
  2. Heipcke, Applications of Optimization with Xpress (2002)
  3. Williams, Model Building in Mathematical Programming (1999)
  4. Wolsey, Integer Programming (1998)
  5. Pochet, Production Planning by Mixed Integer Programming (2006)
  6. Schrijver, Theory of Linear and Integer Programming (1986)
  7. Nemhauser George, Wolsey Laurence, Integer and Combinatorial Optimization : Nemhauser/Integer and Combinatorial Optimization, ISBN:9781118627372, 10.1002/9781118627372
  8. Marchand, Discrete Applied Mathematics, 123/124, 397 (2002)
  9. Fugenschuh, Combinatorial Optimization, Vol. 12 of Handbooks in Operations Research and Management Science (2006)
  10. Cornu��jols, Mathematical Programming B, 112, 3 (2007)
  11. Wolsey, Mathematical Programming B, 97, 423 (2003)
  12. Savelsbergh M. W. P., Preprocessing and Probing Techniques for Mixed Integer Programming Problems, 10.1287/ijoc.6.4.445
  13. Andersen, Mathematical Programming, 71, 221 (1995)
  14. Achterberg, Operations Research Letters, 33, 42 (2005)
  15. Combinatorial Analysis, 211 (1960)
  16. R. E. Gomory An algorithm for the mixed integer problem RM-2597 1960
  17. Balas, Mathematical Programming, 8, 146 (1975)
  18. Hammer, Mathematical Programming, 8, 179 (1975)
  19. Wolsey, Mathematical Programming, 8, 165 (1975)
  20. Fischetti, Mathematical Programming, 98, 23 (2003)
  21. Danna, Mathematical Programming, 102, 71 (2005)
  22. Barnhart, Operations Research, 46, 316 (1998)
  23. Dantzig, Operations Research, 8, 101 (1960)
  24. Geoffrion A. M., Lagrangean relaxation for integer programming, Approaches to Integer Programming (1974) ISBN:9783642007392 p.82-114, 10.1007/bfb0120690
  25. Benders, Numerische Mathematik, 4, 238 (1962)
  26. Achterberg, Operations Research Letters, 34, 1 (2003)
  27. http://www.ilog.com/cplex
  28. http://www.dashoptimization.com
  29. http://www.lindo.com
  30. http://www.coin-or.org/
  31. T. Achterberg 2004 http://scip.zib.de
  32. M. W. P Savelsbergh http://www2.isye.gatech.edu/ mwps/software/
  33. R. Fourer D. M. Gay B. W. Kernighan 2002 http://www.ampl.com/
  34. A. Ben-Tal A. Nemirovski Lectures on Modern Convex Optimization: Analysis, Algorithms and Engineering Applications, MPS-SIAM Series on Optimization 2001
  35. Geoffrion, Jo. Optimization Theory and Applications, 10, 237 (1972)
  36. Fletcher, Mathematical Programming, 66, 327 (1994)
  37. Duran, Mathematical Programming, 36, 307 (1986)
  38. Floudas, Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications (1995)
  39. Weismantel, Mixed Integer Nonlinear Programming (2006)
  40. http://www.gams.com
  41. http://neos.mcs.anl.gov/neos/solvers/go:BARON/GAMS.html
  42. Tawarmalami, Mathematical Programming, 99, 563 (2004)
  43. http://sedumi.mcmaster.ca/
  44. P. Bonami L. T. Biegler A. R. Conn G. Cornuejols I. E. Grossman C. D. Laird J. Lee A. Lodi F. Margot N. Sawaya A. W��chter An algorithmic framework for convex mixed integer nonlinear programs RC23771 T. J. Watson
  45. Sawaya (2006)
Bibliographic reference Wolsey, Laurence. Mixed Integer Programming. In: Wiley Encyclopedia of Computer Science and Engineering, Wiley-Interscience  : USA 2008, p.1883-1892
Permanent URL http://hdl.handle.net/2078/18625