IJCNS  Vol.5 No.4 , April 2012
Improved Balas and Mazzola Linearization for Quadratic 0-1 Programs with Application in a New CuttingPlane Algorithm
Abstract: 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.
Cite this paper: 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.

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