#18871: MILP formulation for cutwidth
-------------------------------------------------+-------------------------
Reporter: dcoudert | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.8
Component: graph theory | Resolution:
Keywords: cutwidth, MILP | Merged in:
Authors: David Coudert | Reviewers: Nathann
Report Upstream: N/A | Cohen
Branch: | Work issues:
9ccfe02e0fa0f866c83b1db484dcb15a8786a512 | Commit:
Dependencies: | Stopgaps:
-------------------------------------------------+-------------------------
Changes (by vbraun):
* status: closed => new
* commit: 9ccfe02e0fa0f866c83b1db484dcb15a8786a512 =>
* resolution: fixed =>
Comment:
This tests insanely slow, to the point of making tests time out (possibly
randomly):
{{{
sage -t --warn-long 27.3 src/sage/graphs/graph_decompositions/cutwidth.pyx
Timed out
**********************************************************************
Tests run before process (pid=23887) timed out:
sage: from sage.graphs.graph_decompositions import cutwidth ## line 206 ##
sage: G = graphs.CycleGraph(6) ## line 207 ##
sage: L = G.vertices() ## line 208 ##
sage: cutwidth.width_of_cut_decomposition(G, L) ## line 209 ##
2
sage: from sage.graphs.graph_decompositions import cutwidth ## line 214 ##
sage: P = graphs.PathGraph(6) ## line 215 ##
sage: cutwidth.width_of_cut_decomposition(P, [0, 1, 2, 3, 4, 5]) ## line
216 ##
1
sage: cutwidth.width_of_cut_decomposition(P, [5, 0, 1, 2, 3, 4]) ## line
218 ##
2
sage: cutwidth.width_of_cut_decomposition(P, [0, 2, 4, 1, 3, 5]) ## line
220 ##
5
sage: from sage.graphs.graph_decompositions import cutwidth ## line 227 ##
sage: cutwidth.width_of_cut_decomposition(Graph(), ['a','b']) ## line 228
##
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line
232 ##
0
sage: from sage.graphs.graph_decompositions.cutwidth import cutwidth ##
line 294 ##
sage: G = graphs.CompleteGraph(5) ## line 295 ##
sage: cw,L = cutwidth(G, algorithm="exponential"); cw ## line 296 ##
6
sage: K = graphs.CompleteGraph(6) ## line 298 ##
sage: cw,L = cutwidth(K, algorithm="exponential"); cw ## line 299 ##
9
sage: cw,L = cutwidth(K+K, algorithm="exponential"); cw ## line 301 ##
9
sage: from sage.graphs.graph_decompositions.cutwidth import cutwidth ##
line 306 ##
sage: G = graphs.Grid2dGraph(3,3) ## line 307 ##
sage: cw,L = cutwidth(G, algorithm="exponential"); cw ## line 308 ##
4
sage: G = graphs.Grid2dGraph(3,5) ## line 310 ##
sage: cw,L = cutwidth(G, algorithm="exponential"); cw ## line 311 ##
4
sage: from sage.graphs.graph_decompositions import cutwidth ## line 318 ##
sage: for i in range(10): # long test
G = graphs.RandomGNP(10, 0.2)
ve, le = cutwidth.cutwidth_dyn(G)
vm, lm = cutwidth.cutwidth_MILP(G)
if ve != vm:
print "Something goes wrong!" ## line 319 ##
**********************************************************************
----------------------------------------------------------------------
sage -t --warn-long 27.3 src/sage/graphs/graph_decompositions/cutwidth.pyx
# Timed out
----------------------------------------------------------------------
Total time for all tests: 323.1 seconds
cpu time: 123.0 seconds
cumulative wall time: 231.2 seconds
}}}
This was on my state of the art Haswell-E desktop fyi
--
Ticket URL: <http://trac.sagemath.org/ticket/18871#comment:21>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
