A Parametric Linearization Approach for Solving Zero-One Nonlinear Programming Problems

DOI: 10.4236/am.2011.210168   PDF   HTML     3,870 Downloads   7,159 Views   Citations


In this paper a new approach for obtaining an approximation global optimum solution of zero-one nonlinear programming (0-1 NP) problem which we call it Parametric Linearization Approach (P.L.A) is proposed. By using this approach the problem is transformed to a sequence of linear programming problems. The approximately solution of the original 0-1 NP problem is obtained based on the optimum values of the objective functions of this sequence of linear programming problems defined by (P.L.A).

Share and Cite:

A. Vaziri, A. Kamyad and S. Efatti, "A Parametric Linearization Approach for Solving Zero-One Nonlinear Programming Problems," Applied Mathematics, Vol. 2 No. 10, 2011, pp. 1207-1212. doi: 10.4236/am.2011.210168.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] P. Hansen, “Method of Nonlinear 0-1 Programming,” Annals of Discrete Mathematics, Vol. 5, 1979, pp. 53-70.
[2] J. Mitchell, P. M. Pardalos and M. G. C. Re-sende, “Interior Point Method for Combinatorial Optimi-zation,” In: D. Z. Du and P. Paradalos, Eds., Handbook of Combinatorial Optimization, Vol. 1, 1998, pp. 189-298.
[3] G. L. Nemhauser and L. A. Wolsey, “In-teger and Combinatorial Optimization,” John Wiley and Sons, New York, 1988.
[4] P. M. Paradalos, “Continuous Approaches to Discrete Optimization Problems,” In: G. Di Pillo and F. Gianessi, Eds., Nonlinear Optimization and Applications, Plenum Publishing, New York, 1996, pp. 313-328.
[5] M. S. Chern and R. H. Jan, “Reliability Optimization Problems with Multiple Constraints,” IEEE Transactions on Reliability, 1986, Vol. 35, No. 4, pp. 431-436. doi:10.1109/TR.1986.4335497
[6] K. B. Mira and U. Sharma, “An Efficient Algorithm to Solve Integer Pro-gramming Problems Arising in System-Reliability De-sign,” IEEE Transactions on Reliability, Vol. 40, No. 1, 1991, pp. 81-91.
[7] E. L. Lawlev and M. D. Bell, “A Method for Solving Discrete Optimization Problems,” Operations Research, Vol. 14, No. 6, 1966, pp. 1098-1112. doi:10.1287/opre.14.6.1098
[8] P. C. Gilmol and R. E. Gomory, “The Theory and Computation of Knapsack Function,” Operations Research, Vol. 14, 1966, pp. 1045-1074. doi:10.1287/opre.14.6.1045
[9] E. Balas, “An Additive Algorithm for Solving Linear Programs with 0-1 Varia-ble,” Operations Research, Vol. 13, No. 4, 1965, pp. 517-545. doi:10.1287/opre.13.4.517
[10] F. Glover, “Improved Linear Integer Programming Formulations of Nonlinear Integer Problems,” Management Science, Vol. 22, No. 4, 1975, pp. 455-460. doi:10.1287/mnsc.22.4.455
[11] M. Oral and O. Kettani, “Reformulating Nonlinear Combinatorial Optimization Problems for Higher Computational Efficiency,” European Journal of Operational Research, Vol. 58, No. 2, 1992, pp. 236-249. doi:10.1016/0377-2217(92)90210-Z
[12] M. Oral and O. Kettani, “A Linearization Procedure for Quadratic and Cubic Mixed Integer Problems,” Opera-tions Research, Vol. 40, Supplement 1, 1992, pp. s109- s116.
[13] P. Hansen and C. Meyer, “Improved Compact Linearizations for the Unconstrained Quadratic 0-1 Minimization Problem,” Discrete Applied Mathematics, Vol. 157, 2009, pp. 1267-1290. doi:10.1016/j.dam.2007.12.008

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.