Just adding a penalty to the objective works. Another alternative is to consider a two-dimensional lexicographic objective (total constraint violation, actual objective), so that reducing constraint violations is always preferable, and the actual objective is only compared between solutions that are equally good in terms of constraint violations.