Bilevel Integer Programming: Theory and Algorithms

该奖项为层次化决策系统中出现的优化模型的求解方法研究提供资金。这类系统的特点是存在一个决策等级，其中多个自私自利的决策者(DM)根据等级中较高级别作出的决定所规定的任务，各自确定最佳行动方案。对这种制度的分析最自然地考虑到最高级别的DM的观点，他们必须考虑到所有较低级别的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.