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

Asadollah Mahmoodzadeh Vaziri, A. V. Kamyad, S. Efatti

.

DOI: 10.4236/am.2011.210168                

Abstract

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).

Keywords

Zero-One Programming, Nonlinear Programming, Nonlinear Optimization

Conflicts of Interest

The authors declare no conflicts of interest.

References

[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