This paper deals with the problem of optimizing the load distribution and the on/off switching sequences of parallel compressor units in natural gas pipeline compression stations. Natural gas pipelines are used to deliver gas from production sources to customers. Compression stations on these pipelines are generally composed of the interconnection of several compressors units and the aim of the load sharing optimization is to operate these units in an energy efficient way while continuously satisfying the varying demand of gas flow. As the gas demand changes start-up and shut-down of compressor units might be required and the impact of these switching events on the expected lifetime of the compressors also needs to be taken into consideration. Two types of operational constraints are involved: continuous constraints concerning the conservation equations of mass and flow and combinatorial constraints concerning the possibility of changing the number of active compressors. Overall the optimization problem can be formulated as a mixed integer nonlinear programming (MINLP) problem. In this article the generic optimization problem setup and appropriate techniques for the solution are presented. Compared to other traditional strategies such as equal load balancing or equal distance operation from surge, the MINLP approach has shown considerable improvement in terms of energy savings.