An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
From MaRDI portal
Publication:3790963
DOI10.1287/opre.36.3.493zbMath0646.90084OpenAlexW2159739530MaRDI QIDQ3790963
Francisco Barahona, Martin Grötschel, Michael Jünger, Gerhard Reinelt
Publication date: 1988
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/2a618975e68a2a669f03c8757fc163b5f05f1d85
cutting plane algorithmcircuit designsolid-state physicsprinted circuit board designground states of spin glassesmax-cut problem in graphs
Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Applications of mathematical programming (90C90) Combinatorial optimization (90C27)
Related Items
Introduction to QUBO, Unnamed Item, Unnamed Item, Fast Distributed Approximation for Max-Cut, MAX CUT in weighted random intersection graphs and discrepancy of sparse random set systems, Quantum Annealing versus Digital Computing, A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis, Algorithm unions for solving discrete optimization problems, Faster exact solution of sparse maxcut and QUBO problems, Graph partitioning: an updated survey, On optimization problems in acyclic hypergraphs, A universal quantum algorithm for weighted maximum cut and Ising problems, Complexity of maximum cut on interval graphs, Maximum Cut Parameterized by Crossing Number, Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches, What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO, Global equilibrium search applied to the unconstrained binary quadratic optimization problem, Complexity of the weighted max-cut in Euclidean space, Feasible direction algorithm for solving the SDP relaxations of quadratic {−1, 1} programming problems, \(f\)-flip strategies for unconstrained binary quadratic programming, Two-edge connected spanning subgraphs and polyhedra, An augmented Lagrangian method for binary quadratic programming based on a class of continuous functions, Connected max cut is polynomial for graphs without the excluded minor \(K_5\backslash e\), Decomposition and optimization over cycles in binary matroids, Building an iterative heuristic solver for a quantum annealer, Application of cut polyhedra. I, Applications of cut polyhedra. II, The expected relative error of the polyhedral approximation of the max- cut problem, An approximate max-flow min-cut relation for undirected multicommodity flow, with applications, On computational capabilities of Ising machines based on nonlinear oscillators, The equipartition polytope. I: Formulations, dimension and basic facets, Solving the max-cut problem using eigenvalues, An effective iterated tabu search for the maximum bisection problem, Computational study of valid inequalities for the maximum \(k\)-cut problem, Via Minimization with Pin Preassignments and Layer Preference, A branch-and-cut algorithm for the equicut problem, Facets of the balanced (acyclic) induced subgraph polytope, A cutting plane algorithm for a clustering problem, Experiments in quadratic 0-1 programming, Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights, A class of spectral bounds for max \(k\)-cut, Computational study of a branching algorithm for the maximum \(k\)-cut problem, Lifting and separation procedures for the cut polytope, The unconstrained binary quadratic programming problem: a survey, Teams of global equilibrium search algorithms for solving the weighted maximum cut problem in parallel, New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph, Minimizing breaks by maximizing cuts., The maximum cardinality cut problem in co-bipartite chain graphs, Intractability of min- and max-cut in streaming graphs, Probabilistic nonunitary gate in imaginary time evolution, Exact ground states of two-dimensional \(\pm J\) Ising spin glasses, Solving VLSI design and DNA sequencing problems using bipartization of graphs, Partitioning planar graphs: a fast combinatorial approach for max-cut, A new discrete filled function method for solving large scale max-cut problems, Bounds for Random Binary Quadratic Programs, A semidefinite relaxation based global algorithm for two-level graph partition problem, A VNS metaheuristic with stochastic steps for Max 3-cut and Max 3-section, A polynomial-time recursive algorithm for some unconstrained quadratic optimization problems, Finding the maximum cut by the greedy algorithm, A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem, Cuts in undirected graphs. I, Cardinality constrained minimum cut problems: complexity and algorithms., Solving the maxcut problem by the global equilibrium search, Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs, NP-hardness of the Euclidean Max-Cut problem, A successive quadratic programming algorithm for SDP relaxation of Max-Bisection, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, A branch-and-bound algorithm for solving max-\(k\)-cut problem, Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem, A discrete filled function algorithm for approximate global solutions of max-cut problems, Approximation algorithms, A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs, Ising formulations of some graph-theoretic problems in psychological research: models and methods, A multiple search operator heuristic for the max-k-cut problem, A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs, Compositions in the bipartite subgraph polytope, Facets for the cut cone. I, Facets for the cut cone. II: Clique-web inequalities, Round robin scheduling -- a survey, The inequicut cone, Canonical dual approach to solving the maximum cut problem, Maximum cut in fuzzy nature: models and algorithms, A discrete dynamic convexized method for the max-cut problem, Pseudo-Boolean optimization, A projected gradient algorithm for solving the maxcut SDP relaxation, A tight lower bound for a special case of quadratic 0-1 programming, Randomized heuristics for the Max-Cut problem, Approximation algorithms for the bi-criteria weighted MAX-CUT problem, Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm, Application of semi definite relaxation and variable neighborhood search for multiuser detection in synchronous CDMA, A new branch and bound method with pretreatment for the binary quadratic programming, A semidefinite programming based polyhedral cut and price approach for the maxcut problem, Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems, A novel formulation of the max-cut problem and related algorithm, Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints, Approximating graph-constrained max-cut, Approximating max-cut under graph-MSO constraints, Computational Methods for Solving Nonconvex Block-Separable Constrained Quadratic Problems, A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems, Spectral bounds for the maximum cut problem, From Graph Orientation to the Unweighted Maximum Cut, Solution of Boolean quadratic programming problems by two augmented Lagrangian algorithms based on a continuous relaxation, Greedy differencing edge-contraction heuristic for the max-cut problem, A linearization framework for unconstrained quadratic (0-1) problems, Maximization of submodular functions: theory and enumeration algorithms, The node capacitated graph partitioning problem: A computational study, Engineering Branch-and-Cut Algorithms for the Equicut Problem, A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem, New approaches for optimizing over the semimetric polytope, Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut, A \(2^{|E|/4}\)-time algorithm for MAX-CUT, A technique for speeding up the solution of the Lagrangean dual, Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem, Laplacian eigenvalues and the maximum cut problem, Node and edge relaxations of the max-cut problem, Speeding up a memetic algorithm for the max-bisection problem, Solution of large weighted equicut problems, An unconstrained quadratic binary programming approach to the vertex coloring problem
