Nonlinear Binary Optimization

这类优化问题称为非线性整数规划问题，可以归结为实值函数在0-L变量上的无约束极大化问题。这些函数通常称为伪布尔函数(PBF)。期望这项研究将有助于澄清PBF的某些基本性质，并有助于识别和使用特殊类别的PBF，从而设计出有效的优化算法。一个名为“屋顶对偶”的新概念将成为设计此类优化算法的主要工具。

This research addresses that class of optimization problems known as nonlinear integer programming problems which can be formulated as unconstrained maximization problems of real-valued functions in 0-l variables. These functions are often called pseudo-Boolean functions (pBf). It is expected that this research will lead to the clarification of certain fundamental properties of pBf's and the recognition and use of special classes of pBf's for which efficient optimization algorithms can be devised. A new concept called "roof duality" will be a major tool for designing such optimization algorithms.