Min-cut clustering

DOI10.1007/BF01585164zbMath0807.90117OpenAlexW1970801029WikidataQ60395648 ScholiaQ60395648MaRDI QIDQ1321669

Anuj Mehrotra, Ellis L. Johnson, Nemhauser, George I.

Publication date: 28 April 1994

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

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

zbMATH Keywords

decomposition compiler design strong valid inequalities column generation scheme min-cut clustering NP-hard mixed integer programming subproblem optimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Mixed integer programming (90C11)

Related Items

A new family of facet defining inequalities for the maximum edge-weighted clique problem, Planning personnel retraining: column generation heuristics, An overview of graph covering and partitioning, Iterated maxima search for the maximally diverse grouping problem, A polyhedral approach for a constrained quadratic 0-1 problem, An exact algorithm for IP column generation, Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables, A branch-and-bound algorithm for the acyclic partitioning problem, Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems, An iterated ``hyperplane exploration approach for the quadratic knapsack problem, An exact algorithm for min-max hyperstructure equipartition with a connected constraint, Large-scale pickup and delivery work area design, Cluster analysis and mathematical programming, LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison, Graph bisection revisited, On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study, Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions, Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems, A hub location problem with fully interconnected backbone and access networks, Cardinality constrained Boolean quadratic polytope, Spectral clustering with local projection distance measurement, The quadratic knapsack problem -- a survey, Unmanned aerial vehicle set covering problem considering fixed-radius coverage constraint, Size-constrained graph partitioning polytopes, A cut-and-branch algorithm for the quadratic knapsack problem, Strong inequalities and a branch-and-price algorithm for the convex recoloring problem, A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem, The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>, Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations, A general purpose exact solution method for mixed integer concave minimization problems, An exact algorithm for graph partitioning, An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem, Lagrangian relaxation versus genetic algorithm based metaheuristic for a large partitioning problem, Unnamed Item, New facets and a branch-and-cut algorithm for the weighted clique problem., On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem, Graph clustering, New bounds and constraint propagation techniques for the clique partitioning problem, Global optimality conditions and optimization methods for quadratic knapsack problems, Reformulated acyclic partitioning for rail-rail containers transshipment, Lifting cover inequalities for the precedence-constrained knapsack problem, Quadratic knapsack relaxations using cutting planes and semidefinite programming, Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement, HEURISTIC AND EXACT SOLUTION METHOD FOR CONVEX NONLINEAR KNAPSACK PROBLEM, The robust binomial approach to chance-constrained optimization problems with application to stochastic partitioning of large process networks, A branch-and-cut algorithm for solving an intraring synchronous optical network design problem, Clustering data that are graph connected, Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem, Maximum cut in fuzzy nature: models and algorithms, A reactive GRASP with path relinking for capacitated clustering, A Lagrangian relaxation approach to the edge-weighted clique problem, Finding optimal solutions to the graph partitioning problem with heuristic search, A branch-and-price algorithm for the Steiner tree packing problem., A polyhedral study of the maximum edge subgraph problem, Lagrangian heuristics for the quadratic knapsack problem, A Lagrangian Relaxation-Based Heuristic to Solve Large Extended Graph Partitioning Problems, Evaluating the quality of image matrices in blockmodeling, Integer programming approach to the printed circuit board grouping problem, Tightening concise linear reformulations of 0-1 cubic programs, A new upper bound for the 0-1 quadratic knapsack problem, An exact combinatorial algorithm for minimum graph bisection, A bounded-error quantum polynomial-time algorithm for two graph bisection problems, Column-Generation in Integer Linear Programming, Cliques and clustering: A combinatorial approach, Formulations and valid inequalities of the node capacitated graph partitioning problem, Distance preserving model order reduction of graph-Laplacians and cluster analysis, Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1, An extended formulation approach to the edge-weighted maximal clique problem, Combinatorial optimization models for production scheduling in automated manufacturing systems, A matheuristic for the 0--1 generalized quadratic multiple knapsack problem, Scheduling Personnel Retraining: Column Generation Heuristics, The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations, The node capacitated graph partitioning problem: A computational study, An optimal tree search method for the manufacturing systems cell formation problem, An approximate dynamic programming approach to convex quadratic knapsack problems, Engineering Branch-and-Cut Algorithms for the Equicut Problem, Performance analysis and optimization of web proxy servers and mirror sites, Political districting to minimize cut edges, Solving the 0-1 quadratic knapsack problem with a competitive quantum inspired evolutionary algorithm, The quadratic 0-1 knapsack problem with series-parallel support

Cites Work