Piecewise convex formulations of binary and permutation problems

It is well-known that the problem of maximization of any difference of convex functions can be turned into a convex maximization problem; here the aim is a piecewise convex maximization problem instead. Although this may seem harder, sometimes the dimension may be reduced by 1, and the local search may be improved by using extreme points of the closure of the convex hull of better points. We show that it is always the case for both binary and permutation problems and give, as such instances, piecewise convex formulations for the maximum clique problem and the quadratic assignment problem.