Section 2 of the Voting Rights Act (VRA) prohibits voting practices that minimize or cancel out minority voting strength. While this section provides no clear framework for avoiding minority vote dilution and creating minority-majority districts, the Supreme Court proposed the Gingles test in the 1986 case Thornberg v Gingles. The Gingles test provides three conditions (“Gingles prongs”) that are necessary for creating a minority-majority district. Mathematical optimization models are increasingly employed to analyze the first prong: compactness and numerosity. Our paper proposes mixed integer programming (MIP) formulations and techniques to explore the maximum number of Black-majority congressional districts for multiple states of the United States. Furthermore, we generalize the diameter-based compactness criterion of Garfinkel and Nemhauser (Management Science, 1970) and provide a framework for optimizers to capture compactness in constraints. To alleviate the solving process, we propose fixing procedures and symmetry-breaking constraints. Our proposed MIP formulations provide (i) an upper bound on the number of Black-majority districts and (ii) lower bounds for the diameter of districts. We finally run a state-of-the-art districting package, GerryChain, to provide feasible bounds for the optimum number of Black-majority districts and their diameters. This provides the best existing optimality gaps that can be closed by both districters and optimizers in the future.