Bilevel Integer Programming: Theory and Algorithms

该奖项为分层决策系统中出现的优化模型的解决方法的研究提供资金。这种系统的特点是存在一个决策层次，在这个层次中，多个自利的决策者（DMs）每个人根据层次中较高层次的决策所施加的命令确定一个最佳的行动方针。对这样一个系统的分析最自然地采用最高级别的DM的观点，他必须考虑到所有较低级别DM的行动，以便采取最佳行动。这样的决策问题可以用多层数学规划模型来分析，它类似于标准的数学规划，只是变量被分成不同的组，每个组由不同的DM控制。通过要求低层DM控制的变量值是最优的，给定那些已经由高层DM确定的变量值，就有可能将最高层DM面临的优化问题表述为单个优化模型。如果成功，本研究将开发一个解决两级整数程序的原型系统，其中只有两个dm，其中一些变量需要取整数值。由于目前还没有有效的方法来解决两层整数规划，这项研究将导致我们分析决策系统的能力的提高，可以用这种方式建模。研究的一个特别重点将是所谓的拦截模型，其中两种导弹是直接对手。在最简单的情况下，高级DM能够以各种方式限制低级DM的操作。高级DM的决策是如何分配资源，以最大限度地影响低级DM执行给定任务的能力。这种模式具有广泛的适用性，特别是在军事环境和对某些竞争市场的分析方面。作为这项研究的结果而产生的软件将以开源的方式发布，并将提供给广泛的研究人员，他们将从中受益。

This award provides funding for the study of solution methods for optimization models that arise in hierarchical decision systems. Such systems are characterized by the existence of a decision hierarchy in which multiple, self-interested decision-makers (DMs) each determine an optimal course of action subject to mandates imposed by decisions made at higher levels in the hierarchy. Analysis of such a system most naturally takes the point of view of the highest-level DM, who must take into account the actions of all lower-level DMs in order to act optimally. Such decision problems can be analyzed using multilevel mathematical programming models, which are similar to standard mathematical programs except that the variables are divided into groups, each of which is controlled by a different DM. By requiring the values of the variables controlled by lower-level DMs to be optimal, given those already fixed by higher-level DMs, it is possible to formulate the optimization problem faced by the highest-level DM as a single optimization model. If successful, this research will develop a prototype system for solving bilevel integer programs, in which there exactly two DMs and in which some of the variables are required to take on integer values. As there are currently no effective methods for solving bilevel integer programs, this research will result in an improvement in our ability to analyze decision systems that can be modeled in this way. A particular focus of the research will be so-called interdiction models, in which the two DMs are direct adversaries. In the simplest case, a high-level DM has the ability to restrict the actions of a low-level DM's actions in various ways. The high-level DM's decision is how to allocate resources so as to have maximum impact on the low-level DM's ability to carry out a given mission. Such models have wide applicability, especially in military settings and in the analysis of certain competitive markets. The software produced as a result of this research will be released open source and will be available to a wide range of researchers who will benefit from its availability.