Carbon sequestration with enhanced gas recovery (CS-EGR) is a well-known technology for safe and economical Carbon Capture, Utilization and Storage (CCUS). However, there is lack of a robust and comprehensive approach to study the optimization of the CS-EGR process. In this paper, a multi-objective optimization code based on a genetic algorithm is combined with the multi-phase flow solver TOUGH2 for CS-EGR applications. Using this combined numerical solver/optimizer, the optimal CO2 injection rate is accurately determined via a series of simulations for a CS-EGR process to maximize the CH4 recovery factor. An improvement in the recovery factor by 5% along with a shorter project life cycle is achieved by optimization. Additional optimization studies with time-dependent CO2 injection scenarios indicate that higher production rates of CH4 can be achieved without compromising the structural integrity of the reservoir. The results of this study pave the way for future optimization studies to enhance the appeal of CS-EGR projects and to help launch this technology on an industrial scale. (C) 2015 Elsevier Ltd. All rights reserved.