An exact penalty function approach for nonlinear integer programming problems. (English) Zbl 0625.90061

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.
Reviewer: N.I.Yanev


90C10 Integer programming
90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
Full Text: DOI


[1] Armstrong, R. D.; Cook, W. D.; Palacios-Gomes, F. E., An algorithm for a nonlinear discontinuous knapsack problem, Management Science, 25, 884-894 (1979)
[2] Balas, E., Duality in discrete programming: II. The quadratic case, Management Science, 16, 14-32 (1969) · Zbl 0191.48202
[3] Bazaraa, M. S.; Goode, J. J., A cutting plane algorithm for the quadratic set-covering problem, Operations Research, 23, 150-158 (1975) · Zbl 0331.90043
[4] Beale, E. M.L.; Tomlin, J. A., Special facilities in a general mathematical programming system for non-convex problems using special ordered sets of variables, (Lawrence, J., Proceedings of the Fifth International Conference on Operations Research (1969), Tavistock: Tavistock New York), 447-454
[5] Billionnet, A.; Minoux, M., Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions, Discrete Applied Mathematics, 12, 1-11 (1985) · Zbl 0583.90067
[6] Carter, M. W., The indefinite zero-one quadratic problem, Discrete Applied Mathematics, 7, 23-44 (1984) · Zbl 0524.90061
[7] Gallo, G.; Hammer, P. L.; Simeone, B., Quadratic knapsack problems, Mathematical Programming Study, 12, 132-149 (1980) · Zbl 0462.90068
[8] Granot, D.; Granot, F.; Kallberg, J., Covering relaxation for positive 0-1 polynomial programs, Management Science, 25, 264-273 (1979) · Zbl 0415.90058
[9] Granot, D.; Granot, F.; Vaessen, W., An accelerated covering relaxation algorithm for solving 0-1 positive polynomial programs, Mathematical Programming, 22, 350-357 (1982) · Zbl 0476.90044
[10] Gulati, V. P.; Gupta, S. K.; Mittal, A. K., Unconstrained quadratic bivalent programming problems, European Journal of Operational Research, 15, 121-125 (1984) · Zbl 0536.90063
[11] Hammer, P. L.; Peled, U. N., On the maximization of a pseudo-boolean function, Journal of the A.C.M., 19, 265-282 (1972) · Zbl 0262.90048
[12] Hammer, P. L.; Rudeanu, S., Boolean Methods in Operations Research and Related Areas (1968), Springer: Springer London · Zbl 0155.28001
[13] Korner, F., An efficient branch and bound algorithm to solve the quadratic integer programming problem, Computing, 30, 253-260 (1983) · Zbl 0494.65035
[14] Lu, S.-H., An improved enumerative algorithm for solving quadratic zero-one programming, European Journal of Operational Research, 15, 110-120 (1984) · Zbl 0526.90063
[15] Martello, S.; Toth, P., A branch and bound algorithm for the zero-one multiple knapsack problem, Discrete Applied Mathematics, 3, 275-288 (1981) · Zbl 0466.90050
[16] Marthur, K.; Salkin, H. M.; Morito, S., A branch and bound algorithm for a class of nonlinear knapsack problems, Operations Research Letters, 2, 155-160 (1983) · Zbl 0526.90066
[17] McBride, R. D.; Yormark, J. S., An implicit enumeration algorithm for quadratic integer programming, Management Science, 26, 282-296 (1980) · Zbl 0443.90067
[18] Morin, T. L.; Marsten, R. E., An algorithm for nonlinear knapsack problems, Management Science, 22, 1147-1158 (1976) · Zbl 0357.90045
[19] Nemhauser, G. L.; Wolsey, L. A.; Fisher, M. L., An analysis of approximations for maximizing a submodular set function I, Mathematical Programming, 14, 265-294 (1978) · Zbl 0374.90045
[20] Nemhauser, G. L.; Wolsey, L. A., Maximizing submodular set functions: Formulations and analysis of algorithms, Annals of Discrete Mathematics, 11, 279-301 (1981) · Zbl 0469.90052
[21] Shmelev, V. V., Penalty functions in linear integer programming, Automation and Remote Control (USSR), 36, 1566-1570 (1975) · Zbl 0332.90030
[22] Sinclair, M., Solution methods for nonlinear mixed integer programming problems, Ph.D. thesis, University of Stellenbosch (1978)
[23] Yarlagadda, R., Unit integer quadratic binary programming, Journal of Mathematical Analysis and Applications, 94, 246-267 (1983) · Zbl 0517.90049
[24] Zeitlin, Z., Integer resource allocations with the objective function separable into pairs of variables, European Journal of Operational Research, 8, 152-158 (1981) · Zbl 0464.90058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.