  Two classes of Bell diagonal indecomposable entanglement witnesses in
$\mathbb{C}^4 \otimes \mathbb{C}^4$ are considered. Within the first class, we
find a generalization of the well-known Choi witness from $\mathbb{C}^3 \otimes
\mathbb{C}^3$, while the second one contains the reduction map. Interestingly,
contrary to $\mathbb{C}^3 \otimes \mathbb{C}^3$ case, the generalized Choi
witnesses are no longer optimal. We perform an optimization procedure of
finding spanning vectors, that eventually gives rise to optimal witnesses.
Operators from the second class turn out to be optimal, however, without the
spanning property. This analysis sheds a new light into the intricate structure
of optimal entanglement witnesses.
