Experiments in quadratic 0-1 programming
From MaRDI portal
The paper is concerned with the unconstrained quadratic 0-1 programming problem. An approach proposed by the authors consists in reducing this problem to a max-cut problem in a graph and then using a partial description of the cut polytope to attack the problem with a cutting plane algorithm based on the simplex method. This approach, however, does not guarantee finding an optimum solution. To obtain it the authors use a branch-and-bound method. They report on extensive computational experience and note that in the vast majority of examples considered the problem is solved without branching.
Recommendations
- A heuristic-based branch and bound algorithm for unconstrained quadratic zero-one programming
- Computational aspects of a branch and bound algorithm for quadratic zero- one programming
- scientific article; zbMATH DE number 4070666
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- A solvable case of quadratic 0-1 programming
Cites work
- A Cutting Plane Algorithm for the Linear Ordering Problem
- A solvable case of quadratic 0-1 programming
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Minimum cuts and related problems
- Nonlinear 0–1 programming: I. Linearization techniques
- On the cut polytope
- On the magnetisation of the ground states in two dimensional Ising spin glasses
- Optimization of a 532-city symmetric traveling salesman problem by branch and cut
- Roof duality, complementation and persistency in quadratic 0–1 optimization
- Some Network Flow Problems Solved with Pseudo-Boolean Programming
- The indefinite zero-one quadratic problem
Cited in
(86)- A study of the quadratic semi-assignment polytope
- A solvable case of quadratic 0-1 programming
- Experiments with successive quadratic programming algorithms
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- Compositions in the bipartite subgraph polytope
- Facets for the cut cone. I
- Optimal design of a distributed network with a two-level hierarchical structure
- Linear programming for the \(0-1\) quadratic knapsack problem
- Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- Simulated annealing for the unconstrained quadratic pseudo-Boolean function
- Laplacian eigenvalues and the maximum cut problem
- Node and edge relaxations of the max-cut problem
- Minimization of a quadratic pseudo-Boolean function
- Cluster analysis and mathematical programming
- Some thoughts on combinatorial optimisation
- Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods
- A MAX-CUT formulation of 0/1 programs
- An evolutionary heuristic for quadratic 0-1 programming
- Modelling competitive Hopfield networks for the maximum clique problem
- 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 the max-cut problem using eigenvalues
- On the impact of running intersection inequalities for globally solving polynomial optimization problems
- Volume computation for sparse Boolean quadric relaxations
- A new separation algorithm for the Boolean quadric and cut polytopes
- Cutting planes for RLT relaxations of mixed 0-1 polynomial programs
- On characterization of maximal independent sets via quadratic optimization
- On the number of local maxima in quadratic 0-1 programs
- Generalization of Barahona's algorithm for cases of integer non-linear programming with box constraints
- Building an iterative heuristic solver for a quantum annealer
- On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study
- Rapid screening algorithms for stochastically constrained problems
- A note on the 2-circulant inequalities for the MAX-cut problem
- Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement
- A tight lower bound for a special case of quadratic 0-1 programming
- Lower bound improvement and forcing rule for quadratic binary programming
- A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem
- Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
- Computational aspects of a branch and bound algorithm for quadratic zero- one programming
- Generalised 2-circulant inequalities for the max-cut problem
- Recent Progress in Interior-Point Methods: Cutting-Plane Algorithms and Warm Starts
- An effective compact formulation of the max cut problem on sparse graphs
- Some experiences with solving semidefinite programming relaxations of binary quadratic optimization models in computational biology
- Crossing Minimization in Storyline Visualization
- Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut
- scientific article; zbMATH DE number 4070666 (Why is no real title available?)
- Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization
- The unconstrained binary quadratic programming problem: a survey
- Gap inequalities for non-convex mixed-integer quadratic programs
- scientific article; zbMATH DE number 1199854 (Why is no real title available?)
- An exact solution method for unconstrained quadratic 0--1 programming: a geometric approach
- scientific article; zbMATH DE number 2154265 (Why is no real title available?)
- The Running Intersection Relaxation of the Multilinear Polytope
- Tight cycle relaxations for the cut polytope
- The Boolean quadric polytope
- Mathematical programming models and exact algorithms
- Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization
- Combining semidefinite and polyhedral relaxations for integer programs
- Quantum annealing versus digital computing. An experimental comparison
- Finding quasi core with simulated stacked neural networks
- BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints
- Deriving compact extended formulations via LP-based separation techniques
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Deriving compact extended formulations via LP-based separation techniques
- A Lagrangian relaxation approach to the edge-weighted clique problem
- Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem
- Partial Lasserre relaxation for sparse Max-Cut
- Inductive linearization for binary quadratic programs with linear constraints
- An exact quadratic programming approach based on convex reformulation for seru scheduling problems
- Faster exact solution of sparse maxcut and QUBO problems
- A quadratic simplex algorithm for primal optimization over zero-one polytopes
- An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem
- A novel branch and bound algorithm for solving the linear multiplicative programming problems
- A vectorized positive semidefinite penalty method for unconstrained binary quadratic programming
- Proximity guarantees of a lift-and-project approach for the cardinality-constrained Boolean quadric polytope
- Computing the edge expansion of a graph using semidefinite programming
- A family of spanning-tree formulations for the maximum cut problem
- Quadratic convex reformulations for multiobjective binary quadratic programming
- Edge expansion of a graph: SDP-based computational strategies
- Unconstrained quadratic bivalent programming problem
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
This page was built for publication: Experiments in quadratic 0-1 programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1123806)
