Software-based methods are common approaches for detecting faults in chemical processes. In this paper, new software-based methodologies were developed for locating multiple leaks in a natural gas pipeline. Two types of multiple leaks, subsequent and simultaneous multiple leaks, from a natural gas pipeline were studied, separately. For both subsequent and simultaneous leaks, case studies with two leak occurrences were demonstrated using MATLAB simulation. For detecting and locating subsequent multiple leaks, an unknown input observer was designed and applied, which was modified from our previous study. New Optimization methodology for locating simultaneous multiple leaks was demonstrated. Leak locations were estimated by solving a nonlinear global optimization problem. The global optimization problem contained constraints of partial differential equations, integer, and continuous variables. A new discretization approach was proposed and demonstrated, which required significant less computation effect comparing to conventional global optimization algorithms.