Domino Parity Separator Home Page
051020
This is a joint project of William Cook, Daniel Espinoza and Marcos Goycoolea that started in 2003. The idea was to implement Adam Letchford's separation algorithm for Domino Parity Inequalities for the TSP, as described in "Separating a superclass of comb inequalities in planar graphs", Math. Oper. Res., 25(3), 443-454.
This implementation deals with the problem of separating such inequalities even in the case when the support graph is non-planar (in wich case the separation algorithm is heuristic), parallelization of the main domino-building step, and also heuristics to find more than one violated inequality.
As part of our research we also introduced the so-called K-Parity constraints, and this code provide an heuristic to separate 2-Parity constraints.
For more details see the paper "Computing with Domino-Parity Inequalities for the TSP". For those intersted in the source code, you can get it here.
Special thanks to John Boyer for allowing us to use his excelent implementation of the Boyer-Myrvold planarity testing algorithm. And to Sanjeeb Dash for allowing us to use his implementation of David Karger's algorithm to find minimum cuts.
Generated on Thu Oct 20 14:58:39 2005 for DominoParitySeparator by
1.4.5