Interleavers play a key role in interleave-division multiplexing (IDM), interleave-division multiple access (IDMA) and related techniques such as multi-layer IDMA (ML-IDMA). The separation of the information of different layers/users is achieved by interleaving. Only carefully designed interleaver sets lead to a good error performance. Interleaver sets should be generated efficiently. Only a few bits per interleaver (or even no bits at all) should be necessary to specify the corresponding interleaver pattern. We demonstrate that the interfering weights are responsible for the error performance of IDM/IDMA/ML-IDMA systems. A criterion for interleaver design is proposed, and a factor graph approach is used to optimize a new family of interleavers called shift-orthogonal interleavers.