The beautiful art of rearranging matrices

In this paper we review several optimization problems under uncertainty that can be represented as the problem of finding the optimal rearrangement of a matrix. By rearrangement we mean a permutation of the order of the elements in each column of the matrix, such that each column turns out to be oppositely ordered to the sum of the others. A simple heuristic iterative procedure called the Rearrangement Algorithm has been designed to find rearranged matrices so that the vector of their rowsums is minimal in the so-called Schur order, a notion connected to convex stochastic dominance, and to provide approximations to the solutions of various challenging problems with uncertainty scenarios. By changing the initial design of the matrix, or by introducing a family of matrices to be rearranged simultaneously, or by rearranging the columns in a prescribed way or in blocks, the Rearrangement Algorithm can be adapted to deal with several applications in a variety of fields including: the assembly line crew scheduling problem with uncertain labour times, the multi-way partitioning problem, the computation of dependence uncertainty bounds in finance, the fair allocation of indivisible items, and the estimation of a joint distribution subject to statistical uncertainty.