Ruprecht-Karls-Universität Heidelberg




The TSPSIR project

Background

  • idea: use known polytopes associated with small combinatorial optimization problems for cutting plane separation procedures
  • SIR is an approach to tighten LP relaxations in branch-and-cut exploiting known outer descriptions of small polytopes
  • SIR stands for Small Instance Relaxation

Motivation

  • finding facet defining cutting planes is crucial in the successful optimal solution of TSP instances via branch-and-cut
  • the SIR approach works for the TSP
  • outer desciptions of low-dimensional symmetric TSP polytopes known (computable by PORTA, facet database here)
  • possible to find facet defining cutting planes when other procedures (comb, clique-tree, ...) fail

Steps

  • shrink several pairwise disjoint minimum cuts of a TSP support graph to get a small TSP support graph
  • use known outer descriptions of small TSP polytopes associated with small problems for separation with small support graph
  • lift found small facets of outer descriptions of small polytopes to get cutting planes for original problem

Problems

  • compute and choose sets of minimum cuts of TSP support graph so that shrunken graphs have a predefined order
  • often there is a vast amount of shrinking possibilities; choose most promising shrunken graphs for time-consuming separation
  • separation for small graphs is done via an NP-hard Quadratic Assignment Problem and solved heuristically
  • number of facets is too large even for small polytopes to check them all in a brute-force manner

Contribution

  • we succeeded in generating all promising shrinking possibilities by representing all minimum cuts via a cactus
  • a sophisticated use of the cactus allows to complete this generation within seconds; a former more naive attempt took hours
  • for many TSP support graphs we can compute many facet defining cuts after other separation procedures failed
  • research and experiments are ongoing; emphasis is on picking most promising shrunken graphs and parts of the vast facet pool

Details

 

Research Group Discrete Optimization

optWay
Links