In confirmatory clinical trials with small sample sizes, hypothesis tests based on asymptotic distributions are often not valid and exact non-parametric procedures are applied instead. However, the latter are based on discrete test statistics and can become very conservative, even more so, if adjustments for multiple testing as the Bonferroni correction are applied. We propose improved exact multiple testing procedures for the setting where two parallel groups are compared in multiple binary endpoints. Based on the joint conditional distribution of test statistics of Fisher's exact tests, optimal rejection regions for intersection hypotheses tests are constructed. To efficiently search the large space of possible rejection regions, we propose an optimization algorithm based on constrained optimization and integer linear programming. Depending on the optimization objective, the optimal test yields maximal power under a specific alternative, maximal exhaustion of the nominal type I error rate, or the largest possible rejection region controlling the type I error rate. Applying the closed testing principle, we construct optimized multiple testing procedures with strong familywise error rate control. Furthermore, we propose a greedy algorithm for nearly optimal tests, which is computationally more efficient. We numerically compare the unconditional power of the optimized procedure with alternative approaches and illustrate the optimal tests with a clinical trial example in a rare disease.