  When a black-box optimization objective can only be evaluated with costly or
noisy measurements, most standard optimization algorithms are unsuited to find
the optimal solution. Specialized algorithms that deal with exactly this
situation make use of surrogate models. These models are usually continuous and
smooth, which is beneficial for continuous optimization problems, but not
necessarily for combinatorial problems. However, by choosing the basis
functions of the surrogate model in a certain way, we show that it can be
guaranteed that the optimal solution of the surrogate model is integer. This
approach outperforms random search, simulated annealing and one Bayesian
optimization algorithm on the problem of finding robust routes for a
noise-perturbed traveling salesman benchmark problem, with similar performance
as another Bayesian optimization algorithm, and outperforms all compared
algorithms on a convex binary optimization problem with a large number of
variables.
