Optimization problems with nonlinear cost functions and combinatorial constraints appear in many real-world applications but remain challenging to solve efficiently. Fast optimization techniques like Mixed Integer Linear Programming can be fast in practice but cannot trivially optimize nonlinear cost functions. On the other hand, general nonlinear optimizers like gradient descent often do not handle complex combinatorial structures, may require many queries of the cost function, and are prone to…