Top

4OR

Published in:

02-12-2017 | Research Paper

Compact linearization for binary quadratic problems subject to assignment constraints

Author: Sven Mallach

Published in: 4OR | Issue 3/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article Quasi-Newton methods for multiobjective optimization problems

next article Optimality and duality in constrained interval-valued optimization

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

http://www.gurobi.com/.

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 CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

Glover F, Woolsey E (1973) Further reduction of zero-one polynomial programming problems to zero-one linear programming problems. Oper Res 21(1):156–161CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

Liberti L (2007) Compact linearization for binary quadratic problems. 4OR 5(3):231–245. https://doi.org/10.1007/s10288-006-0015-3 CrossRef

Nemhauser GL, Wolsey LA (1988) Integer and combinatorial optimization. Wiley, New York, NYCrossRef

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 CrossRef

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 CrossRef

Sahni S (1974) Computationally related problems. SIAM J Comput 3(4):262–279. https://doi.org/10.1137/0203021 CrossRef

Sahni S, Gonzalez T (1976) P-complete approximation problems. JACM 23(3):555–565. https://doi.org/10.1145/321958.321975 CrossRef

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 CrossRef

Watters LJ (1967) Reduction of integer polynomial programming problems to zero-one linear programming problems. Oper Res 15:1171–1174CrossRef

Zangwill WI (1965) Media selection by decision programming. J Advert Res 5:23–37

Title: Compact linearization for binary quadratic problems subject to assignment constraints
Author: Sven Mallach
Publication date: 02-12-2017
Publisher: Springer Berlin Heidelberg
Published in: 4OR / Issue 3/2018
Print ISSN: 1619-4500
Electronic ISSN: 1614-2411
DOI: https://doi.org/10.1007/s10288-017-0364-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Other articles of this Issue 3/2018

Quasi-Newton methods for multiobjective optimization problems

Recent studies of agent incentives in internet resource allocation and pricing

A supply chain perspective of synchromodality to increase the sustainability of freight transportation

Optimality and duality in constrained interval-valued optimization

The multiplicative weights update algorithm for mixed integer nonlinear programming: theory, applications, and limitations

Premium Partners