Supply chain redesign (SCR) involves decisions regarding the timings, amounts, and locations of the investment and disinvestment in facilities, production, material purchase, product sales, contracts, capital-raising loans and bonds, etc. such that the profit is maximized. SCR is a heavily constrained problem; hence as the problem size increases, the MILP formulations (Naraharisetti, P. K.; Karimi, I. A.; Srinivasan, R. Supply Chain Redesign through Optimal Asset Management and Capital Budgeting. Comput. Chem. Eng. 2008, 32, 3153-3169) become increasingly difficult to solve. In addition, MILP solvers typically give only one solution, while multiple optimal solutions may be desirable in practice. Hence, an alternative optimization technique is warranted. In this work, we propose a hybrid MILP-evolutionary algorithm strategy for supply chain redesign and present progress on three fronts: (a) a novel reformulation of the MILP in which most decision variables are unconstrained and the rest can be easily repaired to satisfy constraints, (b) a single-objective hybrid optimization algorithm that uses an evolutionary search and reaches 97% of the objective value attained by CPlex 9.0 on a small example, while outperforming CPlex 9.0 on a large SCR problem, and (c) a multimodal algorithm that identifies multiple supply chain networks with 90-95% of the objective value obtained by CPlex 9.0. Finally, we analyze the effect of uncertainty on each supply chain network identified by our multimodal algorithm.