A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
From MaRDI portal
Publication:951124
DOI10.1016/j.disopt.2007.02.001zbMath1170.90454OpenAlexW2095464687WikidataQ59560585 ScholiaQ59560585MaRDI QIDQ951124
Richard Sun, Endre Boros, Peter L. Hammer, Gabriel Tavares
Publication date: 29 October 2008
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2007.02.001
Related Items
Persistency of Linear Programming Relaxations for the Stable Set Problem, Autarkies and Persistencies for QUBO, Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations, Probabilistic GRASP-tabu search algorithms for the UBQP problem, Penalty weights in QUBO formulations: permutation problems, A hybrid metaheuristic approach to solving the UBQP problem, Global optimality conditions and optimization methods for quadratic integer programming problems, A polynomial case of convex integer quadratic programming problems with box integer constraints, Efficient minimization of higher order submodular functions using monotonic Boolean functions, Quadratic reformulations of nonlinear binary optimization problems, Path relinking for unconstrained binary quadratic programming, Efficient branch-and-bound algorithms for weighted MAX-2-SAT, Analyzing quadratic unconstrained binary optimization problems via multicommodity flows, Generalized roof duality, Quantum bridge analytics. I: A tutorial on formulating and using QUBO models, Quantum bridge analytics. I: A tutorial on formulating and using QUBO models, Persistency of linear programming relaxations for the stable set problem
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Efficient branch-and-bound algorithms for weighted MAX-2-SAT
- The max-cut problem on graphs not contractible to \(K_ 5\)
- Pseudo-Boolean optimization
- Multistart tabu search strategies for the unconstrained binary quadratic optimization problem
- Upper-bounds for quadratic 0-1 maximization
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- On the equivalence of paved-duality and standard linearization in nonlinear 0-1 optimization
- The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
- Persistency in quadratic 0-1 optimization
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- On the equivalence between roof duality and Lagrangian duality for unconstrained \(0\)-\(1\) quadratic programming problems
- A spectral bundle method with bounds
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- Numerical evaluation of SBmethod
- An independent benchmarking of SDP and SOCP solvers
- One-pass heuristics for large-scale unconstrained binary quadratic problems
- Exact MAX-2SAT solution via lift-and-project closure
- On the notion of balance of a signed graph
- Adaptive Memory Tabu Search for Binary Quadratic Programs
- Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs
- Roof duality, complementation and persistency in quadratic 0–1 optimization
- Roof duality for polynomial 0–1 optimization
- Methods of Nonlinear 0-1 Programming
- Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- A Spectral Bundle Method for Semidefinite Programming
- Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
- Elementary closures for integer programs.
- Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem
