An Exact Penalty Method for Mixed-Integer Programs

It is shown that a norm penalty method is exact for mixed integer programs in rational data, in the sense that the minimization of the criterion plus penalty over the nonnegativities and integrality constraints has the same set of globally optimal solutions as does the mixed integer program with the equality constraints present. This result is then extended to mixed-integer programs with complementarity constraints.

An example shows that no differentiable penalty can be exact for mixed integer programs.