Artikel
Inductive linearization for binary quadratic programs with linear constraints
A linearization technique for binary quadratic programs (BQPs) that comprise linear constraints is presented. The technique, called “inductive linearization”, extends concepts for BQPs with particular equation constraints, that have been referred to as “compact linearization” before, to the general case. Quadratic terms may occur in the objective function, in the set of constraints, or in both. For several relevant applications, the linear programming relaxations obtained from applying the technique are proven to be at least as strong as the one obtained with a well-known classical linearization. It is also shown how to obtain an inductive linearization automatically. This might be used, e.g., by general-purpose mixed-integer programming solvers.
- Sprache
-
Englisch
- Erschienen in
-
Journal: 4OR ; ISSN: 1614-2411 ; Volume: 19 ; Year: 2020 ; Issue: 4 ; Pages: 549-570 ; Berlin, Heidelberg: Springer
- Klassifikation
-
Management
Econometric and Statistical Methods and Methodology: General
Bayesian Analysis: General
Single Equation Models; Single Variables: General
Multiple or Simultaneous Equation Models; Multiple Variables: General
- Thema
-
Non-linear programming
Binary quadratic programming
Mixed-integer programming
Linearization
- Ereignis
-
Geistige Schöpfung
- (wer)
-
Mallach, Sven
- Ereignis
-
Veröffentlichung
- (wer)
-
Springer
- (wo)
-
Berlin, Heidelberg
- (wann)
-
2020
- DOI
-
doi:10.1007/s10288-020-00460-z
- Letzte Aktualisierung
-
10.03.2025, 11:44 MEZ
Datenpartner
Dieses Objekt wird bereitgestellt von:
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.
Objekttyp
- Artikel
Beteiligte
- Mallach, Sven
- Springer
Entstanden
- 2020
Ähnliche Objekte (12)
Packing under convex quadratic constraints
Locally Exact Lower Bounds and Optimality Cuts for All-Quadratic Programs with Convex Constraints
Notes on automorphs of binary quadratic forms.
Paper XV. On Complex Binary Quadratic Forms.
Binary quadratic forms : classical theory and modern computations
Inductive Synthesis for Probabilistic Programs Reaches New Horizons
Binary tomography by iterating linear programs
Lagrangian Decomposition of Mixed-Integer All-Quadratic Programs
Binary quadratic forms : an algorithmic approach ; with 5 tables
On the hardness of quadratic unconstrained binary optimization problems
PAYNT : A Tool for Inductive Synthesis of Probabilistic Programs
Mathematical programs with vanishing constraints
Packing under convex quadratic constraints
Locally Exact Lower Bounds and Optimality Cuts for All-Quadratic Programs with Convex Constraints
Notes on automorphs of binary quadratic forms.
Paper XV. On Complex Binary Quadratic Forms.
Binary quadratic forms : classical theory and modern computations
Inductive Synthesis for Probabilistic Programs Reaches New Horizons
Binary tomography by iterating linear programs
Lagrangian Decomposition of Mixed-Integer All-Quadratic Programs
Binary quadratic forms : an algorithmic approach ; with 5 tables
On the hardness of quadratic unconstrained binary optimization problems
PAYNT : A Tool for Inductive Synthesis of Probabilistic Programs
Mathematical programs with vanishing constraints
Packing under convex quadratic constraints
Locally Exact Lower Bounds and Optimality Cuts for All-Quadratic Programs with Convex Constraints
Notes on automorphs of binary quadratic forms.
Paper XV. On Complex Binary Quadratic Forms.
Binary quadratic forms : classical theory and modern computations
Inductive Synthesis for Probabilistic Programs Reaches New Horizons
Binary tomography by iterating linear programs
Lagrangian Decomposition of Mixed-Integer All-Quadratic Programs
Binary quadratic forms : an algorithmic approach ; with 5 tables
On the hardness of quadratic unconstrained binary optimization problems
PAYNT : A Tool for Inductive Synthesis of Probabilistic Programs