Many hard combinatorial problems can be modeled with either dynamic programming (DP) or mixed-integer programming (MIP). We examine using information obtained from intermediate DP stage solutions, up to a tractable number of stages, to generate valid inequalities for an equivalent MIP. We show, via a study of the capacitated lot-sizing problem, that this approach may be effective in improving the solvability of hard optimization problems. We further explore connections between DP and MIP in this context and other potential applications of this technique.
GAINESVILLE, FL: Dr. Joseph C. Hartman, Professor and Chair of Industrial and Systems Engineering, will deliver the ISE Graduate Seminar, “Integrating Dynamic Programming within Mixed-Integer Programming Techniques,” on Thursday, September 78 at 4:05 p.m. This is joint work with Dr. J. Cole Smith, Professor of Industrial and Systems Engineering.
Joseph C. Hartman is Professor and Chair of Industrial and Systems Engineering at the University of Florida. He received his M.S. (1994) and Ph.D. (1996) in Industrial and Systems Engineering from the Georgia Institute of Technology after receiving his B.S. (1992) in General Engineering from the University of Illinois at Urbana-Champaign. Previously, he served on the Lehigh University faculty for 11 years, including Department Chair. His research and teaching focuses on dynamic optimization with applications in engineering economics, finance, and transportation systems. His work has been supported by numerous companies and the National Science Foundation, including the CAREER award in 1999. He serves as Editor of The Engineering Economist and is author of the textbook Engineering Economy and the Decision-Making Process.