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.
