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

Wajeb Gharibi^{*}

Show more

References

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