Pseudo-Boolean Functions: Representations and Optimization

伪布尔函数：表示和优化

• 批准号: 9806389
• 负责人: Peter Hammer
• 金额: $ 17.5万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-09-01 至 2001-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9806389&HistoricalAwards=false
• 关键词: Pseudo; Boolean; Functions; Representations; Optimization

9806389Peter L. HammerNumerous problems in area as diverse as VLSI design, game theory, artificial intelligence, neural networks, operations research, statistics, reliability, and finance can be modeled by using set functions, i.e., mappings of the subsets of a finite set into the reals. It was noticed in the mid-60's by the PI that set functions can be viewed as "pseudo-Boolean" functions, i.e., real valued functions with 0-1 variables, and can be represented as multilinear polynomials. It was noticed along the years that beside their polynomial representation, pseudo-Boolean functions admit also other algebraic representations, e.g., as additive posiforms, as logical posiforms, etc. It also turns out that various types of applications may lead naturally to various types of representations. Also, it can be seen that the solution of some of the most important problems concerning pseudo-Boolean problems (finding a global optimum, finding a local optimum, approximating the optimum, finding a good approximation of the functions, finding a good majorant or minorant of the function) depends heavily on the particular representation used. In this proposal the investigators will deal mostly with the optimization of pseudo-Boolean functions with a heavy emphasis on their representation. They will consider separately various problems of optimization, majorization, approximation, etc., for pseudo-Boolean functions given in polynomial form, in additive posiform, as well as in disjunctive posiform representation. Beside investigations concerning the algebraic problems of presentation, the investigators will lay heavy emphasis on the computational aspects of the problem, and plan to elaborate specialized algorithms for exact and heuristic optimization problems of pseudo- Boolean functions in various forms, on local optimization, and on the detection of efficient methods for particular classes of problems.In numerous real-life situations, optimization problems have to be solved involving decisions and selections between various alternatives. When, for example, locations have to be found for cellular ground stations, emergency facilities, warehouses, etc., the usual mathematical optimization procedures cannot be applied blindly, since they may recommend the location of say half a unit in one place and the other half in another. Therefore, new mathematical techniques are needed to make sure that the solutions can only involve locating either an entire unit in one place or no part of it in that place. Similar problems occur when selections are made between projects to be undertaken, people or equipment to be assigned to various tasks, or much more complex situations where a large company (e.g. an airline) has to assign its equipment (e.g. aircrafts) to its various activities (e.g. flights). In such situations, the mathematical formulation of the problem requires the use of variables which can only take the values of 0 or 1. In spite of its apparent simplicity, this requirement can cause major mathematical and computational difficulties. This project deals to a large extent with the problem of finding various mathematical models describing situations like the above ones and developing optimization techniques for handling them. A substantial amount of computational experimentation is part of the project and will complement the mathematical developments.

9806389 Peter L.Hammer在VLSI设计、博弈论、人工智能、神经网络、运筹学、统计学、可靠性和金融学等领域中的大量问题都可以用集合函数来建模，即有限集合的子集到实数的映射。60年代中期，S等人注意到，集函数可以看作是“伪布尔”函数，即具有0-1个变量的实值函数，并且可以用多项式来表示。多年来，人们注意到，除了多项式表示，伪布尔函数还允许其他代数表示，例如，作为加法位置形式、作为逻辑位置形式等。事实也证明，各种类型的应用可能自然地导致各种类型的表示。此外，可以看出，一些与伪布尔问题有关的最重要问题的解决方案(找到全局最优、找到局部最优、逼近最优、找到函数的良好逼近、找到函数的好的主或次)在很大程度上依赖于所使用的特定表示。在这项提案中，研究人员将主要处理伪布尔函数的优化，重点放在它们的表示上。他们将分别考虑各种优化、优化、逼近等问题，对于以多项式形式给出的伪布尔函数、以加法形式给出的伪布尔函数以及以析取形式表示形式给出的伪布尔函数。除了关于表示的代数问题的研究外，研究人员还将重点放在问题的计算方面，并计划为各种形式的伪布尔函数的精确和启发式优化问题、局部优化以及针对特定问题类的有效方法的检测而制定专门的算法。在许多现实生活中，优化问题必须被解决，涉及在不同方案之间的决策和选择。例如，当必须为蜂窝地面站、应急设施、仓库等寻找位置时，不能盲目地应用通常的数学优化程序，因为它们可能建议将比方说半个单元的位置放在一个地方，而将另一半单元放在另一个地方。因此，需要新的数学技术来确保解决方案只能涉及到将整个单元定位在一个地方，或者没有它的一部分在那个地方。当在要承担的项目、要分配给各种任务的人员或设备之间进行选择时，或者在大公司(例如航空公司)必须将其设备(例如飞机)分配给其各种活动(例如飞行)的更复杂的情况下，也会出现类似的问题。在这种情况下，问题的数学公式需要使用只能取0或1的值的变量。尽管表面上很简单，但这一要求可能会造成重大的数学和计算困难。这个项目在很大程度上涉及找到描述上述情况的各种数学模型并开发处理它们的优化技术的问题。大量的计算实验是该项目的一部分，将补充数学发展。