The increased concerns about the effect of human activities on the climate have pushed natural gas among the most obvious solutions for the transition to a low-carbon economy. The growing importance and volumes of liquefied natural gas for transportation over long distances come as a consequence of this tendency. The liquefaction of natural gas requires a high amount of energy that can be recovered during the re-gasification phase. In this paper, a novel approach for this purpose is presented, where the main feature is the use of a combination of Rankine and Brayton cycles while retaining natural gas as the only working fluid of the system. The proposed system is optimized for cost and exergy efficiency using a bi-level multi-objective optimization procedure, where the master level is setup as a nonlinear optimization problem and solved using an evolutionary algorithm, while the slave level as a mixed integer-linear programming problem. The results of the optimization show that such system can potentially achieve high efficiencies (up to 60 % exergy efficiency for the power cycle and above 65 % plant thermal efficiency), at the cost of a significant capital investment for the heat exchanger network. By allowing a lower level of integration in the system a profitability of up to 98 kUSD/y can be achieved, while retaining significantly high performance.