CAREER: Towards Exact Methods for Dynamic Integer Programs

该学院早期职业发展（Career）基金旨在为一类广泛适用的离散组件动态优化模型开发通用解决方案技术和算法。这项研究是由工业和政府对决策支持工具的需求推动的，这些工具必须越来越多地考虑到不确定性，以及最近可用数据量和生成频率的爆炸式增长，这意味着决策者必须以动态的方式不断对新信息做出反应，包括实时的。这些模型出现在对几个经济部门具有重要意义的新兴应用中，例如互联网搜索中的在线广告，生产和制造中的实时调度，以及非卡车运输中的负载选择等等。此外，该项目的教育重点还包括一系列互动讲座，旨在更广泛地吸引和招募高中生学习运筹学和STEM，特别关注历史上代表性不足的群体的学生。该项目将开发第一个通用的，计算上可处理的精确解决算法的两类动态二进制整数规划的包装类型，也称为多维背包问题。这两种建模范式分别允许具有未知参数的已知决策变量，或批量动态到达的未知决策变量。该项目将结合整数规划、线性规划、动态规划和更广泛的运筹学研究的技术，包括切割平面、扩展公式、近似线性规划和仿真。解决方案框架将模仿经典整数规划的传统切割平面方法：对于给定的问题，算法从尽可能多地利用问题结构的紧密线性规划松弛开始，然后诉诸于更通用的切割平面算法，该算法收敛于极限的最优性。每一个先后收紧的松弛也将隐含一个相应的原始策略，该策略也可以启发式地改进，并通过模拟评估提供原始最优性证明。虽然项目中包含的一些模型以前已经被研究过，但这项研究将产生第一个精确的、通用的动态整数程序算法。

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.