Dr. Martin Savelsbergh from Georgia Tech visits INFORMS@USF
Nov 22, 2016 by Nazmus Sakib
Del and Beth Kimbler Lecture Series
Dr. Martin Savelsbergh from Georgia Tech
Topic: Dynamic Discretization Discovery: Solving Discrete Time Integer Programs
In the talk, problems are considered in which decisions have to be made about the times at which activities occur and/or resources are utilized. Such models are pervasive in practice, since they occur whenever a schedule of activities needs to be constructed. The talk focuses on extended integer programming (IP) formulations with time-indexed variables. Such formulations rely on a discretization of time and are known to have strong relaxations, but (tend to) have a huge number of variables. A novel approach for solving such formulations: dynamic discretization discovery is presented. The key to the approach is that it discovers exactly which times are needed to obtain an optimal solution, in an efficient way, by solving a sequence of (small) IPs. The IPs are constructed as a function of a subset of times, with variables indexed by times in the subset. They are carefully designed to be tractable in practice, and to yield a lower bound (it is a cost minimization problem) on the optimal continuous-time value. Once the right (very small) subset of times is discovered, the resulting IP model yields the optimal value.