Abstract This contribution presents a heuristic approach for solving nonconvex mixed-integer nonlinear programming (MINLP) problems with highly constrained discontinuous domains. A new fuzzy penalty strategy is proposed to make stochastic algorithms capable of solving optimization problems with a large number of difficult-to-satisfy constraints. The method consists of a dynamic penalty formulation based on the magnitude and frequency of the constraint violation, applied according to a hierarchical classification of the constraints. The new strategy is introduced to a multi-objective optimization algorithm based on evolutionary strategies. The performance of the proposed methodology is investigated on the basis of a multi-enterprise supply chain optimization problem.