Bilevel Integer Programming: Theory and Algorithms

双层整数规划：理论与算法

• 批准号: 0728011
• 负责人: Theodore Ralphs
• 金额: $ 8万
• 依托单位: Lehigh University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2009-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0728011&HistoricalAwards=false
• 关键词: Bilevel; Integer; Programming; Theory; Algorithms

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.

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