Analyzing quadratic unconstrained binary optimization problems via multicommodity flows

DOI10.1016/J.DAM.2009.07.009MaRDI QIDQ967446zbMATH OpenOpenAlexDBLPWikidataFDO

Authors B. E. Eshmatov

Publication date 28 April 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://europepmc.org/articles/pmc2808708

zbMATH Keywords

network flowmulticommodity flowroof dualitypersistencyquadratic unconstrained binary optimization

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• The quadratic unconstrained binary optimization problem. Theory, algorithms, and applications
• The unconstrained binary quadratic programming problem: a survey
• A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
• scientific article; zbMATH DE number 4116303
• Improving an interior-point algorithm for multicommodity flows by quadratic regularizations
• Faster approximate multicommodity flow using quadratically coupled flows
• Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem
• Lagrangean decompositions for the unconstrained binary quadratic programming problem
• Unconstrained quadratic bivalent programming problem
• Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems

Cites work

• A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
• Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization
• Network flows. Theory, algorithms, and applications.
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• Upper-bounds for quadratic 0-1 maximization

Cited in

(4)

• A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
• Quadratic unconstrained binary optimization problem preprocessing: theory and empirical analysis
• Mathematical programming models and exact algorithms
• Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems

This page was built for publication: Analyzing quadratic unconstrained binary optimization problems via multicommodity flows

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q967446)