Dynamic Discretization Discovery: Solving Discrete Time Integer Programs

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Decision-makers across a wide range of sectors and industries must schedule complex activities so as to balance and coordinate competing demands on resources while achieving maximum efficiency of operations. Problems where the timing of activities plays a critical role are pervasive. Such problems arise in diverse applications, such as scheduling surgical facilities, electric power generation, design and operation of military air- and sea-lift networks for national defense, and in same-day and next-hour delivery of online orders. This project addresses fundamental research leading to computational methods to solve challenging optimization problems that underly these operations. Improved design and operation of these systems is expected to result in significant socioeconomic benefits. The research findings will be incorporated into existing undergraduate and graduate courses in optimization, logistics, and supply chain management. This project will advance the fundamental understanding of time dependent integer programming (IP) problems. By developing dynamic discretization methods that can discover exactly which times are needed to obtain an optimal solution, in an efficient way, the resulting IPs become computationally tractable. The research will involve a priori partial discretization approaches, which divide the planning horizon into time intervals, and base model variables for placement of activities in these intervals. The methods will embed three key components: (i) extended, discrete time, IP models, based on a partial discretization of time, i.e., using only a subset of the possible time points, whose solution yields a dual bound on the value of the original problem; (ii) a "repair" mechanism for the solution to the dual bound IP, or a different extended IP model based on the partial discretization, to obtain feasible solutions to the original problem; and (iii) a refinement technique, that identifies time points to add to the partial discretization, so as to improve the dual bound. Theoretical bounds and quantifiable approximation errors in terms of discretization granularity will be studied.