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.001zbMATH Open1170.90454OpenAlexW2095464687WikidataQ59560585 ScholiaQ59560585MaRDI QIDQ951124FDOQ951124
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
Recommendations
- Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT
- An improved lower bound and approximation algorithm for binary constrained quadratic programming problem
- The quadratic unconstrained binary optimization problem. Theory, algorithms, and applications
- Analyzing quadratic unconstrained binary optimization problems via multicommodity flows
- Lower bound improvement and forcing rule for quadratic binary programming
- Une borne optimale pour la programmation entière quasi-convexe
- The unconstrained binary quadratic programming problem: a survey
- On the complexity of local search in unconstrained quadratic binary optimization
- Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems
Cites Work
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs
- Numerical evaluation of SBmethod
- A Spectral Bundle Method for Semidefinite Programming
- Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
- A spectral bundle method with bounds
- On the notion of balance of a signed graph
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Pseudo-Boolean optimization
- The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- An independent benchmarking of SDP and SOCP solvers
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Roof duality, complementation and persistency in quadratic 0–1 optimization
- Roof duality for polynomial 0–1 optimization
- Adaptive memory tabu search for binary quadratic programs
- Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem
- Multistart tabu search strategies for the unconstrained binary quadratic optimization problem
- Title not available (Why is that?)
- The max-cut problem on graphs not contractible to \(K_ 5\)
- Methods of Nonlinear 0-1 Programming
- One-pass heuristics for large-scale unconstrained binary quadratic problems
- Title not available (Why is that?)
- On the equivalence between roof duality and Lagrangian duality for unconstrained \(0\)-\(1\) quadratic programming problems
- Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization
- Exact MAX-2SAT solution via lift-and-project closure
- Efficient branch-and-bound algorithms for weighted MAX-2-SAT
- Upper-bounds for quadratic 0-1 maximization
- Elementary closures for integer programs.
- On the equivalence of paved-duality and standard linearization in nonlinear 0-1 optimization
- Title not available (Why is that?)
- Persistency in quadratic 0-1 optimization
- Title not available (Why is that?)
Cited In (20)
- Efficient branch-and-bound algorithms for weighted MAX-2-SAT
- Quadratic reformulations of nonlinear binary optimization problems
- Quantum bridge analytics. I: A tutorial on formulating and using QUBO models
- Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT
- Probabilistic GRASP-tabu search algorithms for the UBQP problem
- Persistency of linear programming relaxations for the stable set problem
- Quantum bridge analytics. I: A tutorial on formulating and using QUBO models
- Penalty weights in QUBO formulations: permutation problems
- Path relinking for unconstrained binary quadratic programming
- A hybrid metaheuristic approach to solving the UBQP problem
- Lower bound improvement and forcing rule for quadratic binary programming
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Autarkies and Persistencies for QUBO
- Persistency of Linear Programming Relaxations for the Stable Set Problem
- A polynomial case of convex integer quadratic programming problems with box integer constraints
- Global optimality conditions and optimization methods for quadratic integer programming problems
- Title not available (Why is that?)
- Efficient minimization of higher order submodular functions using monotonic Boolean functions
- Analyzing quadratic unconstrained binary optimization problems via multicommodity flows
- Generalized roof duality
Uses Software
This page was built for publication: A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q951124)
