We study combinatorial problems with real world applications such as machine\nscheduling, routing, and assignment. We propose a method that combines\nReinforcement Learning (RL) and planning. This method can equally be applied to\nboth the offline, as well as online, variants of the combinatorial problem, in\nwhich the problem components (e.g., jobs in scheduling problems) are not known\nin advance, but rather arrive during the decision-making process. Our solution\nis quite generic, scalable, and leverages distributional knowledge of the\nproblem parameters. We frame the solution process as an MDP, and take a Deep\nQ-Learning approach wherein states are represented as graphs, thereby allowing\nour trained policies to deal with arbitrary changes in a principled manner.\nThough learned policies work well in expectation, small deviations can have\nsubstantial negative effects in combinatorial settings. We mitigate these\ndrawbacks by employing our graph-convolutional policies as non-optimal\nheuristics in a compatible search algorithm, Monte Carlo Tree Search, to\nsignificantly improve overall performance. We demonstrate our method on two\nproblems: Machine Scheduling and Capacitated Vehicle Routing. We show that our\nmethod outperforms custom-tailored mathematical solvers, state of the art\nlearning-based algorithms, and common heuristics, both in computation time and\nperformance.\n