Pseudo-Boolean Functions: Representations and Optimization

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

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.