Penalty formulation for zero-one nonlinear programming. (English) Zbl 0622.90059

M. Raghavachari [Oper. Res. 17, 680-684 (1969; Zbl 0176.498)] has shown the equivalence of zero-one integer programming and a concave quadratic penalty function for a sufficiently large value of the penalty. A lower bound for this penalty was found by the authors [Math. Program. 24, 229-232 (1982; Zbl 0539.90074)]. It was also shown that this penalty could not be reduced in specific cases. We show that the results generalize to the case where the objective function is any concave function. Equivalent penalty formulation for non-concave functions is also considered.


90C09 Boolean programming
90C30 Nonlinear programming
Full Text: DOI


[1] Atkinson, K. E., An Introduction to Numerical Analysis (1978), J. Wiley: J. Wiley New York · Zbl 0402.65001
[2] Charnes, A.; Cooper, W. W., Management Models and Industrial Applications of Linear Programming (1961), J. Wiley: J. Wiley New York · Zbl 0107.37004
[3] Hammer, P. L.; Hansen, P.; Simeone, B., Roof duality, complementation and persistency in quadratic 0-1 optimization, Math. Programming, 28, 121-155 (1984) · Zbl 0574.90066
[4] Hansen, P., Methods for nonlinear 0-1 programming, Ann. Discrete Math., 5, 53-70 (1979) · Zbl 0426.90063
[5] Kalantari, B.; Rosen, J. B., Penalty for zero-one integer equivalent problem, Math. Programming, 24, 229-232 (1982) · Zbl 0539.90074
[6] Kalantari, B., Large scale global minimization of linearly constrained concave quadratic functions and related problems, (Ph.D. thesis (1984), Computer Science Department: Computer Science Department University of Minnesota) · Zbl 0638.90081
[7] Raghavachari, M., On connection between zero-one integer programming and concave minimization under linear constraints, Operations Research, 17, 680-684 (1969) · Zbl 0176.49805
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.