We report developments in combinatorial optimization under constraints in chemical space. We considered random functions, which serve as a baseline to measure performance, and constrained optimizations over two databases of electrochromic molecules (similar to 5000 and 10(12), respectively). These problems were optimized using sequential heuristic next-neighbor search (HNNS) (introduced in Elward and Rinderspacher Phys. Chem. Chem. Phys. 2015, 17, 24322 and Elward and Rinderspacher Mol. Syst. Des. Eng. 2018, 3, 485) and kernel-based efficient global optimization (EGO) with two reordering strategies. In addition to the average ordering method introduced with sequential HNNS, a new reordering based on a locally separable linear model is formulated and applied. Presented is the analysis of periodic kernels for EGO: the modified Dirichlet kernels (D) over tilde (n)(x) = Sigma(n)(i)[cos(2 pi ix) - (-1)(i)]/i, the minimalist kernel K-N(x) = cos(pi x/N)(2)/2 -delta(x)/2, and an analogue to the popular Gaussian kernel, G(N)(sigma)(x) = (e-lx mod Nl2/(2 sigma 2)), where n is the order of the Dirichlet kernel, N is the number of choices on a combinatorial site, and sigma is a broadening factor. We find that reordering is pivotal for high optimization efficiency, in both the average and worst-case scenarios. The new linear-estimation ordering paradigm is superior in the chemistry context. Furthermore, with judicious use of hyperparameters and algorithmic choices, EGO outperforms HNNS. The global optimum for the small chemical problem is found with >98% likelihood for all global search methods employing a linear reordering heuristic for organizing the search space.