Sampling from the Birkhoff polytope The set of $n\times n$ real, nonnegative matrices whose rows and columns sum to one forms the well-known Birkhoff polytope
Recently someone asked me if I knew

How to sample (in polynomial time) uniformly at random, from the Birkhoff polytope?

Clearly, modulo a few hacks, I did not have a good answer, so am repeating the above question here (the hacks included trying to exploit that every doubly stochastic matrix is a convex combination of permutation matrices).
 A: This is, to my knowledge, still open. It is connected to the problem of computing the volume of the Birkhoff polytope (or computing the volume of its faces), which is known in closed form only for $n\le 14$. This is also equivalent toThis could be approached by counting non-negative integer matrices with equal row and column sums (because you can read the volume from the leading coefficient of the Ehrhart polynomial, like it is done in the paper The Ehrhart polynomial of the Birkhoff polytope, by Matthias Beck and Dennis Pixton. There are algorithms that sample from distributions that are close to uniform (see the articles below).
The problem is quite old, but there has been a revival of interest recently by several authors. I can point you to a few


*

*"What does a random contingency table look like?", by A. Barvinok

*"On random, doubly stochastic, tri-diagonal matrices", by P. Diaconis and P. Matchett Wood


*"Properties of Uniform Doubly Stochastic Matrices" by S. Chatterjee, P. Diaconis, A. Sly

*Gibbs/Metropolis algorithms on a convex polytope by P. Diaconis, G. Lebeau, L. Michel

A: There is a polynomial time algorithm based on random walks to approximately sample from any $n$-dimensional convex body which also applies to the Birkhoff polytope. This is an algorithm by Dyer, Frieze, and Kannan:  A random polynomial time algorithm for approximating the volume of convex bodies. Quite a few improvements were found. See e.g. ,  Blocking Conductance and Mixing in Random Walks, R. Kannan, L. Lovasz and R. Montenegro, in Combinatorics, Probability and Computing (2005) 
A: Maybe not completely uniformly random, but recently we have proposed an algorithm to sample from the Birkhoff Polytope using a Riemannian-MCMC algorithm, specifically by simulating the Langevin dynamics on the manifold using first order retraction maps. Thought it would be related to share it here:

Birdal, Tolga, and Umut Simsekli. "Probabilistic Permutation
  Synchronization using the Riemannian Structure of the Birkhoff
  Polytope." Proceedings of the IEEE Conference on Computer Vision and
  Pattern Recognition. 2019. 
  https://arxiv.org/abs/1904.05814

