In this paper, a numerical procedure for plastic limit analysis of 3-D elastic-perfectly plastic bodies under complex loads is presented. The method is based on the lower-bound limit theorem and von Mises yield criterion so that the lower-bound limit analysis can be conducted by solving a nonlinear mathematical programming problem. A SQP algorithm and a dimension reduction-based technique are used to solve the discretized finite element optimization formulation. A conception of active constraint set is introduced, so that the number of constraints can be reduced greatly. The basis vectors of reduced residual stress spaces are constructed by performing an equilibrium iteration procedure of elasto-plastic finite element analysis. The numerical procedure is applied to carry out the plastic limit analysis of pipelines with part-through slots under internal pressure, bending moment and axial force. The effects of different sizes of part-through slots on the limit loads of pipelines are investigated and evaluated.