While generating subtour elimination constraints for a traveling salesman problem, I bound a bug in the edge_cut method for undirected weighted graphs. Specifically, when using the Ford-Fulkerson method, the value of the minimum cut is correct, but sometimes the returned edge cut does not have that value. The LP method for edge_cut does seem to always return the correct answer.
Attached is a simplified graph demonstrating the problem; it occurs in Sage 4.8. I can also generate many more counterexamples from the TSP problem, but the graphs are quite large. Related trac tickets include 9852, 9350, and 7599, but those have all been resolved. Best wishes, Stephen -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
example_bad_edge_cut.sage
Description: application/kdeuser1
example_bad_edge_cut.output
Description: Binary data
