Improved Balas and Mazzola Linearization for Quadratic 0-1 Programs with Application in a New CuttingPlane Algorithm


Balas and Mazzola linearization (BML) is widely used in devising cutting plane algorithms for quadratic 0-1 programs. In this article, we improve BML by first strengthening the primal formulation of BML and then considering the dual formulation. Additionally, a new cutting plane algorithm is proposed.

Share and Cite:

W. Gharibi, "Improved Balas and Mazzola Linearization for Quadratic 0-1 Programs with Application in a New CuttingPlane Algorithm," International Journal of Communications, Network and System Sciences, Vol. 5 No. 4, 2012, pp. 208-212. doi: 10.4236/ijcns.2012.54026.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” WH Freeman & Co., New York, 1979.
[2] W. Chaovalitwongse, P. M. Pardalos and O. A. Prokopyev, “A New Linearization Technique for Multi-Quadratic 0-1 Programming Problems,” Operations Research Letters, Vol. 32, No. 6, 2004, pp. 517-522. doi:10.1016/j.orl.2004.03.005
[3] S. Elloumi, A. Faye and E. Soutif, “Decomposition and Linearization for 0-1 Quadratic Programming,” Annals of Operations Research, Vol. 99, No. 1-4, 2000, pp. 79-93. doi:10.1023/A:1019236832495
[4] R. Fortet, “L’algebre de Boole et ses Applications en Recherche Operationnelle,” Cahiers du Centred études de Recheche Operationnelle, Vol. 1, No. 4, 1959, pp. 5-36.
[5] F. Glover, “Imporved 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
[6] F. Glover and E. Woolsey, “Further Reduction of ZeroOne Polynomial Programming Problems to Zero-One Linear Programming Problems,” Operations Research, Vol. 22, No. 1, 1973, pp. 156-161. doi:10.1287/opre.21.1.156
[7] F. Glover and E. Woolsey, “Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program,” Operations Research, Vol. 22, No. 1, 1974, pp. 180-182. doi:10.1287/opre.22.1.180
[8] L. Liberti, “Compact Linearization of Binary Quadratic Problems,” 4OR, Vol. 5, No. 3, 2007, pp. 231-245.
[9] H. D. Sherali and J. C. Smith, “An Improved Linearization Strategy for Zero-One Quadratic Programming Problems,” Optimization Letters, Vol. 1, No. 1, 2007, pp. 3347. doi:10.1007/s11590-006-0019-0
[10] S. Gueyea and P. Michelon, “A Linearization Framework for Unconstrained Quadratic (0-1) Problems,” Discrete Applied Mathematics, Vol. 157, No. 6, 2009, pp. 12551266. doi:10.1016/j.dam.2008.01.028
[11] E. Balas and J. B. Mazzola, “Quadratic 0-1 Programming by a New Linearization,” The TIMS/ORSA Meeting, Washington DC, 1980.
[12] L. Kaufman and F. Broeckx, “An Algorithm for the Quadratic Assignment Problem Using Bender’s Decomposition,” European Journal of Operational Research, Vol. 2, No. 3, 1978, pp. 204-211.
[13] Y. Xia and Y. Yuan, “A New Linearization Method for Quadratic Assignment Problems,” Optimization Methods and Software, Vol. 21, No. 5, 2006, pp. 803-816.
[14] R. E. Burkard and U. Derigs, “Assignment and Matching Problems: Solution Methods with FORTRAN-Programs,” Springer-Verlag, Berlin, 1980.
[15] W. Gharibi and Y. Xia, “A Tight Linearization Strategy for Zero-One Quadratic Programming Problems,” in press, 2012.

Copyright © 2024 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.