An Exact Penalty Method over Discrete Sets

We are interested in solving linearly constrained binary quadratic problems (BQP) by transforming the problems into unconstrained ones and using a max-cut solver. This is in the spirit of "exact penalty methods", but optimizing the penalized function over the discrete set.

We improve on a method investigated by Lasserre (2016) who computed a sufficiently large penalty paramter by solving two semidefinite programs. Our new parameters lead to a better performance when solving the transformed problem. We present preliminary computational results demonstrating the strength of this method.