A solvable case of quadratic 0-1 programming
From MaRDI portal
Publication:1079494
DOI10.1016/0166-218X(86)90065-XzbMath0597.90059OpenAlexW1973069886MaRDI QIDQ1079494
Publication date: 1986
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(86)90065-x
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Quadratic programming (90C20) Boolean programming (90C09)
Related Items (31)
Generalization of Barahona's algorithm for cases of integer non-linear programming with box constraints ⋮ Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ A Classifier to Decide on the Linearization of Mixed-Integer Quadratic Problems in CPLEX ⋮ A unified approach to polynomially solvable cases of integer ``non-separable quadratic optimization ⋮ Graph separation techniques for quadratic zero-one programming ⋮ The equipartition polytope. I: Formulations, dimension and basic facets ⋮ Computational aspects of a branch and bound algorithm for quadratic zero- one programming ⋮ The Boolean quadratic polytope: Some characteristics, facets and relatives ⋮ Experiments in quadratic 0-1 programming ⋮ Efficient joint object matching via linear programming ⋮ The unconstrained binary quadratic programming problem: a survey ⋮ On the complexity of binary polynomial optimization over acyclic hypergraphs ⋮ Adaptive randomization in network data ⋮ The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds ⋮ A polynomial case of convex integer quadratic programming problems with box integer constraints ⋮ A solvable class of quadratic 0-1 programming ⋮ Locating facilities which interact: Some solvable cases ⋮ The generalized vertex cover problem and some variations ⋮ Complexity and algorithms for nonlinear optimization problems ⋮ An O\((nm)\) algorithm for a special case of the multimedian location problem on a tree ⋮ Pseudo-Boolean optimization ⋮ Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm ⋮ The basic algorithm for pseudo-Boolean programming revisited ⋮ Global equilibrium search applied to the unconstrained binary quadratic optimization problem ⋮ Checking robust nonsingularity is NP-hard ⋮ An evolutionary heuristic for quadratic 0-1 programming ⋮ Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture ⋮ Computational complexity of norm-maximization ⋮ Simulated annealing for the unconstrained quadratic pseudo-Boolean function ⋮ Closed-form formulas for evaluating \(r\)-flip moves to the unconstrained binary quadratic programming problem
Cites Work
- Unnamed Item
- The indefinite zero-one quadratic problem
- The max-cut problem on graphs not contractible to \(K_ 5\)
- Polytope des independants d'un graphe série-parallèle
- On certain polytopes associated with graphs
- Topology of series-parallel networks
- Roof duality, complementation and persistency in quadratic 0–1 optimization
- Methods of Nonlinear 0-1 Programming
- Minimum cuts and related problems
- Some Network Flow Problems Solved with Pseudo-Boolean Programming
This page was built for publication: A solvable case of quadratic 0-1 programming
