Conference Slide Presentations

INFORMS Atlanta,Georgia October 2003


MIP Modeling

Abstract: It is well-known in the integer programming community that how one formulates a mixed integer program (MIP) can be the difference between acceptable and lousy run times. In this talk, geared to the practitioner, we survey the commonly held "good practices" of MIP modeling.


Author: Robin Lougee-Heimer
IBM Corporation
Email: robinlh@us.ibm.com
Home Page: www.coin-or.org

Slides

  1. Advanced Modeling Techniques
  2. Agenda
  3. Mathematical Modeling
  4. Modeling Fundamentals
  5. Linear Programming
  6. Escapable nonlinearities
  7. Inescapable
  8. The trouble with rounding
  9. PPT Slide
  10. Indicator Variables
  11. Almost linear
  12. Almost linear: semi-continuous
  13. Indicating Semi-continuous Variables
  14. Indicating Variable Intervals
  15. Indicating Variable Intervals:x >= v … or not
  16. Indicating Greater-Or-Equal-To Constraints: ax>=b
  17. Indicating Greater-Or-Equal-To Constraints: ax>=b
  18. Indicating Greater-Or-Equal-To Constraints: ax>=b
  19. Indicating Greater-Or-Equal-To Constraints: ax>=b
  20. Indicating Lesser-Or-Equal-To Constraints: ax<=b
  21. Indicating Equality Constraints: ax=b
  22. Indicating Equality Constraints: ax=b
  23. Logical Implications
  24. Boolean Conditions
  25. More Boolean Conditions
  26. Classic Linearization
  27. Solving MIPs
  28. More Solving MIPs
  29. Understanding Branch-and-Bound
  30. LP relaxation provides a lower bound (for min)
  31. Divide and Conquer
  32. Sandwich approach
  33. Avoiding large search trees
  34. Cutting Planes
  35. Formulation Matters!
  36. More On Cutting Planes
  37. Search Strategies
  38. Node selection
  39. Preprocessing
  40. Milking a “Bad Solution” to Create a Better Model
  41. Hydro Problem Statement
  42. Time Dynamic Network Representation of the System
  43. Natural Mixed 0-1 Linear Formulation of the Problem
  44. “2-path” variables
  45. Increasing Model Size for Tighter Relaxation
  46. The Mkc Problem: Formulation Matters
  47. Avoid Symmetry
  48. More Good Practices
  49. Simplex Solver Software: Rules of Thumb
  50. How Big is Big?
  51. PPT Slide
  52. How Big is Big for LPs?
  53. MIPs are a different ball game
  54. Avoid
  55. Summary

      Return to Presentations Page