Quadratic reformulations of nonlinear binary optimization problems

DOI10.1007/s10107-016-1032-4zbMath1358.90074OpenAlexW1774926842WikidataQ59560469 ScholiaQ59560469MaRDI QIDQ517297

Endre Boros, Martin Anthony, Aritanan Gruber, Yves Cramer

Publication date: 23 March 2017

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: http://eprints.lse.ac.uk/66580/1/__lse.ac.uk_storage_LIBRARY_Secondary_libfile_shared_repository_Content_Anthony%2C%20M_Quadratic%20reformulations%20of%20nonlinear%20binary_Anthony_Quadratic_reformulations_of_nonlinear_binary.pdf

zbMATH Keywords

pseudo-Boolean functionsnonlinear binary optimizationquadratic binary optimizationreformulation methods

Mathematics Subject Classification ID

Integer programming (90C10) Nonlinear programming (90C30) Quadratic programming (90C20) Boolean programming (90C09)

Related Items

Applications and Computational Advances for Solving the QUBO Model, A Computational Framework for Solving Nonlinear Binary Optimization Problems in Robust Causal Inference, Modeling the Costas array problem in QUBO for quantum annealing, Optimal Seating Assignment in the COVID-19 Era via Quantum Computing, Optimal quadratic reformulations of fourth degree pseudo-Boolean functions, On the impact of running intersection inequalities for globally solving polynomial optimization problems, Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation, Quantum bridge analytics. I: A tutorial on formulating and using QUBO models, Quantum bridge analytics. I: A tutorial on formulating and using QUBO models, Compact quadratizations for pseudo-Boolean functions, Quadratization of symmetric pseudo-Boolean functions

Uses Software

• JBool

Cites Work

• Quadratization of symmetric pseudo-Boolean functions
• Generalized roof duality and bisubmodular functions
• Efficient minimization of higher order submodular functions using monotonic Boolean functions
• Efficient evaluations for solving large 0-1 unconstrained quadratic optimisation problems
• Classes of submodular constraints expressible by graph cuts
• Generating all subsets of a finite set with disjoint unions
• Pseudo-Boolean optimization
• Generalized roof duality
• Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
• A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
• The expressive power of binary submodular functions
• Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem
• A reformulation-linearization technique for solving discrete and continuous nonconvex problems
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• One-pass heuristics for large-scale unconstrained binary quadratic problems
• Greedy and local search heuristics for unconstrained binary quadratic programming
• What we know and what we do not know about Turán numbers
• 2-Bases of Quadruples
• Generating All Sets With Bounded Unions
• Efficient Reduction of Polynomial Zero-One Optimization to the Quadratic Case
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• L’algebre de Boole et ses applications en recherche operationnelle
• State-of-the-Art Survey—Constrained Nonlinear 0–1 Programming
• Extended formulations in combinatorial optimization
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item