In this paper, the problem of how to efficiently operate a natural gas transmission network under steady-state assumptions is considered. The problem is modeled as a nonlinear network optimization problem where the decision variables are mass flow rate in each arc and gas pressure in each node. The objective function to be minimized is the total amount of fuel consumed in the system by the compressor stations. In the past, several techniques ranging from classical gradient-based procedures to dynamic programming, for solving this difficult nonconvex problem have been applied with limited success, particularly when applied to cyclic network topologies. A cyclic system is defined as a network containing at least one cycle involving two or more compressor stations. In this paper we propose a hybrid metaheuristic procedure that efficiently exploits the problem structure. This hybrid procedure combines very effectively a nonsequential dynamic programming algorithm for finding an optimal set of pressure variables fora fixed set of mass flow rate varables, and short-term memory tabu search procedure for guiding the search in the flow variable space. The proposed procedure represents an improvement to the best existing approach to the best of our knowledge. In addition, empirical evidence over a number of instances supports the effectiviness of the proposed procedure outperforming a multi-start GRG method both in terms of solution quality and feasibility. Furthermore, to assess the quality of the solutions obtained by the algorithm, a lower bound is derived. It is found that the solution quality obtained by the proposed procedure is relatively good. (C) 2008 Published by Elsevier Ltd.