Opened 4 years ago

Closed 4 years ago

#17540 closed enhancement (fixed)

Poset.dimension

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.7
Component: combinatorics Keywords:
Cc: mmarco, dimpase, vdelecroix, tmonteil, jmantysalo Merged in:
Authors: Nathann Cohen Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: ffe181b (Commits) Commit: ffe181b536ce832a68620f1c7063807315d370a6
Dependencies: Stopgaps:

Change History (42)

comment:1 Changed 4 years ago by ncohen

  • Branch set to u/ncohen/17540
  • Status changed from new to needs_review

comment:2 Changed 4 years ago by git

  • Commit set to 216d59efca2e03ebce6e9fd76f150abb32e369d5

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

216d59etrac #17540: Poset.dimension()

comment:3 Changed 4 years ago by ncohen

  • Description modified (diff)

comment:4 follow-up: Changed 4 years ago by dimpase

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

comment:5 in reply to: ↑ 4 ; follow-up: Changed 4 years ago by ncohen

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 ?

comment:6 in reply to: ↑ 5 Changed 4 years ago by dimpase

Replying to ncohen:

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

comment:7 Changed 4 years ago by ncohen

  • Description modified (diff)

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

comment:8 follow-up: Changed 4 years ago by dimpase

  • Description modified (diff)

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

comment:9 in reply to: ↑ 8 ; follow-ups: Changed 4 years ago by ncohen

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.

comment:10 in reply to: ↑ 9 Changed 4 years ago by ncohen

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

Done at #17542.

Nathann

comment:11 in reply to: ↑ 9 ; follow-up: Changed 4 years ago by dimpase

Replying to ncohen:

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?

comment:12 in reply to: ↑ 11 Changed 4 years ago by ncohen

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

comment:13 follow-up: Changed 4 years ago by dimpase

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.

comment:14 follow-up: Changed 4 years ago by tmonteil

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).

comment:15 in reply to: ↑ 13 ; follow-up: Changed 4 years ago by ncohen

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

comment:16 in reply to: ↑ 14 ; follow-up: Changed 4 years ago by ncohen

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

comment:17 in reply to: ↑ 16 ; follow-up: Changed 4 years ago by tmonteil

Replying to ncohen:

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

comment:18 follow-up: Changed 4 years ago by jmantysalo

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.

comment:19 in reply to: ↑ 15 ; follow-up: Changed 4 years ago by dimpase

Replying to ncohen:

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).

comment:20 in reply to: ↑ 17 Changed 4 years ago by ncohen

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

comment:21 in reply to: ↑ 18 Changed 4 years ago by ncohen

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

comment:22 Changed 4 years ago by git

  • Commit changed from 216d59efca2e03ebce6e9fd76f150abb32e369d5 to 59f0435008dccc2f06d46c2b1293258c694487fa

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

ced5afftrac #17540: Empty poset
d5dd205trac #17540: final dot
59f0435trac #17540: write the default value at the beginning

comment:23 in reply to: ↑ 19 Changed 4 years ago by ncohen

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

comment:24 Changed 4 years ago by ncohen

Ping ?...

comment:25 Changed 4 years ago by ncohen

Piiiiing ?...

comment:26 Changed 4 years ago by ncohen

Piiiiiiiiiiiiiiiiiing ?...

comment:27 Changed 4 years ago by dimpase

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

comment:28 Changed 4 years ago by dimpase

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).

comment:29 Changed 4 years ago by ncohen

sigh... That's CPLEX :-/

comment:30 Changed 4 years ago by ncohen

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

comment:31 follow-up: Changed 4 years ago by dimpase

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...

Last edited 4 years ago by dimpase (previous) (diff)

comment:32 in reply to: ↑ 31 Changed 4 years ago by ncohen

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

comment:33 Changed 4 years ago by dimpase

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 ?

comment:34 Changed 4 years ago by ncohen

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

comment:35 Changed 4 years ago by dimpase

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.

comment:36 Changed 4 years ago by dimpase

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

comment:37 Changed 4 years ago by jmantysalo

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.

comment:38 Changed 4 years ago by git

  • Commit changed from 59f0435008dccc2f06d46c2b1293258c694487fa to ffe181b536ce832a68620f1c7063807315d370a6

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

a6d229dtrac #17540: Merged with beta0
ffe181btrac #17540: Reviewers' comments

comment:39 Changed 4 years ago by ncohen

Here it is!

Nathann

comment:40 Changed 4 years ago by dimpase

  • Milestone changed from sage-6.5 to sage-6.7
  • Reviewers set to Dima Pasechnik
  • Status changed from needs_review to positive_review

comment:41 Changed 4 years ago by ncohen

Thaaaaaaaaaaaaaanks ! ;-)

Nathann

comment:42 Changed 4 years ago by vbraun

  • Branch changed from u/ncohen/17540 to ffe181b536ce832a68620f1c7063807315d370a6
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.