Training ever-larger deep neural networks (DNNs) on massive accelerator clusters relies on two factors: pipeline parallelism to keep devices busy, and activation recomputation to fit models into memory. However, selecting the optimal combination of multilevel pipeline partitions and recomputation strategies becomes intractable as modern models increase in depth, irregularity and layer heterogeneity.Our planner simultaneously addresses four issues: computation imbalance, memory slack, redundant work and schedule-induced idle time. It encodes computation, memory and pipeline bubbles; in a single symbolic formulation, which is solved using an ILP-based optimizer.When training several state-of-the-art models on a 16-NPU cluster, our planner achieves a speed-up of up to 1.36× over the hand-tuned Megatron baseline and up to 1.27× over the automated planners PipeDream, Merak and AdaPipe. It also increases peak device memory utilization by up to 1.42x compared to Megatron, paving the way for faster, more memory-efficient, very large-scale DNN training.