An exact penalty function approach for nonlinear integer programming problems (Q580179)

The penalty function approach for integer programming problems is investigated. In the first part of the paper the problem of equivalence of the original problem and the relaxed problem is considered. The relaxation is done as usual, i.e. a part of the constraints are removed and added to the objective function by means of a suitable penalty function. The main result is that for a sufficiently large penalty constant the optimal solution sets for both problems coincide. The second part illustrates the possible applications of the approach to the quadratic assignment problem, quadratic knapsack problem, resource allocation and submodular optimization.