Reinforcement learning-based methods for constructing solutions to combinatorial optimization offer an exciting new paradigm for solving optimization problems, requiring less problem-specific human input and insight than traditional Operations Research techniques. This talk discusses how to automatically learn heuristics to solve optimization problems and how to leverage these learned models within heuristic search to find high-quality solutions to a range of optimization problems. We show that these techniques can not only match state-of-the-art human-designed heuristics, but even exceed their performance on well-studied domains like vehicle routing.