  In this work we propose a batch Bayesian optimization method for
combinatorial problems on permutations, which is well suited for expensive cost
functions on permutations. We introduce LAW, a new efficient batch acquisition
method based on the determinantal point process, using an acquisition weighted
kernel. Relying on multiple parallel evaluations, LAW accelerates the search
for the optimal permutation. We provide a regret analysis for our method to
gain insight in its theoretical properties. We then apply the framework to
permutation problems, which have so far received little attention in the
Bayesian Optimization literature, despite their practical importance. We call
this method LAW2ORDER. We evaluate the method on several standard combinatorial
problems involving permutations such as quadratic assignment, flowshop
scheduling and the traveling salesman, as well as on a structure learning task.
