Cut-and-solve: An iterative search strategy for combinatorial optimization problems

DOI10.1016/j.artint.2006.02.005zbMath1131.90050OpenAlexW2103698736MaRDI QIDQ2457618

Sharlee Climer, Weixiong Zhang

Publication date: 23 October 2007

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2006.02.005

zbMATH Keywords

linear programmingbranch-and-boundbranch-and-cutanytime algorithmssearch strategiestraveling Salesman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

A heuristic for BILP problems: the single source capacitated facility location problem ⋮ A symmetry-free polynomial formulation of the capacitated vehicle routing problem ⋮ Discrete heat transfer search for solving travelling salesman problem ⋮ A cut-and-solve based algorithm for the single-source capacitated facility location problem ⋮ An integrated approach for a new flexible multi-product disassembly line balancing problem ⋮ An effective hybrid approach to the two-stage capacitated facility location problem ⋮ An improved cut-and-solve algorithm for the single-source capacitated facility location problem ⋮ A dual RAMP algorithm for single source capacitated facility location problems ⋮ Lower tolerance-based branch and bound algorithms for the ATSP ⋮ Exact algorithms based on Benders decomposition for multicommodity uncapacitated fixed-charge network design ⋮ Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order

Uses Software

• Concorde

Cites Work

• Transforming asymmetric into symmetric traveling salesman problems
• Depth-first iterative-deepening: An optimal admissible tree search
• On the solution of traveling salesman problems
• A complete anytime algorithm for number partitioning
• The traveling salesman problem and its variations
• Outline of an algorithm for integer solutions to linear programs
• Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut
• Exact solution of large-scale, asymmetric traveling salesman problems
• Sensitivity Analysis in Practice
• Determining computational complexity from characteristic ‘phase transitions’
• Solution of a Large-Scale Traveling-Salesman Problem
• A Method for Solving Traveling-Salesman Problems
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• Performance of linear-space search algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item