Experiments in quadratic 0-1 programming

DOI10.1007/BF01587084zbMath0677.90046OpenAlexW2031978868MaRDI QIDQ1123806

Francisco Barahona, Michael Jünger, Gerhard Reinelt

Publication date: 1989

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01587084

zbMATH Keywords

polytopes facets max-cut problem cutting plane algorithm unconstrained quadratic 0-1 programming

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Integer programming (90C10) Quadratic programming (90C20) Combinatorial optimization (90C27) Boolean programming (90C09) Polytopes and polyhedra (52Bxx)

Related Items

On characterization of maximal independent sets via quadratic optimization, BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints, Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods, On the number of local maxima in quadratic 0-1 programs, Minimization of a quadratic pseudo-Boolean function, The Boolean Quadric Polytope, Mathematical Programming Models and Exact Algorithms, Building an iterative heuristic solver for a quantum annealer, Applications of cut polyhedra. II, The expected relative error of the polyhedral approximation of the max- cut problem, A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope, A heuristic-based branch and bound algorithm for unconstrained quadratic zero-one programming, Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations, Solving the max-cut problem using eigenvalues, Computational aspects of a branch and bound algorithm for quadratic zero- one programming, Cluster analysis and mathematical programming, On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study, Rapid screening algorithms for stochastically constrained problems, SOME EXPERIENCES WITH SOLVING SEMIDEFINITE PROGRAMMING RELAXATIONS OF BINARY QUADRATIC OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY, Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization, The Boolean quadratic polytope: Some characteristics, facets and relatives, Generalised 2-circulant inequalities for the max-cut problem, Some thoughts on combinatorial optimisation, A note on the 2-circulant inequalities for the MAX-cut problem, Combining semidefinite and polyhedral relaxations for integer programs, Partial Lasserre relaxation for sparse Max-Cut, Quantum Annealing versus Digital Computing, Inductive linearization for binary quadratic programs with linear constraints, The unconstrained binary quadratic programming problem: a survey, An exact quadratic programming approach based on convex reformulation for seru scheduling problems, Gap inequalities for non-convex mixed-integer quadratic programs, Faster exact solution of sparse maxcut and QUBO problems, An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem, On the impact of running intersection inequalities for globally solving polynomial optimization problems, Crossing Minimization in Storyline Visualization, An exact solution method for unconstrained quadratic 0--1 programming: a geometric approach, Deriving compact extended formulations via LP-based separation techniques, Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement, Compositions in the bipartite subgraph polytope, Facets for the cut cone. I, Deriving compact extended formulations via LP-based separation techniques, Finding quasi core with simulated stacked neural networks, Optimal design of a distributed network with a two-level hierarchical structure, A Lagrangian relaxation approach to the edge-weighted clique problem, Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem, Lower bound improvement and forcing rule for quadratic binary programming, Semidefinite relaxations for partitioning, assignment and ordering problems, Recent Progress in Interior-Point Methods: Cutting-Plane Algorithms and Warm Starts, The Running Intersection Relaxation of the Multilinear Polytope, Semidefinite relaxations for partitioning, assignment and ordering problems, Volume computation for sparse Boolean quadric relaxations, A study of the quadratic semi-assignment polytope, An evolutionary heuristic for quadratic 0-1 programming, Linear programming for the \(0-1\) quadratic knapsack problem, Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case, An effective compact formulation of the max cut problem on sparse graphs, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes, Simulated annealing for the unconstrained quadratic pseudo-Boolean function, A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem, A new separation algorithm for the Boolean quadric and cut polytopes, Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut, Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition, Tight Cycle Relaxations for the Cut Polytope, Cutting planes for RLT relaxations of mixed 0-1 polynomial programs, Laplacian eigenvalues and the maximum cut problem, Node and edge relaxations of the max-cut problem, Modelling competitive Hopfield networks for the maximum clique problem

Cites Work