CAREER: Towards Exact Methods for Dynamic Integer Programs

职业：动态整数规划的精确方法

• 批准号: 1552479
• 负责人: Alejandro Toriello
• 金额: $ 50万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-05-15 至 2022-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1552479&HistoricalAwards=false
• 关键词: CAREER; Towards; Exact; Methods; Dynamic

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.

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