An Exact Penalty Method over Discrete Sets

In this talk we consider binary quadratic problems subject to equality constraints. We present a transformation such that we can optimize these problems by solving a max-cut instance, hence a binary unconstrained problem. This transformation, called exact penalty method over discrete sets, gives also an easy way to check the feasibility of the problem: it outputs a threshold value that separates the set of feasible and infeasible solutions. This threshold value and the penalty parameter are related. We show how to make the penalty parameter as small as possible while keeping some threshold value. Then we give an alternative formulation of the penalty parameter, and we present a family of problems proving that this parameter can not be chosen smaller. We also show numerically the importance of a small penalty coefficient. We conclude by comparing our algorithm to some of the current best solvers available, showing the efficiency of our algorithm.