Abstract
We introduce and prove new necessary and sufficient conditions to carry out a compact linearization approach for a general class of binary quadratic problems subject to assignment constraints that has been proposed by Liberti (4OR 5(3):231–245, 2007, https://doi.org/10.1007/s10288-006-0015-3). The new conditions resolve inconsistencies that can occur when the original method is used. We also present a mixed-integer linear program to compute a minimally sized linearization. When all the assignment constraints have non-overlapping variable support, this program is shown to have a totally unimodular constraint matrix. Finally, we give a polynomial-time combinatorial algorithm that is exact in this case and can be used as a heuristic otherwise.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
References
Adams WP, Sherali HD (1986) A tight linearization and an algorithm for zero-one quadratic programming problems. Manag Sci 32(10):1274–1290. https://doi.org/10.1287/mnsc.32.10.1274
Adams WP, Sherali HD (1999) A reformulation-linearization technique for solving discrete and continuous nonconvex problems, nonconvex optimization and its applications. Springer, Berlin. https://doi.org/10.1007/978-1-4757-4388-3
Allemand K, Fukuda K, Liebling TM, Steiner E (2001) A polynomial case of unconstrained zero-one quadratic optimization. Math Progr 91(1):49–52. https://doi.org/10.1007/s101070100233
Balas E (1964) Extension de l’algorithme additif à la programmation en nombres entiers et à la programmation non linéaire. Comptes rendus de l’Académie des Sciences Paris 258:3136–5139
Balas E, Mazzola JB (1984) Nonlinear 0–1 programming: I. Linearization techniques. Math Progr 30(1):1–21. https://doi.org/10.1007/BF02591796
Billionnet A, Elloumi S, Lambert A (2008) Linear reformulations of integer quadratic programs. Springer, Berlin, pp 43–51. https://doi.org/10.1007/978-3-540-87477-5_5
Boulle M (2004) Compact mathematical formulation for graph partitioning. Optim Eng 5(3):315–333. https://doi.org/10.1023/B:OPTE.0000038889.84284.c7
Bui TN, Leighton FT, Chaudhuri S, Sipser M (1987) Graph bisection algorithms with good average case behavior. Combinatorica 7(2):171–191. https://doi.org/10.1007/BF02579448
Chaovalitwongse W, Pardalos PM, Prokopyev OA (2004) A new linearization technique for multi-quadratic 0–1 programming problems. Oper Res Lett 32(6):517–522. https://doi.org/10.1016/j.orl.2004.03.005
Fortet R (1959) L’algèbre de boole et ses applications en recherche opérationnelle. Cahiers du Centre d’Etudes de Recherche Opérationnelle 1:5–36
Fortet R (1960) Applications de l’algèbre de boole en recherche opérationnelle. Revue de la Société Française de Recherche Opérationnelle 4:17–26
Frieze AM, Yadegar J (1983) On the quadratic assignment problem. Discrete Appl Math 5(1):89–98. https://doi.org/10.1016/0166-218X(83)90018-5
Furini F, Traversi E (2013) Extended linear formulation for binary quadratic problems. Optim Online
Glover F (1975) Improved linear integer programming formulations of nonlinear integer problems. Manag Sci 22(4):455–460. https://doi.org/10.1287/mnsc.22.4.455
Glover F, Woolsey E (1973) Further reduction of zero-one polynomial programming problems to zero-one linear programming problems. Oper Res 21(1):156–161
Glover F, Woolsey E (1974) Converting the 0–1 polynomial programming problem to a 0–1 linear program. Oper Res 22(1):180–182. https://doi.org/10.1287/opre.22.1.180
Gueye S, Michelon P (2009) A linearization framework for unconstrained quadratic (0–1) problems. Discrete Appl Math 157(6):1255–1266. https://doi.org/10.1016/j.dam.2008.01.028
Hammer PL, Rudeanu S (1968) Boolean methods in operations research and related areas. Ökonometrie und Unternehmensforschung/Econometrics and Operations Research. Ökonometrie und Unternehmensforschung/Econometrics and Operations Research, Springer, Berlin. https://doi.org/10.1007/978-3-642-85823-9
Hansen P, Meyer C (2009) Improved compact linearizations for the unconstrained quadratic 0–1 minimization problem. Discrete Appl Math 157(6):1267–1290. https://doi.org/10.1016/j.dam.2007.12.008
Liberti L (2007) Compact linearization for binary quadratic problems. 4OR 5(3):231–245. https://doi.org/10.1007/s10288-006-0015-3
Nemhauser GL, Wolsey LA (1988) Integer and combinatorial optimization. Wiley, New York, NY
Oral M, Kettani O (1992a) A linearization procedure for quadratic and cubic mixed-integer problems. Oper Res 40(1–supplement–1):S109–S116. https://doi.org/10.1287/opre.40.1.S109
Oral M, Kettani O (1992b) Reformulating nonlinear combinatorial optimization problems for highercomputational efficiency. Eur J Oper Res 58(2):236–249. https://doi.org/10.1016/0377-2217(92)90210-Z
Sahni S (1974) Computationally related problems. SIAM J Comput 3(4):262–279. https://doi.org/10.1137/0203021
Sahni S, Gonzalez T (1976) P-complete approximation problems. JACM 23(3):555–565. https://doi.org/10.1145/321958.321975
Sherali HD, Smith JC (2007) An improved linearization strategy for zero-one quadratic programming problems. Optim Lett 1(1):33–47. https://doi.org/10.1007/s11590-006-0019-0
Watters LJ (1967) Reduction of integer polynomial programming problems to zero-one linear programming problems. Oper Res 15:1171–1174
Zangwill WI (1965) Media selection by decision programming. J Advert Res 5:23–37
Acknowledgements
I would like to most sincerely thank Leo Liberti and an anonymous referee for helpful comments on the presentation of the examples and results in this paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mallach, S. Compact linearization for binary quadratic problems subject to assignment constraints. 4OR-Q J Oper Res 16, 295–309 (2018). https://doi.org/10.1007/s10288-017-0364-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10288-017-0364-0