A branch-and-cut algorithm for the equicut problem

DOI10.1007/BF02614373zbMath0889.90142WikidataQ58002925 ScholiaQ58002925MaRDI QIDQ1373750

Michele Conforti, Giovanni Rinaldi, Lorenzo Brunetta

Publication date: 1997

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

zbMATH Keywords

complete graphsheuristic algorithmbranch-and-cutcutting-plane procedureequicut problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

An overview of graph covering and partitioning, An effective iterated tabu search for the maximum bisection problem, An exact algorithm for min-max hyperstructure equipartition with a connected constraint, Performance of a genetic algorithm for the graph partitioning problem, A branch-and-bound algorithm for the minimum cut linear arrangement problem, Partitioning through projections: strong SDP bounds for large graph partition problems, An exact algorithm for graph partitioning, Models and methods for solving the problem of network vulnerability, Facet-defining inequalities for the simple graph partitioning polytope, From equipartition to uniform cut polytopes: extended polyhedral results, Finding optimal solutions to the graph partitioning problem with heuristic search, Knapsack constraint reformulation: A new approach that significantly reduces the number of sub-problems in the branch and bound algorithm, An exact combinatorial algorithm for minimum graph bisection, Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method, The node capacitated graph partitioning problem: A computational study, Engineering Branch-and-Cut Algorithms for the Equicut Problem, Speeding up a memetic algorithm for the max-bisection problem, Solution of large weighted equicut problems

Uses Software

• CPLEX

Cites Work

• Unnamed Item
• Facet identification for the symmetric traveling salesman polytope
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• Some new classes of facets for the equicut polytope
• The equipartition polytope. I: Formulations, dimension and basic facets
• The equipartition polytope. II: Valid inequalities and facets
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• A new approach to the maximum-flow problem
• Odd Minimum Cut-Sets and b-Matchings
• An Efficient Heuristic Procedure for Partitioning Graphs
• On the cut polytope