We introduce methods from convex optimization to solve the multimarginal transport problem arise in the context of strictly correlated electron density functional theory. Convex relaxations are used to provide outer approximation to the set of $N$-representable 2-marginals and 3-marginals, which in turn provide lower bounds to the energy. We further propose rounding schemes based on tensor decomposition to obtain upper bounds to the energy. Numerical experiments demonstrate a gap of order $10^{-3}$ to $10^{-2}$ between the upper and lower bounds.