Discrete optimization on a multivariable boolean lattice

Consider the problem of finding the minimum value of a scalar objective function whose arguments are theN components of 2 ^N vector elements partially ordered as a Boolean lattice. If the function is strictly decreasing along any shortest path from the minimum point to its logical complement, then the minimum can be located precisely after sequential measurement of the objective function atN + 1 points. This result suggests a new line of research on discrete optimization problems.This paper was presented at the 7th Mathematical Programming Symposium, The Hague, The Netherlands.This research was supported in part by U.S. Office of Saline Water Grant No. 699.