An Exact Penalty Method over Discrete Sets

Binary quadratic problems (BQP) are very general and have several applications in different fields. We consider (BQP) with integer valued equality constraints and we want to solve a minimization problem. We apply an exact penalty method over discrete sets, proposed by Lasserre in 2016: it transforms an equality constrained BQP into a max-cut instance. This method is important because it gives also a threshold parameter, from which it is possible to determine whether the original problem is feasible. The penalty parameter used in the Lagrangian reformulation is very high, hence, for some instances, computing the maximum cut is more difficult than solving the original problem. Thus we focus on the algorithm in order to decrease the value of the penalty parameter. We show that, with no need of extra calculations, it is possible to make the penalty parameter smaller while keeping some threshold condition. At the same time we explain the main features of these two parameters and we derive their optimal formulations. We solve the max-cut instances with BiqMac, a solver developed by Rinaldi, Rendl and Wiegele. Then we conclude by comparing our algorithm to some of the current best solvers available, showing the efficiency of our method.