Scientists and engineers in diverse domains need to perform expensive experiments to optimize combinatorial spaces, where each candidate input is a discrete structure (e.g., sequence, tree, graph) or a hybrid structure (mixture of discrete and continuous design variables). For example, in hardware design optimization over locations of processing cores and communication links for data transfer, design evaluation involves performing a computationally-expensive simulation. These experiments are often performed in a heuristic manner by humans and without any formal reasoning. In this paper, we first describe the key challenges in solving these problems in the framework of Bayesian optimization (BO) and our progress over the last five years in addressing these challenges. We also discuss exciting sustainability applications in domains such as electronic design automation, nanoporous materials science, biological sequence design, and electric transportation systems.