Poset.dimension

[nathanncohen]

With this code, Sage at last can compute the dimension of a Poset.

http://en.wikipedia.org/wiki/Order_dimension

Nathann

See https://groups.google.com/d/topic/sage-devel/qEE9YUAPA4g/discussion

CC: @miguelmarco @dimpase @videlec @sagetrac-tmonteil @jm58660

Component: combinatorics

Author: Nathann Cohen

Branch/Commit: ffe181b

Reviewer: Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/17540

[nathanncohen]

Branch: u/ncohen/17540

[sagetrac-git]

Commit: 216d59e

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

216d59e

trac #17540: Poset.dimension()

[dimpase]

comment:4

Is the ticket description wrong? I can't review code that is not supposed to work :-)

[nathanncohen]

comment:5

Is the ticket description wrong? I can't review code that is not supposed to work :-)

Don't get it. You talk about the missing () to dimension ?

[dimpase]

comment:6

Replying to @nathanncohen:

Is the ticket description wrong? I can't review code that is not supposed to work :-)

Don't get it. You talk about the missing () to dimension ?

With this code, Sage can compute the dimension of a Poset.
​http://en.wikipedia.org/wiki/Order_dimension
Turns out that we were not able to.

we are not able to

[nathanncohen]

comment:7

I am glad to see this very confusing typo corrected. Thank you for bringing it to my attention.

[dimpase]

comment:8

IMHO there should be a separate function to compute the chromatic number of a hypergraph.

[nathanncohen]

comment:9

IMHO there should be a separate function to compute the chromatic number of a hypergraph.

It is true, but we could not call it from here. The reason why this code is so long is that we avoid building the LP from the start every time we need to add a constraint. It is only re-built when we notice that the new hypergraph is not k-colorable anymore.

Nathann

P.S. : Actually I will write a LP for that. I will surely need it some day.

[nathanncohen]

comment:10

P.S. : Actually I will write a LP for that. I will surely need it some day.

Done at #17542.

Nathann

[dimpase]

comment:11

Replying to @nathanncohen:

IMHO there should be a separate function to compute the chromatic number of a hypergraph.

It is true, but we could not call it from here. The reason why this code is so long is that we avoid building the LP from the start every time we need to add a constraint. It is only re-built when we notice that the new hypergraph is not k-colorable anymore.

Hmm, why do you need to rebuild the hypergraph? The latter is fixed. What is not fixed is the number of colours you need, and you don't want to rebuild the ILP from scratch for this. Why is this poset-specific?

[nathanncohen]

comment:12

Hmm, why do you need to rebuild the hypergraph? The latter is fixed. What is not fixed is the number of colours you need, and you don't want to rebuild the ILP from scratch for this. Why is this poset-specific?

On the paper, the hypergraph is very well defined and you have to compute its chromatic number. In practice, you cannot build the hypergraph because the list of its edges is too huge (I would not know how to do that anyway). So what we do is start with some of the edges in the hypergraph, and find a coloring.

When we have a coloring, we can check that it is valid by building the corresponding graphs --> if all are acyclic that's fine and we are done.

If one is not acyclic, however, we have found a cycle --> a new set to add to our hypergraph. And so we re-color this thing again.

This being said, when you find a new set in your hypergraph, you only have to add one constraint and then you can call .solve again. If we called .coloring() each time, we would in fact be building a new LP and solve it from scratch every time we add a constraint, and that's a waste of computations that this branch avoids.

Nathann

[dimpase]

comment:13

according to [FT00], instead of the hypergraph on inc(P), it suffices to restrict to the induced subhypergraph of the critical incomparable pairs (see Lemma 3.3 in [loc.cit.]), and then do the same chromatic number computation.

[sagetrac-tmonteil]

comment:14

Concerning the certificate, it looks like a half-certificate ; is the algorithm able to provide an evidence that no smaller set of linear ordering can generate the poset by intersection ?

Also, the "just to be sure" section at the end of the code should be run only if some check option is set to True since the algorithm is supposed to work without this ?

By the way, in the INPUT section, it seems more common to write ``certificate`` - boolean (default: ``False``) than to write the default at the end of the description (i first thought the information was missing).

[nathanncohen]

comment:15

according to [FT00], instead of the hypergraph on inc(P), it suffices to restrict to the induced subhypergraph of the critical incomparable pairs (see Lemma 3.3 in [loc.cit.]), and then do the same chromatic number computation.

I do not see how that would change anything. You are just telling me that only a subset of points of the hypergraph matters, but that does not give me the set of edges that only involve critical pairs.

Nathann

[nathanncohen]

comment:16

Concerning the certificate, it looks like a half-certificate ; is the algorithm able to provide an evidence that no smaller set of linear ordering can generate the poset by intersection ?

No it cannot. The problem is NP, so there is a certificate for a 'yes' answer, but it is not co-NP so there is no certificate for the other side. (Insert 'polynomial' wherever it fits in the sentence, and assume P!=NP)

Also, the "just to be sure" section at the end of the code should be run only if some check option is set to True since the algorithm is supposed to work without this ?

I do not think that it should, considering the running time of the algorithm. That's almost for free comparatively, so I don't see the need to make it optional.

By the way, in the INPUT section, it seems more common to write ``certificate`` - boolean (default: ``False``) than to write the default at the end of the description (i first thought the information was missing).

Well I usually write it the way it is written. If you want to change it you are welcome to add a commit, but if it is just about enforcing the coding style you like I will not code it for you :-P

Nathann

[sagetrac-tmonteil]

comment:17

Replying to @nathanncohen:

By the way, in the INPUT section, it seems more common to write ``certificate`` - boolean (default: ``False``) than to write the default at the end of the description (i first thought the information was missing).

Well I usually write it the way it is written. If you want to change it you are welcome to add a commit, but if it is just about enforcing the coding style you like I will not code it for you :-P

This is not the coding style i like, it is about coding conventions, a feature that allow various people to collectively work on some source code, see http://sagemath.org/doc/developer/coding_basics.html#documentation-strings

[jm58660]

comment:18

There seems to be no check for argument, i.e. certificate='cat-says-meow' does not raise an error. Should it?

One-line explanation on TOC should end with dot.

Does this work with empty poset? Checking just now, but compiling is slooow with this machine.

[dimpase]

comment:19

Replying to @nathanncohen:

according to [FT00], instead of the hypergraph on inc(P), it suffices to restrict to the induced subhypergraph of the critical incomparable pairs (see Lemma 3.3 in [loc.cit.]), and then do the same chromatic number computation.

I do not see how that would change anything. You are just telling me that only a subset of points of the hypergraph matters, but that does not give me the set of edges that only involve critical pairs.

It seems that you get a smaller ILP; you run your acyclicity test and compute cycles just as you do, but only leave critical pairs there (i.e. you take the subhypergraph induced on the critical pairs --- the edges get intersected with the subset of critical pairs).

[nathanncohen]

comment:20

This is not the coding style i like, it is about coding conventions, a feature that allow various people to collectively work on some source code, see http://sagemath.org/doc/developer/coding_basics.html#documentation-strings

If the fact that I wrote the defaut value at the end of the sentence instead of the beginning is a problem for you, add a commit. You will find many other such instances in the same document.

Nathann

[nathanncohen]

comment:21

There seems to be no check for argument, i.e. certificate='cat-says-meow' does not raise an error. Should it?

I do not think that there should, especially when the argument is boolean (not even a string) and when it does not produce any bug whatever happens. Chekking this kind of stuff is useful when a string is expected, but really if we begin to check every single arguments of every function like that, then half of the python code we have in Sage will be checking the type of input because Python does not do it instead.

One-line explanation on TOC should end with dot.

Done

Does this work with empty poset? Checking just now, but compiling is slooow with this machine.

Done (Jori: we have a 4h30 difference in our timezones)

Nathann

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ced5aff	trac #17540: Empty poset
d5dd205	trac #17540: final dot
59f0435	trac #17540: write the default value at the beginning

[sagetrac-git]

Changed commit from 216d59e to 59f0435

[nathanncohen]

comment:23

It seems that you get a smaller ILP; you run your acyclicity test and compute cycles just as you do, but only leave critical pairs there (i.e. you take the subhypergraph induced on the critical pairs --- the edges get intersected with the subset of critical pairs).

I see. Well, I am not very eager to dig into that in order to see how I could list all those critical pairs, then add this to this already non-trivial code, given that I am not very convinced that it will make any difference in the runtimes :-P

Nathann

[nathanncohen]

comment:24

Ping ?...

[nathanncohen]

comment:25

Piiiiing ?...

[nathanncohen]

comment:26

Piiiiiiiiiiiiiiiiiing ?...

[dimpase]

comment:27

OK, OK, just a bit of patience...

[dimpase]

comment:28

what is your default LP solver (on which that was tested)?
For me

sage: G = graphs.CompleteBipartiteGraph(3,3)
sage: P = Poset(DiGraph({(u,v):[u,v] for u,v,_ in G.edges()}))
sage: P.dimension()

runs, and runs, and runs (that's with GLPK).

[nathanncohen]

comment:29

sigh... That's CPLEX :-/

[nathanncohen]

comment:30

With GLPK for G=K_{2,3} it returns 3 in 2.5s

sage: %time P.dimension()
CPU times: user 2.58 s, sys: 4 ms, total: 2.59 s
Wall time: 2.58 s
3

With CPLEX it takes 252ms. And for G=K_{3,3} it returns 4 in 6s.

Nathann

[dimpase]

comment:31

for G=K33 and with GLPK your code seems to be looping forever. In the code you call init_LP in the loop, rather than doing a warm restart. This seems to defeat the purpose of constraint generation.

PS. OK, I see, you increase k every time it goes up. Anyhow, one gets stuck on some LP at k=3 here...

[nathanncohen]

comment:32

PS. OK, I see, you increase k every time it goes up.

Indeed.

Anyhow, one gets stuck on some LP at k=3 here...

Well, it depends on the graph. And of course it depends on the solver :-P

[dimpase]

comment:33

OK, tried this with GUROBI, it did work for K33. Trying for Petersen graph now :-)

typo:

+            # We check that all color class induce an acyclic graph, and add a
+            # constraint otherwise.

do you mean classes ?

[nathanncohen]

comment:34

Yes. Tell me when you are done with the review and I will fix everything at once.

[dimpase]

comment:35

I also notice that there is no objective function in LP. Sometimes specifying some more or less random non-symmetric function helps to speed things up.

[dimpase]

comment:36

OK, fix that typo, and I'll set it to positive review, even though the code is very slow...

[jm58660]

comment:37

The Wikipedia article you refer says that this is sometimes also called "Dushnik–Miller dimension". Is this common name for dimension? If so, it should be mentioned somewhere, so that user googling "Dushnik–Miller sagemath" will found this.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

a6d229d	trac #17540: Merged with beta0
ffe181b	trac #17540: Reviewers' comments

[sagetrac-git]

Changed commit from 59f0435 to ffe181b

[nathanncohen]

comment:39

Here it is!

Nathann

[dimpase]

Reviewer: Dima Pasechnik

[nathanncohen]

comment:41

Thaaaaaaaaaaaaaanks ! ;-)

Nathann

[vbraun]

Changed branch from u/ncohen/17540 to ffe181b