Refinery hydrogen network problem is highly nonlinear due to the equation that describes the power of new compressor. Most of the previous attempts to linearize this equation have been made by assuming constant suction and discharge pressure while taking the inlet flow rate as a variable. Such assumption may not be practical in real condition because the calculated power requirement for new compressor may not be compatible with the pressure ratio of the selected compressor. This work proposed a new linearization method for the power of new compressor that provides additional degree of freedom by allowing the solver to choose the optimum new compressor(s) that satisfied the pressure requirement of process sinks. Using our proposed model, mixed‐integer nonlinear programming (MINLP) formulation can be converted into mixed‐integer linear programming. The applicability of our model was validated using two different refinery case studies. Mixed‐integer linear programming results obtained using our model require substantially lower computational cost than their MINLP counterparts where at least 60% savings in terms of iteration number and computational processing time were achieved. The approach demonstrated here can be potentially used to approach more complex refinery hydrogen network cases where the initial guess can be obtained from the linearized MINLP problem. © 2017 Curtin University and John Wiley & Sons, Ltd.