nach oben

4OR

Erschienen in:

02.12.2017 | Research Paper

Compact linearization for binary quadratic problems subject to assignment constraints

verfasst von: Sven Mallach

Erschienen in: 4OR | Ausgabe 3/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Quasi-Newton methods for multiobjective optimization problems

Nächster Artikel Optimality and duality in constrained interval-valued optimization

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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

Titel: Compact linearization for binary quadratic problems subject to assignment constraints
verfasst von: Sven Mallach
Publikationsdatum: 02.12.2017
Verlag: Springer Berlin Heidelberg
Erschienen in: 4OR / Ausgabe 3/2018
Print ISSN: 1619-4500
Elektronische ISSN: 1614-2411
DOI: https://doi.org/10.1007/s10288-017-0364-0

Premium Partner

Marktübersichten

Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen.

Zur Marktübersicht

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2018

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

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

Recent studies of agent incentives in internet resource allocation and pricing

Optimality and duality in constrained interval-valued optimization

Quasi-Newton methods for multiobjective optimization problems

Premium Partner

Marktübersichten