Integrating Dynamic Programming within Mixed-Integer Programming Techniques

该奖项的目标是通过将动态规划(DP)的部分应用获得的信息整合到混合整数规划(MIP)算法的有效不等式生成方案中，来提高组合优化问题的可解性。在计算上，这种技术的优点是，人们可以对手头的问题执行部分DP算法(直到可处理的阶段数)。在这个过程中获得的最优状态值然后可以用来提供作为少量关键变量的函数的部分目标函数值的下界(对于最小化问题)。对该技术的深入分析表明，该过程使用DP将MIP可行域投影到MIP变量的关键子集上。从截断的DP执行中获得的状态信息产生有效的不等式，这些不等式提供作为这些关键变量的函数的问题目标的一部分的界限。人们希望这些研究将把重点从不仅研究MIP多面体的刻面定义不等式，而且转移到产生捕捉一组指定的关键变量和部分目标函数值之间的强关系的不等式。生产、供应链管理和国家安全中的许多重要问题都可以建模为组合优化问题。例如，有能力的批量问题(CLSP)在许多行业中都得到了解决，以做出定期的库存重新排序和生产调度决策。不幸的是，这个问题和其他组合问题可能很难解决。初步分析表明，所提出的求解方法在求解CLSP问题上是成功的。如果成功，我们希望该方法能够提高供应链管理(广义分配和领奖路径)、财务(背包)和安全(节点检测和网络监控)中其他困难但重要的问题的可解性。

This objective of this award is to improve the solvability of combinatorial optimization problems by integrating information obtained from a partial application of dynamic programming (DP) within valid inequality generation schemes for mixed-integer programming (MIP) algorithms. Computationally, the advantage of this technique is that one can execute a partial DP algorithm (up to a tractable number of stages) for the problem at hand. The optimal state values obtained in this process can then be used to provide lower bounds (for minimization problems) on partial objective function values, as a function of a small number of key variables. A deeper analysis of the technique reveals that the process uses DP to project the MIP feasible region onto a key subset of MIP variables. The state information obtained from the truncated DP execution yields valid inequalities, which provide bounds on a portion of the problem objective as a function of these key variables. It is hoped that these investigations will shift focus from not only examining facet-defining inequalities for MIP polyhedra, but also to generating inequalities that capture strong relationships between a set of designated key variables and partial objective function values. A number of important problems in production, supply chain management and national security can be modeled as combinatorial optimization problems. For example, the capacitated lot-sizing problem (CLSP) is solved in numerous industries to make periodic inventory re-ordering and production scheduling decisions. Unfortunately, this, and other combinatorial problems, can be hard to solve. Preliminary analysis has shown the proposed solution method to be successful at solving the CLSP. If successful, we hope the method can improve the solvability of other hard, but important, problems in supply chain management (generalized assignment and prize-collecting routing), finance (knapsack) and security (node detection and network monitoring).