Graph separation techniques for quadratic zero-one programming

DOI10.1016/0898-1221(91)90165-ZMaRDI QIDQ2638933zbMATH OpenOpenAlexFDO

Authors Panos M. Pardalos, Somesh Jha

Publication date 1991

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0898-1221(91)90165-z

zbMATH Keywords

divide-and-conquer algorithmquadratic zero-one programs

Mathematics Subject Classification ID

Quadratic programming (90C20) Programming involving graphs or networks (90C35) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Abstract computational complexity for mathematical programming problems (90C60) Boolean programming (90C09)

Recommendations

• scientific article; zbMATH DE number 4070666
• A Decomposition Method for Quadratic Zero-One Programming
• Graph Partitioning and Continuous Quadratic Programming
• An algorithm for quadratic zero-one programs
• Linear and quadratic programming approaches for the general graph partitioning problem
• scientific article; zbMATH DE number 995811
• Decomposition and linearization for 0-1 quadratic programming
• scientific article; zbMATH DE number 1182569
• scientific article; zbMATH DE number 4062622
• Semidefinite programming approach for the quadratic assignment problem with a sparse graph

Cites work

• scientific article; zbMATH DE number 3643044 (Why is no real title available?)
• scientific article; zbMATH DE number 4033059 (Why is no real title available?)
• scientific article; zbMATH DE number 3473554 (Why is no real title available?)
• scientific article; zbMATH DE number 3249560 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• A Survey of Methods for Pure Nonlinear Integer Programming
• A solvable case of quadratic 0-1 programming
• An Implicit Enumeration Algorithm for Quadratic Integer Programming
• Applications of a Planar Separator Theorem
• Computational aspects of a branch and bound algorithm for quadratic zero- one programming
• Constrained global optimization: algorithms and applications
• Methods of Nonlinear 0-1 Programming
• Minimum cuts and related problems
• Some simplified NP-complete graph problems
• Unconstrained quadratic bivalent programming problem

Cited in

(14)

• A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs
• Locating facilities which interact: Some solvable cases
• Computational aspects of a branch and bound algorithm for quadratic zero- one programming
• Closed-form formulas for evaluating \(r\)-flip moves to the unconstrained binary quadratic programming problem
• The unconstrained binary quadratic programming problem: a survey
• Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture
• A new linearization technique for multi-quadratic 0-1 programming problems.
• Complexity of uniqueness and local search in quadratic 0-1 programming
• Complexity and polynomially solvable special cases of QUBO
• Global equilibrium search applied to the unconstrained binary quadratic optimization problem
• An efficient combined DCA and B\&B using DC/SDP relaxation for globally solving binary quadratic programs
• A branch and bound algorithm for the maximum clique problem
• Adaptive randomization in network data
• Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem

This page was built for publication: Graph separation techniques for quadratic zero-one programming

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