In recent decades, energy efficiency has become one of the key issues facing large process industries. Mounting economic, environmental and social pressure motivate energy-intensive industries to improve their efficiency. Identifying retrofit opportunities in large-scale problems is extremely complex due to numerous interconnections and dependencies between process units, sub-units and utilities present on most industrial sites. Therefore, when attempting to identify promising retrofit opportunities, methods detecting early design decisions are crucial. Techniques applying heat integration (HI) often use mathematical models and optimization to survey potential solutions. Mixed integer linear programming (MILP) is often used for industrial energy efficiency case studies due to its flexibility, solution speed and guaranteed optimal solution while taking advantage of the extensive bodies of work dedicated to this type of problem. The current work proposes a methodology based on HI and MILP to represent process energy requirements with different heat exchange interfaces. Switching from the current utility interface to an alternative one requires additional heat transfer area while it might bring operational benefits due to better system integration. The optimal combination of the processes with different interfaces is obtained by considering the trade-off between the cost of additional heat exchanger area required and decrease in the operating cost. The proposed method is applied to two industrial case studies which show the added value for HI and impact of the proposed method for reducing the problem size in heat exchanger network (HEN) design. In the first case study, the total cost of the system is reduced by 45% taking into account the cost of the modifications in the existing heat exchangers while in the second case study the computation time of heat load distribution (HLD) is reduced by 78% using the results of optimal interface selection. The proposed method provides early design decisions for retrofit solutions on industrial sites. Utilizing this methodology provides a dual benefit of identifying the most promising options for retrofit applications while also eliminating inconsequential ones at an early stage of the analysis.