# Batch Bayesian Optimization on Permutations using the Acquisition Weighted Kernel

Source: [Batch Bayesian Optimization on Permutations using the Acquisition Weighted Kernel](<https://www.sota2.com/research/paper/68fa6e761e209131cea4006b>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-01-02T13:12:17.643Z

Authors: Changyong Oh, Roberto Bondesan, Efstratios Gavves, Max Welling

Published: 2021-02-26T10:15:57.000Z

## Abstract

In this work we propose a batch Bayesian optimization method for combinatorial problems on permutations, which is well suited for expensive-to-evaluate objectives. We first introduce LAW, an efficient batch acquisition method based on determinantal point processes using the acquisition weighted kernel. Relying on multiple parallel evaluations, LAW enables accelerated search on combinatorial spaces. 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. On the theoretical front, we prove that LAW2ORDER has vanishing simple regret by showing that the batch cumulative regret is sublinear. Empirically, we assess 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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Traveling Salesman Problem on TSP burma14](<https://www.sota2.com/research/sota/traveling-salesman-problem-on-tsp-burma14.md>): Traveling Salesman Problem; TSP burma14; Mean Tour Length: 3369.

- [Flowshop Scheduling Problem on FSP-hel2](<https://www.sota2.com/research/sota/flowshop-scheduling-problem-on-fsp-hel2.md>): Flowshop Scheduling Problem; FSP-hel2; Mean Performance: 140.7.

- [Flowshop Scheduling Problem on FSP-reC19](<https://www.sota2.com/research/sota/flowshop-scheduling-problem-on-fsp-rec19.md>): Flowshop Scheduling Problem; FSP-reC19; Mean Objective Value: 2202.

- [Traveling Salesman Problem on TSP bayg29](<https://www.sota2.com/research/sota/traveling-salesman-problem-on-tsp-bayg29.md>): Traveling Salesman Problem; TSP bayg29; Mean Solution Value: 2038.

- [Traveling Salesman Problem on TSP-att48](<https://www.sota2.com/research/sota/traveling-salesman-problem-on-tsp-att48.md>): Traveling Salesman Problem; TSP-att48; Mean Tour Length: 19846.

- [Flowshop Scheduling Problem on FSP-car5](<https://www.sota2.com/research/sota/flowshop-scheduling-problem-on-fsp-car5.md>): Flowshop Scheduling Problem; FSP-car5; Mean Objective Value: 7780.

- [Quadratic Assignment Problem on QAP-chr12a](<https://www.sota2.com/research/sota/quadratic-assignment-problem-on-qap-chr12a.md>): Quadratic Assignment Problem; QAP-chr12a; Mean Cost: 11914.

- [Quadratic Assignment Problem on QAP-esc32a](<https://www.sota2.com/research/sota/quadratic-assignment-problem-on-qap-esc32a.md>): Quadratic Assignment Problem; QAP-esc32a; Mean Cost: 191.7.

- [Quadratic Assignment Problem on QAPLIB nug instances](<https://www.sota2.com/research/sota/quadratic-assignment-problem-on-qaplib-nug-instances.md>): Quadratic Assignment Problem; QAPLIB nug instances; QAP Cost: 3724.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2102.13382>)

[PDF](<https://arxiv.org/pdf/2102.13382.pdf>)

[Implementation](<https://github.com/ChangYong-Oh/LAW2ORDER>)