The flexural and compressive strength requirements of deep cement mixing (DCM) columns subjected to lateral loading have brought forth the demand to specify how the incorporation of fiber and fly ash improves these properties and the mixture quality, including the construction design characteristics of segregation and swelling. The paper addresses this issue considering the experimental results from the extensive parametric study in which various lengths and content of carbon fiber (4-, 6-, and 12-mm lengths and 0.1, 0.4, 0.8% by volume of the mixture) are incorporated into the cement-based mixtures with and without the optimized fly ash content. Along the strength parameters, the effects of mixture quality responses on the performance of DCM columns are also investigated. The segregation results of the fresh mixtures, unconfined compression strength (UCS), flexural strength, and swelling values from the 28-day cured specimens are presented. The novel version of the Goal Attainment Method is used for the optimizations, in which the procedures of high-order regression equations and the multi-objective desirability contents are included to obtain more accurate optimization results in terms of the controlling parameters of segregation, swelling, UCS, and flexural strength. The setting time and workability results from the mixtures having the optimized parameters are also presented to demonstrate the fluidity of the optimized mixtures. The addition of carbon fiber led to significant improvements in the segregation and swelling ratios, with gains of up to 35%. Moreover, the three-point flexural strength and unconfined compressive strength were enhanced by 278% and 54%, respectively. The paper specifically reveals that the incorporation of carbon fiber significantly improves the mixture quality characteristics of segregation and swelling as well as the parameters of flexural strength and UCS.