In low-temperature processes, heat rejected from separation columns is removed by refrigeration systems to heat sinks (reboilers & pre-heaters), process streams, other refrigeration streams, or external utilities. The need for efficient utilization and recovery of energy in sub-ambient gas separation processes is still challenging. Performance and reliability of Simulated Annealing (SA) for simultaneous design and optimization of such systems has been investigated previously. In this work, the effect of different refrigerants satisfying a set of process cooling duties at different temperatures is addressed. Cost reduction can be realized by encompassing both effective screening of heat-integrated separation columns and selecting the best refrigerants. A 29.7% cost savings has been shown through a case study. Afterwards, a comprehensive thermodynamic analysis has been carried out on achieved solutions to verify the accuracy of existing shortcut models and robustness of optimized structure. It has been shown that exergy analysis using two different approaches (i.e. stream wise and unit operation wise) are the same, which indicate the accuracy of the used models. Moreover, we have indicated that both utility costs and exergy losses can be considered as an objective function when optimizing the designs.