We introduce the Birkhoff Extension, a polynomial-time, almost-everywhere differentiable relaxation of permutation objectives to doubly stochastic matrices, enabling efficient combinatorial optimization.