This Faculty Early Career Development (CAREER) grant is developing general-purpose solution techniques and algorithms for a widely applicable class of dynamic optimization models with discrete components. This research is driven by the need for decision support tools in industry and government which must increasingly account for uncertainty, and the recent explosion in the amount of available data and the frequency of its generation, implying that decision makers must constantly react to new information in a dynamic fashion, including in real time. Such models arise in emerging applications of importance to several economic sectors, such as online advertisement in internet search, real-time scheduling in production and manufacturing, and load selection in less-than-truckload transportation, among others. In addition, the project's educational thrusts include a series of interactive lectures aimed at attracting and recruiting high school students to operations research and STEM more broadly, with a particular focus on students from historically under-represented groups.
The project will develop the first general-purpose, computationally tractable exact solution algorithms for two classes of dynamic binary integer programs of the packing type, also called multi-dimensional knapsack problems. The two modeling paradigms respectively allow for known decision variables with unknown parameters, or unknown decision variables that arrive dynamically in batches. The project will combine techniques from integer programming, linear programming, dynamic programming and broader operations research, including cutting planes, extended formulations, approximate linear programs and simulation. The solution framework will mimic traditional cutting plane methods for classical integer programming: For a given problem, the algorithm begins from a tight linear programming relaxation that exploits the problem's structure as much as possible, before resorting to a more generic cutting plane algorithm that converges to optimality in the limit. Each successively tighter relaxation will also imply a corresponding primal policy, which may also be heuristically improved, and whose evaluation via simulation provides the primal optimality certificate. Though some of the models included in the project have been studied previously, this research will produce the first exact, general-purpose algorithms for dynamic integer programs.
