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.