We consider the problem of separating two sets of points in an Euclidean space with a hyperplane that minimizes the sum of L_p-norm distances to the plane of points lying on the "wrong" side of the plane. A Variable Neighborhood Search heuristic is used to determine the plane coefficients. For a set of examples with L₁-norm, L₂-norm and L_∞-norm, for which the exact solution can be computed, we show that our algorithm finds it in most cases, and gets good approximations in the others. The use of our heuristic solutions for problems in these norms can dramatically accelerate exact algorithms. Our method can be applied on very large instances that are intractable by exact algorithms. Since the proposed approach works for truly arbitrary norms (other than the traditional L₁, L₂ and L_∞), we can explore for the first time the effects of the choice of p on the generalization properties of L_p-norm hyperplane separation.